UL/FRI/UNI-RI/APS2/Vaje/Pregled snovi

Analiza algoritmov

•Uvod

•Dokazovanje pravilnosti in ustavljivosti

•Poraba časa in prostora

•Asimptotična notacija

Navadne metode za notranje urejanje

•Problem urejanja s pomočjo operacije primerjave

•Navadno vstavljanje

•Navadno izbiranje

•Navadne zamenjave

Izboljšane metode za notranje urejanje

•Shellovo urejanje

•Urejanje s kopico

•Urejanje s porazdelitvami

•Rekurenčne relacije

•Iskanje k-tega elementa

Zunanje urejanje

•Navadno dvosmerno zlivanje

•Naravno uravnoteženo dvosmerno zlivanje

•Naravno uravnoteženo večsmerno zlivanje

•Polifazno zlivanje

Množenje matrik

•Množenje velikih števil

•Množenje matrik po metodi deli in vladaj

•Množenje matrik s Strassenovim algoritmom

•Uporaba rekurenčnih relacij (master theorem)

Diskretna Fourierjeva transformacija

•Predstavitve polinomov

•Primitivni koren enote

•Diskretna Fourierjeva transformacija

•Rekurzivni FFT algoritem

•Iterativni FFT algoritem

Največji pretok v omrežju

•Definicija problema

•Ford-Fulkersonov algoritem

Problem 0-1 nahrbtnika

•Definicija problema

•Algoritem po metodi dinamičnega programiranja

•Grafično reševanje

•Tabelarično reševanje

Linearno programiranje

•Uvod

•Simpleksni algoritem

Najkrajše poti v omrežju

•Uvod

•Bellman-Fordov algoritem

•Topološko urejanje

•Algoritem za iskanje najkrajših poti v acikličnem grafu

•Dijkstrov algoritem

•Posplošeni Bellman-Fordov algoritem

•Floyd-Warshallow algoritem