Nada

Kursanalys för Komplexitet, Läsåret 96/97

Författare: Mikael Goldmann, NADA

^ Upp till kurssidan VT-97.

Nedan följer en kursanalys av kursen i komplexitetsteori för Matte-data-linjens studenter. I texten refereras till en enkät gjord med ACE i WWW. Enkäten har hittills fyllts i av 14 personer (ca 50% av eleverna).

En elev som gick en 2p-variant av kursen 1995 blev i år godkänd på den kursen. Han har tagits bort ur statistiken.

Kursdata

Kurs: Komplexitetsteori (SU), KPLX, 4p
Examination: Tenta (4p)
Kursen genomfördes VT 1997
Föreläsningar: 36 timmar (18 st)
Övningar: 18 timmar (9 st)
Kurslitteratur: Introduction to algorithms (Manber) + kursbunt

Antal elever: 27 (exkl student som fick G på 2p-kurs)
Prestations- och examinationsgrad efter ordinarie tenta: 56%
Prestations- och examinationsgrad efter första omtentan: 85%

Kursansvarig: Mikael Goldmann
Övningsassist: Mats Näslund (som har haft den enda övningsgruppen)
Mikael höll 14 föreläsningar, Mats höll två (pga sjukdom) och Johan Håstad höll två (pga konferens). Mats höll sju av övningarna och Mikael och Christer Berg höll varsin.

Mål

Kursen handlar om hur man undersöker vilka problem som kan lösas (i rimlig tid) med datorns hjälp, vilka som tar orimligt lång tid och vilka som inte kan lösas med en dator över huvud taget.

Syftet är att eleven ska

Det är alltid ett hopp mellan "känna till" (passiv kunskap) och "kunna använda"/"kunna visa" (aktiv kunskap). För att få VG måste man i stort sett uppnå samtliga mål, men för att att bli godkänd på kursen är det inte nödvändigt. För G krävs mindre "aktiv kunskap", men för att klara tentans andra del måste man ändå visa att man klarar av att lösa problem någorlunda inom något delområde.

Förutom att kursen går igenom flera viktiga begrepp, så tror jag att en del av nyttan med den är att man får träna sig i att tillämpa matematik och logik för att bevisa saker om problem och algoritmer. Det är bra att se att kunskaper från en kurs kan tillämpas i en annan, och dessutom hoppas jag att de får en "kick" av att själva lösa problem.

Nytt för i år

Förra året gavs tre inlämningsuppgifter som var frivilliga, men gav bonus på tentan. Uppgifterna skulle lösas individuellt och redovisades skriftligt (tredje uppgiften redovisades även muntligt).

I år har jag istället gett fyra omgångar med "hemtal". Uppgifterna har varit fler, och i genomsnitt enklare än förra året. Dessutom har det varit tillåtet att arbeta i grupp förutsatt att man lämnar in en gemensam lösning. Talen redovisades på övningarna genom att en slumpvis vald elev fick komma fram och presentera gruppens lösning. Lösningarna samlades in och snabbrättades. Beroende på hur väl man löst talen fick man upp till fem bonuspoäng på tentan.

Sammanfattning

Det mesta har flutit bra, och de flesta har klarat kursen. Betydligt fler har klarat tentan i år utan att behöva ta till komplettering. Det är svårt att veta vad det beror på. Eftersom det bara rör sig om 25-30 studenter kan variationerna vara stora från år till år. I år hade jag dessutom skalat bort en del material och försökt få bättre spridning på tentafrågornas svårighetsgrad. För övrigt tycker jag efter att ha provat i tre år att kompletteringar fungerar dåligt på den här kursen. Jag måste antingen hitta på ett nytt sätt att låta folk komplettera (jag har provat med inlämningsuppgift och "minitenta"), eller också får de som kör tentan med endast något enstaka poäng vänta till omtentan.

Det har i år varit en viss förskjutning från komplexitet till algoritmer. Framför allt har betydligt färre komplexitetsteoretiska begrepp berörts i år. Istället har jag koncentrerat mig på två mycket centrala begrepp: oavgörbarhet och NP-fullständiga problem. Att döma av tentaresultaten har "medianeleven" förstått dessa två begrepp bättre i år än förra året.

