Beskjeder

De som har fått godkjent alle 3 obliger skal nå ha fått status "Qualified for final exams" i Devilry. Gå inn på "Active semester" og se under INF2080. Hvis du oppdager feil må du snarest ta kontakt med Andreas Nakkerud (andreana).

Fra og med tirsdag 30. april erstattes forelesningene av repetisjonsforelesninger. Repetisjonsforelesningene er samme tid og sted som ordinære forelesninger. Plan for repetisjonsforelesningene er lagt ut på semestersiden.

Kurset siste forelesning har funnet sted. Jeg vil snart informere om hva som blir pensum i fra del III av Sipsers bok. (Det blir stort sett kap. 7, kap. 8 og seksjon 9.1 og 9.2 fra kap. 9)

Takk for nå

Lars

Ukeoppgaver fra Sipsers bok: 9.6, 9.9, 9.11, 9.20, 9.21 og 9.23.

De som ønsker en ekstra utfordring kan forsøke seg på 9.17 og 9.18.

Jeg er nå ferdig med å forelese kapittel 8. Jeg har begynt å forelese fra kapittel 9. Jeg vil starte forelesningene neste uke ved å se på beviset for Teorem 9.10 (Space Hierarchy Theorem). Siste forelesning er onsdag i neste uke (den 24. april).

Ukeoppgaver fra Sipsers bok: 7.21 (side 324), 7.37 (side 326), 8.32, 8.33 (side 360), 9.1, 9.2, 9.3 (side 389).

De som trenger en ekstra utfordring kan også prøve seg på 7.30 og 8.34.

Neste uke vil jeg forelese over seksjon 8.6 i læreboken. Deretter begynner jeg på kapittel 9.

Ukeoppgaver fra Sipsers bok: 8.5, 8.7, 8.11, 8.19 og 8.23.

(8.23 er vanskelig, men det finnes et løsningsforslag i boka.)

De som trenger en ekstra utfordring kan også prøve seg på 8.12. Dette se ut til å være en meget  vanskelig oppgave. Man kan jo starte med å vise at UCYCLE er i NL.

Definisjonen av coNP i den tredje obligatoriske oppgaven ble ikke ble som den skulle. Feilen er nå rettet opp. Pass på å laste ned siste versjon av oppgaveteksten fra:

http://folk.uio.no/larsk/oblig2080.pdf

Ukeoppgaver fra Sipsers bok: 8.2, 8.3, 8.4 og 8.27.

De som trenger en ekstra utfordring kan også prøve seg på 8.24 og 8.25 i Sipsers bok.

Så er det snart påske. Neste forelesning blir tirsdag 2. april!

Jeg er nå ferdig men å forelese fra kapittel 7 i Sipsers bok. Etter påske begynner jeg å forelse fra kapittel 8.

Jeg gir ikke nye ukeoppgaver. Bruk tiden dere har til rådighet til å arbeide med den obligatoriske oppgaven og gamle ukeoppgaver som dere ikke er ferdig med.

Kursets tredje og siste obligatoriske oppgave finner du her:

http://folk.uio.no/larsk/oblig2080.pdf

Innleveringsfristen er fredag 19. april.

STUDENTSEMINAR

Vi fortsetter med seminar med pizza att?t.

Lars Kristiansen : Det tellbare og det overtellbare.

Torsdag 21.03.2013 kl 1615 5.etasje OJD

Husk ? melde deg p? med skjemaet under

https://nettskjema.uio.no/answer/logidstudsem2013w12.html

OBLIG 2

F?tt beskjed om at mange er forvirret over bruk av fargene i oppgaven. De fargene jeg har brukt i presentasjonen er bare ment for ? gi pene figurer. Anta at du har en turing maskin med m symboler og n tilstander. Jeg har brukt 5 ulike flistyper. Da trenger du

m farger for ? gi flistype 1 - de svarer til symboler p? tapen der lesehodet ikke er

m x n nye farger for ? gi enten flistype 2 eller 3 - de svarer til ruter der lesehodet er med symbol lest og tilstand. I tillegg trenger du ogs? fargene for symboler og for tilstander.

n nye farger for ? gi flistype 4 eller 5 - de svarer til flistyper som er med til ? skifte lesehodet til enten h?yre eller venstre til neste rad

Du trenger alts? mange farger - langt fler enn de som er p? figurene.

UKEOPPGAVER: Fortsett med oppgavene som ble gitt i forrige uke dersom du ikke er ferdig med dem. Videre kan du pr?ve deg p? 7.43, 7.44, 7.48, 7.49, 7.50 (s. 327 og 328).

Tex-kode

Jeg har lagt ut latex-koden for oblig-2 til hjelp for de som vil bruke grafikken i oblig-2 i besvarelsen. - H

Foredrag 07.03

Hele foredraget er lagt ut

UKEOPPGAVER: 7.1, 7.3, 7.5, 7.6, 7.7, 7.8, 7.9, 7.10 (side 322-323). De som ?nsker en ekstra utfordring kan pr?ve seg p? 7.41 (side 327).

Denne uken har jeg forelest seksjon 7.1, 7.2 og det meste av seksjon 7.3 i Sipsers bok. Nest uke begynner jeg ? forelese seksjon 7.4.

I dag starter forelesningen om kompleksitetsteori. Jeg heter Lars Kristiansen og skal holde forelesningene. Min mailadresse er larsk@math.uio.no .

FOREDRAG 7 mars - 1615 - 5 etasje OJD

Hei,

Kan du legge ut denne lenken

https://nettskjema.uio.no/answer/logidstudsem13w10.html

p? semestersidene til INF2080? De som vil ha pizza m? melde seg p? s? vi vet hvor mange de er.

• Andreas

UKEOPPGAVER

5.1, 5.2, 5.3, 5.33, 5.34, 5.35

Ekstra utfordring: 5.19

OBLIG 2

Andreas fant et par problemer med v?re fliser. Som et resultat kutter vi ut

• de to siste punktene p? oppgave 6
• oppgave 8

Dere kan jo pr?ve ? finne ut hva problemet var - jeg tenkte ikke p? det. Men det er ikke en del av obligen.

OBLIG 2

En av studentene p? gruppetimen gjorde meg oppmerksom p? at det i figuren p? oppgave 1.2 mangler en pil p? en av overgangene (den fra 1 til 3).