Табела 5.1 Спецификација  предмета  на студијском програму докторских студија

Назив предмета:    И311 - Формални језици, аутомати и израчунљивост
Наставник или наставници (презиме, средње слово име):    Ћирић Д. Мирослав
Статус предмета:     изборни
Број ЕСПБ:     12
Услов:     нема
Циљ предмета Упознавање са основним идејама, концептима и резултатима теорије израчунавања, са формалним језицима и аутоматима, симболичком динамиком и кодирањем, као и са алгоритмима за процеси-рање текста.
Исход предмета По завршетку курса студент треба да овлада основним идејама, концептима и резултатима теорије формалних језика и аутомата, симболичке динамике и кодирања, и основним алгоритмима за проце-сирање текста, и да буде оспособљен да поменуте идеје, концепте и резултате самостално практич-но примени у научним истраживањима у оквиру те исте или неке друге научне области.
Садржај предмета Формални језици: Операције и комбинаторика на речима, формални језици, генеративне граматике, класификација граматика. Аутомати: Детерминистички и недетерминистички аутомати, трансдук-тори, регуларни изрази и њихове примене, регуларни језици, контекстно-независне граматике и њихове примене, потисни аутомати, Тјурингове машине и њихови језици, линеарни ограничени аутомати и контекстно зависни језици, питања одлучивости, израчунљивости и комплексности. Симболичка динамика и кодирање: Бесконачне речи, алгебра и топологија на бесконачним речима, аутомати и језици бесконачних речи, симболички динамички системи, sofic шифтови и шифтови коначног типа, аутомати и графови у симболичкој динамици, ентропија, кодирање, кодови, корек-ција грешака, синхронизација, декодирање. Текст алгоритми: Алгоритми за спаривање шаблона (pattern matching), аутомати за спаривање шаблона, спаривање регуларних израза, текст алгоритми повезани са сортирањем, апроксимативно спаривање, најдужи заједнички подниз, вишедимензио-нално спаривање, компресија текста.
Препоручена литература 1. М. Ћирић, Т. Петковић и С. Богдановић, Језици и аутомати, Просвета, Ниш, 2000. 2. M. V. Lawson, Finite automata, Chapman & Hall/CRC, Boca Raton, Florida, US, 2004. 3. J. E. Hopkroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001. 4. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1996. 5. M. Crochemore and W. Rytter, Jewels of Stringology, World Scientific, Singapore, 2002. 6. G. Rozenberg and A. Salomaa (eds.), Handbook of Formal Languages, Vol.1-3, Springer, Berlin-Heidelberg, 1997.
Број часова  активне наставе		Предавања: 4		Студијски истраживачки рад:
Методе извођења наставе На предавањима се користе класичне методе наставе уз коришћење видео пројектора и интеракцију са студентима. Знање студената се тестира преко израде домаћих задатака и одбране семинарских радова. На завршном усменом испиту се проверава свеобухватно разумевање изложеног градива.
Оцена  знања (максимални број поена 100)
Предиспитне обавезе	поена		Завршни испит		поена
домаћи задаци	10 (2x5)		усмени испит		70
семинарски рад	20		..........