Nada

^ Upp till kursens ingångssida.

Information om DD1352, Algoritmer, datastrukturer och komplexitet våren 2000

Senaste nytt

Restlabbsredovisning i augusti

Den som har någon labb kvar att redovisa kan göra det torsdag den 24 augusti klockan 13-15. Sitt helst i Grå sal och anmäl dej för redovisning med QM.

Kolla labbresultat

Gör gärna res show adk00 och kolla att du blivit inrapporterad på alla labbar och fått rätt teoripoäng på labbarna. Om något är fel ber jag att du visar upp ditt signerade labbkvitto för Viggo eller någon av assistenterna.

Kursanalys

Kursutvärderingsenkäten finns sammanställd tillsammans med kursledarens synpunkter och planer på förändringar i årets kursanalys.

Reducerat antal övningsgrupper

Övningsgrupp 4 har ställts in från och med vecka 8.

Lärare

Kursledare och föreläsare är Viggo Kann, viggo@nada.kth.se. Mottagningstid är tills vidare torsdagar klockan 10.00-11.00, telefon 08-790 62 92. Övningsassistenter för dom fyra grupperna är
  1. Lars Ivansson, ivan@nada.kth.se
  2. Johan Karlander, johank@nada.kth.se
  3. Stefan Nilsson, snilsson@nada.kth.se
  4. Jonas Holmerin, joho@nada.kth.se

Kurslitteratur

Kurslitteraturen ska läsas på egen hand parallellt med kursen. Föreläsningar och övningar täcker endast en del av kursmaterialet.

Kursbok

Ausiello m fl: Complexity and Approximation - Combinatorial optimization problems and their approximability properties, Springer Verlag, ISBN 3-540-65431-3.

Dessutom ingår kapitel 9 och 11 i Biggs: Discrete mathematics som är kursbok i kursen Diskret matematik som går samtidigt som ADK för D2.

Det finns en detaljerad läsanvisning inför tentan.

Kursbunt

Kursbunten kommer att kunna köpas på Nadas studentexpedition för 40 kr. Papper som delas ut under kursens gång kommer att finnas i en pärm i hyllan i entrérummet utanför expeditionen.

Schema

Schema för period 3, 2000

 F ti 09-11 v 3-5,7-9   D1 
 F on 09-11 v 3-5,7-9   E1 
 Ö on 11-13 v 3-5,7-9   E32-33, 35-36 
 L on 14-16 v 5,7-8 gr 1-2 Grå, Karmosin 
 L on 11-13 v 6 gr 1-2 Grå, Karmosin 
 L fr 14-16 v 5,7-8 gr 3-4 Grå, Karmosin 
 L on 14-16 v 6 gr 3-4 Grå, Karmosin 

Schema för period 4, 2000

 F 09-11 v 11-15   Q1 
 F on 09-11 v 11-15,19   D1 
 F ti 10-12 v 19   E1 
 Ö on 11-13 v 11-15   D31-32, 34-35 
 Ö on 15-17 v 19   D31-32, 34-35 
 L on 14-16 v 11-15 gr 1-2 Grå, Karmosin 
 L fr 11-13 v 11-13 gr 3-4 Grå, Karmosin 
 L on 16-18 v 14 gr 3-4 Grå, Karmosin 
 L fr 09-11 v 15 gr 3-4 Grå, Karmosin 

Detaljschema

