2D1446 Komplexitetsteori
Kursen ges läsåret 2003/2004 i period 4 med
Mikael Goldmann som kursansvarig.
Komplexitetsteorins syfte är att studera vad som kan beräknas
med hjälp av datorer. Det är oftast tämligen enkelt att visa
hurvida en
viss funktion kan beräknas med hjälp av en dator med oändligt
mycket tid och minne. Tyvärr har nu inte våra datorer oändligt
mycket resurser. Av denna anledning studerar man inom komplexitetsteorin
vad som kan beräknas
i rimlig tid eller med hjälp av rimligt mycket minne.
Eftersom datorer skiljer sig i prestanda ägnar sig komplexitetsteorin
åt teoretiska modeller av beräkningar. Tiden som beräkningen
av en funktion tar betraktas som en funktion av storleken på indata.
Med rimliga resurser menas ofta polynomiell tid eller minne, ibland
kan kraven vara striktare t.ex. logaritmiskt minne.
KTH har helt nyligen beslutat att avbryta och utvärdera försöket med
att ge betyg 6 i vissa kurser. Därför kommer betygsskalan VT 2004
att vara 3-5.
|
