Nada

^ Upp till kursens ingångssida.

Information om omgang01, Seminariekurs i teoretisk datalogi våren 2001

Kursanalysen är nu klar.

Hemtal 4 är rättat och slutbetyg är inrapporterat i res. Trevlig sommar!

Svara på kursutvärderingsenkäten nu!
Nu är det dags att utvärdera kursen. Var snäll och fyll i kursutvärderingsenkäten. Klicka här!

Lydelse till hemtal 4 i Postscript och PDF finns nu.

Lydelse till hemtal 3 i Postscript och PDF. Sista inlämningsdag för hemtalet är senarelagd till den 7 maj.
Uppgift 3 (5.8 i boken) kan inte lösas med den givna uppgiftsformuleringen. Ändra uppgiften på följande sätt:
Sätt en variabel xj till 1 med sannolikhet xj* ln n (eller med sannolikhet 1 om xj* ln n är större än 1) där n är antalet element som ska täckas, dvs med ln n gånger större sannolikhet än den som står i lydelsen. Visa att sannolikheten för att Sj är täckt (dvs att alla element i delmängden är täckta) är minst (1-1/n)n, vilket är ungefär 1/e då n är stort.
(Det är vissa som redan har löst uppgiften genom att bara byta "a set Si" mot "an element si" i uppgiftslydelsen. Jag kommer att godkänna även sådana lösningar.)

Uppgift 1 (implementation av algoritm för viktad satisfierbarhet): På rad 9 på sida 171 är klausulernas vikter bortglömda i höverledet i uttrycket för väntevärdet.

Lydelse till hemtal 2 i Postscript och PDF. Sista inlämningsdag för hemtalet var den 6 april.

I uppgift 1 ska algoritmen i steget find a maximum independent set bara hitta en oberoende mängd som inte går att utöka, dvs en maximal independent set.
I uppgift 3 (exercise 3.14) ska k betraktas som en konstant.
I uppgift 4 räcker det att visa att varje maximeringsproblem i PTAS uppfyller villkoret.

Lydelse till hemtal 1 i Postscript och PDF. Sista inlämningsdag för hemtalet är senarelagd till den 28 mars.
I uppgift 1 kan du räkna med att största avståndet mellan två städer är begränsat av 2O(n).

Fyra fredagsseminarier är flyttade i tid och rum. Nya tider och platser:

Lärare

Kursledare är Viggo Kann, viggo@nada.kth.se. Mottagningstid är onsdagar klockan 10.00-11.00, telefon 08-790 62 92.

Kurslitteratur

Kursbok är Ausiello m fl: Complexity and Approximation - Combinatorial optimization problems and their approximability properties, Springer Verlag, 1999, ISBN 3-540-65431-3. Boken kan köpas i kårbokhandeln för 500 kronor.

Det finns en lista över kända feltryck i boken.

Läsanvisning

Det finns ingen kursbunt. Fyra omgångar hemtalsuppgifter kommer att delas ut under kursens gång.

Schema och detaljschema

Schemat nedan är preliminärt. Den första föreläsningen kommer vi att diskutera eventuella schemaändringar. Det kan tänkas att vissa tillfällen kommer att flyttas. Alla schemaändringar kommer att anslås på denna webbsida i så god tid som möjligt.
S1 måndag 12 mars 13-15, E36
Talare: Viggo
Introduktion, omröstning om schemaändringar, repetition av approximationsbegreppet och komplexitet (kapitel 1)
S2 tisdag 13 mars 14-16, E36
Talare: Viggo
Approximationsalgoritmkonstruktion: giriga algoritmer, sekvensiella algoritmer, lokal sökning (avsnitt 2.1-2.3)
S3 fredag 16 mars 12-14, D31 Ny tid!
Talare: Viggo
Approximationsalgoritmkonstruktion: linjärprogrammering, dynamisk programmering, probabilistiska algoritmer, heuristiker (avsnitt 2.4-2.7)
S4 måndag 19 mars 13-15, E36
Talare: Ali Tofigh och Mikael Ylikoski
Approximationsklasser: absolut och relativ approximation, NPO, APX, undre gränser för approximation (avsnitt 3.1)
S5 fredag 23 mars 12-14, D31 Ny tid!
Talare: Eric Nordenstam och Erik Stackenland
Approximationsklasser: PTAS och FPTAS (avsnitt 3.2-3.3)
Hemtal 1, senast onsdag 28 mars
Kapitel 1-2.
S6 måndag 26 mars 13-15, E36
Talare: Ulf Bourelius och Magnus Holm
Indataberoende approximationsgrad: mellan APX och NPO, mellan APX och PTAS (kapitel 4)
S7 fredag 30 mars 16-18, E36 Ny tid!
Talare: Torbjörn Skog och Oskar Linde
Probabilistisk approximation: viktad hörntäckning och viktad satisfierbarhet (avsnitt 5.1-5.2)
S8 måndag 2 april 13-15, E36
Talare: Simon Grönlund, Erik Joelsson och Isaac Elias
Probabilistisk approximation: semidefinit programmering och slumpeliminering (avsnitt 5.3-5.4)
Hemtal 2, senast fredag 6 april
Kapitel 3-4.
S9 fredag 6 april 12-14, D31 Ny tid!
Talare: Viggo
Orakel, PCP och negativa resultat som använder PCP (avsnitt 6.2-6.4)
Hemtal 3, senast måndag 7 maj
Kapitel 5-6.
S10 torsdag 3 maj 13-15, E35
Talare: Anna Redz och Douglas Wikström
PCP: genomskinliga långa bevis (avsnitt 7.1)
S11 fredag 4 maj 15-17, E36
Talare: Jonas Holmerin och Mårten Trolin
PCP: nästan genomskinliga korta bevis (avsnitt 7.2)
S12 måndag 7 maj 13-15, E36
Talare: Glenn Lawyer och Jonas Sjöstrand
PCP: det sista beviset (avsnitt 7.3)
S13 torsdag 10 maj 13-15, E32
Talare: Viggo
Approximationsbevarande reduktioner: definition av reduktion, NPO-fullständighet (avsnitt 8.1-8.3)
S14 måndag 14 maj 13-15, E36
Talare: Viggo
Approximationsbevarande reduktioner: APX-fullständighet (avsnitt 8.4)
S15 torsdag 17 maj 13-15, E32
Talare: Henrik Bäärnhielm och Gustav Grundin
Heuristiker (kapitel 10)
Hemtal 4, senast tisdag 5 juni
Kapitel 7-8 och 10.

