Курс: Дизайн и анализ на алгоритми, КН1, летен семестър 2018/2019

Схема на раздела

Изберете раздел Главна

Разгъване Разширяване
Главна

Сгъване на всички Разгъване на всички
- Изберете дейност Конспект
  
  Конспект Файл
- Изберете дейност Схема за оценяване
  
  Схема за оценяване Файл
- Изберете дейност   Учебни материали:
  
  Учебни материали:
- Изберете дейност Записки за алгоритмите
  
  Записки за алгоритмите Файл
  
  (автор: гл. ас. Г. Георгиев — Скелета)
- Изберете дейност Изследване на алгоритми
  
  Изследване на алгоритми Файл
  
  (автор на файла: Стефан Фотев)
- Изберете дейност Примерни контролни и домашни
  
  Примерни контролни и домашни Файл
  
  (автор: гл. ас. Добромир Кралчев)
- Изберете дейност Комплекти задания за самоподготовка
  
  Комплекти задания за самоподготовка URL
  
  по различни учебни дисциплини
- Изберете дейност Нестандартни задачи
  
  Нестандартни задачи Файл
  
  Сборник с интересни
  и не много известни задачи.
  Състои се от четири глави:
  
  1) Логически и математически задачи.
  2) Алгоритмични задачи.
  3) Програмистки трикове.
  4) Неопределени задачи.
  
  За курса по ДАА е важна глава 2.
Изберете раздел 18 февруари — 24 февруари

Разгъване Разширяване
18 февруари — 24 февруари
- Изберете дейност   Изследване на алгоритми. &n...
  
  Изследване на алгоритми.
  Сложност на алгоритъм
- Изберете дейност Асимптотични сравнения
  
  Асимптотични сравнения URL
- Изберете дейност Анализ на времевата сложност
  
  Анализ на времевата сложност URL
  
  чрез сумиране
- Изберете дейност Сумиране чрез интегриране
  
  Сумиране чрез интегриране Файл
  
  (автор на файла: Стефан Фотев)
- Изберете дейност Амортизирана сложност
  
  Амортизирана сложност URL
Изберете раздел 25 февруари — 3 март

Разгъване Разширяване
25 февруари — 3 март
- Изберете дейност Рекурентни уравнения:
  
  Рекурентни уравнения: URL
  
  — линейно-рекурентни уравнения
  (метод на характеристичните уравнения);
  — развиване на рекурентно уравнение;
  — дърво на рекурсията.
- Изберете дейност Алгоритмична схема
  
  Алгоритмична схема URL
  
  "разделяй и владей"
- Изберете дейност Приложения на мастър-теоремата
  
  Приложения на мастър-теоремата URL
  
  за анализ на алгоритми
  от тип "разделяй и владей"
- Изберете дейност   Бързо умножение:   —&n...
  
    Бързо умножение:
    — на числа;
    — на матрици.
Изберете раздел 4 март — 10 март

Разгъване Разширяване
4 март — 10 март
- Изберете дейност Коректност на алгоритми
  
  Коректност на алгоритми URL
Изберете раздел 11 март — 17 март

Разгъване Разширяване
11 март — 17 март
- Изберете дейност   Сортиране чрез сравнения
  
  Сортиране чрез сравнения
- Изберете дейност   Елементарни сортировки:  &n...
  
    Елементарни сортировки:
    — метод на мехурчето;
    — сортиране чрез вмъкване;
    — сортиране чрез пряк избор.
- Изберете дейност Ефективни сортировки:
  
  Ефективни сортировки: Файл
  
  — сортиране чрез сливане;
  — пирамидално сортиране;
  — бързо сортиране.
- Изберете дейност     Приоритетна опашка. &nbs...
  
  Приоритетна опашка.
  Двоична пирамида
Изберете раздел 18 март — 24 март

Разгъване Разширяване
18 март — 24 март
- Изберете дейност   Сортиране чрез трансформация...
  
    Сортиране чрез трансформация:
    — сортиране чрез броене;
    — метод на бройните системи.
    Сортиране в линейно време
  
    Съпоставяне на различните сортировки
  
    Приложения на сортирането
- Изберете дейност Сортиране чрез пасианс
  
  Сортиране чрез пасианс Файл
  
  Решава едновременно две задачи:
  — сортира масив;
  — търси най-дълга растяща подредица.
Изберете раздел 25 март — 31 март

