Nada

Kursanalys för Algoritmer och komplexitet, Läsåret 99/00

Författare: Mikael Goldmann, NADA

^ Upp till kurssidan.

Nedan följer en kursanalys av kursen i algoritmer och komplexitet för Matte-data-linjens studenter samt för fristående kurs. I texten refereras till en enkät gjord med ACE i WWW. Enkäten har hittills fyllts i av 16 personer.

Kursdata

Kurs Algoritmer och komplexitet (SU), ALKO, 5p
Examination Tenta (4p), Lab (1p)
Kursen genomförd VT 2000
Föreläsningar 36 timmar (18 st)
Övningar 26 timmar (13 st)
Labb 16 timmar
Kurslitteratur Introduction to algorithms (Cormen--Leiserson--Rivest) + kursbunt
Antal studenter 41 (varav 4 ej gjort något utöver att registrera sig i res)
Kursansvarig Mikael Goldmann, som hållit föreläsningarna 17 av föreläsningarna. En föreläsning har hållits av Henrik Eriksson.
Övningsassist Jonas Holmerin (som har haft den enda övningsgruppen)

Sammanfattning

Prestationsgraden är något högre än förra året, vilket förmodligen beror på variationer som inte är direkt knutna till denna kurs. I övrigt tycks kursen ha fungerat väl. Både prestations- och examinationsgrad är dock fortfarande lägre än man skulle önska. De som svarat på enkäten är nöjda eller mycket nöjda med det mesta, och jag ser inte några skäl till radikala förändringar. Från och med nästa år samläses denna kurs med motsvarande kurs på KTHs D-linje.

Nyckeltal

Totalt har 41 studenter registrerat sig genom att köra res. Av dessa hade tre sedan tidigare klarat labbmomentet. De som inte haft något moment godkänt sedan tidigare kallas förstagångsstudenter. Fyra av förstagångsstudenterna har hoppat av (inte gjort något utöver att anmäla sig i res). Dessa är inte medräknade i statistiken nedan. Kursen har också följts av en doktorand som också är klar med alla moment. Hon är inte heller medtagen i statistiken nedan.

För förstagångsstudenterna (33 st, exklusive doktoranden och de avhoppade) gällde 2000-06-08 följande:

22 har klarat labb-momentet.
25 har klarat tentan (varav 18 är klara med hela kursen).

Prestationsgrad 2000-04-08: 56%
Prestationsgrad 2000-06-08: 74%
Examinationsgrad 2000-06-08: 55%

Samtliga tre studenter som sedan tidigare är godkända på labbmomentet har klarat tentan och är därmed godkända på kursen.

Mål

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

Syftet är att studenten ska

Det är ett hopp mellan "känna till" (passiv kunskap) och "kunna använda"/"kunna visa" (aktiv kunskap). För att få VG måste man uppnå de flesta målen, men för att att bli godkänd på kursen är det inte nödvändigt. För G krävs mindre "aktiv kunskap".

Förutom att kursen går igenom flera viktiga begrepp, är 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

Tidigare litteratur om oavgörbarhet ersattes med ett utdrag ur en bok av Michael Sipser. Reaktionerna var blandade, även om jag själv tycker att det ger en bättre balans mellan intuition och formella resonemang än tidigare material. Jag tror att kritiken delvis bottnar i att "oavgörbarhet" upplevs som abstrakt och svårt. I övrigt är det bara små ändringar av bonussystemet som skiljer årets kurs från förra årets. Ändringarna har varit till det bättre, men jag (och enstaka studenter) tycker fortfarande att framför allt de "teoretiska" poängen på labbarna är väl lättförtjänta, men att avgöra om förändringar behövs överlåts till Viggo Kann som är kursansvarig för nästa omgång.

Undervisning

Föreläsningarna har varit ganska välbesökta, och de som svarat på enkäten har varit nöjda (Nästan alla som deltagit har svarat "bra" eller "mycket bra"). Tyvärr var det betydligt färre på föreläsningarna just den vecka som oavgörbarhet behandlades, och detta brukar upplevas som svårt.
Övningarna får lite blandade omdömen, vilket beror på att Jonas har mindre undervisningsvana än Staffan Ulfberg som var övningsassistent förra året. Övningarna kommer säkerligen att bli mer polerade nästa år pga mer erfarenhet.

