Дизайн и анализ на алгоритми

Здрасти.


Това е най-важният предмет във ФМИ.
Освен това е много труден предмет във ФМИ.

Познава се че е важен, защото в него има думата Алгоритми.
Познава се че е най-важен, защото единствено в него има думата Алгоритми.
Познава се че е много труден, защото в него има думата Анализ.

Тук ще се пишат програми, които другите не могат да пишат.
Ще се решават проблеми, които другите не могат да решават.
Тук програмирането престава да бъде препитание, занаят, изкуство и се превръща в магия.

Мацките си падат по магия.


Нещата по конспекта на Манев

  1. Алгоритми - същност и неформално определение. Общи изчислителни проблеми (масови задачи), примери. Големина на входа на алгоритми.
  2. Формални изчислителни модели - машина на Тюринг, машина с произволен достъп до паметта, език за програмиране. Сложност по време в най-лошия случай, средна и в най-добрия случай. Други аспекти на анализирането на алгоритмите - сложност по памет и коректност.
  3. Асимптотичен анализ на сложността - важност, предимства и недостатъци. Нотации, използвани при асимтотичния анализ. Свойства на нотациите.
  4. Рекурсивни алгоритми и рекурентни отношения. Методи за решаване на рекурентни отношения: развиване, дърво на рекурсията, индукция, Master Theorem, метотъд с характеристичното уравнение. Примери.
  5. Сортиране - приложения, важност, примери за използване на сортирането като първа фаза от решението на други проблеми. Стабилни и нестабилни сортиращи алгоритми. Важност на стабилността. Елементарни сортиращи алгоритми: Bubble Sort, Selection Sort и Insertion Sort. Анализ на сложността им по време. Анализ на стабилността им.
  6. Двоична пирамида. Брой на листата и брой на вътрешните върхове на пирамидата. Формули за индексите на родителя и на децата на даден връх, ако пирамидата е масив. Построяване на пирамида - анализ на сложността по време. Процедура Build Heap - наивна и бърза имплементация. Анализ на сложностите по време на двете имплементации. Пирамидална сортировка (Heapsort). Приоритетна опашка.
  7. Алгоритмична схема //Разделяй и Владей//: същност, приложение.
  8. Quicksort - основна идеа и имплементация. Анализ на сложност по време и на стабилността на Quicksort. Анализ на средната сложност по време на Quicksort.
  9. Долна граница върху асимптотична сложност по време на сортиращите алгоритми, базирани на директно сравнение.
  10. Сортиране, което не е базирано на директно сравнение. Сортиране в линейно време - Counting Sort. Анализ на коректността им и на сложността им по време.
  11. Ориентирани и неориентирани графи и мултиграфи. Представяния на графи. Предимства и недостатъци на различните представяния. Анализ по сложността по време на алгоритмите върху графи - въвеждане на асимптотични нотации на функции на две променливи. Линейна сложност по време при графи.
  12. Обхождане на графи. Обхождане в ширина (BFS). Дърво на обхождането в ширина. Видове ребра в обхождането в ширина. Обхождане в дълбочина (DFS) на графи. Дърво на обхождането в дълбочина. Видове ребра в обхождането в дълбочина при неориентираните и ориентираните графи. Топологическо сортиране.
  13. Силно свързани компоненти на ориентирани ациклични графи. Алгоритъм за намирането на силно свързаните компоненти в ориентиран граф. Срязващи гласове (cut vertices) и срязващи ребра (bridges) в неориентираните графи. Двусвързани компоненти в неориентирани графи. Алгоритми за намиране на срязващи върхове и срязващи ребра на граф.
  14. Минимални покриващи дървета (МПД) на неориентирани графи. Примери за приложения на МПД. Обща алгоритмична схема за построяване на МПД. Greedy стратегии. Алгоритъм на Прим - анализ на сложността по време. Алгоритъм на Крусал - сложност по време на наивната имплементация. Union-find операции върху разбиване на множество - имплементации. Евристика Union by rank и Path Compression. Анализ на сложността по време при използването на евристики.
  15. Най-къси пътища в графи. Примери за приложения. Потенциални трудности при наличието на отрицателни тегла. Анализ на задачата и сравнението и със задачата за най-дълъг път в граф. Алгоритъм на Дейкстра за намиране на най-късите пътища от даден връх до всички останали върхове. Анализ на корекността и сложността по време на този алгоритъм.
  16. Алгоритми за намиране на най-късите пътища между всички двойки върхове - алгоритъм, изполващ алгоритъма на Дейкстра, и алгоритъм, използващ идеята на динамичното програмиране (алгоритъм Floyd-Warshall). Анализ на сложността по време. Алгоритъм на Bellman-Ford за графи с отрицателни тегла на ребрата.
  17. Динамично програмиране - същност, предимства и приложения. Примери. Динамично програмиране в топологически сортиран ориентиран ацикличен граф. Анализ на сложността по време. Сравнение между динамичното програмиране и схемата "Разделяй и Владей".
  18. Сложност по време на масови задачи. Практически решими проблеми - клас на сложност P. Недетерминирани алгоритми. Клас на сложност NP. P = NP?
  19. Полиномиално свеждане между масови задачи. NP-пълнота. Масова задача Satisfiability. Доказване на NP-пълнота на Satisfiability - теорема на Кук.
  20. Масова задача. 3-Satisfiability. Доказване на NP-пълнота на 3-Satisfiability. Съпоставка на 3-Satisfiability с 2-Satisfiability. Доказване на NP-пълнота на Vertex Cover, Clique, Hamilton Cycle и Longest Path. Други NP-пълни масови задачи.
  21. Апроксимацията като средство за "справяне" с практическата нерешимост. Апроксимиращи алгоритми с точност до мултипликативна константа. Примери с Vertex Cover и задача за търговския пътник в "планарен вариант".

—-
В лекциите по ДАА се учат интересни теоретични резултати и алгоритми.
В упражненията по ДАА се решават задачи имащи за цел понятието "Времева сложност на алгоритъм" да стане напълно съвсем ама докрай ясно какво означава.
В практикума по ДАА се използват научените в лекции и упражнения неща, за да се пишат турбо яки програми.

Тези статии ще са основно посветени на практикума.

Духът на бъдещата Коледа или още "Какво ще правим в следващите часове"
Сортиране
Задача за пресмятане на сложност

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License