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.