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

Предмет: Теорија сложености израчунавања (17.DOM46L)

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

Стицање основних знања из теорије сложености израчунљивости и укључивање у научно-истраживачки рад.

Познавање основних појмова и резултата из теорије сложености. Способност да се методе ове теорије примене у истраживању по избору студента, а у сарадњи са научницима из земље и иностранства.

Теорија сложености израчунавања О-нотација. Апстрактна сложеност израчунавања. Класе сложености израчунавања, хијерархија класа. Отворени проблеми у хијерархији класа сложености, П-НП проблем. Комплетни проблеми. Вероватне класе сложености. Примене теорије сложености у криптологији.

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

Аутори Назив Година Издавач Језик
Зоран Огњановић, Ненад Крџавац Увод у теоријско рачунарство 2005 Факултет организационих наука, Београд Српски језик
H. Lewis, C. Papadimitriou Elements of the theory of computation 1981 Prentice-Hall Енглески
Sipser, M. Introduction to the Theory of Computation 2006 Thomson Course Technology, Boston Енглески
C. Papadimitriou Computational complexity 1995 Addison-Wesley Енглески
Предметна активност Предиспитна Обавезна Број поена
Предметна активност
Семинарски рад
Предиспитна
Да
Обавезна
Да
Број поена
50.00
Предметна активност
Теоријски део испита
Предиспитна
Не
Обавезна
Да
Број поена
50.00
API Image

проф. др Силвиа Гилезан

Редовни професор

Предавања

API Image

проф. др Силвиа Гилезан

Редовни професор

Студијски истраживачки рад