Beskjeder

Publisert 13. juni 2019 15:03

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.

Publisert 12. juni 2019 16:35

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.

Publisert 6. juni 2019 00:24

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.

Publisert 23. mai 2019 23:12

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.

Publisert 22. mai 2019 14:55

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.

 

 

Publisert 8. mai 2019 19:05

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.

Publisert 6. mai 2019 10:27

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.

Publisert 30. apr. 2019 17:22

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.

Publisert 29. apr. 2019 01:09

Oppgaver til neste gruppetime er følgende fra Sipser:

8.5, 8.7, 8.18, 8.19, 8.29

Publisert 25. apr. 2019 20:58

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.

Publisert 25. apr. 2019 13:31

Den tredje (og siste) obligatorisk oppgaven har nå blitt lagt ut. Fristen er 10. mai kl. 23:59.

Oppgaven kan finnes her, og LaTeX-kildekoden kan finnes her.

Publisert 8. apr. 2019 18:33

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!

Publisert 3. apr. 2019 20:05

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).

Publisert 1. apr. 2019 19:19

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.

Publisert 30. mars 2019 14:50

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

Publisert 27. mars 2019 21:14

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.

 

Publisert 22. mars 2019 22:29

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!

Publisert 22. mars 2019 21:42

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.

Publisert 16. mars 2019 11:55

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.

Publisert 14. mars 2019 15:07

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.

Publisert 9. mars 2019 12:46

5.1 - 5.3,

5.16 - 5.19 og

5.33 - 5.35

Publisert 7. mars 2019 20:48

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.

Publisert 6. mars 2019 19:48

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.

 

Publisert 2. mars 2019 11:25

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

Publisert 28. feb. 2019 15:24

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.