Nada

Kursanalys för Komplexitetsteori, Läsåret 01/02

Författare: Mikael Goldmann, NADA

^ Upp till kurssidan.

Nedan följer en kursanalys av kursen Komplexitetsteori. I texten refereras till en enkät gjord med Ace i WWW. Enkäten har fyllts i av 19 personer, av de 28 som varit aktiva på kursen. Det finns en länk till enkätsvaren i slutet av detta dokument. Svaren tyder på att nästan alla deltagare är nöjda med nästan allt, och det är svårt att se att enkätresultaten föranleder några åtgärder förutom vissa små justeringar. Kursanalysen baseras också på synpunkter från kursnämnden som bestod av Mattias Amnefelt och Fredrik Niemelä.

Kursdata

Kurs 2D1446, Komplexitetsteori, 4p
Examination Inlämningsuppgifter
Kursen genomförd VT 2002
Föreläsningar 30 timmar (15 st)
KurslitteraturPapadimitriou: Computational Complexity
Antal studenter 30 (två avhopp)
Kursansvarig/föreläsare Mikael Goldmann

Sammanfattning

De studenter som svarat på enkäten är nöjda med vad de betraktar som en ganska svår kurs. Examinationsgraden är tillräcklig och studieresultaten goda.

Det finns inga problem som kräver stora förändringar, men en del detaljer kan justeras och förbättras: innehållet i vissa föreläsningar (se Undervisning nedan) och val av kursbok (se Kurslitteratur nedan).

Studenter

Studenterna går i huvudsak tredje eller fjärde året av sin utbildning. De 30 som registrerat sig är fördelade enligt

16 från D
2 från Matematisk-Datalogisk linje, SU
3 från F
4 utbytesstudenter
5 doktorander

Av dessa har 2 inte gjort några inlämningsuppgifter. I det ena fallet vet jag att studenten efter en dryg vecka bestämde sig för att kursen inte var något för honom. I det andra fallet vet jag inte orsaken till avhoppet, eller ens om studenten kommit på föreläsningar. Av de 28 som lämnat in någon inlämningsuppgift är 22 helt klara, en har fått förlängd tid och två kan komplettera.

Nyckeltal

Prestationsgrad och Examinationsgrad (2002-03-25): 79%.
Denna har räknats på de 28 som lämnat in någon uppgift. Om de tre som är nästan klara blir det kommer det att bli 89%, vilket kan betraktas som bra.

Mål

Kursens mål är att för att eleverna ska

Nytt för i år

Jag har försökt få en bättre blandning av svåra och lätta uppgifter och se till att svårighetsgraden inte stegras markant under kursens gång. Innehållet i kursen varierar från omgång till omgång beroende på vilka delar av komplexitetsteorin man fördjupar sig i under kursens senare delar. I år har även sista omgången hemtal redovisats muntligt.

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.

En synpunkt både på enkät och kursnämndsmöte var att några av föreläsningarna ägnades åt långa bevis av saker som inte kändes centrala i kursen. De föreläsningar jag tror var jobbigast är grafnåbarhet i coNL, bevisen av att primalitet är i NP, analysen av Miller-Rabins primalitetstest och eventuellt interaktiva bevis för permanenten av 0/1-matriser. Jag ska gå igenom de bevistunga föreläsningarna och se vad som är viktigt. Själv tycker jag dessa är viktiga, men en del kan säkert tas bort och annat motiveras tydligare.

På slutet behandlades kryptografi, komplexitet för parallella beräkningar och interaktiva bevis. Detta var kanske ett fördjupningsområde för mycket.

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.

Studenterna tycker examinationsformen är bra och flera säger spontant att tenta inte är något alternativ. Själv är jag övertygad om att detta är mycket bättre än att använda sig av tenta på den här kursen.

Det är inte alltid lätt att sätta rättvisa individuella betyg när examinationen inte garanterar att studenterna arbetar individuellt. Å andra sidan ger de muntliga presentationerna en bra känsla för hur väl den enskilde studenten tillgodogjort sig materialet. Jag har haft en klar känsla av att studenterna följt de regler för samarbete som fanns. En person tyckte att reglerna var svårtolkade.

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. Förra årets stegrades svårigheten från omgång till omgång. I år verkar svårighetsgraden varit jämnare även om sista omgången verkar lite svårare, dels för att nästan inga begrepp som behandlas i kursens slut känns igen från ADKn och dels för att tentaperioden närmat sig.

Exempel inlämningsuppgifter finns på kursens hemsida.

Kurslitteratur

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 det som behandlas inom kursen. Dess svaga sida är 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.

Boken får även godkänt av studenterna, men det finns en del kritik. Framför allt är det flera som tycker att en del "uppenbara" steg som utelämnas i bevisen inte är så uppenbara.

