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

Предмет: Теорија аутомата (17.0M512)

Матичне организационе јединице предмета: Департман за опште дисциплине у техници

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

Основни циљ предмета јесте стицање основних знања из теорије аутомата, укључујући регуларне језике, коначне аутомате, формалне језике и потисне аутомате. Студенти ће бити упознати са овим фундаменталним формалним моделима, али и са њиховом применом у неким гранама рачунарства (пре свега утицају на развој компајлера, развој програмских језика и формалних модела за конкурентне системе). Током извођења предмета, биће проучавани наведени формални модели, као и технике за њихову анализу, кроз примере и дискусију. Коначни циљ јесте да студенти развију вештине за постављања формалних модела и коришћење формалних алата и техника за анализу комплексних система.

Као исход предмета, студент ће поседовати основна знања из теорије аутомата и формалних језика. Поред тога, студенти ће овладати вештином постављања формалних метода и анализирањем њихових особина, користећи познате методе из наведених области. Студенти ће научити формалне технике које се најчешће користе у неким областима рачунарства (нпр. развоју програмских језика).

Детеминистички коначни аутомати, дефиниција и примери. Регуларни језици и регуларне операције. Недетерминистички коначни аутомати, дефиниција и примери. Регуларни изрази и њихова веза са коначним аутоматима. Језичка еквиваленција над коначним аутоматима. Контекстно независни језици. Потисни аутомати. Веза измедју потисних аутомата и контекстно независних језика.

На предавањима се излаже теоретски део градива пропраћен карактеристичним примерима ради лакшег разумевања градива. Студент самостално проучава додатну литературу и дискутује је са наставником на консултацијама.

Аутори Назив Година Издавач Језик
Hopcroft, J.E., Ullman, J.D. Introduction to automata theory, languges and computation 1979 Adison-Wesley, Reading, Mass. Енглески
С. Црвенковић , Р. Мадарас, Н. Мудрински Збирка задатака из теорије аутомата 2005 ПМФ, Нови Сад Српски језик
Shawn Hedman A First Course in Logic 2008 Oxford University Press Енглески
Мадарáсз, Р., Црвенковић, С. Увод у теорију аутомата и формалних језика 1995 Стyлос, Нови Сад Српски језик
Dexter C. Kozen Automata and Computability 1997 Springer Енглески
Sipser, M. Introduction to the Theory of Computation 2006 Thomson Course Technology, Boston Енглески
Предметна активност Предиспитна Обавезна Број поена
Предметна активност
Присуство на предавањима
Предиспитна
Да
Обавезна
Да
Број поена
5.00
Предметна активност
Теоријски део испита
Предиспитна
Не
Обавезна
Да
Број поена
30.00
Предметна активност
Присуство на вежбама
Предиспитна
Да
Обавезна
Да
Број поена
5.00
Предметна активност
Тест
Предиспитна
Да
Обавезна
Да
Број поена
10.00
Предметна активност
Тест
Предиспитна
Да
Обавезна
Да
Број поена
10.00
Предметна активност
Писмени део испита - комбиновани задаци и теорија
Предиспитна
Не
Обавезна
Да
Број поена
40.00

Предавања

Аудиторне вежбе