KTH

Skolan för datavetenskap och kommunikation

     
  2D1446  

  Nyheter    
  KursPM med schema    
  Hederskodex>>    
  Uppgifter    
  Länkar    
  Utdelade papper    
  Kursenkät    
  Kursanalys arrow rigth  
  Tidigare år    
  Studiehandbok>>    

 

    

KTH / Nada / Utbildning / Teknologer / 2D1446

2D1446 Komplexitetsteori

Kursanalys

Kursanalysen för föregående omgång finns under "Tidigare år".

VT 2004

Författare: Mikael Goldmann

Kursdata

Kurs 2D1446, Komplexitetsteori, 4p
Examination Inlämningsuppgifter
Genomförd HT 2003
Föreläsningar 24 timmar (12 st)
KurslitteraturPapadimitrou: Complexity Theory
Antal studenter 37
Ansvarig/föreläsare Mikael Goldmann
Assistenter Fredrik Niemelä
Jakob Nordström

Sammanfattning

Studenter

D24
E1
F6
MD3
Utbyte2
Dokt1
Totalt37

Detta baserar sig på vilka som registrerat sig på kursen i LADOK, eller som genomgört någon del av kursen trots att de inte finns registrerade.

Tre studenter har meddelat att de hoppat av kursen och en student har fått barn och skjutit kursen på framtiden.

Nyckeltal

Prestationsgrad och Examinationsgrad (2004-06-17) är 62%.

Av 37 deltagare har 23 blivit helt klara.Bland de som inte är klara finns 3 som meddelat att de hoppat av kursen, och 5 som restar med mindre delar som de säkert kan komplettera om de vill. En person har kvar sina muntliga redovisningar och har för lite lösta uppgifter totalt, en har fått barn och hoppas komplettera senare. Resterande fem har gjort en eller ingen uppgiftsomgång och har antagligen hoppat av kursen utan att meddela det. Man kan nog hoppas att ca 5 till blir klara.

Mål

Kursens mål är att

  • ge en utförlig orientering om modern komplexitetsteori
för att eleverna ska
  • förstå begreppen komplexitetsklasser och fullständighetsproblem för sådana,
  • kunna bevisa påståenden inom komplexitetsteorin, t.ex. fullständighet hos ett problem,
  • kunna läsa (relativt enkla) forskningsartiklar inom området komplexitetsteori.

Nytt för i år

Justeringar av kursinnehållet har gjorts, huvudsakligen för att nya resultat visat att man kan avgöra primalitet i polynomisk tid. Detta var inte känt vid förra kursomgången och krävde mer eller mindre omfattande ändringar i några föreläsningar.

Verkligt kursinnehåll

En logg fördes under kursens gång över vad som gjordes på respektive föreläsning.

Lecture 1

Chapter 1, parts of chapters 2 and 3. Administration. Solving computational problems using bounded resources. Turing machines: definition and examples (palindromes). Definitions of computability, decidability and recursive enumerability. The classes R (recursive languages) and RE (recursively enumerable languages). Church's thesis.

Lecture 2

More from chapters 2 and 3, Multi-tape TMs. Encoding TM as a string. Universal TM. R, RE, coRE, R = (RE intersect coRE). Showed that there is a TM that enumerates L iff there is a TM that accepts L. Defined non-deterministic TM and what it means for it to accept input x in k steps. Showed the existence of undecidable problems and that the Halting language is in RE but not in R.

Lecture 3

Concluded chapters 2 and 3, parts of Chapter 7. RE-complete problems and man-one-reductions. Defined TIME(f(n)) and SPACE(f(n)) and corresponding for non-deterministic computation. Linear speed-up (and corresponding result for space). Defined the classes L, NL, coNL, P, NP, coNP, PSPACE, NPSPACE, EXP, and stated some inclusion results.

Lecture 4

More of Chapter 7. Time- and space-hierarchies. Thereom 7.4 and the connection between nondeterministic space and the reachability problem.

Lecture 5

Chapter 7. Savitch's theorem. PSPACE = NPSPACE. Defined logspace-reductions, NL-completeness and coNL-completeness. Reachability NL-complete and Non-reachability coNL-complete. NL = coNL (by showing that non-reacability is in NL).

Lecture 6

Chapter 8. Reductions and complete problems. What it means for a class to be closed under logspace-reductions. SAT and CLIQUE as examples of complete problems. A detailed reduction of CLIQUE to SAT.

Lecture 7

Chapters 8 and 9. NP-certificates and polynomially balanced relations. Circuit value is P-complete, Circuit satisfiability and 3SAT are NP-complete.

Lecture 8

