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

Domaci i drugi kolokvijum

Nastava i kolokvijum

Kolokvijum 12.12.

Prijava na DL anketa

Predavanja - 05.10.2023 18:11

Nastava

Materijali, organizacija vježbi

Materijali sa vjezbi