×
Универзитет у Новом Саду

Предмет: Примењени алгоритми (17.D0M31L)

Основне информације:
 
Категорија Научно-стручни
Ужа научна област Теоријска и примењена математика
ЕСПБ 10

Образовни циљ курса је увођење основних концепата теорије алгоритама. Алгоритми се појављују у готово свакој грани информатике, као и инжењерским наукама, биологији, итд. Сваки проблем који се појави у научном процесу и треба да буде решен захтева алгоритам који је у стању да на основу датих података нађе решење. Због тога наведене теме имају и теоријски и практичан значај.

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

1.Увод.Рекурзивне функције. Турингове машине и њихови језици. Алгоритам, дефиниција. Комплексност алгоритма. Временска и просторна комплексност. 2.Класе комплексности. Примери полиномних алгоритама. Редукције. P=NP<\eng> pitanje. NP<\eng>-kompletni problemi, primeri. Klasa coNP<\eng>. 3.Prostorna kompleksnost. Savičeva teorema. Klase L<\eng> i NL<\eng>. Klasa Pspace<\eng>, pobedničke strategije. Problemi prebrajanja. 4. Verovatnosni algoritmi i aproksimativni algoritmi. Verovatnosni algoritmi. Klase BPP<\eng>, RP<\eng> i coRP<\eng>. Derandomizacija. Mali uzorački prostori. Aproksimativni algoritmi. Klasa NPO<\eng>. Deo nastave na predmetu se odvija kroz samostalni studijski istraživački rad u oblasti primenjene matematike. Studijski istraživački rad obuhvata aktivno praćenje primarnih naučnih izvora, organizaciju i izvođenje eksperimenata i statističku obradu podataka, numeričke simulacije, eventualno pisanje rada iz oblasti primenjene matematike.

Предавања. Менторски рад. Предавања се изводе комбиновано. Излагање теоретског дела пропраћено је одговарајућим примерима који доприносе разјашњењу теоретског дела градива. Поред предавања редовно се одржавају и консултације. Кроз студијски истраживачки рад студент, проучавајући научне часописе и осталу литературу самостално продубљује градиво са предавања. Уз рад са наставником студент се оспособљава за самостално писање научног рада.

Аутори Назив Година Издавач Језик
M. Atallah<\eng> Algorithms and theory of computation hanbook<\eng> 1999 CRC Press, London<\eng> Енглески
Sipser, M. Introduction to the Theory of Computation 2006 Thomson Course Technology, Boston Енглески
U. Schöning<\eng> Theoretische Informatik kurzgefaßt<\eng> 1995 Spektrum Akademischer Verlag GmbH, Berlin<\eng> Немачки
Предметна активност Предиспитна Обавезна Број поена
Предметна активност
Присуство на предавањима
Предиспитна
Да
Обавезна
Да
Број поена
10.00
Предметна активност
Семинарски рад
Предиспитна
Да
Обавезна
Да
Број поена
20.00
Предметна активност
Усмени део испита
Предиспитна
Не
Обавезна
Да
Број поена
70.00