Beregnbarhets- og kompleksitetsteori - høsten 2010

Kursbeskrivelse finnes i studiehåndboka.

Beskjeder

  • 10. desember 2010: Eksamen høsten 2010. Oppgavesettet, og løsningsforslaget.
  • 8. desember 2010: Mange har spurt om hva som er de spesielle hjelpemidlene som er nevnt i beskrivelsen av Hjelpemiddelkode C. I dette emnet er det ikke noen spesielle hjelpemidler. Jeg kommer en runde på eksamen. Under regning av oppgavene oppdaget jeg to små trykkfeil i oppgave 3. De er ganske opplagte, men jeg vil si i fra om dem på eksamensdagen.
  • 28. november 2010: Tar med Notat 6 også i pensumlista. Det er ikke egentlig noe nytt her. Det er bare ment som litt hjelp til å forstå boka.
  • 23. november 2010: En student gjorde meg oppmerksom på at det ble en liten konflikt mellom bokas definisjon av Lq nederst på side 73 og min definisjon av Lq, Definisjon 6 i Notat 2. Dette er nå rettet opp og forklart bedre. Min term heter nå Rq. Se her.
  • 22. november 2010: Jeg fikk ikk gjordt repetisjonen av stoppeproblemet slik som jeg skulle ønsket på siste forelesning den 18. november. Notat 6 er en kort skisse av beviset for at stoppeproblemet for Turingmaskiner er uavgjørbart.
  • 17. november 2010: Jeg oppdaget litt sent at uke 47 også er med dette semesteret. Den uka blir selvstudium. Se gjerne gjennom øvingsoppgavene, og kom og spør meg om hva som helst, eller send e-post. (72593523 eller 91634712)
  • 17. november 2010: Merk at pensum består av boka, Notat 1,2 og 5, samt øvingsoppgavene.
  • 16. november 2010: Løsningsforslaget til øving 13 er lagt ut.
  • 11 november 2010: Øving 13 er lagt ut.
  • 9 november 2010: Korrigert løsning 11 er lagt ut. Karin har mye av skylda for denne.
  • 8 november 2010: Forslag til noen oppgaver til i morgen. Eksamen vår 05 oppgave 3, Eksamen vår 08 oppgave 3(vis også at dette språket ikke er regulært.) og oppgave 5.
  • 6. november 2010: Notat 5 er endelig ferdig, men det kan tenkes det fremdeles er ting jeg vil forandre litt. Notat 5.
  • 2. november 2010: Notat 5 er vesentlig korrigert. Denne versjonen er både kortere og bedre. Det var en kommentar fra Karin som fikk meg til å innse at forrige versjon ikke var brukbar.
  • 2. november 2010: Det var en trykkfeil i øving 11. Det skal være oppgave 6 og 8 fra Eksamen vår 06.
  • 31. oktober 2010: Her kan dere lese litt om primtallstesting .
  • 30. oktober 2010: Øving 11 er lagt ut.
  • 26. oktober 2010: Begynnelsen av notat 5, som vil bli en del av pensum, er lagt ut. Dere finner der en oppgave som blir en del av øving 11.
  • 22. oktober 2010: Øving 10. Fortsett med 9.12, Se så på oppgavene 10 - 14 i kapittel 10.
  • 19. oktober 2010: Et foreløpig løsningsforslag til øving 9 er lagt ut.
  • 14. oktober 2010: Øving 9 er lagt ut og løsningsforslaget til øving 8 er lagt ut.
  • 11. oktober 2010: Løsningsforslaget til øving 7 er lagt ut.
  • 08. oktober 2010: Øving 8 er lagt ut.
  • 03. oktober 2010: Gamle eksamensppgaver er lagt ut her og lengere nede på siden.
  • 30. september 2010: Denne løsning 6 er ikke helt ferdig. Her er lf for eksamen 03 våt lfMA2301-03v.
  • 30. september 2010: Her og her er to nettsider som handler om Allan Turing, og her er 2 artikler av Turing.
  • 29. september 2010: Øving 7 er lagt ut. Løsningsforslag 5 er komplett, og feil er rettet.
  • 28. september 2010: Løsningsforslaget til øving 5 er lagt ut. Si gjerne fra om dere finner feil. Det var en trykkfeil i notat 2. Det gjaldt bokstavindeksen k. Den var blitt til i på noen plasser.
  • 23. september 2010: Øving 6 er repetisjon. Den består av oppgave 1, 2 og 3 (-punkt d) i Eksamen høst 01 samt oppgave 1 og 3 i Eksamen vår 03 . Merk at i boka fra den gang var betegnelsen for det tomme ordet e. Dette gjelder Oppgave 1 fra høsten 01. Denne boka behandlet Chomskys normalform på en litt annerledes måte. Løs oppgaven ï følge Martin og glem noe av det som står i oppgave 3 høst 01.
  • 21. september 2010: For at Oppgave 4.50 b skal ha noen mening, så ta med enhetsproduksjonene "S pil A" og "S pil B".
  • 15. september 2010: Øving 5 er lagt ut og enda en feil i forrige løsningsforsleg er rettet.
  • 14. september 2010: Løsningsforslaget til øving 4 er lagt ut. Det var noen feil(3.37). De er rettet nå.
  • 13. september 2010: Etter forelesningen i dag fant jeg det nødvendig å revidere lf 3. Spesielt Oppgave 2.57 a.
  • 10. september 2010: Løsningsforslaget til øving 3 er ferdig.
  • 9. september 2010: Øving 4 er lagt ut.
  • 8. september 2010: Endelig ferdig med Notat 2. Nå kommer det ikke flere notater på en stund. Øving 4 blir det neste.
  • 8. september 2010: Nå er minimaliseringsalgoritmen kommet med i Notat 2, men det er ennå ikke helt ferdig.
  • 5. september 2010: Notat 2 er lagt ut men det er ikke ferdig. Det er for fint vær i dag til å fullføre det nå, men det kommer snart.
  • 2. september 2010: En trykkfeil i Notat 1 er rettet opp. Det var i Teorem 1, Strukturell induksjon. Det var en student som gjorde meg oppmerksom på det. Var det Erlend eller var det Fredrik?
  • 1. september 2010: Øving 3 er lagt ut.
  • 1. september 2010: Jeg er syk og er hjemme i dag og håper å være bra igjen i morgen. Jeg kommer ikke på øvingen. De som vil kan se et løsningsforslag her.
  • 30. august 2010: Hele øving 2 er lagt ut.
  • 28. august 2010: Notat 1 er lagt ut. Det oppklarer noe av det jeg gjorde torsdag. Spesielt ser dere den riktige definisjonen av transitiv tillukning. Man får ikke dette til uten å generalisere rekursiv definisjon til delvise operasjoner. Det er ingen grunn til ikke å gjøre det siden det er minst like enkelt.
  • 26. august 2010: De som ikke kan møte på øving tirsdager kan møte onsdager fra 12:15 til 14:00 i F6. Jeg kommer innom i andre time eller på forespørsel.
  • 26. august 2010: Forelesningen i dag hadde kanskje noen uklarheter. Jeg kommer til å legge ut et lite notat om dette snart.
  • 23. august 2010: Deler av øving 2 er lagt ut.
  • 23. august 2010: Vi har fått rom S22 tirsdager 08:15 - 10:00.
  • 23. august 2010: Øving 1 er lagt ut. Jeg jobber med å finne rom tirsdag 08:15 - 10:00.
  • 13. juli 2010: Ny lærebok i dette emnet.
  • 13. juli 2010: Første forelesning mandag 23 august.

Kursinformasjon

Forelesninger

  • Mandag 11.15-12, F3
  • Torsdag 10.15-12, F2

Øvinger

  • Tirsdag 08.15-10, S22
  • Onsdag 12.15-14, F6, for de som ikke kan møte tirsdager.

Faglærer og øvingslærer

Lærebok

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

Notater

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

Gamle eksamensoppgaver

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

Pensum

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

Eksamen

Eksamensdato er 10. desember med tillatte hjelpemidler C.

Forelesningsplan

Tentativ

Uke Kapittel Øving Løsning
34 1 øving 1 løsning 1
35 2 øving 2 løsning 2
36 3 øving 3 løsning 3
37 4 øving 4 løsning 4
38 4 øving 5 løsning 5
39 7 øving 6 løsning 6
40 7, 8.1-2. øving 7 løsning 7
41 8.5, 9.1, 9.2, 8.3 øving 8 løsning 8
42 9.4, 10.1. øving 9 løsning 9
43 10.2, notat 5, 11.1-2. øving 10 løsning 10
44 notat 5, 11.3-4. øving 11 løsning 11
45 repetisjon øving 12 løsning 12
46 repetisjon øving 13 løsning 13
2018-01-31, Hallvard Norheim Bø