Beskjeder
Det kan hende vi kikker litt på eksamen på forelesningen i morgen. Siste forelesning. Einar vil også komme.
Det blir ikke forelesninger neste uke. Tirsdag er det 17. mai og forelesningen 18. mai er avlyst.
- 8.6, 8.27 og 8.29
- 8.23
- deretter kan dere kikke på eksamen fra 2019
Her er eksamen fra 2019 med løsningsforslag.
Vi gir ingen nye ukeoppgaver denne uken. Gruppetimene neste uke kan brukes til å diskutere oppgaver som allerede er gitt eller den obligatoriske oppgaven.
Nå har jeg begynt å snakke om stoffet i kap. 8. I den digitale forelesning jeg har lagt ut for denne uken snakker jeg også del om coNP. Kompleksitetsklassen coNP står sentral i den tredje obligatoriske oppgaven.
Oppgaver til gruppetime torsdag 28. april:
- Eksamen 2017 (exam17.pdf): Oppgave 3.3
- Eksamen 2015 (exam15.pdf): Del II (oppgavene 7, 8, 9 og 10)
- Oppgave 7.29, side 325 i Sipsers bok.
Et utval av disse oppgave diskutere i gruppetimen.
Forelesningen den 27. april er avlyst på grunn av en begravelse.
Oppgaver til gruppetime torsdag 21. april: 7.7, 7.45, 7.47, 7.35, 7.37 samt oppgavene på denne pdf-filen.
Oppgavene på pdf-filen er meget relevante med tanke på neste oblig.
Et utvalg av oppgavene vil diskuteres i gruppetimen.
Jeg holder på å forelese kap. 7 i Sipsers bok. Neste forelesning vil starte med beviset av teorem 7.32 (side 202). Jeg antar da at tilhørerne er kjent med problemet 3SAT. Jeg bruke en del tid av siste forelesning før påsken til å forklare 3SAT.
Oppgaver til gruppetime torsdag 15. april (et utvalg av disse oppgavene vil bli diskutert i gruppetimen): 7.1, 7.5, 7.6, 7.7, 7.8, 7.13.
Dere bør også diskutere noen som er gitt tidligere hvis det er behov for det.
Oppgaver til neste gruppetime torsdag 31. mars (et utvalg av disse oppgavene vil bli diskutert i gruppetimen): 5.1, 5.2, 5.5-5.7, 5.10, 5.11, 5.16-5.19, 5.33-5.35
Oppgaver: 4.1--4.5, 4.8, 4.13, 4.19, 4.24, 4.29, 4.30.
Disse oppgavene (ikke nødvendigvis alle) vil diskuteres i gruppeundervisningen torsdag 24. mars.
Her er noen passende oppgaver om det stoffet jeg har forelest denne ukene: 3.1-3.3, 3.5-3.9, 3.15. Dere kan også prøve der på oppgavene 3.13, 3.16 og 3.17.
Så nå har jeg (Lars) overtatt forelesningene. I dag foreleste jeg seksjon 3.1 i Sipsers bok. I morgen vil jeg forelese sekskjon 3.2 (sånn circa).
Da ble vi enige om å utsette repetisjonen av del 1 av kurset til litt senere i semesteret. Dvs at det ikke blir forelesning i morgen, 2 mars.
Hei, jeg må dessverre avlyse forelesningene denne uken. Min tur til å bli syk. Vi fortsetter med Pumpelemma for CFL neste tirsdag!
- Einar
I morgen begynner vi på kontekst-frie språk på forelesningen. For de som ikke kan komme på de neste forelesningene, kan dere evt se på Sipsers video for å få en rask intro til materialet:
I dag starter vi med fysiske forelesninger i Stoe Aud, Kristen Nygårds Hus. Velkommen til forelesning.
For de som ikke kan komme, kan det være nyttig å se Michael Sipser's videoforelesninger fra i fjor:
Første gruppe (27. jan, 10.15) er på zoom. Vi kommer hovedsaklig til å gå gjennom oppgavene som ble lagt ut for forrige uke.
Join Zoom Meeting
https://uio.zoom.us/j/7835019196
Meeting ID: 783 501 9196