Beregnbarhets- og kompleksitetsteori - høsten 2014

Kursbeskrivelse finnes i studiehåndboka.

• Mandag 13.15–15.00 rom 822 SII
• Torsdag 8.15–10.00 rom 822 SII
• Fredag 8.15–10.00 rom 822 SII
• En av dobbeltimene blir brukt til øvingsgjennomgang. Førtse forelesning torsdag 21. august.
• Det blir ingen forelesning torsdag 18/9 og fredag 19/9. Oppgaver blir gjennomgått mandag 22/9.

Øving 1: Martin; Oppgave 1.1, 1.12, 1,20, 1.36, 1.56, 1.60 og 1.67.

Øving 2: Oppgave 1.24, 1.32, 1.43, 1.44, 1.63, 2.1 a,e,f,h, 2.4, 2.5 og 2.9.

Øving 3: Oppgave 2.12 e,f, 2.13, 2.18, 2.21 c,d, 2.22, 2.30, 2.44, 2.57 a,i,k,m, 2.62 d,e,f, 3.1.

Øving 4: Oppgave 3.11, 3.12, 3.22, 3.37 a, 3.40 b, 3.54 a,b,c,d, 4.1, 4.3, 4.31 b.

Øving 5: Oppgave 4.34, 4.35, 4.47, 4.50 a, 4.54 a,b, 4.55, 5.1, 5.5, 5.8, 5.13.

Øving 6: Eksamen høst 01; 1, 2 og 3. Eksamen vår 03; 3 og 7. Fra Boka; 7.1, 7.2 og 7.3.

Øving 7: Oppgave 7.4, 7.10, 7.16, 7.7 a,b og c, 7.18 og 7.26.

Øving 8: Oppgave 7.27, 7.28 a og b, 8.1, 8.2, 8.3, 8.4, 8.8 og 8.13.

Øving 9: Oppgave 8.41, 8.42, 9.1, 9.4, 9.5, 9.6 og 9.12.

Øving 10: Oppgave 10.1, 10.10, 10.11, 10.12, 10.13 og 10.14.

Øving 11: Eksamen v03 oppgave 6, Eksamen v06 oppgave 6 og 8, Boka: 11.3 og 11.9.

Øving 12: Eksamen V06 oppgave 8, Eksamen V05 oppgave 3, Eksamen V08 oppgave 3 og 5.

Øving 13: Eksamen 01 oppg.4; v03 oppg. 1,2b og 4a; v06 oppg.1 og 5; v08 oppg.1; v10 oppg.1,2,3,4,5 og 6.

Øving 14: Eksamen 12, hele settet.(finnes øverst på siden)

• Sverre O. Smalø sverresm [at] math [dot] ntnu [dot] no
  Treffetid: mandager 15-17, Rom 850 i SB2.

• 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

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 15. desember med tillatte hjelpemidler C. Ikke at dere har noen som helst bruk for den, men SR-270X College er lovlig å ha med.

Tentativ