Inlämningsuppgifter

Omgångar med frivilliga inlämningsuppgifter har delats ut. Vardera omgången har poängsats med 0 till 6 poäng. Korrekt lösta uppgifter svarar mot tal på tentan. Dessa tentatal är automatiskt godkända om man är godkänd på motsvarande inlämningsuppgift. Delpoäng på inlämningsuppgifter räknas som delpoäng på motsvarande uppgifter på tentan.

Inlämningsuppgifterna har redovisats skriftligt och muntligt. Den muntliga redovisningen har fungerat så att studenten bokar en redovisningstid hos Mikael eller Jonas. Den muntliga redovisningen tar inte så mycket extra tid eftersom man kan använda betydligt mindre tid för rättning av skriftliga lösningar. Studenten får möjlighet att klargöra detaljer och visa att han/hon förstår den inlämnade lösningen, och det ger även viss träning i muntlig framställning. Framförandet bedöms dock inte, utan endast innehållet.

Uppgifterna är tänkta att lösas individuellt. Visst samarbete har säkert förekommit, men om identiska lösningar lämnats in av flera personer blir det poängavdrag (detta har inte inträffat i år). Tyvärr verkar det vara svårt att få studenterna att ta till sig att uppgifterna ska lösas individuellt, förmodligen därför att de är vana från tidigare kurser att samarbete är tillåtet.

Examination

Kursen examineras med labbuppgift och med en tenta. Tentan består av en "teoridel" (20p) och en "problemdel" (30p). För att få G krävs minst 25 poäng totalt (inklusive ev bonuspoäng) varav minst 10 poäng på problemdelen (inklusive poängen på de uppgifter man klarat via inlämningsuppgifterna). Vid omtentan lättades det på det senare kravet, och detta krav försvinner troligen nästa år, eftersom det inte förekommer i ADK-kursen (se nedan).

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 Cormen, Leiserson och Rivest, får huvudsakligen positiva omdömen. Fördelen med boken är att den mer än väl täcker kursen förutom oavgörbarhet, och att man lätt kan välja och vraka bland ämnen att fördjupa sig i, vilket är bra till laborationsuppgiften.

Eftersom kursboken inte tar upp turingmaskiner och oavgörbarhet ingår i kursbunten ett kapitel ur Michael Sipsers "Introduction to the theory of computation". Det ger en bättre presentation av materialet än motvarande delar av kursbunten föregående år, men studenterna är i allmänhet inte entusiastiska.

Studenternas arbetsbelastning

Ingen tidsstudie har gjorts. De flesta som svarat på enkäten säger sig ha hunnit med vårens kurser någorluna, och verkar inte anse att eventuella problem hänger ihop med denna kurs.

Förkunskaper

De förkunskaper som formellt krävs är godkänt resultat på moment motsvarande minst 60 poäng på matematisk-datalogiska linjens två första å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. Det visar att just det sista är svårt för många av studenterna. En del verkar bli bättre på det under kursens gång.

Verkligt kursinnehåll

Vi har i stort sett hållit oss till detaljschemat för kursen. Det som de godkända studenterna kan bra är den del som handlar om algoritmer och datastrukturer, medan endast ett mindra antal kan sägas behärska NP-fullständighet eller oavgörbarhet.

Kommande förändringar

Från och med våren 2001 samläses denna kurs med "Algoritmer, datastrukturer och komplexitet" (som ges för D2 på KTH), med Viggo Kann som kursledare. Examination och kursinnehåll kommer därför att anpassas, men redan idag är kurserna mycket lika både vad gäller innehåll och examination. En trolig förändring är att tentan blir på 3 poäng och att inlämningsuppgifterna blir obligatoriska och kommer att ge 1 poäng.

Gamla tentor kan nås via kursens hemsida

Bilaga: Enkätsvar

Bilaga: Kursbeskrivning

^ Upp till kurssidan.


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