Seminarier

Kursen är en seminariekurs där Viggo håller sex av seminarierna. Övriga nio seminarier förväntas hållas av kursdeltagarna, två eller tre talare per gång, beroende på hur många som vill tala. Det är frivilligt att hålla ett seminarium, men det ger poäng och är dessutom obligatoriskt för högre betyg (se nedan). Anmälan om intresse att hålla ett seminarium ska lämnas till Viggo under kursens första vecka.

Viggo ger varje talare upp till 20 poäng. Bedömningen grundar sig på följande kriterier:

Dom två eller tre som ska tala vid samma seminarium fördelar tillsammans materialet (se detaljschemat) mellan sig och får själva välja vilket upplägg seminariet ska ha, till exempel om talarna ska tala efter varandra, varvat eller tillsammans.

Kursregistrering

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

res checkin semteo01

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 semteo01

Detta kommando gör att du får se eventuella nya meddelanden från kursledaren varje gång du loggar in.
När du är klar med kursen ger du kommandot

course leave semteo01

Endast dom teknologer som studievägledningen lagt in i Ladok som studerande på en kurs kan godkännas på kursen. Vill du läsa en kurs som inte är obligatorisk för dig måste du alltså först välja kursen i KTHs valsystem eller vid ditt programs studievägledning.

Obligatoriska moment och slutbetyg

Kursen har bara ett moment i Ladok, nämligen ÖVN1, 4 poäng. Examinationen görs genom fyra skriftliga hemtal. Varje hemtal består av flera uppgifter och kan ge upp till 25 poäng. Den som håller ett seminarium under kursen får upp till 20 poäng till.

Betygsgränserna är
KTHSU
betyg 340-59betyg G40-69
betyg 460-79betyg VG70-120
betyg 580-99
betyg 6100-120

För att få betyg 5, 6 eller VG krävs dessutom att man håller ett seminarium.

Hemtalen får göras i tvåmannagrupper, men individuella lösningar måste lämnas in. Skriv i så fall överst på lösningen vem du har samarbetat med. Vissa uppgifter på hemtalen är extra svåra och därför stjärnmärkta. Det går inte att få betyg 6 utan att ha fått full poäng på minst en stjärnmärkt uppgift.

Den som inte nått godkänt efter att det sista hemtalet lämnats in måste göra en uppsättning helt nya hemtal för att få godkänt.

Hederskodex

Grundregeln är att det jobb du gör i kursen (labbar, inlämningsuppgifter, tentor m.m.) ska du göra själv, förutom att labbarna kan göras i tvåmannagrupper. Vid redovisning av labbar ska båda i gruppen kunna redogöra i detalj även för vad labbkompisen skrivit.

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.

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. Mer om fusk vid examination kan du läsa om här.

Synpunkter på kursen

Lämna gärna synpunkter på kursen till Viggo. En datorstödd kursutvärdering kommer att utföras.

^ Upp till kursens ingångssida.


Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Senast ändrad 27 september 2002
Tekniskt stöd: <webmaster@nada.kth.se>