Табела 5.2 Спецификација  предмета

Студијски програм/студијски програми: Информатика
Врста и ниво студија: Дипломске академске студије
Назив предмета: И221 - Теорија алгоритама, аутомата и језика
Наставник (Презиме, средње слово, име):   Долинка В. Игор
Статус предмета: обавезан
Број ЕСПБ: 8
Услов: нема
Циљ предмета Упознавање са основним видовима и моделима израчунавања, посебно са израчунавањима уз помоћ апстрактних математичких машина, као и са формалним језицима и граматикама.
Исход предмета На крају курса студент треба да овлада основним моделима израчунавања уз помоћ апстрактних  математичких машина, да стекне увид у то шта се може алгоритамски решити, а шта не, као и да стекне знања о практичним применама формалних језика и аутомата у рачунарским наукама.
Садржај предмета Речи, полугрупа речи, језици, генеративне граматике (GG), хијерархија Чомског, контекстно-зависне граматике (CSG), контекстно-независне граматике (CFG), регуларне граматике, детерминистички коначни аутомати (DFA), недетерминистички коначни аутомати (NFA), примене у претраживању текста, трансдуктори, регуларни изрази, примене у лексичкој анализи и тражењу шаблона, регуларни језици, својства регуларних језика, теорема Клинија, минимални аутомат језика, CFG и њихове примене – парсери, језици за означавање, XML, контекстно-независни језици, потисни аутомати (PDA), еквивалентност PDA и CFG, Тјурингове машине (TM) и њихови језици, еквивалентност TM и GG, линеарни ограничени аутомати (LBA), еквивалентност LBA и CSG, одлучивост, израчунљивост и комплексност, Черч-Тјурингова теза.
Литература 1. М. Ћирић, Т. Петковић и С. Богдановић, Језици и аутомати, Просвета, Ниш, 2000. 2. M. V. Lawson, Finite automata, Chapman & Hall/CRC, Boca Raton, Florida, US, 2004. 3. J. E. Hopkroft, R. Motwani and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001. 4. Р. Мадарас и С. Црвенковић, Увод у теорију аутомата и формалних језика, Стилос и Природно-математички факултет, Нови Сад, 1995.
Број часова  активне наставе						Остали часови
Предавања: 3	Вежбе: 3	Други облици наставе:			Студијски истраживачки рад:
Методе извођења наставе На предавањима се користе класичне методе наставе уз коришћење пројектора. На вежбама се практично реализују изложени принципи и анализирају типични проблеми и њихова решења. Знање студената се тестира преко израде домаћих задатака и кроз два колоквијума, где се путем решавања задатака утврђује како степен усвојених теоријских знања, тако и вештина њихове примене. На завршном усменом испиту се проверава свеобухватно разумевање изложеног градива.
Оцена  знања (максимални број поена 100)
Предиспитне обавезе			поена	Завршни испит			поена
активност у току предавања			5	писмени испит
домаћи задаци			10 (5x2)	усмени испт			45
колоквијум-и			40 (2x20)	..........
семинар-и