|
Šifra modula |
CS 380 |
Fakultet |
PMF Sarajevo |
Napredne algoritamske tehnike
NASTAVNI PROGRAM
A. OPŠTI PODACI
|
Fakultet |
Prirodno-matematički fakultet Univerziteta u
Sarajevu |
|
Odsjek |
Odsjek za matematiku |
|
Smjer |
Svi smjerovi (ako je student slušao neophodne
module) |
|
Semestar |
Šesti |
|
Naziv modula |
Napredne algoritamske tehnike |
|
Tip modula |
Izborni |
|
Broj kreditnih bodova |
5 |
|
Kontakt sati |
Ukupno |
Predavanja |
Vježbe |
Seminari |
Konsultacije |
|
90 |
30 |
AV30, LV30 |
0 |
po potrebi |
|
Samostalni rad (sati) |
35 |
|
Obavezni prethodno položeni moduli |
Uvod u programiranje; Strukture podataka i
algoritmi |
|
Modul relevantan za module |
– |
|
Nastavno osoblje |
|
|
– Nastavnik nosilac modula |
Doc. dr. Haris Gavranović |
|
– Ostali nastavnici |
Doc. dr. Željko Jurić; Prof. dr. Naser Prljača |
|
– Asistenti |
Damir Hasić; Mr. Esmir Pilav |
B. CILJEVI MODULA
|
Modul predstavlja napredni
kurs dizajniranja algoritamskih struktura. Cilj modula je ovladati
matematskim metodama u analizi i konstrukciji algoritama, kao i
karakterističnim složenijim algoritmima. Koriste se programski jezik
C++ i programski paket Mathematica. |
C. SPECIFIČNI ZADACI MODULA
|
Kroz navedeni modul studenti
će kroz samostalan rad na laboratorijskim vježbama biti usmjereni
na implementaciju naprednih algoritamskih tehnika u programskom
jeziku C++ i programskom paketu Mathematica. |
D. OČEKIVANI REZULTATI NASTAVNOG
PROCESA
|
Nakon završetka modula,
studenti će biti u stanju da:
- Koriste napredne matematičke metode
za analizu i sintezu algoritama;
- Razumiju standardne napredne
algoritamske tehnike;
- Razumiju heurističke tehnike za
pristup rješavanju računski zahtjevnih problema;
- Razumiju ulogu randomizacije u
rješavanju računski zahtjevnih problema;
- mplementiraju napredne algoritme u
programskom jeziku C++.
|
E. SADRŽAJ NASTAVNOG PROCESA
|
Br. |
Nastavna jedinica |
Nastavni metod |
Sati rada |
|
Kontakt |
Samostalno |
|
1. |
Napredne tehnike analize algoritama; Primjena
diferentnih jednačina na analizu algoritama |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
2. |
Dinamičko programiranje i srodne tehnike;
Pohlepni algoritmi; Rekurzija sa pamćenjem (memoizacija) kao
alternativa dinamičkom programiranju |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
3. |
Linearni optimizacioni problemi; Simpleks
algoritam |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
4. |
Problemi cjelobrojne optimizacije; Tehnike
grananja sa odsjecanjem; |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
5. |
Napredni algoritmi sa grafovima; Eulerovi i
Hamiltonovi ciklusi; Problem maksimalnog protoka; Problem
raspoređivanja |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
6. |
Eksterno sortiranje i pretraživanje;
Balansirana stabla |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
7. |
Uvod u teoriju parsiranja;
Gramatike, leksički analizatori i prevodioci;
Parsiranje aritmetičkih izraza |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
8. |
Algoritmi sa stringovima i tokovima bita
(Knuth-Morris-Pratt, Rabin-Karp, Boyer-Moore). |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
9. |
Prepoznavanje uzoraka u tekstu; Primjena
konačnih automata na prepoznavanje uzoraka |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
10. |
Algebarski algoritmi; Brzi algoritmi za
stepenovanje; Brzi algoritmi za rad sa matricama; Brza Furijeova
transformacija i njene primjene |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
11. |
Tehnike kompresije podataka; Huffmanov
algoritam; Implode algoritam; Kompresija sa gubicima |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
12. |
Kriptološki algoritmi; RSA i srodni algoritmi
|
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
13. |
Uvod u teoriju modela; Diferentne i
diferencijalne jednačine kao standardni modeli dinamičkih procesa;
Osnovne metode numeričkog rješavanja diferencijalnih jednačina;
Markovljevi lanci; Simulacije |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
14. |
Heurističke metode u rješavanju računski
zahtjevnih problema |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
|
15. |
Paralelni algoritmi; Algoritmi na računarskim
mrežama |
Usmeno izlaganje 2
Vježbe i zadaci 2
Rad na računaru 2 |
6 |
2 |
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 (4 projekta) |
40 |
25 |
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 in C++”, Princeton University,
Addison Wesley Publishing Company, 1992.
2.
G. J. E. Rawlins: “Compared to what? An introduction to the
analysis of algorithms”, Computer Science Press, 1992.
3.
M. Živanović: “Algoritmi”, Matematički fakultet, Beograd,
2000.
4.
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.
S. Lipschutz, M. Lipson, “Discrete Mathematics”, McGraw Hill,
1997.
4.
A. Gibbons, “Algorithmic Graph Theory”, Cambridge University
Press, 1989.
5. M. R. Garey, D. S. Johnson, “Computers & Intractability – A Guide
to the Theory of NP‑completeness”, W. H. Freeman and Co, 1979.
6.
M. Vugdelija: “Dinamičko programiranje”, Društvo matematičara
Srbije, Beograd, 1999.
7.
D. Cvetković, M. Milić, “Teorija grafova i njene primjene”,
Naučna knjiga, Beograd, 1977.
8. J. Gruska: “Foundations of Computing”, International Thomson Computer
Press, 1997.