Nada

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

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 drygt 20 personer.

Kursdata

Kurs Algoritmer och komplexitet (SU), ALKO, 5p
Examination Tenta (4p), Lab (1p)
Kursen genomförd VT 1999
Föreläsningar 36 timmar (18 st)
Övningar 26 timmar (13 st)
Labb 8 timmar (+ redovisningar)
Kurslitteratur Introduction to algorithms (Cormen--Leiserson--Rivest) + kursbunt
Antal studenter 43 (varav 4 ej gjort något utöver att registrera sig i res)
Kursansvarig Mikael Goldmann
Övningsassist Staffan Ulfberg (som har haft den enda övningsgruppen)
En föreläsning har hållits av Johan Håstad och en av Viggo Kann.

Nyckeltal

Totalt har 43 studenter registrerat sig genom att köra res. Av dessa hade sju sedan tidigare klarat labbmomentet. De som inte haft något moment godkänt sedan tidigare kallas förstagångsstudenter.

För förstagångsstudenterna (36 st) gällde 1999-06-07 följande:
32 har varit aktiva (redovisat labb, hemtal eller tentat).
24 har klarat labb-momentet.
18 har klarat tentan (varav 17 är klara med hela kursen).

Prestationsgrad: 53% (60% för aktiva)
Examinationsgrad: 47% (53% för aktiva)

Av de sju studenter som sedan tidigare är godkända på labbmomentet har fem 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 studentenen 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

Laborationerna har redovisats vid dator och kombinerats med teorifrågor. Teorifrågorna har inte varit obligatoriska, men gett bonuspoäng. Teorifrågorna har konstruerats så att man ska ha nytta av svaren när man löser labben. Redovisningarna har fungerat bra, men det totala antalet bonuspoäng man kan samla ihop har varit lite väl stort.

I år har individuella inlämningsuppgifter använts istället för hemtal som löstes i grupp året innan. Lösningarna har redovisats muntligt på mitt eller Staffans tjänsterum. Muntliga redovisningar tar tid, men hindrar att folk lämnar in lösningar som de inte själva förstår, och ger också en möjlighet att diskutera studentens lösning på tu man hand.

Ett nytt bonussystem har använts, där godkända inlämningsuppgifter gör att man slipper lösa vissa tentauppgifter.

Sammanfattning

Prestationsgraden är liksom förra året låg. Bland förstagångsstudenterna som inte klarat tentan har endast 8 tenterat. I övrigt har kursen fungerat väl. De som svarat på enkäten är nöjda eller mycket nöjda med det mesta. De förändringar som gjorts sedan förra året har varit till det bättre.

Undervisning

Föreläsningarna har varit välbesökta, och de som svarat på enkäten har varit nöjda (alla som deltagit har svarat "bra" eller "mycket bra").
Övningarna får också bra omdömen.

Inlämningsuppgifter

Omgångar med frivilliga inlämningsuppgifter har delats ut. Varje har bedömts som godkänd, halvt godkänd eller ej godkänd. Korrekt lösta uppgifter svarar mot tal på tentan. Dessa tentatal är automatiskt godkända om man är godkänd på motsvarande inlämningsuppgift.

Inlämningsuppgifterna har redovisats skriftligt och muntligt. Den muntliga redovisningen har fungerat så att studenten bokar en redovisningstid hos Mikael eller Staffan.

Uppgifterna är tänkta att lösas individuellt. Visst samarbete har säkert förekommit, men i de fall då identiska lösningar lämnats in av flera personer har poängavdrag gjorts.

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).

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.

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 vag. Meningen var att de skulle komplettera varandra. Lösningen är inte idealisk, men det enda alternativ jag ser är att skriva ett kompendium som i högre grad än Johans är anpassat till en kurs i grundutbildningen.

Studenternas arbetsbelastning

Ingen tidsstudie har gjorts. Förra året menade många att det varit problem med schemat mitt i terminen. I år har schemat inte varit detsamma, och jag har inte hört några sådana klagomål. De flesta tycker att de i stort sett hunnit med vårens kurser.

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 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, och mycket få har förstått oavgörbarhet.

Att ändra på

Bonsusystem och betygsgränser behöver trimmas in. Jag ska överväga att dela ut föreläsningsanteckningar. Jag ska fundera över litteratur till delen om oavgörbarhet.

Bilaga: Enkätsvar

Bilaga: Kursbeskrivning

Bilaga: Tentalydelse

^ Upp till kurssidan.


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