Beskjeder

På søndag 5. juni fra kl. 12 er det eksamensverksted med repetisjon, regning av gamle eksamener og pizza. Det skal holdes på ifi i seminarrom C. De som har eksamensrett og vil bli med kan melde seg på her.

Det skal holdes repetisjonstimer hver tirsdag og torsdag før eksamen. Timeplanen finnes her. Dessuten finnes det eksamensrelevante oppgaver her. Lykke til!

Kursets siste forelesning finner sted i morgen (onsdag 4. mai).

Pensum i kompleksitetsteori blir kap. 7 og kap. 8 samt seksjon 9.1 og 9.2.

Gruppeundervisningen på torsdager fortsetter fram til eksamen. Det vil sannsynligvis  bli et arrangement dagen før eksamen (hvor det serves mat og løses oppgaver). Gruppelærerne kan gi mer informasjon om undervisningen framover.

Jeg er nesten ferdig med å forelese seksjon 8.3 i Sipser. Hele kap. 8 vil bli forelest relativt grundig, men jeg vil ikke si noe om beviset av Teorem 8.5 (Savitchs teorem) og Teorem 8.9 (TQBF er PSAPCE-komplett). Dette er viktige teoremer, men beviset av disse teoremene regnes ikke som pensum. Ellers så vil kjernepensum bestå av kap.7 og kap. 8. I tillegg vi noen utvalgte emner fra kap. 9 regnes som pensum.

Jeg regner med å bruke ca. havparten av neste forelesning på å gjøre meg ferdig med seksjon 8.3. Deretter vil jeg forelse seksjon 8.4, 8.5 og 8.6 i nevnte rekkefølge.

Jeg er nesten ferdig med å forelese fra kap. 7.  Neste uke vil jeg si litt om beviset av Corollary 7.43 (i kap. 7). Deretter vi jeg begynne å forelese kap. 8 (space complexity).

Husk at det er viktig å arbeide med ukeoppgave. Gruppelærerne forsyner der med egnede oppgaver.

Oblig 3 is now out!. As before, please submit your solutions in Devilry, the dealine is April 29, 23:59.

Jeg foreleser fortsatt fra kap. 7. Dette kapittelet foreleses grundig (og er dermed viktig med tanke på eksamen). Tirsdag den 5. april vil jeg gå gjennon beviset av Cook-Levins teorem.

Det blir ingen forelesning onsdag 6. april.

På forelesningene har vi brukt mye tid på å se hvordan 3SAT kan redusers til k-KLIQUE, og å se hvordan 3SAT kan reduseres til  SUBSET-SUM. I gruppeundervisningen vil det brukes tid på å studere hvordan 3SAT kan reduseres til HAMPATH. 

Tirsdag den 12. april vil jeg begynne å forelese kap. 8.

Mvh

Lars

En forbedret versjon av UniversalTM.java gitt i Oblig2 er nå tilgjengelig på https://github.com/torenord/universaltm. Denne versjonen skriver ut computation history mens koden kjører som gjør det enklere å se hvordan maskinen oppfører seg. Filformatet er også utvidet slik at det nå er mulig å legge inn kommentarer i turingmaskinfilene noe som burde gjøre det litt enklere å holde oversikt. Legg gjerne inn issues eller pull requests på repoet på Github hvis det er noe som er feil eller som kan forbedres.

 -- Tore Norderud

Denne uken har jeg forelest stoff fra kap. 7 i Sipser. Jeg har sagt
 det jeg har å si om de tre første seksjonene (7.1, 7.2 og 7.3). Neste forelesning starter jeg på seksjon 7.4.

Mvh

Lars

Oblig 2 is now out! As before, please submit your solutions in devilry, deadline is March 20, 23:59. 

Contrary to what I said in the lecture, the oblig will be posted some time tomorrow due to some technical difficulties.

A sample solution/explanation of the first challenge can be found here.

We have received multiple submissions for the last challenge, many of which were correct, some of which were extremely close! A sample solution will be posted some time this week. So on to the next challenge:

Let A be a set of natural numbers, and k a natural number greater then one. Define

B_k(A)= {w | w is the representation in base k, without leading zeros, of some number in A}.

For example: B₂({3,5})={11,101} and B₃({3,5})={10,12}. Give an example of a set A for which B₂(A) is regular and B₃(A) is not regular (with proof). 

Due to sickness, the lecture on Wed. Feb 10 is cancelled.

As already announced in the grubletimer, there will be a series of challenges throughout the semester. Lucrative prizes (e.g., chocolate) await the winners!

The first challenge: Construct a finite automaton (DFA, NFA, all-NFA) that accepts the following language with as few states as possible:

L={a^120k | k >=0 }

The first submission of a correct automaton with less than 18 states wins! Submisions can be handed in during the lecture, group sessions, or by email. Good luck!

Grubletimen på fredag den 5. februar skal holdes kl. 14:15-16:00, OJD Seminarrom C, ikke kl. 8:00!

Grubletimen på fredag den 29. jan. skal holdes kl. 14:15-16:00, OJD Seminarrom C, ikke kl. 8:00!

Oblig 1 ligger nå ute. Innleveringsfrist er 19. 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.