Студијски програм : Дипломске академске студије
Назив предмета: Структуре података и алгоритми
Наставник: Доц. Зоран Николић
Статус предмета: Изборни
Број ЕСПБ: 4
Услов:
Циљ предмета: Да студентима омогући познавање теорије, принципа, стандарда на којима је базирано организовање структуираних података и упознавање са стандардним генеричким алгоритмима који су иманентни алгоритми за дате структуре података.. Овај курс захтева познавање неког програмског језика попут C/C++, који подржавају стандардне типове података, структуирано програмирање, рекурзију и показиваче.
Исход предмета: Усвајање теоријских основа и принципа на којима је засновано структуирање података. Паралелно са тим стиче се теоријско и практично знање у адаптирању алгоритама за манипулисање структуираним подацима. На крају овога курса на основу стечених знања развија се самостални пројекат – апликација на програмском језику C++, која манипулише комплексним, динамичким организованим подацима, којој је тежиште у адаптацији стандардних алгоритама из овог курса.
Садржај предмета: Теоријска настава: Основне структуре података. Примитивни и стандардни типови података. 1.4.2 Типови REAL, BOOLEAN, CHAR. Структуре типа ARRAY, RECORD и SET и њихове репрезентације. Датотеке и секвенце. Операције са датотекама. Баферовање. Баферовање у конкурентским процесима. Текстуални улаз и излаз. Линеарно, бинарно и табеларно претраживање. Претраживања стрингова и Knuth-Morris-Pratt и Boyer-Moore алгоритни. Сортирања. Елементрарни алгоритми за сортирања низова - Straight Insertion, Straight Selection и Straight Exchange. Напредне методе сортирања: Tree Sort и Partition Sort. Quicksort, Heapsort и Radix сортирање. Сортирање секвенци. Спајања: Straight, Natural и Balanced Multiway. Процесирање стрингова. Претраге, проналажења патерна, парсирање, компресија и криптовање. Рекурзивни алгоритми. Предности и мане. Начини коришћења. Примери.Динамичке структуре. Рекурзивни типови, показивачи и листе. Основне операције са листама. Уређене листе и реорганизација. Структуре типа дрво. Основни концепти и дефиниције. Бинарно дрво. Претрага кроз дрво. Уметање и брисање чворова. Балансирано дрво. Претраге, уметања и брисања чворова. Дрво за оптималне претраге. B-дрво. Multiway B-дрво и бинарно B-дрво. Дрво са приоритетом претраге. Трансформација кључева. Hash функције. Нумерички алгоритми. Гаусова елиминација. Интерполација и алгоритми са итеративним поступцима. Нумеричка апроксимација и интеграција. Брза Фуријеова трансформација. Геометријски алгоритми. Полигони и алгоритми за генерисања ковенсних полигона. Претраживање области. Геометријски пресеци. Методе најближе тачке. Алгоритми припадности области. Графови и елементрарни алгоритми са графовима. Динамичко и линеарно програмирање. Min-max алгоритми и оптимизације. Примене Simplex методе у оптимизацијама.
Литература: 1. N. Wirth, Algorithms and Data Structures, Prentice Hall PTR, (1985). 2. R. Sedgewick, Algorithms, Addison-Wesley Publishing Company, (1984).
Број часова активне наставе: 2	Теоријска настава: 4 (2+2)		Практична настава:
Методе извођења наставе Предавања (Теоријска обрада тематских јединица, практични примери, домаћи задаци), рачунске вежбе (домаћи задаци и семинари).
Оцена знања (максимални број поена 100)
Предиспитне обавезе	поена	Завршни испит		поена
активност у току предавања	15	писмени испит		15
активност у току рачунских вежби	15	усмени испит		25
семинар	30	UKUPNO		100