Chapters 9 and 10 + notes. Proofs of NP-completeness for Three-partite matching, Exact cover, and Knapsack. Defined coNP and coNP-completeness. Example of problem in (NP intersect coNP) that is not known to be in P: given (g,p), decide if p is prime and g is generator of Zp*. (Notes, see below.)

Lecture 9

Chapters 9 and 10 + notes. Proof that Zp* is cyclic when p is prime. NP-function problems and NP-optimization problems. Oracle Turing machines. If we have a SAT-oracle we can find a satisfying assignment in polynomial time, and if we have an oracle for graph colorability then we can find an optimal coloring in polynomial time. The class FNP, reductions for FNP-problems, and FNP-completenes.

Lecture 10

Chapter 11 (11.1 and 11.2). Probabilistic Turing machines. The classes RP, coRP, ZPP, and BPP. ZPP = (RP intersect coRP). A in ZPP iff A can be decided in expected polynomial time. Error reduction for RP and coRP.

Lecture 11

Chapter 11 (11.1 and 11.2), and a handout (5 pages from Sipser's Introduction to the Theory of Computation). Error reduction for BPP. Chernoff bounds. Proof that equivialence Read-once brancing programs is in coRP.

Lecture 12

Chapter 19.1. PSPACE. PSPACE complete problems: Generalized geography, QSAT. Chapter 13 (pages 299-313). Approximation of NPO-problems. Approximation ratio and ε-approximation.

Lecture 13

More about approximation of NPO-problems. Approximation algorithm for Max3SAT and FPTAS for Knapsack. Non-approximability of general TSP. L-reductions (preserve approximability).

Lecture 14

Overview of some complexity classes: PP, parity-P, #P. Polynomial hierarchy (PH). Introduction to interactive proofs and the class IP. IP contains NP but also problems that are (probably) not in NP such as Graph Non-isomorphism. PSPACE contains IP (sketch of proof).

Lecture 15

Claimed that PSPACE=IP. Proved weaker result that P#P is contained in IP. This implies that IP contains coNP, and by a result of Toda that IP continains the polynomial hierarchy.

Undervisning

Undervisningen bygger på traditionella föreläsningar och inlämningsuppgifter. Eftersom gruppen är liten och studenterna motiverade blir det en stämning där det ställs frågor och ges synpunkter. Jag tycker att föreläsningar fungerar bra i den här kursen så länge deltagarna inte är rädda för att avbryta, fråga och kommentera. OH-bilder har använts ganska sparsamt till förmån för svarta tavlan.

Eftersom det fanns deltagare som inte förstod svenska särskilt väl hölls de flesta av föreläsningarna under kursens andra halva på engelska.

Examination

Kursen examineras med tre omgångar inlämningsuppgifter. Många av problemen är ganska svåra, och skulle inte kunna användas på en skriftlig tentamen. Svaren redovisas både skriftligt och muntligt.

Även om visst samarbete är tillåtet så ger de muntliga presentationerna en bra känsla för hur väl den enskilde studenten tillgodogjort sig materialet. Det har i några fall hänt att två studenter med likvärdiga skriftliga lösningar fått olika poäng då de klarat den muntliga delen mer eller mindre bra. Jag har haft en klar känsla av att studenterna följt de regler för samarbete som fanns.

Det är heller inte lätt att hitta en lagom svårighetsnivå på uppgifterna. Jag har försökt få en spridning så att varje omgång ska innehålla några lätta, några medelsvåra och en eller två riktigt svåra uppgifter. I år blev dock den sista omgången lite lättare än de två första.

Exempel inlämningsuppgifter finns på kursens hemsida.

Litteratur

Kursboken Complexity Theory av Papadimitriou har använts även tidigare år. Dess starka sidor är att den håller en lagom nivå och täcker i stort sett allt som behandlas inom kursen. Dess svaga sida är att den börjar få några år på nacken och att den innehåller en del förtretliga fel i satser och bevis. Oftast går det lätt att fixa till, men det kan ändå vara en rejäl stötesten för läsaren.

Jag kommer att överväga alternativ, men jag har ingen uppenbar kandidat till ny kursbok.

Studenternas arbetsbelastning

Tyvärr glömde jag att ha med frågor i enkäten som frågar efter arbetstid. Någon har påpekat att man går och tänkter på uppgifterna lite då och då och att det är svårt att säga hur lång tid det tar. Somliga anser uppgifterna ganska lätta medan andra tycker de är riktigt svåra. Däremot har ingen sagt att de är mycket tidskrävande.

Enkät

Enkäten har 2004-06-16 besvarats av 17 personer. Resultatet återges nedan. Av integritets- och utrymmesskäl har jag sammanfattat de svar som är skrivna som fri text. På de tre sista frågorna ser jag dock inget skäl att sammanfatta eftersom de svaren inte identifierar någon inblandad person.

  1. Upplever du kursen som lätt eller svår?

    1. 6% (1 st) Mycket lätt.  
    2. 6% (1 st) Lätt.  
    3. 18% (3 st) Medel.  
    4. 53% (9 st) Ganska svår.  
    5. 18% (3 st) Mycket svår.  

  2. Fick du i början av kursen klart för dig vad kursens mål var?

    1. 94% (16 st) Ja.  
    2. 6% (1 st) Tveksam.  
    3. 0% (0 st) Nej.  

    Om inte, vad hade du velat veta?

    Inga svar

  3. Tycker du att kursen är intressant och meningsfull?

    1. 71% (12 st) Ja, mycket.  
    2. 24% (4 st) Ja.  
    3. 6% (1 st) Neutral.  
    4. 0% (0 st) Inte särskilt.  
    5. 0% (0 st) Nej.  

  4. Vad tycker du om kursboken?

    1. 12% (2 st) Mycket bra.  
    2. 53% (9 st) Bra.  
    3. 12% (2 st) Hyfsad.  
    4. 6% (1 st) Mindre bra.  
    5. 0% (0 st) Dålig.  
    6. 18% (3 st) Har inte använt den.  

    Ev. kommentar om boken (ange både starka och svaga sidor -- och tala om vilket som är vilket):

    Styrkor: Intressant, engagerad, täcker mycket.
    ---
    Svagheter: Tryckfel, lite gammal, inte lätt att slå upp i utan måste läsas ganska sammanhängande, priset.
    ---
    Somliga finner den ganska lättläst, andra tycker den är svår.

  5. Hur stor del av föreläsningarna har du varit på?

    1. 0% (0 st) Mindre än 20%.  
    2. 6% (1 st) 20-40%.  
    3. 6% (1 st) 40-60%.  
    4. 18% (3 st) 60-80%.  
    5. 65% (11 st) Mer än 80%.  

  6. Många föreläsningar hölls på engelska. Hur var det jämfört med när föreläsningarna hölls på svenska?

    1. 0% (0 st) Bättre med engelska föreläsningar.  
    2. 82% (14 st) Spelar ingen roll.  
    3. 18% (3 st) Sämre med engelska föreläsningar.  
    4. 0% (0 st) Har inte deltagit.  

    Ev. kommentar om att föreläsa på engelska:

    De flesta tycker det går bra (förutsatt att föreläsaren kan engelska). Så länge deltagarna fortfarande får fråga på svenska så går det bra. Någon tycker det är självklart att man ska välja engelska om det finns deltagare som inte förstår svenska. Negativa kommentarer är att föreläsningarna blir lite sämre, att det sänker tempot lite, och att det blir svårare att hänga med.

  7. Vad tycker du om föreläsningarna pedagogiskt sett? (Förklaras stoffet bra? Talar och skriver läraren tydligt? Används stordia i lagom omfattning?)

    1. 65% (11 st) Mycket bra.  
    2. 24% (4 st) Bra.  
    3. 12% (2 st) Acceptabelt.  
    4. 0% (0 st) Mindre bra.  
    5. 0% (0 st) Dåligt.  
    6. 0% (0 st) Har inte deltagit.  

    Ev. kommentar om föreläsningar:

    Mest positiva omdömen. En person saknar "information om hur ett bevis ska skrivas" på inlämningsuppgifterna. Någon har också sagt att föreläsningarna låg på en väl hög nivå.

  8. Vad tycker du om examination med inlämningsuppgifter?

    1. 71% (12 st) Mycket bra.  
    2. 29% (5 st) Bra.  
    3. 0% (0 st) Acceptabelt.  
    4. 0% (0 st) Mindre bra.  
    5. 0% (0 st) Dåligt.  

    Ev. kommentar om inlämningsuppgifter:

    Ingen vill byta ut examinationsformen. En person tycker att uppgifterna var för lätta. Ett par personer uppfattar det som att bedömingen varit olika beroende på vem man redovisat för.

  9. Hur svår var första omgången med uppgifter på en tiogradig skala där 1 är mycket lätt och 10 är mycket svår?

    1. 0% (0 st) 1  
    2. 0% (0 st) 2  
    3. 0% (0 st) 3  
    4. 6% (1 st) 4  
    5. 6% (1 st) 5  
    6. 24% (4 st) 6  
    7. 24% (4 st) 7  
    8. 35% (6 st) 8  
    9. 0% (0 st) 9  
    10. 6% (1 st) 10  

  10. Hur svår var andra omgången med uppgifter?

    1. 0% (0 st) 1  
    2. 0% (0 st) 2  
    3. 6% (1 st) 3  
    4. 0% (0 st) 4  
    5. 6% (1 st) 5  
    6. 6% (1 st) 6  
    7. 41% (7 st) 7  
    8. 41% (7 st) 8  
    9. 0% (0 st) 9  
    10. 0% (0 st) 10  

  11. Hur svår var tredje omgången med uppgifter?

    1. 0% (0 st) 1  
    2. 0% (0 st) 2  
    3. 6% (1 st) 3  
    4. 0% (0 st) 4  
    5. 6% (1 st) 5  
    6. 24% (4 st) 6  
    7. 24% (4 st) 7  
    8. 24% (4 st) 8  
    9. 18% (3 st) 9  
    10. 0% (0 st) 10  

  12. Vad borde man ändra på i kursen (varför är det inte bra och hur blir det bättre)?

    prata ihop sig innan om vilken nivå man skall hålla på redovisningarna
    ---
    Det vore bra med föreläsningsanteckningar av något slag. Det behöver inte alls vara så omfattande men om man missat en föreläsning är det bra att åtminstone veta vad man ska läsa i boken.
    ---
    Jag kommer inte på något.
    ---
    Kursboken? Kan vara svårt att hitta någon bättre dock.

    Mer detaljer i PMet om vilka avsnitt som tas upp på varje föreläsning, så att man kan läsa igenom dem i förväg. (Eller kanske mer realistiskt: så man kan läsa igenom dem efteråt, eller istället för föreläsningen).
    ---
    Det tog onödigt lång tid mellan upgift ett och två.

  13. Vad borde man låta vara som det är i kursen?

    Systemet med inlämningsuppgifter
    ---
    Allt.
    ---
    Examinationssystemet är bra. Eftersom kursen bygger vidare på tidigare kurser som har traditionell tenta så är det inte motiverat att övergå till tenta i denna kurs.
    ---
    Inlupparna.
    ---
    Antal föreläsningar var lagom.
    Ha kvar inlämningsuppgifter som eximinationsform.

  14. Övriga kommentarer om kursen:

    Mycket bra kurs!
    ---
    jag har bara löst tre av de sista talen ännu, så ta svårighetsangivelsen med en nypa salt. komplex är kul. migo är mycket bra. systemet med inlämningsuppgifter som redovisas muntligt är bra, om än lite problematisk ur rättvisesynpunkt.
    ---
    Mycket bra kurs.
    ---
    Ganska intressant men absolut den svåraste kursen jag läst hittills på KTH.
    ---
    Mycket intressant ämne som också genomförs i en mycket bra och inte allt för svår kurs.
    ---
    Toppenkurs!
    ---
    En bra kurs
    ---
    En av NADA:s bästa kurser!

Slutsatser och kommande förändringar

Givet enkätsvaren finns det några saker att fundera över

Bör man byta kursbok?

Om man kan hitta en bra bok som är väsentligt nyare kan det vara bra att göra det. Vi får se vilka böcker som kan dyka upp till nästa kursomgång.

Ska man föreläsa på engelska?

Vi provade för att försöka tillmötesgå utbytesstudenterna. Överenskommelsen var att om någon önskade föreläsningar på svenska så skulle de hållas på svenska eftersom det är det språk kursen officiellt ges på. Hur mycket extra arbete detta innebär beror på den enskilda kursen och den enskilde föreläsaren. Jag kommer antagligen att fortsätta att göra så.

Hur ser man till att alla bedöms lika?

Ett av förslagen i enkäten är att man (jag och assistenterna) ska "prata ihop sig innan om vilken nivå man skall hålla på redovisningarna". Det har vi också försökt att göra. Vi har diskuterat de skriftliga lösningarna och i viss mån vad som ska ingå i den muntliga redovisningen.

För att göra det mer rättvist och dessutom tydligare så bör lärare och assistenter komma fram till en gemensam syn på den muntliga redovisningen (vilket vi nog ändå hade i ganska stor utsträckning) och dessutom eperimentera med att kräva att studenterna redovisar för olika personer under kursens gång.

Ska man dela ut föreläsningsanteckningar?

Det finns inga färdiga OH-bilder eller skrivna anteckningar i Word eller LaTeX att dela ut och det är ett ganska omfattande arbete att göra sådana. Efter föreläsningarna har jag på webbsidan för nyheter sammanfattat föreläsningen på några rader vilket ett par studenter kanske inte upptäckt.

Det kan vara bra att prova att studenterna turas om att skriva föreläsningsanteckningar för föreläsningarna. Dessa kan sedan delas ut till alla och skulle kunna ge poäng vid examination.


 
Sidansvarig: Mikael Goldmann <migo@nada.kth.se>
Uppdaterad: 2004-06-24