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