Šifra modula

PMAT 260

Fakultet

PMF Sarajevo

 

Analiza i sinteza algoritama

 

NASTAVNI PROGRAM

 

A. OPŠTI PODACI

Fakultet	Prirodno-matematički fakultet Univerziteta u Sarajevu
Odsjek	Odsjek za matematiku
Smjer	Teorijska kompjuterska nauka
Semestar	Četvrti
Naziv modula	Analiza i sinteza algoritama
Tip modula	Obavezni
Broj kreditnih bodova	4
Kontakt sati	Ukupno	Predavanja	Vježbe	Seminari	Konsultacije
	60	30	30	0	po potrebi
Samostalni rad (sati)	40
Obavezni prethodno položeni moduli	Uvod u programiranje
Modul relevantan za module	Strukture podataka i algoritmi; Projektovanje računarskih aplikacija
Nastavno osoblje
– Nastavnik nosilac modula	Doc. dr. Željko Jurić
– Ostali nastavnici	Doc. dr. Haris Gavranović
– Asistenti	Mr. Esmir Pilav; Adis Alihodžić

 

B. CILJEVI MODULA

Modul predstavlja uvodni kurs u tehnike analize i sinteze algoritama, kao i upoznavanje sa osnovnim algoritamskim tehnikama.

C. SPECIFIČNI ZADACI MODULA

Kroz navedeni modul studenti će kroz samostalan rad na laboratorijskim vježbama biti  usmjereni na razvoj i implementaciju osnovnih algoritamskih rješenja u programskom jeziku C++.

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; Koriste i primjenjuju standardne algoritamske tehnike;

E. SADRŽAJ NASTAVNOG PROCESA

Br.	Nastavna jedinica	Nastavni metod	Sati rada
			Kontakt	Samostalno
1.	Pojam algoritama. Iterativni i rekurzivni algoritmi	Usmeno izlaganje 2 Vježbe i zadaci 2	4	2
2.	Uvod u analizu algoritama. O i Q notacija.	– II –	4	3
3.	Diferentne jednačine koje se koriste za potrebe analize algoritama.	– II –	4	2
4.	Pojam izračunljivosti i algoritamske rješivosti. Algoritamski nerješivi problemi.	– II –	4	2
5.	Tehnike za sintezu algoritama. Konstrukcija indukcijom.	– II –	4	3
6.	Princip “podijeli i osvoji”.	– II –	4	3
7.	Elementarni algoritmi za sortiranje.	Usmeno izlaganje 2 Rad na računaru 2	4	3
8.	Brzi algoritmi za sortiranje. Shell sort. Merge Sort. Heap Sort. Quick Sort. Radix Sort	– II –	4	3
9.	Brzi algoritmi za pretraživanje. Heš tabele. Višestruko heširanje.	– II –	4	3
10.	Opća teorija rekurzivnih algoritama.	– II –	4	2
11.	Uklanjanje rekurzije. Ubrzavanje rekurzije.	– II –	4	3
12.	Dinamičko programiranje. Problem ranca i srodni problemi.	– II –	4	3
13.	Rekurzija sa pamćenjem (memoizacija) kao alternativa dinamičkom programiranju.	– II –	4	2
14.	Randomizacija i njena uloga u sintezi algoritama.	– II –	4	3
15.	Algoritmi Monte Carlo i Las Vegas tipa.	– II –	4	3

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)	40	25	< 55,00	5	F
Projektni zadaci (3 projekta)	30	15	55,00 – 64,99	6	E
Usmeni 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.   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.    M. R. Garey, D. S. Johnson, “Computers & Intractability – A Guide to the Theory of NP‑completeness”, W. H.   Freeman and Co, 1979.

3.    M. Vugdelija: “Dinamičko programiranje”, Društvo matematičara Srbije, Beograd, 1999.

4.    V. Aho, J. E. Hopcroft, J. D. Ulman: “Data Structures and Algorithms”, Addison-Wesley, 1983.

5.   D. E. Knuth: “The Art of Computer Programming, Volume 1: Fundamental Algorithms”, Addison-Wesley, 1968.