Податочни структури и анализа на алгоритми

Објавено: јуни 28, 2022
1. Наслов на наставниот предмет Податочни структури и анализа на алгоритми
2. Код 4ФЕИТ07З017
3. Студиска програма КТИ
4. Организатор на студиската програма Факултет за електротехника и информациски технологии
5. Степен Прв циклус студии
6. Академска година / семестар III/5 7. Број на ЕКТС 6
8. Наставник Д-р Даниел Денковски
9. Предуслов за запишување на предметот Положени: Програмирање и алгоритми, Податочни структури и програмирање
10. Цели на предметната програма (компетенции). Познавање на податочни структури и стратегии за дизајн на алгоритми. Способност за работа со сложени податочни структури во програмскиот јазик Јава. Способност за дизајн на соодветни алгоритми за работа со податочните структури. Способност за анализа на комплексност на алгоритми. По завршување на курсот студентот ќе може да решава проблеми со сложени податочни структури и алгоритми (во Јава).
11. Содржина на програмата: Вовед за теорија на алгоритми и основни концепти на податочни структури. Логички и физички структури. Имплементација со Јава ADT. Анализа и комплексност на алгоритам. Линеарни податочни структури-низи и листи. Статички и динамички низи и листи во Јава. Примена на низи и листи за логички податочни структури: пласт/магацин, ред, двостран ред, приоритетен ред (имплементација со Јава). Алгоритамски стратегии. Дизајн на алгоритми. Класификација на алгоритми. Стратегија на груба сила (brute force). Алчни (greedy) алгоритми. Стратегија раздели и владеј (Divide and Conquer). Нелинеарни структури. Дрва. Бинарни дрва. Бинарни пребарувачки дрва. Балансирани бинарни пребарувачки дрва. AVL дрва. Црвено-црни балансирани дрва (Red‐Black Trees). Хеш (hash) структури. Функции за хеширање и нивни својства. Колизии и разрешување. Претстава на графови преку податочни структури. Примена на графови (насочени и ненасочени графови, тежински графови). Пребарување во графови: по длабочина и по широчина. Алгоритми за најкратки патеки во тежински графови. Белман-Форд алгоритам. Алгоритам на Дијкстра. Алгоритам на Крускал. Алгоритам на Прим.
12.Методи на учење Предавања, аудиториски и лабораториски вежби
13. Вкупен расположив фонд на часови 2 + 2 + 1 + 0
14. Распределба на расположивото време 180
15. Форми на наставните активности 15.1. Предавања – теоретска настава 30
15.2. Вежби, семинари, тимска работа 45
16. Други форми на активност 16.1. Проектни задачи 0
16.2. Самостојни задачи 25
16.3. Домашно учење 80
17. Начини на оценување 17.1. Тестови 0
17.2. Семинарска работа/проект 0
17.3. Активност и учење 10
17.4. Завршен испит 90
18. Критериуми за оценување до 50 бодови 5 (пет) (F)
од 51до 60 бодови 6 (шест) (E)
од 61до 70 бодови 7 (седум) (D)
од 71до 80 бодови 8 (осум) (C)
од 81до 90 бодови 9 (девет) (B)
од 91до 100 бодови 10 (десет) (A)
19. Услов за потпис и полагање на завршен испит Редовно посетување на наставата и аудиториските вежби и комплетно изработени лабораториски вежби
20. Начин на полагање на испитот Два парцијални писмени испити во текот на семестарот (на половина и на крај од семестарот) во времетраење од по 120 минути или еден завршен писмен испит во соодветна испитна сесија во времетраење од 120 минути. Оценување и на лабораториските вежби. Во конечната оцена влегуваат поените од писмениот испит и лабораториските вежби. За време на испитот не е дозволено користење книги, скрипти, ракописи или белешки од кој било вид.
21. Јазик на кој се изведува наставата Македонски и Англиски
22. Метод на следење на квалитетот на наставата Интерна евалуација и анкети
23. Литература
23.1. Задолжителна литература
Бр. Автор Наслов Издавач Година
1 T. H. Cormen, et al. Introduction to Algorithms, 3rd Ed. MIT Press 2009
2 R. Lafore Data Structures and Algorithms in JAVA, 2nd Ed. SAMS 2003
3 M. Goodrich and R. Tamassia Data Structures and Algorithms in Java, 6th Ed. John Willey 2014