Course: Дизайн и анализ на алгоритми (втора част), зимен семестър 2021/2022

Weekly outline

General

Collapse all Expand all
- Конспект File
- Виртуална класна стая URL
  
  за лекциите по ДАА 2
  в електронна среда
- Забранено е записването на лекциите,
  съхраняването и разпространяването
  на видеозаписи и/или аудиозаписи!
- Виртуална класна стая URL
  
  за упражненията по ДАА 2
  в електронна среда
- Транслатор за Си-плюс-плюс URL
  
  (транслаторът работи в Интернет
  без инсталиране на файлове
  на локалната машина)
- Учебни материали:
- Алгоритми и сложност File
  
  (автор: Хърбърт Уилф)
- Записки по алгоритми File
  
  (автор: Г. Георгиев — Скелета)
- Учебни материали от Д. Кралчев URL
  
  по различни предмети
27 септември — 3 октомври
Терминология
- Българска терминология в информатиката
4 октомври — 10 октомври
Рандомизирани алгоритми
- Рандомизирани алгоритми File
  
  (общи сведения)
11 октомври — 17 октомври
Приложения на рандомизацията
- Проверка на алгебрични тъждества File
  
  (автори: Michael Mitzenmacher, Eli Upfal)
- Алгоритъм на Каргер File
  
  за търсене на минимален разрез
- Структурата Union-Find, File
  
  използвана в алгоритмите
  на Каргер и на Крускал
- Пресмятане на перманента:
- — обзор на алгоритмите; URL
- — рандомизиран алгоритъм File
  
  за пресмятане на перманента
  с помощта на детерминанта;
  — приложение: преброяване
  на съвършените съчетания
  в двуделен граф.
- Най-малък покриващ кръг:
- — рандомизиран алгоритъм; File
- — демонстрационна програма. File
  
  При презареждане на страницата
  се генерират нови точки.
  Първичният код може да бъде разгледан
  чрез съответната команда на браузъра.
  Автор на описанието на алгоритъма
  и на програмата: Стефан Фотев.
18 октомври — 24 октомври
Анализ на амортизираната сложност
- Амортизирана сложност URL
-   Търсене в текст:
    наивен алгоритъм,
    търсене чрез краен автомат,
    алгоритми на Рабин—Карп
    и на Кнут—Морис—Прат
- Пирамида на Фибоначи File
25 октомври — 31 октомври
Потоци в графи
- Теорема за максималния поток
  и минималния разрез
- Алгоритъм на Форд—Фалкерсон URL
- Алгоритъм на Едмондс—Карп URL
- Алгоритъм на Диниц и алгоритъм MPM URL
  
  (Malhotra, Pramodh-Kumar, Maheshwari)
25 октомври — 31 октомври
Неинициализирана памет
- Работа с неинициализирана памет File
25 октомври — 31 октомври
Автоматично диференциране
-   Видове диференциране:
    — символно диференциране;
    — числено диференциране;
    — автоматично / алгоритмично диференциране.
- Автоматично / алгоритмично диференциране File
- Пример за програмен код, File
  
  използващ автоматично диференциране
- Дуални числа URL
1 ноември — 7 ноември
Квантови компютри
- Решаване на оптимизационни задачи File
  
  с помощта на квантови компютри
8 ноември — 14 ноември
Комбинаторно генериране
- Комбинаторно генериране File
15 ноември — 21 ноември
Съчетания в графи
-   Съчетания (сдвоявания)
  
    Максимални и съвършени съчетания.
    Алтерниращи и удължаващи пътища
- Алгоритъм на Едмондс File
- Алгоритъм на Хопкрофт—Карп File
- Задача за назначенията
  
  Унгарски алгоритъм:
- — описание и пример; File
- — програмна реализация File
  
  с времева сложност Θ(n³)
  (автор: Владислав Харалампиев).
- Задача за устойчивите бракове
- Алгоритъм на Гейл—Шепли File
22 ноември — 28 ноември
Търсене в текст
- Точно търсене
-   Алгоритми за точно търсене в текст
    има в раздела "18 октомври — 24 октомври".
  
    Приблизително търсене
- Разстояние на Левенщейн. URL
  
  Алгоритъм на Вагнер—Фишер.
  Отсичане по Уконен
- Други метрики URL
  
  за разстояние между низове.
  Алгоритми за приблизително
  търсене в текст
