KTH

Skolan för datavetenskap och kommunikation

   
  arrow rigth

     
     
     
     
     
     
     
     
     
     

 

   
KTH / Nada / Utbildning / Teknologer / 2D1446

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.


 
Sidansvarig: Mikael Goldmann <migo@nada.kth.se>
Uppdaterad: 2004-05-14