Direkte tilgang til ukeoppgavene
24/08 - 07/09: Kapitlene 1 og 2
14/09 - 05/10: Kapittel 3
12/10 - 26/10: Kapittel 4
02/11 - 09/11: Kapittel 5
16/11 Avsnitt 6.1
23/11 Oppsummering/repetisjon
28/11 Eksamen
24/8 tar jeg sikte på å presentere kurset og meg selv, og å forelese over avsnittene 1.8, 1.9 og 2.1. Hvis vi få tid vil vi snakke litt om avsnitt 2.2.
31/8 tar jeg sikte på å forelese stoff fra avsnittene 2.2 - 2.4, ikke-deterministiske endelige tilstandsmaskiner og de språk de aksepterer.
Til 7/9 har jeg forberedt avsnittene 2.5 og 2.6 hvor vi skal vise at alle endelige tilstandsmaskiner aksepterer regulære språk, og vi vil vise pumpeteoremet for endelige tilstandsmaskiner i en litt sterkere versjon enn slik det er formulert i boka.
14/9 vil vi starte på avsnittene om kontekstfrie gramatikker, gi de formelle definisjonene og en del eksempler, og vise at alle regulære språk kan genereres av kontekstfrie gramatikker, både via maskin-representasjonen og representasjonen ved regulære uttrykk.
21/9 vil vi definere pushdown-automater og se på noen eksempler.
VIKTIG:
Jeg vil tillate grafisk fremstilling av pushdown-automater i oppgaveløsninger, også til eksamen.
Dette betyr at tilstander kan representeres ved ringer som ved endelige tilstandsmaskiner, lovlige overganger ved hjelp av piler, og langs pilen skriver man et trippel som beskriver
(innlest delord fra input, innlest delord fra stack'en, ny topp av stack'en)
Aksepterende tilstander markeres som ved endelige tilstandsmaskiner
28/9 skal vi vise at alle språk akseptert av en push-down-automat er kontekstfrie.
Videre skal vi se på derivasjonstrær og pumpeteoremet for kontekstfrie språk.
Tilslutt vil vi se at visse egenskaper ved kontekstfrie språk er avgjørbare.
5/10 vil vi fortsatt se på pumpeteoremet og derivasjonstrær, og gjøre ferdig det vi ikke rakk uken før.
Vi skal så se på deterministiske pushdown-automater og metoder for å omskrive gramatikker slik at de kan 'parseres' av deterministiske pushdown-automater.
Som et eksempel vil vi gjennomgå Eksamensoppgave 2 fra 8/12-1990.
Vi rakk ikke å gjennomgå Eksamensoppgave 2 fra 8/12-1990 forrige uke, og vil gjø&re det innledningsvis denne uken i stedet.
Deretter vil vi diskutere Turings analyse av beregninger og gi den formelle definisjonen av Turing-maskiner og beskrive hvordan de virker.
Neste uke vil vi se hvordan vi kan beskrive Turing-maskiner på en emr rasjonell måte.
19/10 ga vi endel eksempler på Turingmaskiner som vi kan bruke i løsningen av eksamensoppgaver, som "kopimaskinen" og "shift"-maskinene.
Ved bruk av disse oppgavene i oppgaveløsninger må de enten følge spesifikasjonene gitt i boka, eller presise spesifikasjoner om hvordan disse delmaskinene virker må gis.
23/10 skal vi konstruere en Turingmaskin som multipliserer to tall.
Vi vil deretter se på mulige utvidelser av Turingmaskins-begrepet og på hvorfor dette ikke leder til at vi kan beregne flere funksjoner eller akseptere flere mengder.
30/10 skal vi se litt på ikke-deterministiske Turingmaskiner. Videre skal vi konstruere en universell maskin. (Dette gjorde vi 2/11)
Det er ikke bare viktig å ha et eksistens-teorem for universelle Turing-maskiner, men å se hvordan den etterlikner hvordan vi tenker oss at en Turingmaskin arbeider.
Derfor vil jeg konstruere en universell Turingmasin på forelesningen som etterlikner elementene i et regnetrinn for en vilkårlig maskin som å lete opp riktig instruksjon, skrive om båndet og markere den nye tilstanden.
9/11 skal vi se på generelle gramatikker og sammenhengen med Turing-maskiner.
Jeg minner om at også dette avsnittet er eksamensrelevant, selv om det ikke prøves hvert år.
16/11 skal vi se på stoppeproblemet for Turingmaskiner og på hvilke konsekvenser det har at dette problemet ikke er algoritmisk løsbart.
Det kan også bli noe tid til å diskutere/repetere deler av pensum.
Oppgaver til regneøvelsene vil bli gitt på forelesningene
hver mandag. De blir slått opp i Vilhelm Bjerknes' hus, og de vil
også bli lagt inn her med de nyeste oppgavene først.
Jeg vil normalt gi flere oppgaver enn det blir tid til å gå igjennom på gruppene. Det er meningen at gruppelærer sammen med studentene skal plukke ut de oppgavene som skal gjennomgåes.