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

Назив предмета: И351 - Алгебарске и комбинаторне методе за процесирањe информација
Наставник или наставници (презиме, средње слово име):   Црвенковић Ђ. Синиша
Статус предмета:    изборни
Број ЕСПБ:    12
Услов:    нема
Циљ предмета Упознавање са основним алгебарским и комбинаторним концептима и методима који се примењују у представљању, процесирању, складиштењу и преносу информација.
Исход предмета По завршетку курса студент треба да овлада основним алгебарским и комбинаторним идејама, концептима и методима који се примењују при представљању, процесирању, складиштењу и преносу информација, и да буде оспособљен да поменуте идеје, концепте и методе самостално практично при-мени у научним истраживањима.
Садржај предмета Полугрупе, полугрупе релација и трансформација, слободне полугрупе и моноиди, језици и кодови, распознавање језика, синтаксичка полугрупа језика, полугрупа прелаза аутомата. Релације Myhill-а и Nerode-а, изводи (разломци) и Myhill-Nerode-ова теорија, минимални аутомат језика, минимизација аутомата, распознатљиви подскупови полугрупе, квази-уређења и rewriting системи. Псеудоваријетети полугрупа, варијетети језика, Eilenberg-ова теорема о кореспонденцији, star-free језици, локално тестабилни и део-по-део тестабилни језици, теореме Eilenberg-овог типа за полугрупе и аутомате. Примена полугрупа и графова у симболичкој динамици, симболички динамички системи, sofic шифтови и шифтови коначног типа, синтаксичка полугрупа sofic шифта, аутомати и графови у симболичкој динамици, ентропија, примена спектралне теорије графова у рачунању ентропије. Полупрстени, формални степени редови и матрице, представљање језика формалним степеним редовима, тежински (weighted) аутомати, примене тежинских аутомата. Алгебре језика, релационе алгебре и Клинијеве алгебре, алгоритамски проблеми у алгебрама језика.
Препоручена литература 1. U. Hebish and H. J. Weinert, Semirings: Algebraic Theory and Applications in Computer Science, World Scientific, Singapore, 1998. 2. A. de Luca and S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer, 1999. 3. G. Rozenberg and A. Salomaa (eds.), Handbook of Formal Languages, Vol.1-3, Springer, Berlin-Heidelberg, 1997. 4. J. Berstel and Ch. Reutenauer, Rational Series and Their Languages, EATCS Monographs in Theoretical Computer Science, vol 12, Springer, Berlin, 1988. Electronic Edition 2007. 5. М. Ћирић, Т. Петковић и С. Богдановић, Језици и аутомати, Просвета, Ниш, 2000. 6. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1996.
Број часова  активне наставе	Предавања: 4		Студијски истраживачки рад:
Методе извођења наставе На предавањима се користе класичне методе наставе уз коришћење видео пројектора и интеракцију са студентима. Знање студената се тестира преко израде домаћих задатака и одбране семинарских радова. На завршном усменом испиту се проверава свеобухватно разумевање изложеног градива.
Оцена  знања (максимални број поена 100)
Предиспитне обавезе	поена	Завршни испит		поена
домаћи задаци	10 (2x5)	усмени испит		70
семинарски рад	20	..........