Nada

^ Upp till kursens hemsida.

2D1446, Komplexitetsteori period 3 2001/2002

Kursen är nu avslutad

En preliminär kursanalys finns nu, baserad på kursnämndsmöte och enkätsvar.

Senaste nytt

Some comments related to problem set 3 in answer to questions I have been asked.

The article Algebraic Methods for Interactive Proof Systems by Lund, Fortnow, Karloff, and Nisan was covered 18 Feb.

Homework set 3 is now available. It is due on Feb. 28.

Homework set 2 is now available.

In the last three lectures we will talk a bit about cryptography (just an overview of some theoretical aspects), interactive proofs, and complexity of parallel computation.

There has been several requests that I switch to Swedish, and since that is officially the language the course is taught in I will do so. I still plan to use English for information, login messages, and problem sets. I hope that is OK with everyone. Otherwise let me know.

Some comments related to problem set 1 in answer to questions I have been asked.

There is a typo in problem set 1, problem 8: the hint should refer to problems 2.8.4 and 2.8.5 in the book.

Thanks to Mattias Amnefelt the Lecture log now has pointers to copies of my lecture notes (such as they are).

Mattias Amnefelt and Fredrik Niemelä have volunteered to form a "kursnämnd". Comments and suggestions can either be brought to them or to me. I am happy to discuss any questions, comments, or suggestions you might have.

Homework set 1 is now available.

Välkommen till första föreläsningen måndag 14/1 kl 10 i E33. KursPM i pdf finns här.

Kursboken finns enligt uppgift på kårbokhandeln (som flyttat till Osquars backe 21) och kostar ca 735 kr.

Glöm inte att registrera er.

Lärare

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

Registrering

Endast de teknologer som delfakulteten lagt in i Ladok som studerande på en kurs kan godkännas på kursen. Se alltså till att du är registrerad i Ladok. För doktorander vid andra institutioner än Nada gäller särskilda regler som finns här. Dessutom måste du, för att kursledaren ska kunna hålla reda på dina resultat, registrera dig i Nadas resultatrapporteringssystem. Detta görs med kommandot >>res checkin kplx02>> på någon av Nadas unixdatorer. Registrera dig så snart som möjligt! För din egen skull bör du också ge kommandot >>course join kplx02>>.

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 oregelbundenheter markerats med fetstil.
vecka 3 F12002-01-14 10-12 E33
F22002-01-16 On 13-15 E33
F32002-01-17 To 10-12 E33
vecka 4 F42002-01-2110-12 E33
F52002-01-23On 13-15 E33
F62002-01-24 To 10-12 E33
vecka 5 F72002-01-28 10-12 E33
F82002-01-30 On 10-12 E33
F92002-01-31 To 10-12 E33 Inlämning av uppgift 1
vecka 6 F102002-02-04 10-12 Q12
F112002-02-07 To 10-12 E33
vecka 7 F122002-02-11 10-12 E33
F132002-02-14 To 10-12 E34 Inlämning av uppgift 2
vecka 8 F142002-02-18 10-12 E33
F152002-02-21 To 10-12 E34
vecka 9 2002-02-28 To kl 16Exp/Postfack Inlämning av uppgift 3

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 (men lämna varsin lösning och ange den andra gruppmedlemmen). Lösningarna ska även redovisas muntligt på speciella pass som ligger utanför ordinarie schema.

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. På varje omgång kommer det att finnas en eller ett par problem av överkurskaraktär. För betyg 6 krävs 80% av maximal poäng och att man klarat flertalet av överkursproblemen. För studenter på SU gäller att kraven för G är desamma som för betyg 3, och för VG gäller dessutom totalt minst 53% av maximal poäng. Observera att "överkursuppgifterna" ger poäng på samma sätt som övriga uppgifter och att deras poäng räknas med i totalpoängen.

Föreläsningar (preliminärt)

Nedan finns ett preliminärt schema. Dessutom finns här en föreläsningslog som kortfattat beskriver vad som gjorts på respektive föreläsning.
F1-3 Administration. Introduktion till komplexitetsteori och komplexitetsklasser. Beräkningsbarhet och beräkningsmodeller. Tids- och minneskomplexitet. (Kapitel 1-3)
F4-9 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-12 Algoritmer med slump (kapitel 11), approximationsalgoritmer och approximerbarhet (kapitel 13).
F13-15 Fördjupning inom några områden, förslagsvis parallell komplexitet och interaktiva bevis. Kom gärna med egna 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 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 (att lösa dem individuellt går också bra), men alla ska skriva en egen lösning med egna ord där det ska framgå vilka som ingår i gruppen. Om ni utnyttjar resultat, bevis eller ideer från kurslitteraturen eller någon annan källa så ange tydlig referens. Så länge man spelar med öppna kort kan det aldrig bli frågan om fusk.

En utförligare version av reglerna finns här.

Till sist, undvik att lägga era lösningar publikt tillgängliga, speciellt före inlämningsdatum, men gärna även därefter.

^ Upp till kursens hemsida.


Sidansvarig: <migo@nada.kth.se>
Senast ändrad 10 april 2002
Tekniskt stöd: <webmaster@nada.kth.se>