Седмичен изглед
-
-
Най-важни са страниците от главата
"Грешки и трудности при превод",
но и другите глави от справочника
съдържат полезни съвети.
-
30 септември — 6 октомври
Потоци в графи
-
(Хърбърт Уилф, 1994 г.)
Темата "Потоци в графи"
е изложена в глава 3
(общо 18 страници). -
защо са важни обратните ребра
в алгоритъма на Форд—Фалкерсон -
за алгоритъма на Форд—Фалкерсон
(и за други алгоритми) -
(автор: Георги Бърнев).
-
-
7 октомври — 13 октомври
Съчетания в графи
-
(Джак Едмондс, 1965 г.)
Не е разказ за разходка сред природата,
а фундаментална статия, която:1) предлага полиномиален алгоритъм
за търсене на съчетание в граф;2) дефинира класа P и обсъжда
технологичната значимост
на полиномиалните алгоритми. -
(от Уикипедия)
-
-
14 октомври — 20 октомври
Алгоритмична нерешимост
-
21 октомври — 27 октомври
Задача за назначенията
-
с времева сложност Θ(n 3)
(автор: Владислав Харалампиев).
-
21 октомври — 27 октомври
Търсене в текст
-
на алгоритъма на Кнут—Морис—Прат
(автор на проекта: Илиян Йорданов) -
(автор на проекта: Минчо Паскалев)
-
28 октомври — 3 ноември
Рандомизирани алгоритми
-
(общи сведения)
-
-
4 ноември — 10 ноември
Приложения на рандомизацията
-
-
използвана в алгоритмите
на Каргер и на Крускал -
за пресмятане на перманента
с помощта на детерминанта; — приложение: преброяване
на съвършените съчетания
в двуделен граф. -
При презареждане на страницата
се генерират нови точки.
Първичният код може да бъде разгледан
чрез съответната команда на браузъра.Автор на описанието на алгоритъма
и на програмата: Стефан Фотев.
-
11 ноември — 17 ноември
Пирамида на Фибоначи
-
18 ноември — 24 ноември
Алгоритми за класиране
Задачи:
— класиране на кандидат-студенти;
— устойчиви бракове;
— трансплантация на органи;
— оптимална тъканна съвместимост;
и други.
За работи по тази тема
през 2012 година е присъдена
Нобеловата награда за икономика.-
Кратко и ясно описание —
дефиниции, алгоритми
и тяхната коректност и сложност.
-
25 ноември — 1 декември
Компресиране на данни
-
Част от записките към курса
"Algorithms in the Real World",
Carnegie Mellon University -
(автор на проекта: Християна Панайотова)
-
-
2 декември — 8 декември
Алгоритми за консенсус
Репликация в модела "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.
-
-
9 декември — 15 декември
Приблизително търсене в текст
-
— разстояние на Левенщейн
и Optimal String Alignment
с възстановяване на пътя;
— класическият алгоритъм
с динамично програмиране;
— Ukkonen's cut-off heuristic;
— diagonal transitions;
— bit-parallelized matrix. -
Първата статия, в която се разглежда задачата за приблизително търсене в текст
чрез идеята за еволюционно разстояние. Труден материал; само за по-любознателните. -
Една от първите статии, предлагащи начин за съкратено генериране на таблицата
по метода на диагоналните преходи — запазване само на промените по диагонала
вместо на всички негови елементи. -
Един от алгоритмите за паралелно изчисляване на пълната таблица.
Цитиран като [BPM] във файла "A Guided Tour..." по-долу. -
Широк поглед към проблема от теоретична и практическа гледна точка.
Множество алгоритмични схеми и алгоритми; модификации, коментари и забележки.
Всичко е представено по разбираем начин.
Този учебен материал е достатъчен за цялостна подготовка по темата.
Може да бъде използван като източник на идеи за курсови проекти. -
(магистърска дипломна работа
на д-р Петър Митанкин) -
(презентацията от лекцията)
-
-
16 декември — 22 декември
Разпознаване на прости числа
-
на алгоритмите на Ферма и на Милер—Рабин
(автор на проекта: Георги Самарджиев) -
на алгоритъма на Милер—Рабин
(автор на проекта: Костадин Гаров)
-
23 декември — 5 януари
Зимна ваканция
-
6 януари — 12 януари
Бързо преобразувание на Фурие
-
13 януари — 19 януари
Подготовка за изпит
-
13 февруари 2020 г.
Изпит по ДАА 2
-
31 август 2020 г.
Изпит по ДАА 2