Teorija složenosti algoritama


Semestar: 8
ECTS: 5
Status: VP
Fond: 3+1+0
Klinički: Ne
Str.umj.: Ne
Duplikat: Ne
ECTS katalog

Ishodi učenja:

Nakon što student položi ovaj ispit, biće u mogućnosti da: 1. Konstruiše algoritme za množenje velikih brojeva (Karatsubin, Tomov,Šenhage-Štrasenov,...). 2. Razvije algoritme bazirane na Štrasenovom algoritmu za množenje matrica (trougao u grafu, refleksivno tranzitivno zatvorenje grafa,...). 3. Kategoriše zadatke prema klasama složenosti (P, NP, PSPACE, EXPTIME,...). 4. Objasni PCP teoremu. 5. Razvije algoritme za faktorizaciju velikih brojeva (npr. koristeći eliptičke krive). 6. Analizira zadatke i razvija „dobre“ algoritme za njih (npr. bliske donjoj granici složenosti posmatranog zadatka ili aproksimativne ako je zadatak NP-kompletan).

Prikaži još

Angažovano osoblje

Ime Predavanja Vježbe Laboratorija
Mosurović Milenko3x1
24B+3S


Bulatović Luka
1x1
24B+3S