På denne siden vil du finne en del informasjon om emnet MA-IN118 relevant for høsten 2000. Hvis du vil vite hvilke ukeoppgaver jeg ga i fjor og/eller undervisningsprogresjonen jeg hadde da, kan du se på hjemmesiden for 1999.
FLYTTING AV SISTE OPPGAVEREGNING
NYTT: Hvis du har Mac med Turings verden innstallert, kan du finne en side med lenker til noen eksempler gjennomgått på forelesningene.
Jeg vil fortløpende orientere om utviklingen i forelesningene, ved for hver uke å angi i forkant hva jeg har forberedt av undervisning. Jeg vil også gi ukeoppgavene her.
VIKTIG: Læreboka kom i ny utgave i 1999.
Det er pensumendringer i forhold til 1998.
Du finner følgende overskrifter på denne siden:
Kursfakta
Lærebok og støttelitteratur
Faglig innhold
Pensum
Forelesningene
Ukeoppgavene
Alternativ Turingsimulator
Forelesninger
Mandag 10.15 - 12.00 i Auditorium 3, Vilhelm Bjerknes hus.
Første gang: 21/8-00.
Øvelser
Tirsdag 14.15 - 16.00 i Auditorium 1, Vilhelm Bjerknes hus.
Første gang 29/8-00.
Eksamen
Lørdag 25/11-00.
Sted: Lesesalen i Vilhelm Bjerknes hus.
Tilbake til toppen.
Oppgavesamling
Eksamensoppgaver MA-IN118, Matematisk Institutt.
Støttelitteratur
Jon Barwise og John Etchemendy:
TURING'S WORLD.
Med denne boken følger en diskett med programmet "Turing's world " . Ved hjelp av dette programmet kan man lage sine egne Turingmaskiner og endelige tilstandsmaskiner, og boken inneholder en del teoristoff relevant for MA-IN118, men ikke alt. Vi kommer til å demonstrere noe av teorien på forelesningene via Turing's world.
Turing's World finnes i en versjon for Macintosh og en versjon for Windows.
Tilbake til toppen.
I MA-IN118 studerer vi forholdet mellom språk og maskin på tre nivåer.
Innledningsvis vil vi se på de såkalte regulære språkene og de endelige tilstandsmaskinene. En endelig tilstandsmaskin kan betraktes som en form for flyt-diagram hvor bevegelsen innen diagrammet avhenger av data som strømmer inn fra omverdenen. Tradisjonelt har endelige tilstandsmaskiner spilt en rolle i syntaks-analyse, men i de senere årene er anvendelsesområdet utvidet til å modellere kontroll-prosesser og for å håndtere strømmer av data maskiner imellom. Denne delen av MA-IN118 er relevant for emner som IN270 og IN-ODS.
I den andre delen vil vi se på kontekstfrie gramatikker, kontekstfrie språk og pushdownautomater. Arkitekturen til de fleste programmeringsspråk, som t. eks. JAVA , er i hovedsak basert på kontekstfrie gramatikker.
Pushdownautomater er formelle maskiner som kan brukes til parsering av kontekstfrie språk, det vil si avgjøre om et uttrykk er i språket eller ikke. Vi drøfter problemer i tilknytning til å finne deterministiske parseringsalgoritmer for visse kontekstfrie språk. Denne delen er relevant for IN211 og IN310, uten at stoffet er overlappende i noen betydelig grad.
Den siste delen dreier seg om Turingmaskiner. Turingmaskiner er matematiske modeller for hva vi kan kalle 'mekanisk utførbare algoritmer'. Vi vil vise at det finnes en universell Turingmaskin, det vil si en maskin hvor vi kan "programmere" alle andre Turingmaskiner.
Dette resultatet fra 1936 kan sees på som et matematisk eksistensbevis for den programmerbare datamaskinen, og regnes av mange som en viktig milepel i datateknologiens utvikling. Den fullstendige historien til denne teknologien er svært sammenstatt, også når det gjelder de tidligste fasene, men vi kommer bare til å vektlegge betydningen av Turings resultater.
Turingmaskiner regnes som en av de viktigste modellene for algoritmiske beregninger, også når det gjelder problemstillinger relevante for dagens forskning. Vi vil imidlertid konsentrere oss om de klassiske anvendelsene av disse modellene.
Et viktig aspekt ved MA-IN118 er at vi gir en matematisk stringent behandling av de språkklassene vi studerer. Dette gir oss et verktøy for å påvise at visse språk faller utenfor de aktuelle språkklassene. Et viktig eksempel på et slikt resultat, som vi vil vise, kan spissformuleres som
'Det finnes ingen algoritme som avgjør om
et gitt program svarer til en gitt spesifikasjon'.
En lærdom av dette teoretiske resultatet er at det aldri blir noen automatikk i det å utvikle gode og feilfrie program eller program-pakker, og at man for å være på den helt sikre siden må verifisere programmene med matematisk stringens. I praksis må dette ballanseres mot en innsiktsfull testing av programmene.
Turingmaskinene er en god matematisk modell for teoretisk utførbare algoritmer, med favner for vidt til bare å omfatte algoritmer som kan utføres i praksis. Mot slutten av kurset vil vi se på en bedre modell for dette formålet, Turingmaskiner som arbeider i polynomiell tid. Vi vil også se på tilsvarende ikke-deterministiske maskiner, og gi en presis beskrivelse av
P = NP - problemet,
kanskje det mest sentrale åpne problemet i teoretisk databehandling.
Kapittel 1
Hele
Kapittel 2
Avsnittene 1, 2, 3, 4 og 6.
Kapittel 3
Avsnittene 1, 2, 3 og 4 fram til Lemma 3.4.2.
Avsnittene 5, 6 og 7 fram til Bottom-Up Parsing.
Kapittel 4
Avsnittene 1, 2, 3, 5 og 6.
Kapittel 5
Avsnittene 1 - 4.
Kapittel 6
Hele.
Mandag 28/8 vil vi snakke om deterministiske og ikke-deterministiske tilstandsmaskiner. Stoffet er hentet fra avsnittene 2.1, 2.2 og delvis fra avsnitt 2.3.
Det er meningen at vi skal demonstrere noen endelige tilstandsmaskiner ved hjelp av Turings verden.
Mandag 4/9 ser vi litt grundigere på sammenhengen mellom deterministiske og ikke-deterministiske tilstandsmaskiner.
Vi skal videre vise at de regulære språkene er nøyaktig de språkene som kan aksepteres av endelige tilstandsmaskiner.
Vi skal vise pumpeteoremet for regulære språk med anvendelser, og hvis det blir tid skal vi snakke litt om stoffet fra avsnitt 2.6.
MERK!
Vi rakk ikke å formulere og bevise pumpeteoremet.
Vi kommer til å starte med det neste uke.
Mandag 11/9 fullfører vi det stoffet om endelige tilstandsmaskiner og regulære språk som vi ikke rakk forrige uke, nemlig pumpeteoremet med anvendelser, og litt om stoffet fra avsnitt 2.6.
Deretter vil vi se på kontekstfrie gramatikker og språk, i hovedsak avsnittene 3.1 og 3.2.
Mandag 18/9 repeterer vi litt om kontekstfrie gramatikker og parsingtrær.
Deretter vil vi snakke om pushdown-automater og sammenhengen med kontekstfrie språk.
Mandag 25/9 skal vi fullføre beviset om sammenhengen mellom kontekstfrie språk og pushdown-automater.
Vi skal vise at snittet mellom et kontekstfritt språk og et regulært språk er kontekstfritt.
Til slutt skal vi se på pumpeteoremet for kontekstfrie språk, og gjennomgå et amputert avsnitt 3.6.
Mandag 2/10 repeterer vi pumpeteoremet for kontekstfrie språk, og gir et par anvendelser til.
Vi foretar videre en amputert gjennomgang av avsnitt 3.6.
Hovedtemaet blir deterministiske pushdownautomater og deterministisk kontekstfrie språk. Vi vil vise at komplementet til et deterministisk kontekstfritt språk selv er deterministisk kontekstfritt. Vi vil videre se på de heuristiske reglene for omforming av gramatikker som er gitt i boka, og vise at mengden av regulære uttrykk over et alfabet utgjør et deterministisk kontekstfritt språk.
Mandag 9/10 avslutter vi stoffet om kontekstfrie språk og pushdownautomater.
Vi starter så med kapittel 4 om Turingmaskiner, og tar sikte på å dekke avsnitt 4.1.
Vi vil demonstrere noen Turingmaskiner ved hjelp av "Turing's World".
Mandag 16/10 fortsetter vi innføringen av Turingmaskiner, og vil i hovedsak dekke stoff fra avsnittene 4.1 og 4.2 i læreboka.
Hvis det blir tid, vil vi også snakke litt om Turingmaskiner som bruker flere bånd, lesehoder m.m.
Når man skal presentere en Turingmaskin, for eksempel som et forsøk på å besvare en eksamensoppgave, er dokumentasjonen eller forklaringen en viktig del.
Man kan godt dele hovedmaskinen opp i flere smådeler og forklare hvilke subrutiner delmaskinene utfører.
Det er viktig å få frem den algoritmen som ligger til grunn for konstruksjonen av maskinen.
Hvis man bruker kopi- eller shift-maskiner fra læreboka, må de virke ut fra de spesifikasjonene som boka angir, det vil si subrutinene starter og stopper med lesehodet i den posisjonen som boka forutsetter. Hvis man ikke husker disse, skal man angi spesifikasjonene for maskiner man bruker, men ikke konstruerer selv.
Der hvor gamle eksamensoppgaver presiserer hvordan inngangsdata og utgangsdata organiseres på en Turingmaskin, er dette basert på konvensjoner i den første utgaven av læreboka.
Vi vil bruke konvensjonene i den siste utgaven når vi løser oppgavene.
Merk at # var tegnet for 'blank' i den første utgaven.
Mandag 23/10 skal vi se på forsøk på å generalisere Turingmaskiner til maskiner med flere bånd, lesehoder, dimensjoner m.m.
Hvis vi får tid vil vi også se på ikke-deterministiske Turingmaskiner.
Mandag 30/10 skal vi se på ikke-deterministiske Turingmaskiner og på generelle gramatikker.
Målet med dette er delvis å forberede oss til P = NP-problemet og delvis å lære styrken til Turingmaskin-begrepet bedre å kjenne.
Mandag 6/11 skal vi vise eksistensen av en universell Turingmaskin, og vi skal se på uløsbarheten av stoppeproblemet og andre problemer.
Mandag 13/11 starter vi på kapittel 6 om P og NP, og vi vil rekke det meste av det kapitlet.
Mandag 20/11 er siste forelesning. Da skal vi definere klassen NP og forklare hvordan vi kan vise at en del av de problemene vi har sett på tilhører denne kompleksitetsklassen.
Vi skal ikke se på NP-kompletthet som en del av pensum. Et problem er ( litt populært uttrykt ) NP-komplett hvis det er i NP og vi kan vise at om dette problemet er i P så er P = NP.
Mathias Barra, en av studentene i år, har sendt meg adressen til en side ved KTH i Stockholm hvor en rekke NP-komplette problemer er listet opp.
PS. Nærmere ettersyn av siden referert til over viser at den omhandler approksimasjonsresultater for problemer som faller inn under klassen NP. Den viser likevel hvor vidt denne klassen sprer seg når det gjelder problemstillinger.
Tilbake til toppen.
Torsdag 23/11
Læreboka, oppgaver 6.1.1, 6.4.1 og 6.4.2.
Ellers vil eksamensoppgaven fra 1999 bedre illustrere hva slags oppgave omkring P og NP det er aktuelt å gi til årets eksamen.
Grunnet avviklingen av Ex. Phil må vi flytte denne oppgaveregningen i tid og sted.
Torsdag 23/11 kl. 12.15 - 14.00 i grupperom C 315.
Tirsdag 14/11
Læreboka, oppgave 5.3.1
Vi fortsetter deretter med etterslepet fra uke 45, se under.
Tirsdag 7/11
Læreboka, oppgaver 4.5.2, 4.5.3 og 4.6.2
Når vi har tatt igjen etterslepet av oppgaver, går vi i gjennom eksamensettene fra 1998 og 1999 så langt vi rekker.
Ved siden av noen få øvingsoppgaver fra læreboka skulle det holde oss beskjeftiget det meste av den tiden som er igjen.
Tirsdag 31/10
Læreboka, oppgaver 4.3.4 og 4.5.1
Eksamen
9/12-89, oppgave 4.
7/12-91, oppgaver 1, 2 og 4.
30/11-96, oppgave 3.
Tirsdag 24/10
Læreboka
Avsnitt 4.2, oppgaver 1, 3 og 4.
Eksamen:
2/3-90, oppgave 7.
8/12-90, oppgave 3.
Tirsdag 17/10
Avsnitt 4.1, oppgaver 1, 2, 6, 7, 9 og 10.
Der hvor Turing-maskiner er gitt på tabellform vil vi bruke grafisk fremstilling under oppgaveregningen.
Eksamen:
8/12-90, oppgave 4.
Denne oppgaven ble gitt til forrige uke, men på grunn av trykkfeil på oppslagene, utsatte vi den.
5/12-92, oppgaver 1, 2 og 3.
Tirsdag 10/10
Læreboka:
Avsnitt 3.7, oppgaver 1 og 5.
Eksamen:
2/3-90, oppgaver 4, 5 og 6.
8/12-90, oppgaver 1, 2 og 4. (Her har jeg oppgitt oppgave 3 i stedet for oppgave 4 på oppslag og på forelesningene. Jeg lar derfor oppgave 3 utgå denne uken, og tar den igjen neste uke.)
7/12-91, oppgave 3.
Tirsdag 3/10
Eksamen 9/12-89, oppgave 2.
Eksamen 2/3-90, oppgaver 1 og 3.
Læreboka:
Avsnitt 3.5, oppgaver 1, 2, 5a), 7, 8, 14 og 15.
Tirsdag 26/9
Eksamen 9/12-88 Oppgave 2.
Eksamen 9/12-89 Oppgaver 1 og 3.
Læreboka:
Avsnitt 3.3, oppgaver 1 og 2.
Avsnitt 3.4, oppgaver 1 og 4.
MERK! I oppgave 3.4.4 er det en trykkfeil. Det skal stå L(M') = L(M), og ikke (M') = L(M).
Tirsdag 19/9
Eksamen 9/12-88 Oppgave 1.
Læreboka
Avsnitt 3.1, oppgaver 2, 3, 5, 7 og 9.
Avsnitt 3.2, oppgaver 1 og 2.
Tirsdag 12/9
Læreboka
Avsnitt 2.3, oppgaver 7a og 7b.
Avsnitt 2.4, oppgaver 1, 2, 3, 4, 5, 7, 8 og 12.
Tirsdag 5/9
Læreboka
Avsnitt 2.1, oppgaver 1, 2 og 3.
Avsnitt 2.2, oppgaver 1, 2, 3 og 6.
Avsnitt 2.3, oppgaver 1, 2 og 4.
Tirsdag 29/8
Læreboka
Avsnitt 1.7, oppgaver 3, 4 og 5.
Avsnitt 1.8, oppgaver 1, 2, 3, 4, 5 og 6.
Tilbake til toppen.
Denne siden er redigert av Dag Normann, Matematisk Institutt.
Sist oppdatert 15/11-00.