Kursen består av 24 föreläsningar och 12 övningar. Följande tabell visar vad som preliminärt kommer att behandlas under föreläsningarna och övningarna. För varje föreläsning anges vilket avsnitt i kurslitteraturen som behandlas. CA står för kursboken Complexity and approximation.
Period 3
F1 18 januari
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller, bitkostnad och enhetskostnad. (CA 1.1)
F2 19 januari
Repetition av sortering, undre gräns för sortering, korrekthet. (repetition)
Ö1 19 januari
Algoritmanalys.
F3 25 januari
Repetition av datastrukturer (heapar, binära träd), balanserade träd. (repetition, även Biggs 9.2)
F4 26 januari
Grafer: sökning, maximala flöden. (Biggs 9.4,9.5,11)
Ö2 26 januari
Grafalgoritmer.
F5 1 februari
Grafalgoritmer: minimala spännande träd, kortaste stigar. (Biggs 9.3,9.6)
F6 2 februari
Algoritmkonstruktion: dekomposition och giriga algoritmer. (CA 2.1)
Ö3 2 februari
Dekomposition och partitioneringsproblem. (CA 2.2)
F7 15 februari
Algoritmkonstruktion: totalsökning, lokalsökning, linjärprogrammering. (CA 2.3-2.4, A.7)
F8 16 februari
Algoritmkonstruktion: dynamisk programmering. (CA 2.5, även Biggs 12.4-12.6)
Ö4 16 februari
Dynamisk programmering.
Labb 1 16 och 18 februari
Flöden och matchningar, redovisning.
F9 22 februari
Algoritmkonstruktion: Mer dynamisk programmering, probabilistiska algoritmer, sortering i linjär tid. (CA 2.5-2.7)
F10 23 februari
Algoritmkonstruktion: Heurestiker. (CA 10)
Ö5 23 februari
Algoritmkonstruktion.
Hemtal 1, senast tisdag 29 februari klockan 14.00
Algoritmer.
F11 29 februari
Datastrukturer: skipplistor, praktiska datastrukturer. (Pugh, artikel i kursbunten)
F12 1 mars
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Ö6 1 mars
Datastrukturer.
Period 4
F13 13 mars
Introduktion till komplexitet. (CA 1.2)
F14 15 mars
Reduktioner. (CA 1.3-1.4)
Ö7 15 mars
Reduktioner.
F15 20 mars
Oavgörbarhet. (Harel, artikel i kursbunten)
F16 22 mars
Deterministiska och ickedeterministiska turingmaskiner och deras kraftfullhet. (CA 6.1-6.1.3)
Ö8 22 mars
Oavgörbarhet.
Labb 2 22 och 24 mars
Optimering av ordkedja, redovisning.
F17 27 mars
Formell definition av NP och co-NP, polynomisk reduktion, Cooks sats. (CA 6.1.4-6.1.5)
F18 29 mars
NP-fullständighetsbevis.
Ö9 29 mars
NP-fullständighetsbevis.
F19 3 april
NP-fullständighetsreduktioner.
F20 5 april
Komplexitetsklasser. (CA 1.2)
Ö10 5 april
NP-fullständighetsbevis.
F21 10 april
Approximationsklasser. (CA 3.1)
F22 12 april
Approximationsscheman. (CA 3.2)
Ö11 12 april
Komplexitetsklasser, approximationsalgoritmer.
Labb 3 12 och 15 april
Konkordans, redovisning.
F23 9 maj
Probabilistiska algoritmer. (CA 5.1-5.2)
F24 10 maj
Repetition.
Ö12 10 maj
Repetition.
Hemtal 2, senast måndag 15 maj
Komplexitet.

Kursregistrering

Alla som vill gå kursen måste registrera sig på den. Detta görs med kommandot

res checkin adk01

på någon av Nadas Unixdatorer. Registrera dig så snart som möjligt efter att kursen börjat!

Du bör också ge kommandot

course join adk01

Detta kommando gör två saker:

När du är klar med kursen ger du kommandot

course leave adk01

för att återställa allt.

Endast teknologer som delfakulteten lagt in i Ladok som studerande på en kurs kan godkännas på kursen. Om ADK inte är obligatorisk för dig (det vill säga om du inte går i D2) måste du först välja kursen vid ditt fakultetskansli som måste godkänna ditt val.

Obligatoriska moment

Kursen har tre obligatoriska moment i Ladok:
TEN1
Tenta, 3 poäng
HEM1
Hemtal, 1 poäng
LAB1
Datorlaborationer, 2 poäng
Nedan finns detaljerad information om dessa moment.

Tenta

Ordinarietentan går lördagen den 27 maj 2000 klockan 14-19 i sal F41-F55.

Tentan består av en teoridel (om 20 poäng) utan hjälpmedel och en problemdel (om 30 poäng) med kursböckerna, föreläsningsanteckningar och egna anteckningar som hjälpmedel (men inga lösta tentor). För godkänt krävs minst 25 poäng. Den som presterat bra lösningar till båda hemtalen kan ha klarat av 12 poäng på problemdelen i förväg. Den som redovisat datorlabbarna i tid och har svarat rätt på teoriuppgifterna på labbarna får 9 poängs bonus på tentan. Frågorna på teoridelen behandlar bara det som tagits upp på föreläsningarna och nämnts i dom utdelade föreläsningsanteckningarna.

Nästa tentatillfälle blir i augustiperioden.

Tentaresultatet anslås högst tre veckor efter tentan på institutionens anslagstavla på plan 3 (rakt under elevexpeditionen). Klagomål på rättning av tentan lämnas in skriftligen till kursledaren.

