|
Šifra modula |
CS 330 |
Fakultet |
PMF Sarajevo |
Strukture podataka i algoritmi
NASTAVNI PROGRAM
A. OPŠTI PODACI
|
Fakultet |
Prirodno-matematički fakultet Univerziteta u
Sarajevu |
|
Odsjek |
Odsjek za matematiku |
|
Smjer |
Svi smjerovi |
|
Semestar |
Peti |
|
Naziv modula |
Strukture podataka i algoritmi |
|
Tip modula |
Obavezni |
|
Broj kreditnih bodova |
7 |
|
Kontakt sati |
Ukupno |
Predavanja |
Vježbe |
Seminari |
Konsultacije |
|
120 |
45 |
AV30, LV30 |
– |
15 |
|
Samostalni rad (sati) |
55 |
|
Obavezni prethodno položeni moduli |
Uvod u programiranje; Objektno orjentirano i
generičko programiranje; Analiza i sinteza algoritama |
|
Modul relevantan za module |
Napredne algoritamske tehnike; Projektiranje
računarskih aplikacija |
|
Nastavno osoblje |
|
|
– Nastavnik nosilac modula |
Doc. dr. Željko Jurić |
|
– Ostali nastavnici |
Prof. dr. Naser Prljača; Doc. dr. Haris
Gavranović |
|
– Asistenti |
Mr. Esmir Pilav; Mr. Almasa Odžak |
B. CILJEVI MODULA
|
Modul predstavlja uvodni
kurs u napredne strutkure podataka i elementarne algoritamske
strukture koje čine osnovu za programiranje složenijih algoritama.
Cilj modula je ovladati tehnikom dizajniranja struktura podataka
koje su najbolje prilagođene problemu koji se rješava i tehnikom
izbora odgovarajućeg algoritma. |
C. SPECIFIČNI ZADACI MODULA
|
Kroz navedeni modul studenti
će kroz samostalan rad na laboratorijskim vježbama biti usmjereni
na razvoj i implementaciju struktura podataka i osnovnih
algoritamskih rješenja u
programskom jeziku C++ i
programskom paketu Mathematica. |
D. OČEKIVANI REZULTATI NASTAVNOG
PROCESA
- Nakon završetka modula,
studenti će biti u stanju da:
- Razumiju osnovne tehnike analize i
sinteze algoritama;
- Razumiju osnovne pojmove vezane za
teoriju kompleksnosti i izračunljivosti;
- Razumiju i samostalno dizajniraju
složene strukture podataka;
- Koriste i primjenjuju standardne
algoritamske tehnike;
- Koriste standardne strukture
podataka i algoritme iz standardne biblioteke predložaka za
programski jezik C++;
- Koriste programski paket
Mathematica za efikasno i brzo rješavanje standardnih problema;
|
E. SADRŽAJ NASTAVNOG PROCESA
|
Br. |
Nastavna jedinica |
Nastavni metod |
Sati rada |
|
Kontakt |
Samostalno |
|
1. |
Pojam struktura podataka. Vrste struktura
podataka. Linearne i razgranate strukture. |
Usmeno izlaganje 3
Vježbe i zadaci 2
Rad na računaru 2 |
8 |
3 |
|
2. |
Linarne strukture podataka. Niz i vektor. Stek
i red. Implementacije. |
– II – |
8 |
4 |
|
3. |
Jednostruko i dvostruko povezane liste;
Statička implementacija. Dinamička implementacija. |
– II – |
8 |
4 |
|
4. |
Sekvence i njihova implementacija. |
– II – |
8 |
3 |
|
5. |
Razgranate strukture podataka. Stabla i grafovi. |
– II – |
8 |
4 |
|
6. |
Binarna stabla. Statička implementacija.
Dinamička implementacija. |
– II – |
8 |
4 |
|
7. |
Primjene stabala. Binarno stablo pretrage.
Gomila (hîp). Sortiranje zasnovano na gomili. |
– II – |
8 |
3 |
|
8. |
Elementarni algoritmi sa grafovima.
Pretraživanje po dubini i širini. |
– II – |
8 |
4 |
|
9. |
Nalaženje najkraćeg puta. Nalaženje minimalnog
povezujućeg stabla. |
– II – |
8 |
3 |
|
10. |
Tehnike iscrpnog pretraživanja. Povratno
pretraživanje. Min-max i alfa-beta pretraga. |
– II – |
8 |
4 |
|
11. |
Tehnike za rad sa NP kompletnim problemima.
Randomizirani algoritmi. Simulacije. |
– II – |
8 |
4 |
|
12. |
Napredni algoritmi sa grafovima. Eulerovi i
Hamiltonovi ciklusi. Problem maksimalnog protoka. |
– II – |
8 |
3 |
|
13. |
Problem raspoređivanja. Mađarski algoritam
raspoređivanja. |
– II – |
8 |
4 |
|
14. |
Linearni optimizacioni problemi. Simpleks
algoritam. Problemi cjelobrojne optimizacije. |
– II – |
8 |
4 |
|
15. |
Brza Fourierova transformacija i njene primjene. |
– II – |
8 |
4 |
F. PROVJERA ZNANJA I OCJENJIVANJE
|
Provjera znanja – kriteriji |
Ocjenjivanje |
|
Kriterij |
Maksimalan broj bodova |
Bodovi za prolaz |
Osvojen broj bodova |
Ocjena (BiH) |
ECTS ocjena |
|
Testovi tokom kursa (2 testa) |
30 |
15 |
< 55,00 |
5 |
F |
|
Projektni zadaci (5 projekata) |
40 |
20 |
55,00 – 64,99 |
6 |
E |
|
Pismeni završni ispit |
30 |
15 |
65,00 – 74,99 |
7 |
D |
|
|
|
|
75,00 – 84,99 |
8 |
C |
|
|
|
|
85,00 – 94,99 |
9 |
B |
|
|
|
|
95,00 – 100,00 |
10 |
A |
|
U k u p n o |
100 |
55 |
|
G. LITERATURA
Osnovna literatura:
1.
R. Sedgewick, “Algorithms”, Addison
Wesley Publishing Company, 1988.
2.
R. Sedgewick: “Algorithms in C++”,
Princeton University, Addison Wesley Publishing Company, 1992.
3.
U. Breymann: “Designing Components with
the C++ STL”, Addison-Wesley Longman Limited, 1998.
4.
R. E. Maeder: “Programming in
Mathematica (2nd edition)”, Addison Wesley, 1991.
5.
M. Živanović: “Algoritmi”,
Matematički fakultet, Beograd, 2000.
6.
D. Urošević: “Algoritmi u programskom
jeziku C”, Mikro Knjiga, Beograd, 2003.
Dopunska literatura:
1.
T. H. Cormen, C. E. Leiseron, R. L. Rivest
& C. Stein, “Introduction to Algorithms”, MIT Press, 2001.
2.
S. Lipschutz, “Theory and Problems of
Data Structures”, McGraw Hill, 1986.
3.
A. Gibbons, “Algorithmic Graph Theory”,
Cambridge University Press, 1989.
4.
M. R. Garey, D. S. Johnson, “Computers &
Intractability – A Guide to the Theory of NP‑completeness”, W. H.
Freeman and Co, 1979.
5.
M. Vugdelija: “Dinamičko programiranje”,
Društvo matematičara Srbije, Beograd, 1999.
6.
D. Cvetković, M. Milić, “Teorija grafova
i njene primjene”, Naučna knjiga, Beograd, 1977.
7.
S. Wolfram: “The Mathematica Book (4th
edition)”, Cambridge University Press, 1999.
8.
A. Koenig, B. Moo: “Ruminations on C++”,
Addison-Wesley Longman Inc, 1997.
9.
V. Aho, J. E. Hopcroft, J. D. Ulman: “Data
Structures and Algorithms”, Addison-Wesley, 1983.
10.
D. E. Knuth: “The Art of Computer
Programming, Volume 1: Fundamental Algorithms”, Addison-Wesley,
1968.