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

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

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

Испитна питања пдф.

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

• 1. 14. октобра: суфиксни низ. Алгоритам Каркаинена-Сандерса (снимак)
• 2. 21. октобра: суфиксни низ. Низ lcp, суфиксно стабло, формирање суфиксног стабла на основу суфиксног низа и низа lcp, примене пдф, (снимак)
• 3. 28. октобра: Сортирање, пробабилистички алгоритми (снимак)
• 4. 4. новембра: Графови: упаривање, транспортне мреже (снимак)
• 5. 18. новембра: Хамилтонови циклуси у густом графу. Свођења (редукције)
  • Свођење са циљем да се реши проблем, примери, свођење на линеарно програмирање
  • Свођење са циљем да се докаже доња граница сложености алгоритма
    • Свођење множења матрица на множење симетричних матрица, на квадрирање матрица
    • Свођење сортирања на одређивање простог многоугла
  (снимак)
• 6. 26. новембра: NP комплетни проблеми, Кукова теорема, докази NP комплетности (покривач грана, доминирајући скуп, 3-SAT) (снимак)
• 7. 2. децембра: докази NP комплетности (клике, 3-SAT, 3-обојивост, збир подскупа, покривање подскупова као специјални случај покривача грана); приближни алгоритми са гаранцијом квалитета решења (доминирајући скуп, 1Д паковање) (снимак)
• 8. 9. децембра: приближни алгоритми са гаранцијом квалитета решења (еуклидска варијанта проблема трговачког путника са фактором 2, односно 1.5; најмање покривање скупа подскуповима), доказ неопостојања приближног алгоритма са фиксним фактором за општи проблем трговачког путника; (снимак)
• 10. 16. децембра: Паралелни алгоритми - алгоритми за рачунаре са заједничком меморијом: паралелно сабирање, максимум низа - EREW и CRCW варијанта, паралелни префикс (снимак)
• 11. 24. децембра: алгоритми за рачунаре са заједничком меморијом: рангови елемената повезане листе, обрада стабла - техника Ојлеровог циклуса; алгоритми за мреже рачунара - сортирање на низу процесора, мреже за сортирање (снимак)
• 12. 30. децембра: алгоритми за рачунаре са заједничком меморијом; систолички алгоритми (снимак)