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.