Hemtalen fungerade bättre än inlämningsuppgifterna. Att tillåta öppet samarbete känns ärligare, och dessutom tror jag att "grupparbete" har varit ett stimulerande sätt att lära sig olika begrepp i kursen. En annan fördel är förstås att man får färre lösningar att rätta (en per grupp istället för en per student). Med den här sortens system finns det säkert alltid några som åker snålskjuts på andras arbete, men en person som inte lärt sig något kommer knappast att klara tentan trots fem bonuspoäng. De flesta tyckte att årets system var bra, och jag tänker fortsätta att använda det nästa år.

Eftersom första omtentan ligger mindre än två månader efter ordinarietentan väljer många att inte gå upp på ordinarietentan. Det var bara 19 personer som skrev ordinarietentan (varav 12 fick G och tre fick VG). Omtentan skrevs av nio studenter varav sex fick G, och ytterligare två fick G efter komplettering.

Eftersom tentan är enda examinationen (i år) så är examinationsgrad och prestationsgrad samma sak på den här kursen. I dagsläget är den 85% (om vi räknar bort eleven som blev godkänd på 2p-varianten), och det tycker jag är tillfredställande.

Undervisning

Föreläsningarna har varit välbesökta, och de som svarat på enkäten har varit nöjda (samtliga har svarat "bra" eller "mycket bra"). Den kritik som finns är att förelsäningsanteckningarna ofta inte fanns tillgängliga förrän i efterskott, att OH-bilder automatiskt driver upp tempot och att jag pratar för fort för studenter som inte har svenska som modersmål. Förhoppningsvis kan alla tre problemen avhjälpas enkelt. Tempot sjunker förmodligen om jag använder mer tavla och mindre OH.

Övningarna har fått mer skiftande omdöme. Jag tror det finns flera orsaker till det, bl a tidpunkt, sal och innehåll.

Övningarna låg mellan 15 och 17 på torsdagseftermiddagar, direkt efter föreläsningen. Vid den tiden på dan var nog flera elever ganska "möra". Dessutom var de flesta övningarna förlagda till L11, som inte är en idealisk sal: tavlan sitter på en jalusivägg med många skarvar, det står pelare mitt i salen, och slutligen så är takljuset gemensamt med angränsande sal vilket ställer till problem när man vill visa diabilder eller film i den ena salen!

Övningarna bestod kanske i alltför stor utsträckning av tavelräkning av ibland väl svåra tal (mitt fel, inte Mats). Nästa år vill jag göra övningar där eleverna blir mer aktiva.

Examination

Kursen examineras med en tenta som består av en "teoridel" (ca 20p) och en "problemdel" (fyra tal, totalt ca 20p). För att få G krävs minst 15 poäng totalt och att de två bästa lösningarna på proböemdelen tillsammans ger minst fem poäng. De bonuspoäng man fått på hemtalen läggs till totala poängsumman, men räknas inte in i tentans problemdel.

Teoridelen är tänkt att kontrollera centrala begrepp och algoritmer (ungefär "känna till" i målen), medan problemdelen mer handlar om problemlösning och tillämpning av stoffet i kursen ("kunna använda" och "kunna visa")

Kurslitteratur

Kursboken, "Introduction to Algorithms" av Udi Manber, får lite blandade omdömen, även om få tycker att den är dålig. Det som jag själv tycker talar för boken är att den förklarar det mesta ganska väl och att det i varje kapitel finns ett stort antal övningsuppgifter, och att det finns ett kapitel med lösningar till mång av uppgifterna. Nackdelen är att den inte på ett bra sätt tar upp hashing och balanserade träd. Jag funderar på att prova med en annan kursbok nästa år.

Eftersom kursboken inte tar upp turingmaskiner och oavgörbarhet har jag delat ut delar av ett kompendium som Johan Håstad skrivit och ett kapitel ur boken "Algorithmics, the spirit of computing" av David Harel. Johans kompendium skrevs egentligen för en forskarkurs, och kan vara lite hårdsmält. Harels bok är inte lika svårläst, men däremot lite för vag. Meningen var att de skulle komplettera varandra. Av enkätsvaren att döma är detta inte någon idealisk lösning, men jag vill inte pracka på studenterns två böcker i fyrahundrakronorsklassen. Eventuellt får jag skriva ett eget kompendium om oavgörbarhet.

