Nada

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

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 Eval i WWW. Enkäten har fyllts i av 26 personer, vilket är ganska många av de 34 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.

Kursdata

Kurs 2D1446, Komplexitetsteori, 4p
Examination Inlämningsuppgifter
Kursen genomförd VT 2001
Föreläsningar 30 timmar (15 st)
KurslitteraturPapadimitriou: Computational Complexity
Antal studenter 38
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äcklitg. Studenterna har dessutom varit mycket duktiga, vilket resulterat i höga, och välförtjänta, betyg.

Studenter

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

24 från D
7 från Matematisk-Datalogisk linje, SU
2 från F
1 international masters student
4 doktorander

Av dessa har fyra inte gjort några inlämningsuppgifter. I ett av fallen berodde det på att studenten läst en liknande kurs utomlands och tyckte att överlappet var för stort, medan jag inte vet anledningen i de tre övriga fallen. Av de 34 som lämnat in någon inlämningsuppgift är 31 helt klara, och två är nästan klara.

Nyckeltal

Totalt har 38 studenter registrerat sig på kursen. Av dessa hade fyra inte lämnat in någon inlämningsuppgift. Siffran inom parentes är resultatet om man räknar bort dessa fyra.

Prestationsgrad och Examinationsgrad (2001-04-17): 82% (91%).

Mål

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

Nytt för i år

Kursen gick senast våren 1999. I år var det ny föreläsare, och betyg 6 infördes (tidigare var 5 högsta betyg). I övrigt har inga större förändringar gjorts, men 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.

Undervisning

Undervisningen består av traditionella föreläsningar. Eftersom gruppen är liten, och studenterna motiverade går det att få 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.

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.

Det är inte alltid så lätt att sätta individuella betyg när examinationen inte garanterar att studenterna arbetar individuellt. Å andra sidan ger de muntliga presentationerna en viss känsla för hur väl den enskilde studenten tillgodogjort sig materialet.

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 stegrades svårighetenfrån omgång till omgång, vilket inte var meningen från början. Jag vet att flera studenter fann sista omgången mycket svår, och trots detta var 6 det vanligaste betyget på kursen. Det kan dels bero på att studenter som på de flesta kurser har ganska lätt för sig här fick slita en del för att göra ett bra resultat, och det kan också bero på att uppgifterna var så svåra att uppgifterna i praktiken kom att lösas i större grupper än det var tänkt.

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. Jag kommer att överväga alternativ, men jag har ingen uppenbar kandidat till ny kursbok.

Boken får även godkänt av studenterna, men det finns en del kritik som framgår av enkäten. Somliga anser boken vara svårläst medan andra vill ha en mer rigorös text. Tyvärr tror jag det kan vara svårt att tillgodose båda önskemålen.

Studenternas arbetsbelastning

Jag har förstått att inlämningsuppgifterna varit ganska krävande. Det är i och för sig meningen, men nästa år kommer jag att ha färre frågor per omgång. Trots att uppgifterna varit omfattande har examinationsgraden varit hög, och många har lämnat in mycket bra lösningar. 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 av en ganska svår kurs.

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

Vi har i stort sett hållit oss till föreläsningsplaneringen i kursbeskrivningen (se bilaga). Fördjupningen handlade om interaktiva bevis. Följande kapitel i kursboken har ingått: 1-3, 4 (endast terminologi och definitioner), 7-10, 11.1, 11.2, 12.2 (ineraktiva bevis), 13 (översiktligt), delar av 17, 18.1, 19.1, 19.2.

De mest centrala begreppen i kursen är komplexitetsklasser (speciellt L, NL, P, NP, R, BPP, PSPACE och IP) och deras relationer till varandra, fullständighet, samt reduktioner. Därutöver ska man kunna förstå och genomföra matematiska resonemang inom området.

Det finns ett visst, avsiktligt, överlapp med kurserna Algoritmer datastrukturer och komplexitet, respektive Algoritmer och komplexitet, där beräkninsbarhet, NP och NP-fullständighet tidigare behandlats. Detta repeteras i den här kursen. Vi har i år behandlat en algoritm för primalitetstestning, vilket ibland förekommer även på kurserna Kryptografins grunder och Avancerade algoritmer.

Kommande förändringar

Utöver eventuellt byte av kurslitteratur och en minskning av antalet uppgifter kommer kursen inte att förändras nämnvärt till nästa omgång.

Exempel inlämningsuppgifter finns på kursens hemsida.

Bilaga: Enkätsvar

Bilaga: Kursbeskrivning (pdf)

^ Upp till kurssidan.


Sidansvarig: <migo@nada.kth.se>
Senast ändrad 23 maj 2001
Tekniskt stöd: <webmaster@nada.kth.se>