Разгъване Разширяване
25 март — 31 март
- Изберете дейност   Търсене:   — на с...
  
    Търсене:
    — на стойност (ключ):
         — последователно;
         — двоично;
    — на k-тия най-малък елемент
         (включително медианата):
         — бързо търсене;
         — алгоритъм PICK.
- Изберете дейност Алгоритъм PICK за търсене
  
  Алгоритъм PICK за търсене Файл
  
  на k-тия най-малък елемент,
  с линейна времева сложност
Изберете раздел 1 април — 7 април

Разгъване Разширяване
1 април — 7 април
- Изберете дейност Алгоритми върху графи
  
  Алгоритми върху графи URL
  
  (стр. 9–16 от записките)
- Изберете дейност  Обхождане в ширина,  обхож...
  
  Обхождане в ширина,
  обхождане в дълбочина
  и техните приложения
- Изберете дейност Структури от данни,
  
  Структури от данни, URL
  
  използвани при
  алгоритмите върху графи
  (стр. 7–8 от записките)
- Изберете дейност Структурата Union-Find,
  
  Структурата Union-Find, Файл
  
  използвана в алгоритъма на Крускал
- Изберете дейност Алгоритъм на Шмит
  
  Алгоритъм на Шмит Файл
  
  за търсене на мостове
  и срязващи върхове.
  На стр. 3 има псевдокод и пример.
  Лемите № 4 и № 5 от стр. 4
  служат за намиране на мостовете
  и срязващите върхове.
Изберете раздел 8 април — 14 април

Разгъване Разширяване
8 април — 14 април
- Изберете дейност Демонстрационни аплети
  
  Демонстрационни аплети URL
  
  за някои алгоритми върху графи
  (алгоритъма на Крускал,
  алгоритъма на Прим—Ярник,
  алгоритъма на Дейкстра
  и други алгоритми)
- Изберете дейност Псевдокод на алгоритмите
  
  Псевдокод на алгоритмите Файл
  
  на Прим—Ярник и на Дейкстра
- Изберете дейност Примери за алгоритмите
  
  Примери за алгоритмите Файл
  
  на Прим—Ярник и на Дейкстра
- Изберете дейност     Алгоритъм на Белман—...
  
  Алгоритъм на Белман—Форд
  
  Алгоритъм на Флойд—Уоршал
Изберете раздел 15 април — 21 април

Разгъване Разширяване
15 април — 21 април
- Изберете дейност Динамично програмиране
  
  Динамично програмиране Файл
  
  (основни задачи)
- Изберете дейност Алгоритъм CYK
  
  Алгоритъм CYK Файл
  
  за синтактичен анализ
  на безконтекстни граматики
  в нормална форма на Чомски
- Изберете дейност Най-дълга обща подредица
  
  Най-дълга обща подредица URL
Изберете раздел 22 април — 28 април

Разгъване Разширяване
22 април — 28 април
- Изберете дейност Динамично програмиране
  
  Динамично програмиране Файл
  
  (задачи от минали контролни)
- Изберете дейност Динамично програмиране
  
  Динамично програмиране Файл
  
  (задачи от минали изпити)
Изберете раздел 29 април — 5 май

Разгъване Разширяване
29 април — 5 май
- Изберете дейност Алчни алгоритми
  
  Алчни алгоритми Файл
Изберете раздел 6 май — 12 май

Разгъване Разширяване
6 май — 12 май
- Изберете дейност  Класове на алгоритмична сложн...
  
  Класове на алгоритмична сложност
- Изберете дейност NP-пълнота
  
  NP-пълнота URL
- Изберете дейност Проблемът "P срещу NP"
  
  Проблемът "P срещу NP" URL
- Изберете дейност Теорема на Кук—Левин
  
  Теорема на Кук—Левин Файл
  
  за NP-пълнотата на задачата SAT
  (с доказателство)
- Изберете дейност Някои NP-пълни задачи
  
  Някои NP-пълни задачи Файл
  
  (доказателства с помощта
  на полиномиална редукция)
- Изберете дейност Важни NP-пълни задачи: — SAT&n...
  
  Важни NP-пълни задачи:
  — SAT и 3-SAT;
  — SubsetSum;
  — задачата за раницата;
  — хамилтонов път / цикъл;
  — задачата за
  търговския пътник;
  — изоморфен подграф;
  — клика;
  — независимо множество
  (антиклика);
  — върхово покритие;
  — доминиращо множество;
  и др.
