- Тема 1: Асимптотични нотации. Асимптотични сравнения на функции.
- Тема 2: Анализ на сложността на итеративни алгоритми. Задачи. Анализ на сложността на алгортими за търсене и алгоритми за сортиране (в най-лош случай и среден случай)
- Тема 3: Амортизиран анализ. Анализ на сложността на рекурсивни алгоритми. Задачи. Решаване на рекурентни уравнения по метода с характерситчното уравнение. Решаване на р.у. с други методи.
- Тема 4: Анализ на сложността на рекурсивни алгоритми - част 2. Алгоритми изградени по схемата Разделяй и владей. Сортиращи алгоритми (изградени по Р.В.). Мастър теоремата. Разширение на М.Т. и примерни задачи.
- Тема 5: Задачи за предговор. Асимптотични нотации, амортизиран анализ и анализ на рекурсивни алгоритми (пример с комбинаторно генериране). Коректност на итеративни алгоритми. Доказателство за коректност с инварианта на цикъла.
- Тема 6: Доказателство за терминация на итеративни алгоритми. Доказателство за коректност с инварианта на цикъла (част 2).
- Тема 7: Доказателство за коректност с инварианта на цикъла (част 3). Доказателство на линейно търсене и на сортиране по метода на мехучето.
- Тема 8: Доказателство за коректност на рекурсивни алгоритми. Доказателство с индукция, доказателство за финитност, сложност. Решаване на рекурентно уравнение с индукция.
- Тема 9: Долни граници. Доказателство за долна граница чрез дърво на вземане на решения и чрез "игра срещу противник".
- Тема 10: Долни граници (част 2). Доказателство за долна граница чрез редукция.
- Тема 11: Съставяне на алгоритми върху масиви. Модификации на изучавани алгоритми.
- Тема 12: Алгоритми върху графи (част 1). BFS, DFS(итеративна и рекурсвна имплементация). Приложения и алгоритми с BFS и DFS (търсене на цикъл, топологично сортиране и др.).
- Тема 13: Алгоритми върху графи (част 2). Алгоритми за най-къс път и минимално покриващо дърво.
- Тема 14: Динамично програмиране. Мемоизация.
- Тема 15: Задачи за предговор. Динамично програмиране. Долни граници. Алгоритми върху графи.
Angeld55/Algorithms_FMI
Repository with examples for the "Design and аnalysis of аlgorithms" course given by me @ Faculty of Mathematics and Informatics, Sofia University (2018 - present)
C++