Algoritmer och komplexitet, påbyggnadskurs, 5 poäng
(NA4110)

(Algorithms and Complexity, advanced course, 5 credits)


Kursplanen är fastställd av matematisk-naturvetenskapliga fakultetsnämnden 2000-05-24 och ändrad av naturvetenskapliga fakultetsnämnden 2003-10-22.

Placering i utbildningen och förkunskapskrav

För tillträde till kursen krävs kunskaper motsvarande Datalogi grundkurs II, 10 poäng (NA2030), samt matematik: Kombinatorik, påbyggnadskurs, 5 poäng (MA3200) och matematisk statistik: Sannolikhetsteori I, grundkurs, 5 poäng (MS1050).

Mål

Kursens mål är att
  • ge grundlig förmåga att utveckla algoritmer med datastrukturer och analysera dem med avseende på korrekthet och effektivitet,
  • ge orientering om komplexitetsteori
    för att studenterna ska
  • kunna konstruera datorprogram som effektivt utnyttjar datorresurser,
  • inse att det finns problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.
    
    

    Innehåll

    Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering. Algoritmanalys. Probabilistiska algoritmer. Approximation. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri. Implementation av algoritmer.
    Datastrukturer: Repetition av hashtabeller och heapar; balanserade träd, skipplistor, bloomfilter. Implementation av datastrukturer.
    Beräkningsbarhet och komplexitet: Reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid), NP (ickedeterministisk polynomisk tid) och NC (effektivt parallelliserbara problem). NP-fullständiga problem, oavgörbara problem.
    
    

    Undervisning

    Undervisningen består av föreläsningar, övningar och laborationer. Deltagande i datorlaborationer är obligatoriskt. Annan obligatorisk undervisning kan också förekomma. Om särskilda skäl föreligger kan examinator, efter samråd med kursansvarig lärare, medge den studerande befrielse från skyldigheten att delta i vissa obligatoriska moment.
    
    

    Examination

    Examinationen utgörs av tentamen, hemuppgifter och datorlaborationer.
    Studerande som godkänts på tentamen får ej undergå förnyad tentamen för högre betyg. Studerande som underkänts i ordinarie tentamen har rätt att delta vid ytterligare tentamenstillfällen. Studerande som underkänts på tentamen två gånger har rätt att begära att annan lärare än den kursansvarige utses för att bestämma betyg på kursen. Framställan härom ska göras till institutionsstyrelsen.
    Som betyg på kursen används något av uttrycken underkänd, godkänd eller väl godkänd.
    
    

    Litteratur

    Kurslitteratur fastställs av institutionsstyrelsen. Aktuell litteratur enligt KTHs studiehandbok, finns här.
    
    

    Kursinformation (om sådan finns tillgänglig)

    Här!
    
    
    ^ Upp till kursplaner; innehållsförteckning.


    Senast ändrad 04-07-07 <svl-su@nada.kth.se>