- Изберете дейност Важни задачи от клас P: —&n...
  
  Важни задачи от клас P:
  — 2-SAT;
  — максимално съчетание;
  — ойлеров път / цикъл;
  и др.
Изберете раздел 13 май — 19 май

Разгъване Разширяване
13 май — 19 май
- Изберете дейност  Долни граници  за времевата&...
  
  Долни граници
  за времевата сложност
  на алгоритмични задачи.
  
  Тривиални долни граници:
  — по размера на входа;
  — по размера на изхода.
  
  Методи за доказване
  на нетривиални долни граници:
  — редукция;
  — рекурентни неравенства;
  — игра срещу противник;
  — дърво за взимане на решения.
- Изберете дейност Алгебрични дървета
  
  Алгебрични дървета Файл
  
  за взимане на решения
Изберете раздел 20 май — 26 май

Разгъване Разширяване
20 май — 26 май
- Изберете дейност  Долна граница n log n &...
  
  Долна граница n log n
  за времевата сложност
  на алгоритмични задачи:
  — сортиране чрез сравняване;
  — неповтарящи се елементи;
  — най-малко разстояние;
  — мода;
  и др.
Изберете раздел 27 май — 2 юни

Разгъване Разширяване
27 май — 2 юни
- Изберете дейност   Апроксимиращи алгоритми:  &...
  
    Апроксимиращи алгоритми:
    — върхово покритие;
    — задача за търговския пътник.
  
    Паралелни алгоритми:
    — сортиране чрез сливане;
    — алгоритъм на Борувка.
- Изберете дейност Квантови компютри
  
  Квантови компютри Файл
- Изберете дейност Метод на четиримата руснаци
  
  Метод на четиримата руснаци URL
Изберете раздел 3 юни — 9 юни

Разгъване Разширяване
3 юни — 9 юни
Резултати от текущ контрол
- Изберете дейност Контролно № 1 —
  
  Контролно № 1 — Файл
  
  анализ на алгоритми
  (15 март 2019 г.)
- Изберете дейност Домашно № 1 —
  
  Домашно № 1 — Файл
  
  алгоритми върху масиви
  (27 март — 3 април 2019 г.)
- Изберете дейност Решения на задачите
  
  Решения на задачите Файл
  
  от домашно № 1
- Изберете дейност Контролно № 2 —
  
  Контролно № 2 — Файл
  
  сортиране и търсене
  (3 април 2019 г.)
- Изберете дейност Контролно № 3 —
  
  Контролно № 3 — Файл
  
  алгоритми върху графи
  (24 април 2019 г.)
- Изберете дейност Домашно № 2 —
  
  Домашно № 2 — Файл
  
  съставяне на алгоритми
  (25 април — 3 май 2019 г.)
- Изберете дейност Решения на задачите
  
  Решения на задачите Файл
  
  от домашно № 2
- Изберете дейност Контролно № 4 —
  
  Контролно № 4 — Файл
  
  динамично програмиране
  (15 май 2019 г.)
- Изберете дейност Домашно № 3 —
  
  Домашно № 3 — Файл
  
  класове на сложност P и NP
  (16–22 май 2019 г.)
- Изберете дейност Решения на задачите
  
  Решения на задачите Файл
  
  от домашно № 3
- Изберете дейност Резултати от текущия контрол
  
  Резултати от текущия контрол Файл
  
  към 9 юни 2019 г.
Изберете раздел Изпит (12–13 юни 2019 г.)

Разгъване Разширяване
Изпит (12–13 юни 2019 г.)
- Изберете дейност  Изпит:  писмен  &nbs...
  
  Изпит:   писмен     устен
  
  Дата:   12 юни   13 юни
  
  Начало:   13:00 ч.     9:00 ч.
  
  Място: ФХФ 210 ФМИ 503
- Изберете дейност Задачи от изпита по ДАА
  
  Задачи от изпита по ДАА Файл
  
  (12 юни 2019 г.)
- Изберете дейност Резултати от изпита
  
  Резултати от изпита Файл
  
  (13 юни 2019 г.)
Изберете раздел 5 септември 2019 г. (поправка)

Разгъване Разширяване
5 септември 2019 г. (поправка)
- Изберете дейност Задачи
  
  Задачи Файл
- Изберете дейност Точки и оценки
  
  Точки и оценки Файл

Изпит:	писмен	устен
Дата:	12 юни	13 юни
Начало:	13:00 ч.	9:00 ч.
Място:	ФХФ 210	ФМИ 503

Схема на раздела

Резултати от текущ контрол