Aktuell information om 2D1961, Algoritmer och komplexitet

^ Upp till kursens hemsida.


Senaste nytt

Algoritmer och komplexitet kommer hösten 1996 att återuppstå i ny skepnad, då som kursen 2D1354, Algoritmer och komplexitet för F. Den nya kursen kommer att innehålla ungefär samma saker som den gamla kursen. Kursen är fortfarande på 4 poäng och lärare blir Viggo Kann.

D-elever som inte är klara med gamla Algoritmer och komplexitet rekommenderas att läsa den nya kursen istället. Den kan också läsas som ett alternativ till 2D1353, Algoritmer, datastrukturer och komplexitet.

Tentor

Extratentan 1996-03-30

Omtentan 1996-01-13

Omtentan 1995-08-26

Ordinarietentan 1995-05-24

Lärare

Kursledare, föreläsare och övningsassistent är Viggo Kann, viggo@nada.kth.se. Mottagningstid måndagar kl 13.15-14.15.

Kurslitteratur

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

Kursböcker

Båda böckerna finns att köpa på kårens bokhandel. Läsanvisning inför tentan finns.

Kursbunt

Kursbunten kan köpas på Nadas elevexpedition för 20 kr. Papper som delas ut under kursens gång finns också på elevexpeditionen.

Kursuppläggning

Kursen består av 15 föreläsningar och 9 övningar. Följande tabell visar schemat och vad som preliminärt kommer att behandlas under föreläsningarna och övningarna. Alla föreläsningar är i sal E4 utom föreläsning 11 den 24 april som är i V1. Alla övningar är i sal F21
F1, 6 mars kl 10-12
Introduktion, repetition av algoritmanalys, beräkningsmodeller, bitkostnad och enhetskostnad, undre och övre gränser. (CLR 1-10, Har 6)
F2, 7 mars kl 11-13
Formella språk, beslutsproblem, optimeringsproblem, uttrycksfullhet, reduktioner. (BDD 1.1)
Ö1, 7 mars kl 14-16 och 9 mars kl 10-12
Algoritmanalys, reduktioner.
F3, 13 mars kl 10-12
Introduktion till komplexitet. (Har 7)
F4, 14 mars kl 11-13
Oavgörbarhet. (Har 8)
Ö2, 14 mars kl 14-16 och 16 mars kl 10-12
Oavgörbarhet, reduktioner.
F5, 20 mars kl 10-12
Enkla beräkningsmodeller (turingmaskiner, ändliga automater) och deras kraftfullhet. (Har 9, BDD 1.2)
F6, 21 mars kl 11-13
KMP-automaten, grammatik, reguljära uttryck. (BDD 2-4)
Ö3, 21 mars kl 14-16 och 23 mars kl 10-12
Automater och reguljära uttryck, turingmaskiner.
F7, 27 mars kl 10-12
Algoritmkonstruktion: dekomposition, dynamisk programmering och giriga algoritmer. (CLR 16, 17, 31.2, Har 4)
F8, 28 mars kl 11-13
Översikt över algoritmer. (CLR 23-27)
Ö4, 28 mars kl 14-16 och 30 mars kl 10-12
Algoritmkonstruktion, grafalgoritmer.
F9, 3 april kl 10-12
FFT (CLR 32)
F10, 4 april kl 11-13
Formell definition av NP och co-NP, polynomisk reduktion, Cooks sats. (CLR 36.1-36.3)
Ö5, 4 april kl 14-16 och 6 april kl 10-12
Grafalgoritmer och FFT.
F11, 24 april kl 10-12 i sal V1
NP-fullständighetsbevis. (CLR 36.4-36.5)
F12, 25 april kl 11-13
Approximationsalgoritmer. (CLR 37)
Ö6, 25 april kl 14-16 och 27 april kl 10-12
NP-fullständighetsbevis.
Ö7, 4 maj kl 10-12
Mer NP-fullständighetsbevis.
F13, 9 maj kl 11-13
Mer om approximation.
Ö8, 9 maj kl 14-16 och 11 maj kl 10-12
Approximationsalgoritmer.
F14, 16 maj kl 11-13
Parallella och probabilistiska algoritmer och komplexitet. (Har 10-11)
Ö9, 16 maj kl 14-16 och 18 maj kl 10-12
Tentaräkning.
F15, 19 maj kl 10-12 i sal E7
Repetition

Kursregistrering

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

res checkin algokomp95

på någon av Nadas unixdatorer. Registrera dej så snart som möjligt!

Hemtal

Två frivilliga hemtal delas ut under kursen. Dom ska lösas enskilt och redovisas enligt följande. Summan av bonuspoängen adderas till den på tentan uppnådda poängsumman. Detta gäller ett kalenderår räknat från kursstart. Du kan se hur många poäng du fått på hemtalen om du ger kommandot

res show algokomp95

på någon av Nadas unixdatorer.

Hederskodex

Grundregeln är att det jobb du gör i kursen (på hemtal och tenta) ska du göra själv.

Ibland, speciellt när man skriver program, kan det vara nödvändigt att fråga någon annan (en kamrat eller en handledare) om hjälp med att hitta fel. Detta är tillåtet förutsatt att du uppfyller följande villkor.

Varje annan form av samarbete och utnyttjande av andras lösningar betraktas som ett brott mot hederskodexen och kan bestraffas, t ex genom att du förlorar alla bonuspoäng.

Tentamen

Tid och plats för ordinarietentan är onsdag 24 maj kl 8-13 i F11-F15.

Tentan består av en teoridel om cirka 17 poäng och en problemdel om cirka 20 poäng. På problemdelen får allt kursmaterial utom extentor med lösningar användas som hjälpmedel. För godkänt krävs minst 13 poäng (inklusive maximala 5 bonuspoäng från hemtalen), varav minst 5 poäng på teoridelen och 5 poäng på problemdelen. 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 kursansvarige inom tre veckor från det att tentaresultatet anslagits.

Anmälan till tentan

Du behöver inte anmäla dig till tentan. (Tentaanmälan var tidigare obligatorisk för D- och E-teknologer men Nada använder sig inte av detta anmälningssystem längre.)

Kurskatalog

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

Synpunkter på kursen

Jag är tacksam för synpunkter på kursen, både under kursens gång och efteråt. Tala direkt med mej eller skicka ett brev. Adressen är viggo@nada.kth.se

^ Upp till kursens hemsida.


Senast ändrad 11 sept. 1996 <viggo@nada.kth.se>