Beskjeder

Publisert 31. mai 2016 11:30

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.

Publisert 5. mai 2016 21:20

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

Publisert 3. mai 2016 17:33

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.

 

Publisert 13. apr. 2016 14:58

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.

 

 

Publisert 10. apr. 2016 14:29

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.

 

Publisert 8. apr. 2016 14:22

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

Publisert 4. apr. 2016 00:38

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

 

 

Publisert 16. mars 2016 15:52

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

Publisert 16. mars 2016 14:22

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

Publisert 5. mars 2016 20:18

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

Publisert 4. mars 2016 19:47

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

Publisert 25. feb. 2016 16:55

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

Publisert 15. feb. 2016 11:02

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

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

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

Publisert 10. feb. 2016 00:07

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

Publisert 4. feb. 2016 17:29

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={a120k | 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!

Publisert 4. feb. 2016 17:25

 

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

Publisert 27. jan. 2016 17:37

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

Publisert 27. jan. 2016 17:34

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.