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

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

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.;