Beskjeder
N? er l?sningsforslaget til eksamen lagt ut. Husk at til de fleste oppgaver finnes det flere mulige riktige l?sninger, og det som er vist her er kun en mulig l?sning. Det kan ogs? godt hende at det er feil i disse l?sningene. Hvis dere finner noen feil, ta gjerne kontakt s? skal vi rette opp i det.
Jeg h?per at dere gjorde det bra p? eksamen i g?r. Teksten til eksamen er n? lagt ut under tidligere eksamensoppgaver. I l?pet av morgendagen vil det ogs? bli lagt ut et l?sningsforslag.
Vi tar litt eksamensforberedelse p? l?rdag 8. juni fra 12-16. Vi kommer til ? se p? litt gamle eksamensoppgaver og begge gruppel?rerne er der for ? svare p? sp?rsm?l om alt mulig. M?t opp ved seminarrom Prolog.
Gruppetimen i morgen (fredag 24. mai) er den siste gruppetimen dette semesteret.
Vi skal se p? f?lgende oppgaver fra Sipser:
9.1-9.3, 9.6, 9.9, og 9.10
Disse oppgavene bruker det vi har l?rt i kapittel 9.1 og 9.2, som er siste delen av pensum for eksamen.
F?lgende fra Sipsers bok skal betraktes som pensum:
- Kap. 1 (hele)
- Kap. 2, seksjonene 1, 2 og 3, dvs., side 101-129
- Kap. 3 (hele)
- Kap. 4 (hele)
- Kap. 5 (hele)
- Kap. 7 (hele)
- Kap. 8 (hele)
- Kap. 9, seksjonene 1 og 2, dvs., side 364-379.
P? gruppetimen p? fredag (10. Mai) vil vi jobbe med tidligere eksamensoppgaver. Spesifikt skal vi se p? f?lgende oppgaver:
Oppgave 7-9 fra eksamen 2016
Oppgave 3.1-3.3 fra eksamen 2017
Husk ogs? at siste obligen har frist samme fredag. Dere kan stille sp?rm?l om denne i gruppetimen.
P? grunn av d?rlig oppm?te blir det ikke gjennomf?rt noen flere plenumsregninger dette semesteret. Men det blir fortsatt lagt ut l?sningsforslag innen tirsdagen etter gruppetimen.
PS: Husk at obligfristen er fredag 10. mai.
Jeg er n? ferdig med ? forelese kapittel 8.
To forelesninger st?r igjen. De vil finne sted den 21. og 22. mai.
Den 21. mai vil jeg snakke litt om hva som st?r i de de to f?rste seksjonen av kapittel 9. Den 22. mai vil jeg gi en oppsummering av kurset og snakke litt om eksamen.
Oppgaver til neste gruppetime er f?lgende fra Sipser:
8.5, 8.7, 8.18, 8.19, 8.29
P? gruppetimen i morgen (26. april) vil dere f? mulighet til ? jobbe med og stille sp?rsm?l om oblig tre. I tillegg skal vi se p? noen f? oppgaver fra Sipser:
8.2-8.4, 8.6, 8,26, og 8.27.
De fleste skal v?re greie ? l?se. Jeg planlegger ? ta noen av oppgavene p? tavla.
Ukeoppgavene for neste gruppetime vil bli lagt ut i morgen, slik at dere f?r en uke til ? se p? dem som vanlig.
Det er avlyst to forelesninger - en f?r og en etter p?ske. Derfor avlyses ogs? gruppetimen p? fredag 12. april, slik at gruppetimene f?lger progresjonen i forelesningene. Neste gruppetime blir da 26. april.
De som ikke gikk gjennom del 2 av eksamen 2015 i forrige gruppetime oppfordres igjen til ? pr?ve seg p? det hjemme. Det er lagt ut l?sningsforslag p? noen av oppgavene.
God p?ske!
Jeg har n? forelest kapittel fram til seksjon 8.4 p? side 348. Alt stoffet i tre f?rste seksonen av kapittelet har bli forelest ganske grundig med unntak av beviset av teorem 8.9 (TQBF is PSAPCE-komplete). Jeg har ikke forelest dette beviset, og det er ikke aktuelt ? stille sp?rsm?l knyttet til dette beviset p? eksamen.
Neste forelesning starter jeg p? seksjon 8.4. Vi bruke mye forelesningstid p? seksjon 8.4, 8.5 og 8.6 (selv om disse seksjonen tilsammen kun best?r av litt over 8 sider).
Forlesningen tirsdag 9. april er avlyst.
Forelesningen tirsdag 23. april er avlyst.
Den 16. og 17. april blir det heller ikke forelesninger p? grunn av p?skeuken.
Dermed blir det forelesninger p? f?lgende datoer i april:
2., 3. 10, 24. og 30.
Denne uken kan dere pr?ve dere p? oppgave 6-10 fra eksamen 2015, som handler om det siste vi har l?rt om kompleksitetsteori. Det har ogs? blitt lagt ut andre gamle eksamensoppgaver under mappen "tidligere eksamensoppgaver".
I tillegg har vi vanlige ukesoppgaver fra Sipser: 7.28, 7.29, og 7.30
Jeg er ferdig med ? forelese kapittel 7. Neste uke begynner jeg ? forelese kapittel 8 (Space Complexity). Kapittel 7 er et meget viktig kapittel med tanke p? eksamen. Stort sett alt i kapittel 7 har blitt forelest grundig.
Til gruppetimen neste uke har vi disse oppgavene, i tillegg til oppgave
7.7, 7.35, 7.37, 7.45, 7.47, og 7.49 fra Sipser.
NB: Oppgavene om coNP-kompletthet i PDF-en er veldig relevante for neste oblig!
Jeg har n? forelest fram teorem 7.37 p? side 304. Nest uke vil jeg forelese resten av kapittel 7. Alt i kapittel 7 er viktig med tanke p? eksamen.
Til neste gruppetime har vi oppgaver fra b?de kap.5 og kap.7.
5.5 - 5.7, 5.10, 5.11
7.1, 7.5, 7.6, 7.8, 7.13
Det er litt flere enn vanlig, men de fleste skal v?re greie ? l?se.
Jeg har begynt ? forelese kap. 7. Jeg er s?nn circa ferdig med seksjon 7.2 og vil begynne ? forelese seksjon 7.3 f?rstkommende tirsdag.
Det blir ingen plenumsregning p? mandag 11. mars (og det blir heller ikke lagt ut l?sningsforslag), siden oppgavene som er gitt til denne uken er kun ment som ekstra utfordringer.
Denne uken har jeg forelest seksjon 5.1 og 5.2. Seksjon 5.2 ble forelest grundig. Jeg snakket ogs? en god del om stoffet i seksjon 5.1 (nesten en dobbelttime), men jeg hoppet over mange av teoremene og nesten alle bevisene (et unntak er Teorem 5.1 med bevis).
Neste uke vil jeg forelesne seksjon 5.3. Jeg regner med ? bruke ca. en time p? det. Deretter vil starte ? forelese del tre av boken (Kompleksitetsteori. Vi skal igjennom kap. 7 og 8, og muligens noe fra kap. 9, f?r vi gir oss).
Kapittel 6 er ikke pensum og vil ikke bli forelest. Alt i kapitell 5 er fors?vidt viktig med tanke p? eksamen, men det vil ikke bli gitt oppgaver som er n?rt relatert til de teoremene jeg hoppet over i seksjon 5.1.
Siden det ikke ble forelest noe nytt pensum forrige uke bruker vi neste gruppetime p? ? jobbe med oblig 2, samt gamle ukesoppgaver for dem som ?nsker det.
Dere kan ogs? pr?ve dere p? disse litt ekstra utfordrende oppgavene fra de f?rste fire kapitlene:
1.48, 1.52, 2.35, 2.54, 3.14, 4.12, 4.14, og 4.17
Oblig 2 er n? publisert og kan finnes her. Tidsfristen for innlevering er fredag 15. mars, klokken 23:59. Til obligen skal dere bruke en Turingmaskin-simulator som kan finnes her: https://github.com/torenord/universaltm.