Jag kommer att överväga alternativ, men jag har ingen uppenbar kandidat till ny kursbok. Jag har diskuterat det med kursnämnden och vi kom fram till att en i och för sig bra bok av Michael Sipser inte är så lämplig eftersom dess upplägg kräver att kursen omarbetas på ett sätt som skulle ge den ett stort överlapp med Artificiella språk och syntaxanalys.

Studenternas arbetsbelastning

Jag har förstått att inlämningsuppgifterna varit ganska krävande. Trots att uppgifterna varit omfattande har examinationsgraden varit hög, och många har lämnat in mycket bra lösningar. På sista omgången inlämningsuppgifter märktes att en del lagt mer mindre tid och prioriterat andra kurser, antagligen delvis för att de redan då visste vilket betyg de skulle få med en rimlig arbetsinsats. Jag ser inget problem för den här kursen med det eftersom kursen avslutas med fördjupning i olika områden. Antagligen är detta ett tecken på att kursen dragit till sig "rätt" studenter, det vill säga de som både är intresserade av området och har kapaciteten att klara en svår kurs med behållning.

Förkunskaper

Förutom de formella förkunskapskraven är det till stor hjälp om man lyckats väl med sina matematikkurser.

Verkligt kursinnehåll

En logg som beskriver föreläsningarnas innehåll har lagts upp på nätet. Den återges här (på engelska).
  1. Introduction: Solving computational problems using bounded resources. Administration. 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.
     
  2. More on R and RE (and coRE). An example of an undecidable language. Encoding a TM as a string. Nondeterministic TMs.
     
  3. Recursive many-to-one reductions, RE-completeness, coRE. Universal TM. Halting language and Halting on empty string. The speed-up theorem. Definition of complexity classes: L, NL, P, NP, PSPACE, NPSPACE.
     
  4. Inclusions between classes (L, NL, P, NP, PSPACE, and EXP). Time and space hierarchies (halting in bounded time). NTIME vs SPACE, NSPACE vs TIME. Connection between SPACE and finding an s,t-path in a directed graph.
     
  5. More about the graph reachability problem. Savitch's theorem. The class coNL. Started on NL=coNL. Why is it non-trivial to solve non-reachability in NL?
     
  6. NL-algorithm for graph non-reachability. Definitions of "closed under reductions" and "complete problems". Logspace reductions and polytime reductions. Example: reduction of CLIQUE to SAT.
     
  7. NP-certificates and polynomially balanced relations. Circuit value is P-complete, Circuit satisfiability and 3SAT are NP-complete.
     
  8. coNP. Primality in (NP intersect coNP). Proof that Zp* is cyclic. Chinese remainder theorem.
     
  9. TMs with oracles. Finding the largest clique using a CLIQUE-oracle. FNP. Some PSAPCE-problems (Generalized Geography, QSAT).
     
  10. Proof that QSAT is PSPACE-complete. Probabilistic TMs. The Miller-Rabin primality test analyzed. The class RP.
     
  11. The classes RP, coRP, BPP, ZPP and their relations. Probabilistic test of multilinear polynomial (checking existence of bipartite matching). ZPP nd expected polynomial time.
     
  12. Approximability of NPO-problems. Examples: deterministic approximation of MAX3SAT, polynomial time approximation scheme for KNAPSACK. Quick overview of some lower bounds. Approximation preserving reductions: L-reductions.
     
  13. An overview of some connections between cryptography and complexity illustrated by notions of security, pseudo random generators, one-way functions, bit commitment, and zero-knowledge proofs.

  14.  
  15. Interactive proofs and the class IP. Examples: graph non-isomorphism, permanent of 0/1-matrices. Proof that #P is a subset of IP, and mentioned IP = PSPACE.

  16.  
  17. Parallel complexity classes and computation models. Overview of PRAM and examples of PRAM-algorithms for matrix product, reachability and summing elements of a list. The circuit classes NCk and ACk.

Kommande förändringar

Kursen kommer inte längre att ges varje år utan vartannat. Nästa gång ges den i period 4 våren 2004. Små förändringar kommer säkert att göras (se rubrikerna Undervisning och Kurslitteratur), men inget tyder på att någon stor förändring behövs.

Bilaga: Enkätsvar

Här har fritextsvaren tagits bort, bland annat eftersom de ibland ganska tydligt identifierar studenten som skrivit dem.

Bilaga: Kursbeskrivning (pdf)

^ Upp till kurssidan.


Sidansvarig: <migo@nada.kth.se>
Senast ändrad 22 april 2002
Tekniskt stöd: <webmaster@nada.kth.se>