Проширење и примена основног знања о структурама података, фундаменталним алгоритмима, анализи и стратегијама конструкције алгоритама.

По завршетку курса, студент има основна знања о стратегијама конструкције и анализи алгоритама. У стању је да усвојена знања примени на решавање нових проблема, направи оптималан избор одговарајуће структуре података за конкретан проблем.

1) Анализа алгоритама: асимптотска анализа најгорег или просечног случаја; асимптотске ознаке О, о, Ω, Θ; временска и просторна сложеност; 2) Графови: основни појмови, алгоритми обиласка графа - претрага у дубину, претрага у ширину 3) Графови: проналажење најкраћег растојања у графу 4) Графови: тополошко сортирање 5) Ниске, проналажење узорка у тексту, наивни алгоритам 6) Knuth–Morris–Pratt алгоритам проналаска узорка у тексту 7) Остали алгоритми проналаска узорка у тексту (Boyer–Moore, Rabin–Karp, ...) 8) Рекурзија и рекурзивни алгоритми 9) Велики бројеви и операције над великим бројевима 10) Претрага са враћањем - backtracking 11) Динамичко програмирање

1) Формирање и представљање графова. Примери, имплементација, примена. 2) Графови: проналажење најкраћег растојања у графу. Примери, имплементација, примена. 3) Графови: тополошко сортирање. Примери, имплементација, примена. 4) Ниске, проналажење узорка у тексту, наивни алгоритам. Примери, имплементација, примена. 5) Knuth–Morris–Pratt алгоритам проналаска узорка у тексту. 6) Остали алгоритми проналаска узорка у тексту (Boyer–Moore, Rabin–Karp, ...) 7) Рекурзија и рекурзивни алгоритми. Примери, имплементација, примена. 8) Велики бројеви и операције над великим бројевима. Примери, имплементација, примена. 9) Претрага са враћањем - backtracking. Примери, имплементација, примена. 10) Динамичко програмирање. Примери, имплементација, примена.

-

-

Укупан фонд часова: 60

Ново градиво: 16
Разрада и примери (рекапитулација): 4

Аудиторне вежбе: 20
Лабораторијске вежбе: 6
Рачунски задаци: 0
Семинарски рад: 0
Пројекат: 4
Консултације: 0
Дискусија/радионица: 0
Студијски истраживачки рад: 0

Преглед и оцена рачунских задатака: 0
Преглед и оцена лабораторијских извештаја: 0
Преглед и оцена семинарских радова: 0
Преглед и оцена пројекта: 0
Колоквијум са оцењивањем: 8
Тест са оцењивањем: 0
Завршни испит: 2

Активност у току предавања: 0
Тест/колоквијум: 60
Лабораторијска вежбања: 0
Рачунски задаци: 0
Семинарски рад: 0
Пројекат: 0
Завршни испит: 40
Услов за излазак на испит (потребан број поена): 0

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, Cambridge, 2009. ; Robert Sedgewick, Algorithms in C. 3rd Edition, 1997.; М. Живковић, Алгоритми, Математички факултет, Београд, 2000.