Beregnbarhets- og kompleksitetsteori - høsten 2012

Kursbeskrivelse finnes i studiehåndboka.

• 12. juni 2012: Siden er under konstruksjon.
• 18. juli 2012: Det var en feil i timeplanen. Forelesninger er mandag og tirsdag.
• 20. august 2012: I morgen blir det mer om rekursiv definisjon og strukturell induksjon. Jeg lover at ting blir klarere etterhvert. Øving 1 er lagt ut. Vi gjennomgår den førstkommende onsdag.
• 23 august 2012: Løsning på øving 1 er lagt ut. Notat om sterk og vanlig induksjon (notat 7) er også lagt ut for spesielt interesserte lesere.
• 24 august 2012: Mandag fortsetter vi i Kapittel 1. og forhåpentligvis begynner vi også med Kapittel 2. Jeg vil også forsøke å gjøre Notat 1 forståelig. Øving 2 er også lagt ut.
• 27 august 2012: Notat 1 er rettet opp litt. Tirsdag 4. september blir det ikke forelesning. Jeg kommer heller ikke til å være til stede på øvingen onsdag 5. september, men det blir øving.
• 30 august 2012: Mandag vil jeg forsøke å gå gjennom resten av kapittel 2. Det dreier seg om uskillbarhet(deriverte språk), Pumpelemmaet og minimalisering. Det står litt om dette i Notat 2. Jeg akter å skrive det om så det blir litt mer leselig.
• 08 september 2012: En løsning, uten noen forklaring, på den siste oppgaven i øving 3 er lagt ut. Detaljer får dere på forelesningen mandag.
• 13 september 2012: Notat 8, som handler om eliminasjonsmetoden er lagt ut. Øving 5 er lagt ut.
• 14 september 2012: Noen småfeil i Notat 8 er fikset.
• 23 september 2012: På forelesningen i morgen går vi gjennom Notat 9. Blir det mer tid konstruerer vi push down automaten til en kontekstfri gramatikk (fra toppen og ned).
• 01 oktober 2012: Notat 9 er korrigert. Øving 7 er lagt ut. Mer om Turingmaskiner og spesielt om universelle Turingmaskiner på forelesningen i morgen.
• 08 oktober 2012: Øving 8 er lagt ut. I morgen: Vi bruker reduksjon til å vise at stoppeproblemet er uavgjørbart.
• 17 oktober 2012: Øving 10 er lagt ut. Mandag 22.10 starter vi på kapittel 10.
• 05 november 2012: I dag ble vi ferdig med Cook-Leven teoremet, slik det er skissert i Notat 5. Noen trykkfeil i dette notatet er fikset. Resten av tiden vil jeg bruke til repetisjon og oppgaveløsning.

• Mandag 10.15-12, K27 (Første gang 20.08.2012.)
• Tirsdag 9.15-10, K27

• Onsdag 14.15-16, K27

• Finn F. Knudsen
  Treffetid: mandager 12-14.

• John C. Martin, "Introduction to Language and Theory of Computation" 4. utgave.

• Rebecca Weber, "Computability Theory".
• S. B. Cooper, "Computability Theory".
• Den offisielle turingsiden
• On Computable Numbers eller klikk her
• Dag Normanns notater

• Notat 1 (oppdatert 27.08.2012)
• Notat 2 Om deriverte språk og standardautomaten til et språk. Minimeringsalgoritmer. Se siste side for en enkel algoritme.
• Notat 3 Dette notatet er et kompendium skrevet av Lars Kristiansen i Oslo. Det inneholder blant annet noen refleksjoner over Turings tese kontra Turings teorem. Videre er det en norsk oversettelse av deler av Turings artikkel "On Computable Numbers". Det begynner på side 25.
• Notat 4 Disse forelesningsnotatene er svært forseggjordte. Turingmaskinene her beveger seg på et eller flere bånd som er ubegrensede i begge retninger. Der har noen fordeler og noen bakdeler. Beviset her for at SAT er NP-komplett går via en dominolek som jeg er fristet til å kopiere, men igjen kanskje ikke.
• Notat 5
• Notat 6
• Notat 7 Dette notatet går nok litt ut over pensum, men dersom du ønsker å forstå det, er det bare å gå i gang å lese det. Egentlig er det ikke så vanskelig.
• Notat 8 Her er eliminasjonsmetodener forklart, og det er bevis for at den gir et regulært uttrykk med samme språk. Metoden er illustrert med et ikke helt trivielt eksempel. Oppdatert 16.09.2012 kl. 23:40
• Notat 9 Dette handler om avgjørelsesproblemet for kontekstfrie språk. Vi bruker Chomsky normalform og den dynamiske algoritmen.

Noe kan virke litt ukjent fordi den gamle boka brukte litt andre konvensjoner.

• Hele boka utenom følgende. Kapitlene 5, 6, 8.3 og 8.4, 9,3, 9.5, 10.5, og 11.5.
• Notat 1, 2, 5, 6, 8 og 9.
• Øvingsoppgavene

Eksamensdato er 12. desember med tillatte hjelpemidler C. Ikke at dere har noen som helst bruk for den, men SR-270X College er lovlig å ha med.

Tentativ