Конструкција и анализа алгоритама 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