Nada

^ Upp till kursens hemsida.

2D1446, Komplexitetsteori period 3 2000/2001

Utvärdering

Kursutvärderingen avslutad. Resultaten meddelas i kursanalysen. Här kan du se enkätresultaten.

Senaste nytt

010320 MaxLin-2 har som indata ett system av ekvationer modulo 2. En ekvation kan se ut som

x1+x3+x4=1

Eftersom vi räknar modulo 2 så är plus och minus samma sak, och de enda koefficienter som förekommer är 0 och 1. Ett system består av ett antal ekvationer, och problemet är att hitta en 0/1-tilldelning till variablerna så att så många ekvationer som möjligt uppfylls.

010316 Förtydligande till omgång 3. De probabilistiska maskiner vi talar om fungerar inte riktigt som i boken, dvs de gör inte bara ickedeterministiska övergångar (då skulle slump log n medföra log n steg). En TM som går i polynomisk tid och använder f(n) slump kan börja med att skriva ner f(n) slumbitar på ett extra arbetsband, och därefter exekvera deterministiskt (men kan läsa bitar en eller flera gånger från slumpbandet). Det totala antalet steg, slumpsteg+deterministiska ska vara polynomiskt.

010315 Rättelse av uppgift 3 på omgång 3. Det ska stå

Visa att man för varje n kan konstruera en starkt sammanhängande riktad graf Gn med n noder, så att om man går ett polynomiskt antal från nod 1 i en slumpvandring så är sannolikheten att besöka nod n exponentiellt liten.

010303 Du kan nu boka redovisningstid för uppgift 2. Om ni jobbat i par kan ni redovisa i par.

Tryck här för att hämta bokningslistor:
010301 Inlämningsuppgift 3 är nu färdig. Meddela Mikael eventuella feltryck och oklarheter.

010224 Deadline för uppgift 2 är senarelagd två dagar till fredag 2/3.

010223: Tryckfel i omgång 2
Uppgift 4: För det första ska "sgd" vara "gcd". För det andra ska man visa att varje kvadrat a i Zn* har fyra rötter (det är inte sant om p eller q delar a).

Uppgift 5: det ska vara n/3 variabler i varje klausul.

010215 Inlämningsuppgift 2 finns nu.

010126 Inlämningsuppgift 1 utdelad.

010117 Följande system används för att beräkna poäng vid sen inlämning. Den totala poängen multipliceras med 0,9f(d), där d är antalet dagar sent, avrundat uppåt till heltal, och f(d) = 1 för d = 1 eller 2, och f(d) = (2+d)/2 för i >= 3.

010115 Registrera dig i resultatrapporteringssystemet genom att köra res checkin kplx01 och kör gärna också course join kplx01 för att få länk till kursens hemsida och eventuella login-meddelanden.

Lärare

Kursansvarig är Mikael Goldmann som enklast nås via epost: migo@nada.kth.se.

Kurslitteratur

Som kursbok används Papadimitriou, Computational Complexity, Addison-Wesley. Boken läses på egen hand under kursens gång. Föreläsningarna täcker endast en del av kursmaterialet.

Läsanvisning: Kapitlen 1-3, 7-10, 11, 13 ingår. Kapitel 4 bör läsas för terminologi och definitioner. Beroende på vad som gås igenom under de sista två veckorna kan exempelvis kapitlen 12, 16, 17, 19 ingå.

Schema

Observera att schemat varierar från vecka till vecka.
vecka 3 F12001-01-16 Ti 13-15 D41
F22001-01-17 On 11-13 D31
F32001-01-19 Fr 11-13 E34
vecka 4 F42001-01-24 On 11-13 D31
F52001-01-26 Fr 11-13 E34
vecka 5 F62001-01-31 On 11-13 D31
F72001-02-02 Fr 11-13 E31
vecka 6 F82001-02-07 On 11-13 D31
F92001-02-09 Fr 11-13 E31
vecka 7 F102001-02-14 On 11-13 D31
F112001-02-16 Fr 11-13 E31
vecka 8 F122001-02-21 On 11-13 D31
F132001-02-23 Fr 11-13 D34
vecka 9 F142001-02-26 10-12 D35
F152001-02-28 On 11-13 D41

Examination

Kursen examineras med inlämningsuppgifter som lämnas ut i tre omgångar. Uppgifterna kan lösas enskilt eller i grupper med två personer (lämna varsin lösning och ange vem ni samarbetat med). Lösningarna ska även redovisas muntligt på speciella pass som ligger utanför ordinarie schema. Vid rättning kommer en helt korrekt lösning att ge mer poäng än två "halvrätta" lösningar.

Nada är en av de institutioner som detta läsår på försök infört betyg 6 på vissa kurser, bland annat denna. Eftersom det rör sig om ett försök och ska utvärderas så vill jag gärna veta dina synpunkter på den utvidgade betygsskalan.

Får man minst 30% av full poäng på varje enskild omgång är man garanterad minst betyg 3. För högre betyg gäller dels minst 30% av maxpoäng på varje omgång, dels totalt 45% för 4, 60% för 5, och 80% för betyg 6.

Föreläsningar (preliminärt!)

F1-F3 Administration. Introduktion till komplexitetsteori och komplexitetsklasser. Beräkningsbarhet och beräkningsmodeller. Tids- och minneskomplexitet. (Kapitel 1-3)
F4-F9 Komplexitetsklasser (P, NP, coNP, L, NL, PSPACE), reduktioner och fullständiga problem (kapitel 7-10 i ordning samt Theorem 19.1, ej 8.3),
F10-F11 Algoritmer med slump (kapitel 11), approximationsalgoritmer och approximerbarhet (kapitel 13).
F12-F15 Fördjupning inom några områden, exempelvis komplexitet och kryptografi och interaktiva bevis. Kom gärna med förslag och önskemål!

Hederskodex

Grundregeln är att det jobb du gör i kursen (labbar, inlämningsuppgifter, tentor m.m.) 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 \emph{brott mot hederskodexen} och kan bestraffas, t ex genom att du förlorar alla bonuspoäng eller får göra en ny uppgift. Allvarliga brott mot kursens regler eller hederskodexen rapporteras till institutionens prefekt.

Detta är en översatt och omarbetad version av den hederskodex som används i kursen Introduction to computer science vid Stanford University. Den tillämpas i många av Nadas kurser.

För den här kursen gäller att man får lösa inlämningsuppgifter i grupper med två personer, och att det ska framgå vilka som ingår i gruppen. Det går givetvis bra att be läraren om hjälp, men i den mån ni får tips, råd eller hjälp av andra måste det framgå vad ni fått hjälp med, och av vem.

^ Upp till kursens hemsida.


Sidansvarig: <migo@nada.kth.se>
Senast ändrad 15 maj 2001
Tekniskt stöd: <webmaster@nada.kth.se>