Anmälan till tentan

Du behöver inte anmäla dig till tentan.

Hemtal

Två obligatoriska hemtal kommer att delas ut. Dessa ska lösas individuellt och redovisas både skriftligt och muntligt. Skriftliga lösningar till dessa uppgifter ska lämnas till någon av lärarna eller lämnas in i bokhyllan utanför studentexpeditionen senast den tid som anges på uppgiftslydelsen. Den muntliga redovisningen kommer att ske senare samma vecka för någon av assistenterna på en tid som ska bokas i förväg.

Varje hemtal består av två uppgifter. Varje uppgift ger upp till 3 poäng. För godkänt på det obligatoriska momentet HEM1 krävs minst hälften rätt (alltså 6 av totalt 12 poäng).

Varje hemtal motsvarar också ett 6-poängstal på problemdelen av tentan. Poängen från motsvarande hemtal adderas till problemdelstalet, men mer än 6 poäng ges inte. Den som har full poäng på ett hemtal slipper alltså göra motsvarande tal på tentan. Detta gäller på alla tentor som går inom ett kalenderår räknat från kursstart.

Den som inte klarat momentet HEM1 på hemtalen kan istället få det godkänt genom att klara (eller komplettera med) motsvarande tal på tentan.

Du kan se hur många poäng du fått på hemtalen om du ger kommandot

res show adk01

på någon av Nadas Unixdatorer.

Labbar

Tre obligatoriska datorlabbar ingår i kursen. Dessa utgör momentet LAB1. Labbarna ska helst göras i tvåpersonsgrupper. En- och trepersonsgrupper kan godkännas i undantagsfall. Varje labb som redovisas senast det labbtillfälle som finns angivet på labben ger en bonuspoäng på tentan. På varje labb finns dessutom ett antal frivilliga teoriuppgifter. Den som vid redovisningen av en labb kan redogöra för lösningarna på teoriuppgifterna får två bonuspoäng. Teoriuppgifterna måste redovisas tillsammans med labben och senast bonusdatumet.

Sammanlagt kan alltså labbarna ge 3+6=9 bonuspoäng på tentan. Bonuspoängen gäller på alla tentor på kursen som går inom ett kalenderår räknat från kursstart.

Det finns schemalagda labbtillfällen från och med tredje veckan av kursen och till och med den vecka då labb 3 ska redovisas. Det kommer att finnas handledare tillgängliga på dessa labbtillfällen. Börja att göra labbarna i god tid och fråga handledarna om du får problem. Du kan i princip redovisa alla labbarna vid alla labbtillfällen, men under det sista labbtillfället för varje labb kan bara den labben redovisas.

Hederskodex

Skolan tillämpar en hederskodex i alla sina kurser och varje student förutsätts tillämpa hederskodexen. Om du inte har läst den eller inte minns den: läs den nu! Mer om fusk vid examination kan du läsa om här.

Arbetssituationer

Det är meningen att arbetet med momenten i kursen ska motsvara olika arbetssituationer i arbetslivet.

Labbarna tränar olika typer av programutvecklingsarbete:

Alla labbar har givna effektivitetskrav och utförs som lagarbete (labbgrupper), precis som i verkliga programmeringsprojekt.

Hemtalen tränar expertsituationen, alltså situationen som den som vet mest om något på en arbetsplats ställs inför när han får ett problem: det finns ingen att fråga, så han måste komma fram till svaret med egen tankekraft och genom att läsa litteratur. När problemet är löst ska experten förklara lösningen för chefen, både skriftligt och muntligt.

Tentan liknar tyvärr ingen verklig arbetssituation. På huvuddelen av tentan (problemdelen) är kurslitteraturen rekommenderat hjälpmedel så att det i alla fall inte ska krävas stora utantillkunskaper.

Kurskatalog

Kursen har en katalog på Nadas Unixdatorer: /info/adk01. På denna katalog finns textfiler, programskelett, program och liknande som har med kursen att göra.

Synpunkter på kursen

Eftersom denna kurs kommer att ges för många elever under flera års tid är vi tacksamma för synpunkter på kursen. En datorstödd kursutvärdering kommer utföras. Synpunkter kan lämnas till lärarna.

Diverse länkar

Skicka gärna brev till Viggo om du har tips på lämpliga länkar för denna lista.

^ Upp till kursens ingångssida.


Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Senast ändrad 16 januari 2010
Tekniskt stöd: <webmaster@nada.kth.se>