TEORIJA SLOŽENOSTI ALGORITAMA

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).