TEORIJA SLOŽENOSTI ALGORITAMA


Semestar: 2
ECTS: 5
Status: Obavezan
Fond: 3+1+0
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).

Angažovano osoblje

Ime Predavanja Vježbe Laboratorija
ALEKSANDAR PLAMENAC1x1
1S
MILENKO MOSUROVIĆ3x1
1S

Rezultati i predlog ocjena

Rezultati-zavrsni ispit

Nastava2

Nastava

Vježbe

Rezultati

Materijali sa vjezbi