Конструкција и анализа алгоритама 2 2020/21
- 1. 16. октобра: Подсећање: анализа алгоритама, стратегије за конструкцију алгоритама - примери. Геометријски алгоритми:
- основни појмови, тачка у простом многоуглу
- повезивање тачака у прост многоугао
- 2. 23. октобра: Геометријски алгоритми (снимак):
- конвексни омотач (инкрементални алгоритам, увијање поклона, Грејемов алгоритам)
- сви пресеци хоризонталних и вертикалних дужи
- две најближе тачке
- две најдаље тачке (дијаметар скупа тачака)
- 3. 30. октобра: Структуре података (снимак):
- АВЛ стабла
- скип листа пдф
- 4. 6. новембра: Структуре података за обраду текста пдф:
- суфиксни низ: дефиниција, алгоритам Каркаинен-Сандерс линеарне сложености
- примене: тражење свих појава речи у тексту, тражење заједничке подниске у два или више текстова
- низ LCP, формирање од суфиксног низа алгоритмом линеарне сложености
- суфиксно стабло: изградња на основу суфиксног низа и низа LCP алгоритмом линеарне сложености, примене
- 5. 13. новембра: Сортирање, пробабилистички алгоритми,
(снимак).
- Сортирање вишеструким разврставањем
- алгоритам сортирања просечне линеарне сложености
- одређивање броја из горње половине
- бојење скупа са две боје тако да у задатој фамилији подскупова сви подскупови имају елементе обе боје
- генератори случајних бројева
- 6. 20. новембра: графови, (снимак):
- Савршено упаривање у густим графовима
- Оптимално упаривање у бипартитним графовима
- Транспортне мреже - оптимизација тока
- Хамилтонов циклус у густом графу
- 7. 27. новембра: свођења (редукције) (снимак):
- Цикличка подударност два низа и тражење речи у тексту
- Свођење са циљем да се докаже доња граница сложености алгоритма
- Свођење множења матрица на множење симетричних матрица
- Свођење множења матрица на квадрирање матрица
- Свођење сортирања на одређивање простог многоугла
- 8. 4. децембра: NP комплетни проблеми, (снимак):
- Доказ NP комплетности проблема збир подскупа
- Приближни алгоритми са гарантованом границом грешке
- Доказ непостојања приближног алгоритма (са фиксираном гарантованом границом грешке) полиномијалне сложености за рашавање општег проблема трговачког путника
- Приближни алгоритам за решавање проблема покривања скупа
- 9. 11. децембра (снимак):
- NP комплетни проблеми, полиномијална апроксимациона шема за решавање проблема збир подскупа (пдф)
- Паралелни алгоритми
- Модели паралелног израчунавања, карактеристике паралелних алгоритама
- Алгоритми за рачунаре са заједничком меморијом - увод
- 10. 18. децембра (снимак):
Паралелни алгоритми - алгоритми за рачунаре са заједничком меморијом
- Паралелно сабирање
- Максимум низа - EREW и CRCW варијанта
- Паралелни префикс
- Рангови елемената повезане листе
- 11. 25. децембра (снимак):
Паралелни алгоритми
- Алгоритми за рачунаре са заједничком меморијом - обрада стабла - техника Ојлеровог циклуса
- Алгоритми за мреже рачунара
- Систолички алгоритми
Испитна питања 2020/21: pdf