22 ноември — 28 ноември
Планарни графи
- Алгоритъм на Демукрон File
22 ноември — 28 ноември
Коректност на алгоритми
- Аксиоматика на Хоор URL
- Коректност на блоксхеми File
29 ноември — 5 декември
Числови алгоритми
-   Бързо преобразувание на Фурие
  
    Определение
  
    Свойства
  
    Алгоритъм
  
    Приложения
  
    Бързо умножение (на дълги цели числа):
    — алгоритъм на Карацуба;
    — алгоритъм на Шонхаге и Щрасен;
    — алгоритъм на Фюрер;
    — алгоритъм на Дейвид Харви
         и Йорис ван дер Хувен.
  
    —————————————————
  
    Прости и съставни числа
- Алгоритъм на Милер—Рабин File
- Алгоритъм на Полард File
  
  ( ρ-алгоритъм )
6 декември — 12 декември
Компресиране на данни
- Алгоритми за компресиране File
13 декември — 19 декември
Разпознаване на образи
- Разпознаване на образи
  с помощта на инварианти
- Проективна геометрия.
  Проективни инварианти
- Двойно отношение URL
- Проективни преобразувания URL
- Статистики за изображения
- Моменти на Хю URL
- Разпознаване на изображения
  чрез моменти на Хю:
- — описание на проекта; URL
- — програма; URL
- — примери. URL
  
  Автор на проекта:
  Цветомир Кайджиев.
13 декември — 19 декември
Долни граници
за времевата сложност
на алгоритмични задачи
- Алгебрични дървета URL
  
  за взимане на решения
20 декември — 26 декември
Студентски доклади
(малки проекти)
- Марио Марков, № 45602:
- Обучение на интелигентни агенти File
- с генетични алгоритми.
-   В приложената компютърна програма
    се използват невронни мрежи.
    ____________________________
- Станислава Тодорова, № 82011:
- Приложения на изпъкналата обвивка File
- и дървото на Ли Чао
- в динамичното оптимиране.
-   За намирането на изпъкнала обвивка
    съществуват множество алгоритми,
    например алгоритъмът на Греъм.
    ____________________________
- Траян Господинов, № 45506:
- Полиномиален алгоритъм, File
- основан на метода на резолюцията,
- за частен случай на задачата 3-SAT.
- ____________________________
- Ангел Димитров, № 45572:
- Списък с пропуски. URL
-   За тази и други структури от данни
    са налични програмни реализации.
    ____________________________
- Стела Маринова, № 81585:
- Търсене на най-малък елемент в подмасив File
- и на най-близък общ предшественик
- в кореново дърво.
- ____________________________
- Иво Илчев, № 45530:
- Симулирано закаляване. File
- ____________________________
- Йонко Йонков, № 45520:
- Минимален автомат на наставките. File
-   Описание на структурата от данни има:
    — в оригиналната публикация;
    — на сайта CP-Algorithms.
27 декември — 3 януари
Зимна ваканция
4 януари — 9 януари
Предварителна и паралелна
обработка на данни
- Сегментно дърво URL
- Многонишково програмиране URL
10 януари — 16 януари
Студентски доклади
(малки проекти)
- Кардам Гергов, № 45535:
- Алгоритъм на Метрополис—Хейстингс. File
-   Справочна информация:
    — описание на алгоритъма;
    — вериги на Марков.
- ____________________________
- Ивайло Панайотов, № 45539:
- Алгоритъм на Ахо—Корасик за търсене в текст. File
- ____________________________
- Кристиян Симов, № 45601:
- Случайни гори. URL
- ____________________________
- Мартин Карликов, № 45343:
- Експериментално изследване File
- на алгоритъма на Карацуба.
17 януари — 23 януари
Текущ контрол
- Първо контролно (теория) — 4. XI. 2021 г.
- Второ контролно (задачи) — 20. I. 2022 г. File
- Трето контролно (теория) — в края на семестъра.
24 януари — 5 февруари
Подготовка за изпит
- Студентите без представени в срок
  и одобрени малки проекти
  не се допускат до изпит!
- Изпитът по ДАА 2 ще се проведе
  на 6 февруари 2022 г., от 16:00 ч.,
  в зала 325 на ФМИ.
- Задължително е представянето
  на официален документ за самоличност —
  валидна лична карта, издадена от МВР.
- Задължителни са предпазните маски
  и сертификатът за COVID-19.
Изпити
6 февруари 2022 г.
9 юни 2022 г.
- Оценките са нанесени
  в изпитните протоколи.

Weekly outline

General