R
SI
1 9 7 5
U
УЦИ NIV E
A У НИВ
UK
Е
AL
АЛ
Т У БА
ИТ Е
Њ
РЗ
F
TY O B A NJ
Назив предмета
Шифра предмета
УНИВЕРЗИТЕТУ У БАЊОЈ ЛУЦИ
ПРИРОДНО- МАТЕМАТИЧКИ ФАКУЛТЕТ
Дипломске академске студије - МАСТЕР
Студијски
програм(и):
Математика и инфоматика
Структуре података и алгоритми
Статус предмета
Семестар
Обавезан
3. (трећи)
Фонд часова
3+3
Број ЕЦТС бодова
8
Наставнцици
Др Илија Лаловић, Доцент, Димитрије Чвокић, асистент
Условљеност другим предметима:
Облик условљености
Увод у програмирање, Увод у рачунарство 1, Увод у рачунарство 2, Дискретна
Положени испити
математика
Циљеви изучавања предмета:
Циљ је да након положеног курса студент може: анализирати асимптотске перформансе алгоритама, показати
познавање важних алгоритама и структура података, примјењивати алгоритамске парадигме дизајна и методе
анализе и писати ефектне алгоритме у уобичајеним ситуацијама инжињерског дизајнирања.
Исходи учења (стечена знања):
Након комплетирања курса студент ће стећи употребљива знања у области структура података и секвенцијалних алгоритама,
као и преглед метода паралелних алгоритама, дистрибуираних алгоритама, стохастичких алгоритама и NP комплетности. Моћи
ће провјерити тоталну коректност програма користећи индуктивне доказе и инваријанте петљи, а користећи асимптотску
анализу анализирати worst-case времена извођења алгоритама. Научиће поредити асимптотско понашање функција добивених
композицијом полиномијлних, експоненцијалних и логаритамских функција и описати односе између worst- case, average-case
и best-case извођења алгоритма. У курсу ће бити изложене парадигме подијели и владај (divide-and-conquer), динамичко
програмирање (dynamic-programming), претраживање са повраћањем унатраг (back-trаcking) и незаситост (greedy paradigm).
Студент треба бити оспособљен да опише сваку од наведенихи парадигми и објасни у којим ситуацијама постоји потреба за
дизајнирње позивом на ту парадигму, да наброји основне алгоритме који користе ту парадигму, да напише алгоритме у тој
парадигми и да их анализира, те да опише перформансе које даје та парадигма. Даље, студент треба овладати главним
алгоритмима за сортирање, знати објаснити анализу тих алгоритама и стратегије њиховог дизајнирања, моћи писати програме у
којима се сортирање користи као метода, извести доње и горње границе за сортирање поређењем, те показати како се ове
границе могу избјећи. У курсу ће бити изложене и главне елементарне структуре података за имплементацију динамичких
скупова и анализа операција које се изводе на њима. Студент треба знати алгоритме који користе структуре података и како
њихове перформансе зависе од избора структуре података, знати правити нове стуктуре података полазећи од постојећих, те
писати алгоритме који користе те структуре као кључне компоненте.
Садржај предмета:
1. Osnovi analize algoritama
Prostorna i vremenska slozenost. Slozenost u najgorem, najboljem i prosjecnom slucaju. Asimptotske oznake.
Hijerarhije slozenosti. Rekurentne relacije i slozenost algoritama.
2. Poredjenje polinomijalne, logaritamske i eksponencijalne slozenosti
Veza izmedju povecanja brzine procesora i kompleksnosti algoritama. Racionalizacija mnozenja velikog broja
kompleksnih brojeva. Hornerova shema. Sortiranje u vremenu O(n^2): sort izborom, sort umetanjem, bubble sort.
Algoritam za nalazenje drugog elementa u nizu i ideje za razvoj algoritama efektivnog sortiranja.
3. Metoda “Podijeli i vladaj” za analizu i dizajn algoritama
Dizajn i analiza slozenosti rekurzivnih algoritama. Efektivno mnozenje dugackih cijelih brojeva u vremenu O(n^1.59).
Binarno pretrazivanje u vremenu O(log n). Dizajn i analiza merge sortiranja. Efektivno mnozenje dvije n x n matrice u
vremenu O(n^2.81).
4. Prosjecna (awerage case) slozenost
Dizajn i analiza slozenosti Quick sort algoritma. Nalazenje k-tog elementa niza u linearnom vremenu. Donje
ogranicenje O(n log n) za algoritme sortiranja poredjenjem u opstem slucaju.
5. Dinamicke strukture podataka
Osnovne operacije na dinamickim strukturama podataka. Rjecnik, stek, red za cekanje, jednostruko i dvostruko
povezane liste. Pokazivaci i implementacija pokazivaca matricom.
6. Binarno drvo
Operacije na drvetima. Heap i operacije na heap-u. Red-Black drveta. Neograniceno grananje drveta.
7. Hes tabele i operacije nad njima
Tabele sa direktnim adresiranjem. Pojam hesiranja. Rjesavanje kolizije uvezivanjem. Analiza slozenosti za hesiranje
sa uvezivanjem. Prosto uniformno hesiranje. Heuristicke hes funkcije. Hesiranje dijeljenjem. Hesiranje mnozenjem.
Stohasticke hes funkcije: univerzalno hesiranje (linearno, kvadratno dvostruko). Otvoreno adresiranje.
8. Dinamicko programiranje
Mnozenje niza matrica. Nalazenje zajednickog podniza. Optimalna triangulacija poligona. Optimalna binarna drveta
za pretrazivanje.
9. Algoritmi sa pretrazivanjem unazad (Backtracking algoritmi)
Nalazenje puta iz lavirinta. Problem osam kraljica na sahovskoj ploci. Rekonstrukcija polozaja tacaka iz zadatih
rastojanja. Ispis racionalnih tacaka iz intervala [0, 1] uz zadata ogranicenja.
10. “Greedy” (nezasiti) algoritmi
Metoda dizajna i analize algoritama metodom “Hill – climbing”. Minimmizacija srednjeg vremena cekanja procesa na
jednom ili vise procesora.
11. “Greedy” (nezasiti) algoritmi (nastavak)
Huffman-ovi kodovi. Huffman-ov algoritam. Pravljenje rasporeda sa minimalnim konacnim vremenom cekanja.
Problem pakovanja ranca.
12. On – line i Off – line algoritmi.
On – line algoritmi. “Next fit”, “Best fit”, “First fit” pakovanje. Off – line algoritmi. “First – fit decreasing”.
13. Probabilistička analiza i randomizovani algoritmi. Problem izbora službenika. Slučajne permutacije nizova.
14. Polinomi i brza Fourier-ova transformacija. Predstavljanje polinoma. Brzo množenje polinoma u formi
koeficijenata. DFT i FFT. Efektna implementacija FFT.
15. Linearno programiranje. Definicija LP. Algoritmi LP. Primjeri primjene linearnog programiranja.
Методе наставе и савадавање градива:
Предавања, вјежбе, колоквијум, пројекат са домаћим радом.
Литература:
1. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, Second Edition, The MIT
Press 2001
2. D. E. Knuth, The Art of Computer Programming, Vols 1-3, Addison-Wesley, Reading, 1973
3. I. Lalovich, Manuskript predavanja, Banja Luka, 2005
4.
Dj. Paunic, Strukture podataka i algoritmi, Univerzitet u Novom Sadu, Novi Sad, 1997
5. M. Zivkovic, Algoritmi, Matematicki fakultet, Beograd,
Облици провјере знања и оцјењивања:
Колоквијум. Пројекат са домаћим задатком. Завршни испит.
Похађање наставе
5
Домаћи задатак
Активност на настави 5
Колоквиј
Посебна назнака за предмет:
20
20
Име и презиме наставника који је припремио податке: Катедра за информатику
Завршни испит
50
Download

Структуре података и алгоритми