Основе теорије алгоритама

ID: 7012
врста предмета: научно-стручни
носилац предмета: Јандрлић Р. Даворка
извођачи: Јандрлић Р. Даворка, Пејчев В. Александар
контакт особа: Јандрлић Р. Даворка
ниво студија: информационе технологије у машинству
ЕСПБ: 5
облик завршног испита: писмени+усмени
катедра: катедра за математику

извођења

  • 3. семестар, позиција 1

циљ

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

исход

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

садржај теоријске наставе

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

активна настава (теоријска)

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

активна настава (практична)

аудиторне вежбе: 0
лабораторијске вежбе: 20
рачунски задаци: 0
семинарски рад: 0
пројекат: 4
консултације: 0
дискусија/радионица: 0
студијски истраживачки рад: 0

провера знања

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

провера знања (укупно 100 поена)

активност у току предавања: 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. ; М. Живковић, Алгоритми, Математички факултет, Београд, 2000;