Nada

Kursanalys för Algoritmer och komplexitet, Läsåret 97/98

Författare: Mikael Goldmann, NADA

^ Upp till kurssidan VT-98.

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 21 personer.

Kursdata

Kurs Algoritmer och komplexitet (SU), ALKO, 5p
Examination Tenta (4p), Lab (1p)
Kursen genomförd VT 1998
Föreläsningar 36 timmar (18 st)
Övningar 26 timmar (13 st)
Kurslitteratur Introduction to algorithms (Cormen--Leiserson--Rivest) + kursbunt
Antal elever 46 (tre har inte gjort något utöver registrerat sig)
Prestationsgrad 50% (980508)
Examinationsgrad 35% (980508)
Prestationsgrad 57% (980527 efter omtenta)
Examinationsgrad 43% (980527 efter omtenta)
Kursansvarig Mikael Goldmann
Övningsassist Mats Näslund (som har haft den enda övningsgruppen)

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 eleven 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", 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, ä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

Vi har haft ny kursbok, fyra extra övningar som använts för hemtalsredovisning, samt ett nytt kursmoment i form av en programmeringslab. Kursboken och övningarna behandlas senare.

Laborationen har huvudsakligen utförts efter kursens slut, eftersom den nödvändiga teorin gicks igenom under de sista föreläsningarna. Årets uppgift var att skriva ett program som kunde kryptera, deryptera och signera med RSA samt generera krypteringsnycklar. Eleverna redovisade genom att dekryotera ett hemligt meddelande, signera det och därefter skicka det till mig eller Mats. De flesta som gjort labuppgiften och besvarat enkäten har uppskattat uppgiften.

Sammanfattning

Prestationsgraden är aldeles för låg. Att endast 55% av de som skrev ordinaire tenta klarade sig har flera orsaker. Dels kan det tänkas att tentan var något svårare än förra året, dels har eleverna varit stressade i kursens slutskede eftersom kurserna under terminens första och andra halva överlappat. Tyvärr har resultatet endast förbättrats marginellt vid omtentan som endast klarades av fem personer (av 16).

I övrigt tycker jag att det mesta fungerat väl, både vad gäller det nya labmomentet och den nya kursboken. Det som bör ses över är övningarnas innehåll, hemtalsredovisningarna och delar av kursliteraturen. Dessa fungerar i och för sig ganska bra idag, men det finns utrymme för förbättrningar.

Undervisning

Föreläsningarna har varit välbesökta, och de som svarat på enkäten har varit nöjda (alla utom en har svarat "bra" eller "mycket bra"). Förra året ansåg en del att OH-bilder automatiskt driver upp tempot och att jag pratat för fort för studenter som inte har svenska som modersmål. I år har jag använt OH i mycket mindre omfattning, och det tycks ha hjälpt.

Övningarna har fått mer skiftande omdömen, även om få är direkt negativa. Den kritik som finns är att övningarna i alltför stor omfattning behandlat teori och att det givits för lite utrymme åt eget räknande.

För att aktivera eleverna på övningarna har Mats dels försökt få dem att ta aktiv del i genomgång av exempel, dels låtit dem räkna själva under övningens första halva. Vi har också haft fyra nya övningar som använts till redovisning av hemtal. Det som fungerat bäst är att under en del av övningen låta eleverna arbeta självständigt, och därför ska vi försöka göra det i större omfattning. Det skulle kunna förbättra deras förmåga att lösa problem.

Hemtal

Fyra omgångar med frivilliga hemtal har delats ut. Lösningar poängsätts och ger bonuspoäng på tentan. Det har 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. Eleverna förvarnades om vilken grupp som skulle redogöra för vilket tal, men däremot inte vilken gruppmedlem som skulle redovisa. Några elever har föreslagit att eleverna ska lämna in egna lösningar i stället för att lämna in en "grupplösning".

Hemtalen har fungerat ganska bra, medan redovisningstillfällena av flera elever upplevts som mindre givande. En del grupper har varit alltför stora, vilket lett till att inte alla lärt sig av att göra hemtalen. Det är naturligtvis beklakligt, men det drabbar i första hand de som åker snålskjuts: de klarar inte tentan. Fyra övningarna användes till hemtalsredovisningar. Detta har i första hand upplevts som, och fungerat som, en test av att folk förstår de lösningar de lämnar in. Det är tveksamt vad åhörarna fått ut av dessa tillfällen.

Examination

Kursen examineras med en labuppgift, beskriven tidigare, och med en tenta. Tentan består av en "teoridel" (20p) och en "problemdel" (fyra tal, totalt 20p). För att få G krävs minst 15 poäng totalt och att de två bästa lösningarna på problemdelen tillsammans ger minst fem poäng. De bonuspoäng man fått på hemtalen läggs till totala poängsumman.

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, med undantag av oavgörbarhet, och att man lätt kan välja och vraka bland ämnen att fördjupa sig i, vilket är bra till laborationsuppgiften. I mitt tycke är den bättre än den föregående kursboken i alla avseenden utom två: det finns inga lösningar till övningsuppgifterna och den är minst två kilo tyngre.

Eftersom kursboken (varken nuvarande eller föregående) inte tar upp turingmaskiner och oavgörbarhet har jag tidigare år 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 vag. Meningen var att de skulle komplettera varandra. Eftersom många fann Johans kompendium svårläst har jag i år försökt att endast använda kapitlet i Harels bok och föreläsningsanteckningar. Enkätsvaren tyder dock på att många inte läst Harel och att de som gjorde det inte var vidare förtjusta.

Sammanfattningsvis kan man säga att kursliteraturen fungerat bra förutom vad gäller den del av kursen som behandlar beräkningsbarhet. Antingen måste denna del tonas ner, eller också behövs det lämplig literatur.

Studenternas arbetsbelastning

Ingen tidsstudie har gjorts. Det som sagts både på enkäten och muntligt är att schemat kört ihop sig i mitten av terminen (dvs i slutet av den här kursen). Detta tycks vara ett övergångsproblem eftersom schemat inte ser likadant ut nästa år.

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.

Från och med nästa år kommer det att vara möjligt att mer noggrannt precisera förkunskapskraven. De kurser som jag då vill framhålla är, förutom de tre första datalogikurserna, kombinatorik, logik och sannolikhetslära.

Verkligt kursinnehåll

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

Att ändra på

Övningarna kan fortfarande användas bättre. En synpunkt som framförts från elevhåll är att man kunde använda dem till "handlett" arbete med hemtalen. Det kan vara en god idé som alternativ till de övningar då hemtal redovisats. En nackdel är att presentationsmomentet i så fall försvinner helt. Övningarna bör inriktas mer mot att ge färdighet i problemlösning. Tentaresultaten tyder på att detta behövs.

Jag tänker fundera en del över tentans poängsättningen och bonussystemet. Viggo har en annan poängsättning och ett annat bonussystem i den kurs med samma namn som han håller för F4 på KTH. Det kan vara värt att provköra den typen av tenta under ett år.

Bilaga: Enkätsvar

Bilaga: Kursbeskrivning

Bilaga: Tentalydelse

^ Upp till kurssidan VT-98.


Sidansvarig: <migo@nada.kth.se>
Senast ändrad 14 december 1998
Tekniskt stöd: <webmaster@nada.kth.se>