Weekly outline
-
-
(настоящия курс)
-
(предишен курс)
-
Потоци в графи
-
-
защо са важни обратните ребра
в алгоритъма на Форд—Фалкерсон -
за алгоритъма на Форд—Фалкерсон
(и за други алгоритми)
-
-
Съчетания в графи
-
(Jack Edmonds, 1965 г.)
Не е разказ за разходка сред природата,
а фундаментална статия, която:1) предлага полиномиален алгоритъм
за търсене на съчетание в граф;2) дефинира класа P и обсъжда
технологичната значимост
на полиномиалните алгоритми. -
(от Уикипедия)
-
-
Алгоритмична нерешимост
-
Компресиране на данни
-
Част от записките към курса
"Algorithms in the Real World",
Carnegie Mellon University
-
-
Рандомизирани алгоритми
-
(общи сведения)
-
-
Приложения на рандомизацията
-
-
използвана в алгоритмите
на Каргер и на Крускал -
програмирана от Андрей Дренски
на C++ 17 (с малки промени може
да се приспособи за C++ 11) -
за пресмятане на перманента
с помощта на детерминанта; — приложение: преброяване
на съвършените съчетания
в двуделен граф. -
При презареждане на страницата
се генерират нови точки.
Първичният код може да бъде разгледан
чрез съответната команда на браузъра.Автор на описанието на алгоритъма
и на програмата: Стефан Фотев.
-
-
————————————————
-
с времева сложност Θ(n3)
(автор: Владислав Харалампиев).
-
-
Приблизително търсене в текст
-
(презентацията от лекцията)
-
Първата статия, в която се разглежда
задачата за приблизително търсене в текст
чрез идеята за еволюционно разстояние.
Труден материал; само за по-любознателните. -
Една от първите статии, предлагащи начин
за съкратено генериране на таблицата
по метода на диагоналните преходи —
запазване само на промените по диагонала
вместо на всички негови елементи. -
Един от алгоритмите
за паралелно изчисляване
на пълната таблица.
Цитиран като [BPM]
във файла "A Guided Tour..." по-долу. -
Широк поглед към проблема
от теоретична и практическа гледна точка.
Множество алгоритмични схеми и алгоритми;
модификации, коментари и забележки.
Всичко е представено по разбираем начин.
Този учебен материал е достатъчен
за цялостна подготовка по темата.
Може да бъде използван като източник
на идеи за курсови проекти. -
— разстояние на Левенщейн
и Optimal String Alignment
с възстановяване на пътя;
— класическият алгоритъм
с динамично програмиране;
— Ukkonen's cut-off heuristic;
— diagonal transitions;
— bit-parallelized matrix.
-
-
Алгоритми за разпознаване
на прости числа -
Алгоритми за класиранеЗадачи:
— класиране на кандидат-студенти;
— устойчиви бракове;
— райони на болници;
и др.
За двете статии по-долу
и други работи по темата
авторите получават
Нобеловата награда
за икономика през 2012 г. -
-
-
Алгоритми за консенсус
Репликация в модела "Fail-Stop"
(primary-backup, chain replication).
Репликация в модела "Crash Failure"
(кворуми, paxos).-
(от A. D. Fekete, K. Ramamritham,
B. Charron-Bost, F. Pedone, A. Schiper).За курса ДАА 2 е важна глава 2:
Replication Techniques for Availability.
-
-
Подготовка за изпит