Studenternas arbetsbelastning

Ingen ordentlig tidsstudie har gjorts. Vid redovisningen av ett av de fyra hemtalen bad jag dem uppskatta hur mycket tid de ägnat åt den aktuella hemtalsomgången, och svaren låg på mellan sju och tio timmar.

De som läser enligt "planen" läser en kurs parallellt med komplexitetsteorin (det varierar vilken kurs). Eftersom 10 av 14 säger sig ägna mindre än 50% (4 säger 15-30%) av sin studietid åt komplexitetsteorin så är den knappast för arbetskrävande.

Förkunskaper

De förkunskaper som formellt krävs är att man läst kombinatorik- och logikkursen och att man har minst 60 p från MD-linjens första två år. Speciellt behöver man känna till ett antal grundläggande algoritmer och datastrukturer som tas upp i de två-tre första datalogikurserna (nuvarande da1, oop1 och oop2). Dessutom bör man kunna utföra och förstå enklare logiska och matematiska resonemang och bevis.

Låt mig börja med att säga att alla utom en av de som besvarat enkäten ansåg att de hade tillräckliga förkunskaper. En student ansåg sig ha för dåliga förkunskaper om datastrukturer och grundläggande algoritmer. Studenten menade att man haft fullt upp med att lära sig programmeringsspråk, paradigm och operativsystem under de inledande kurserna.

Mitt eget intryck är att studenterna kan väldigt olika saker, och att de kan dem väldigt olika bra. En förklaring som framfördes av en student förra året är att mycket gås igenom under de första kurserna, men endast en liten delmängd är väsentlig för att klara tentan. Medianstudenten verkar ändå ha ett visst grepp om enklare algoritmer och datastruklturer, och även ett hum om deras komplexitet/effektivitet.

Verkligt kursinnehåll

Vi har i stort sett hållit oss till detaljschemat för kursen.

Förändringar till nästa år

Från och med nästa år är kursen på fem poäng. I samband med det byter den namn till "Algoritmer och komplextet" eftersom detta bättre avspeglar kursens innehåll. Tentan kommer att fortsätta att ge 4 poäng, men det tillkommer ett "labmoment" på 1 poäng. En av fördelarna med detta system är att de som gick kursen 1996 och 1997 kan skriva samma tentor som årets kursomgång.

Det tillkommer fyra övningar nästa år som är avsedda speciellt för hemtalsredovisningar.

Jag har inte slutgiltigt bestämt vad "labmomentet" ska innehålla, och funderar på olika alternativ för praktiskt respektive teoretiskt lagda studenter. En mer praktisk uppgift kan vara att implementera och testa några icketriviala algoritmer eller datastrukturer, till exempel snabb fourriertransform, universell hashing eller rödsvarta träd. En teoretisk uppgift kan vara att studera en algoritm eller ett begrepp som ligger utanför kursen, eller att lösa ett mer komplicerat problem i form av en inlämningsuppgift. I samtliga fall redovisas resultaten dels skriftligt och dels muntligt inför lärare och elever. Eventuellt kan man tänka sig att dela upp gruppen i halvklass eller tredjedelar vid redovisningarna.

Övningarna kan användas bättre. Framför allt behöver man aktivera studenterna på övningarna. Jag tror att man kan prova att varva exempel med att studenterna löser problem på egen hand med övningsassistenten som handledare.

Jag tänker ockå fundera en del över tentans uppbyggnad och poängsättningen. Att det räcker med 1/3 av maxpoängen för att bli godkänd kan göra att tentan verkar bedrägligt enkel, speciellt med tanke på att man kan samla ihop till fem bonuspoäng genom att göra hemtalen.

Eventuellt kommer jag att byta kursbok till nästa år. I så fall blir det "Introduction to algorithms" av Cormen, Leiserson och Rivest.

Bilaga: Enkätsvar

Bilaga: Kursbeskrivning

Bilaga: Tentalydelse

^ Upp till kurssidan VT-97.


Sidansvarig: <migo@nada.kth.se>
Senast ändrad 27 juni 1997
Tekniskt stöd: <webmaster@nada.kth.se>