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

Предмет: Алгоритми и њихова сложеност (17.EM402)

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

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

Обезбедити један општи увид у фундаменталне аспекте теорије алгоритама и њихове сложености укључујући примере алгоритама из различитих области електротехнике и рачунарства.

Студент који успешно заврши овај предмет стећи ће увид у основне концепте теорије алгоритама и њихове сложености који укључује: - разумевање концепта алгоритма, класификације проблема и алгоритама, поступке којима се доказује да алгоритам решава сваку инстанцу разматраног проблема и процену сложености - компендијум проблема из области електротехнике и рачунарства

Концепт проблема и алгоритамског решења, улога језика у опису проблема, решења и алгоритма. Концепт инстанце проблема и њене величине. Концепт функције сложености и асимптотске сложености алгоритма. Концепт машине и елементарне операције, асимптоске нотације, анализа алгоритама, различите технике у дизајну алгоритама. Класе сложености и релације међу њима. Концепт редукције и комплетних проблема, класе П, НП и цо-НП. Временска, просторна, комуникацијска и енергетска комплексност. Комплексност Булових кола. Параметризовани, апроксимативни, рандомизовани алгоритми.

Предавања; Аудиторне вежбе; Рачунарске вежбе; Лабораторијске вежбе; Консултације.

Аутори Назив Година Издавач Језик
Л. Новак Алгоритми и њихова сложеност - скрипте 2007 ФТН Нови Сад Српски језик
Cormen, T.H. et al. Introduction to Algorithms 2009 MIT Press, Cambridge Енглески
Christos H. Papadimitriou Computational Complexity 1994 Addison Wesley Longman Енглески
Предметна активност Предиспитна Обавезна Број поена
Предметна активност
Присуство на рачунарским вежбама
Предиспитна
Да
Обавезна
Да
Број поена
5.00
Предметна активност
Домаћи задатак
Предиспитна
Да
Обавезна
Да
Број поена
20.00
Предметна активност
Писмени део испита - комбиновани задаци и теорија
Предиспитна
Не
Обавезна
Да
Број поена
70.00
Предметна активност
Присуство на предавањима
Предиспитна
Да
Обавезна
Да
Број поена
5.00

Предавања

Предавања

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

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

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