Beskjeder

S?ndag 31. mai arrangerer LogID-gruppen eksamensverksted for INF2080-studentene. Det blir servert pizza etter verkstedet. Mer info finner du i p?meldingsskjemaet.

En oversikt over l?rebokpensum og ukeoppgaver er lagt ut under undervisningsmateriale. I tillegg til pensum i l?reboken og ukeoppgavene regnes for pensum de obligatoriske oppgavene og alt som har blitt gjennomg?tt i forelesningene.

Pensum i kompleksitetsteori er kapittel 7, kapittel 8 og de to f?rste seksjonene av kapittel 9 (Sipsers bok). Stoff som har v?rt forelest grundig er mer relevant med tanke p? eksamen enn stoff som har v?rt forelest overfladisk. Ukeoppgaver og obligatoriske oppgaver gir ogs? en gode pekepinn p? hvordan man skal forberede seg til eksamen.

Forelesningene 12. og 13. mai er avlyst. Den 13. mai vil vi i steden gjennomg? l?sningsforslag p? oblig 3. De som er usikre p? om de f?r f?rste fors?k p? oblig 3 godkjent b?r komme, da fristen for 2. fors?k til v?re tirsdag 19. mai.

Eksamensoppgavene fra 2013 og 2014 er lagt ut. Vi har ogs? lagt ut lenker til interessante, relevante artikler (disse er ikke pensum).

Jeg er n? ferdig med ? forelese kap. 8 i Sipsers bok. Stoffet  i seksjonene 8.4, 8.5 og 8.6 har blitt grundig forelest. I morgen (onsdag 29. april) begynner jeg ? forelese kap. 9.

Oblig 3 er lagt ut. Innleveringsfrist er 8. mai. Norsk versjon av oppgaveteksten finnes her, men merk at oppgavenummereringen er endret (gamle oppgave 2 har blitt flyttet til slutten).

Takk til Kristoffer for l?sning p? premioppgave 4. Neste premieoppgave er 7.29 i Sipser (oppgave om SET-SPLITTING).

Jeg er n? ferdig med ? forelese kap. 7. Nest uke begynner jeg ? forelese kap. 8 (Space Complexity).

Denne uken har vi brukt mye av forelesningstiden til f?lgende: (1) p-redusere 3SAT til HAMPATH, (2) p-redusere 3SAT til SUBSET-SUM og (3) vise at SAT og 3SAT er NP-komplette spr?k.

Mvh

Lars

Noen sm? feil i UniversalTM.java gjorde at tapen ikke kunne bli lengre enn den begynte med, og at tom input ikke fungerte. Feilene er n? rettet opp og ny kode ligger ute.

Dersom det er feil eller mangler i koden du leverer kan du kommentere dette i en README.txt-fil.

Denne uken har vi snakket om NP og NP-komplette spr?k. Vi har vist at k-CLIQUE og HAMPATH er i NP. Vi har vist at at 3SAT er polynom-tid reduserbart til k-CLIQUE.

Neste forelesning vil jeg bruke en del tid p? vise at 3SAT er polynom-tid reduserbart til HAMPATH. Dette er et vanskelig bevis som vi skal g? grundig gjennom. Det kan v?re en god ide ? forberede seg ved ? lese sidene 314-318 i l?reboken. Deretter vil jeg g? grundig gjennom  bevisene for at spr?kene SAT og 3SAT er NP-komplette. Dette er ogs? vanskelige bevis, og  det kan v?re en god ide ? forberede seg  ved ? lese litt i l?reboken f?r man kommer p? forelesning.  Deretter vil se p? flere NP-komplette spr?k (SUBSET-SUM, UHAMPATH). Jeg regner med ? gj?re meg ferdig med ? forelese kapittel 7 i l?pet av de to-tre  neste forelesningene.

God p?ske

Lars

Takk til Arne Tobias for denne l?sningen av premieoppgave 3. Premieoppgave 4 er oppgave 4.22 i Sipser.

Jeg har begynt ? forelese kapittel 7 i Sipsers bok. S? langt har jeg forelest de tre  f?rste seksjonene av kapittelet (s?nn circa). Jeg har ikke snakket  om liten-o-notasjon. Vi vil ikke ha behov for liten-o-notasjon f?r mot slutten av kurset.

Mvh

Lars

The Turing Machines you make must be single tape, deterministic TMs, that work on a tape that is infinite to the right (and not to the left), that is, they cannot read to the left of start.

Dagens gruppetime (fredag 13. mars) er avlyst. Rommet er fortsatt reservert for de som ?nsker ? bruke det.

Oblig 2 er lagt ut. Innleveringsfrist: 27. mars klokken 23:59.

Premieoppgave 3 er oppgave 3.13. Takk til Bj?rn for l?sning p? premieoppgave 2.

L?sning og neste oppgave blir presentert p? fredag, og deretter lagt ut her.

Kristoffer Th?mt Ravneberg har l?st f?rste premieoppgave (Sipser: oppgave 1.38). Dermed blir det servert snacks fredag 20. februar. Neste premieoppgave er oppgave 2.33 i Sipser.

The group session on Friday, Feb. 13, will take place from 12:15-14:00 in Logo. 

F?rste obligatoriske oppgave ligger n? ute. Innleveringsfrist er 27. februar klokken 23:59. Oppgaven leveres i Devilry. P? gruppetimene kan du f? hjelp til ? komme i gang med oppgavene. De som ?nsker ? skrive oppgaven i LaTeX kan finne eksempler i oppgavens kildefil.

Semesterets f?rste premieoppgave blir oppgave 1.38. Hver gang noen l?ser en premieoppgave vil det bli kake, frukt og/eller godteri p? p?f?lgende gruppetime, pluss en liten ekstra premie til den eller de som f?rst l?ste oppgaven. Ny premieoppgave annonseres etter den f?rste blir l?st. Kontakt Andreas dersom du har l?st premieoppgaven. Lykke til!

Andreas er v?rfast i Boston, s? torsdagens (29. januar) gruppetime er avlyst. Gruppetimen p? fredag g?r som normalt, og plenumsregningen for b?de torsdag og fredag blir holdt da.