Конструкција и анализа алгоритама 2 2022/23

Материјали за курс:

• Књига Алгоритми
• Скрипта са комплетним материјалом за курс пдф
• Књига Cormen, Leiserson, Rivest, Stein, Introduction to algorithms, 4. издање, 2022.

Предавања ће се од 1. новембра одржавати УТОРКОМ од 17 до 19 у учионици јаг1 (уместо четвртком од 18 до 20 у 830, како стоји у распореду часова).

Овогодишњи курс разликује се минимално од прошлогодишњег (замењен редослед: сортирање и пробабилистички алгоритми пре суфиксног низа и суфиксног стабла).

Испит се састоји од писменог (50 поена) и усменог дела (50 поена). Услов за излазак на усмени део испита је бар 20 поена на писменом делу испита.

Прошлогодишња испитна питања пдф.

Одржани часови:

• 1. 18. октобра: Сортирање, пробабилистички алгоритми пдф.
• 2. 26. октобра: Други пример пробабилистичког алгоритма. Суфиксни низ и суфиксно стабло. Алгоритам Каркаинена-Сандерса пдф
• 3. 1. новембра: Суфиксни низ, низ LCP, суфиксно стабло, формирање суфиксног стабла на основу суфиксног низа и низа lcp, примене. пдф
• 4. 8. новембра: Графови: упаривање, транспортне мреже. пдф.
• 5. 15. новембра: Хамилтонови циклуси у густом графу. Свођења (редукције): решавање проблема свођењем на други проблем, примери, свођење на линеарно програмирање. Свођење са циљем да се докаже доња граница сложености алгоритма.
• 6. 22. новембра: NP комплетни проблеми, Кукова теорема, докази NP комплетности (покривач грана, доминирајући скуп, клике, 3-SAT).
• 7. 29. новембра: Докази NP комплетности (3-обојивост, збир подскупа, покривање подскупова као специјални случај покривача грана). Приближни алгоритми са гаранцијом квалитета решења (доминирајући скуп, 1Д паковање).
• 8. 6. децембра: Приближни алгоритми: еуклидска варијанта проблема трговачког путника; неопостојање приближног алгоритма са фиксним фактором за општи проблем трговачког путника; најмања потфамилија фамилије подскупова која покрива скупа. Паралелни алгоритми: увод.
• 9. 13. децембра: алгоритми за рачунаре са заједничком меморијом: паралелно сабирање, максимум низа - EREW и CRCW варијанта, паралелни префикс
• 10. 20. децембра: алгоритми за рачунаре са заједничком меморијом: рангови елемената повезане листе, обрада стабла - техника Ојлеровог циклуса; алгоритми за мреже рачунара - сортирање на низу процесора, мреже за сортирање
• 11. 27. децембра: алгоритми за мреже рачунара: к-ти најмањи на потпуном стаблу, множење матрица на 2Д-мрежи; систолички алгоритми

Курс 2021/22 хтмл.

Курс 2020/21 хтмл.