Generell informasjon
Kursfakta
Lærebok, støttelitteratur og trykkfeil-liste
Faglig innhold
Pensum
Forelesningene
Ukeoppgavene
Løsningsforslag
Eksamen
Alternativ Turingsimulator
På denne siden vil du finne en del informasjon om emnet MA-IN118 relevant for høsten 2002. De komplette hjemmesidene for de tre foregående årene kan du finne på 1999, 2000 og 2001
Hvis du har Mac med Turings verden innstallert (se avsnittet om støttelitteratur), kan du finne en side med lenker til noen eksempler som vil bli 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. Normalt vil siden bli oppdatert på fredager, ettersom jeg forbereder neste ukes forelesninger da.
VIKTIG: Læreboka kom i ny utgave i 1999.
Det er pensumendringer i forhold til 1998.
Tilbake til toppen.
Forelesninger
Mandag 10.15 - 12.00 i Auditorium 3, Vilhelm Bjerknes hus.
Første gang: 19/8-02.
Det er mulig at vi kan benytte Auditorium 1 i et par uker til. Møt fram til Auditorium 3.
Hvis vi flytter, setter jeg opp en lapp på døren ca. 10 minutter før forelesningstart.
Etterhvert vil MAT100B overta Auditorium 1.
Øvelser
Tirsdag 14.15 - 16.00 i Auditorium 3, Vilhelm Bjerknes hus.
Første gang 27/8-02.
Eksamen
Mandag 25/11-02.
Tilbake til toppen.
Trykkfeil-liste
En student har gjort meg oppmerksom på at det finnes en nettside med trykkfeil og rettelser skrevet av Christos H. Papadimitrou.
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 19/8
Jeg vil starte med en presentasjon av meg selv og så gi en kort oversikt over hva kurset skal inneholde og av målet med kurset.
Vi vil hoppe glatt over avsnittene 1.1 - 1.6 i læreboka, og anta at bakgrunnskunnskapene i diskret matematikk er gode nok til at studentene kan lese det relevante stoffet selv.
Jeg tar sikte på å gå gjennom avsnittene 1.7, 1.8 og 2.1 om alfabet, språk og regulære uttrykk og om deterministiske, endelige tlstandsmaskiner.
Neste uke vil vi illustrere stoffet fra 2.1 via programpakken Turing's world.
Mandag 26/8
Vi vil kort repetere definisjonen av regulære uttrykk og regulære språk.
Vi redefinerer de endelige tilstandsmaskinene illustrert ved noen eksempler utviklet i Turing's world.
Vi vil også definere ikke-deterministiske tilstandsmaskiner, og vise sammenhengen både med de deterministiske maskinene og med de regulære språkene.
Jeg tar sikte på at vi dekker avsnittene 2.2 og 2.3.
Mandag 2/9
Til tross for at det kolliderer med årsfesten hvor ti æresdoktorer blir kreert til Abels minne, vil jeg holde forelesning som planlagt.
Vi skal kort repetere sammenhengen mellom deterministiske og ikke-deterministiske tilstandsmaskiner og regulære språk.
Vi skal spesielt se nøyere på konstruksjonen av regulære uttrykk fra en tilstandsmaskin, og gjennomgå et eksempel.
Hovedresultatet denne dagen blir pumpeteoremet for regulære språk, som vi vil bruke destruktivt, det vil si til å vise at endel språk ikke er regulære. Dette er viktig og sentralt stoff.
Til slutt vil vi se mer uformelt på endel algoritmer knyttet til problemstillinger omkring maskiner og regulære språk.
Mandag 9/9
Vi vil gå igjennom avsnittene 3.1 og 3.2 om kontekstfrie gramatikker, kontekstfrie språk og parsingtrær.
Vi vil både gi de formelle definisjonene og se på en rekke eksempler.
Uke 38 - 16/9 og 17/9 - ble det ingen undervisning
Mandag 23/9
Vi gikk igjennom definisjonen av pushdown-automater med et par eksempler.
Minner om at en pushdownautomat bare aksepterer et ord om den kan komme til en aksepterende tilstand slik at lageret (stack'en) er tomt når inngangsordet er lest.
Minner også om at pushdownautomater er ikke-deterministiske som hovedregel.
Vi så hvordan ethvert kontekstfritt språk kan aksepteres av en pushdown-automat, ved at automaten sjekker om det finnes en mulig venstre-utledning av ordet som er gitt.
Vi så også på hvordan ethvert språk som kan aksepteres av en pushdownautomat kan genereres av en kontekstfri gramatikk.
Til slutt viste vi at klassen av de kontekstfrie språkene er lukket under union, sammensetning og Kleene *. Vi så kort på pumpeteoremet for kontekstfrie språk, men vil komme tilbake til dette teoremet neste gang.
Mandag 30/9-02
Vi vil gi et detaljert bevis for pumpeteoremet for kontekstfrie språk og gi noen anvendelser. Flere anvendelser vil bli gitt som oppgaver til neste uke.
Avsnitt 3.6 vil vi behandle temmelig overfladisk, uten å gå inn på kompleksiteten av algoritmene. Dette er stoff som aldri er prøvet til eksamen.
Vi vil gå igjennom avsnitt 3.7 så langt vi rekker. Vi vil definere hva vi mener med deterministiske pushdown-automater og deterministiske kontekstfrie språk.
Vi vil vise at komplementet til et deterministisk kontekstfritt språk selv er deterministisk kontekstfritt.
Jeg regner med at vi får tid til å se på sammenhengen mellom LL(1) - gramatikker og deterministiske parsingautomater. Jeg vil legge en litt mer presis definisjon av LL(1) gramatikker til grunn enn det boka gjør, og bevise at språket da blir deterministisk kontekstfritt. Hvorvidt vi rekker å snakke om de heuristiske reglene 1 og 2 er mer usikkert, men rekker vi det så rekker vi det.
Mandag 7/10-02
Vi vil gjennomgå definisjonen av en LL(1)-gramatikk og se på de heuristiske reglene 1 og 2.
I andre time vil vi starte arbeidet med Turing-maskiner, og jeg tar sikte på å gjennomgå det første avsnittet om Turingmaskiner.
Mandag 14/10-02
Vi vil kort repetere definisjonen av en Turingmaskin. Deretter vil vi se på hva vi mener med at en Turingmaskin avgjør et språk og hva vi mener med at den beregner en funksjon. Vi vil se på en del eksemler.
Deretter skal vi se at selv om vi prøver å lage kraftigere maskiner ved å bruke flere bånd, lesehoder m.m., kan vi ikke avgjøre flere språk eller beregne flere funksjoner.
Mandag 21/10-02
Vi vil først se på mulighetene til å utvide antall bånd, lesehoder etc. og konkludere med at dette ikke gir noen større teoretisk regnestyrke.
Vi ser deretter på ikke-deterministiske Turingmaskiner.
Til sist vil vi gi noen eksempler på generelle gramatikker og starte studiet av slike.
Mandag 28/10-02
Denne uken tar vi sikte på å fullføre innføringen av generelle gramatikker, samt å vise at det finnes en universell Turingmaskin.
Mandag 4/11
Vi vil se på stoppeproblemet for Turingmaskiner og på noen konsekvenser av at stoppeproblmet er algoritmisk uløsbart.
Deretter definerer vi kompleksitetsklassen P og egenskaper ved denne.
Vi vil se på et problem i grafteori om eksistens av Eulersykler, diskutere hvordan dette problemet kan presenteres som et språk og vise at problemet tilhører P.
Hvis det blir tid vil vi se på hvordan andre klasser av problemer kan presenteres som formelle språk.
Mandag 11/11
Vi skal se på hvordan noen av problemene som blir diskutert i boka kan representeres som språk over et passende alfabet.
Eksistens av Hamilton-sykler fra grafteori, den handelsreisendes problem, partisjonsproblemet og problemet om hvorvidt et utsagn i utsagnslogikken kan oppfylles eller ikke, er de problemene vi vil konsentrere oss om.
Etter pause vil vi definere kompleksitetsklassen NP og, så langt vi rekker, vise at de språkene vi så på i første time ligger i denne klassen.
Mandag 18/11
Vi starter med å ta opp temaer jeg får forslag om. Ut fra de forslagene jeg har fått vil vi snakke om:
-- Det generaliserte pumpeteoremet.
-- Forholdet mellom LL(1)-gramatikker og deterministisk kontekstfrie språk.
-- Forskjellige måter å bruke pumpeteoremet for kontekstfrie språk på.
-- Presentasjon av problemer som språk, og hvordan argumentere for hvorfor et problem er i NP.
Nå vi har diskutert de temaene som er ønsket, fortsetter vi med oppgaveregning mandag og tirsdag.
Vi står igjen med oppgavene 4 og 5 fra 1999 og settene fra 2000 og 2001. Jeg planlegger å gjennomgå utvalgte oppgaver fra alle tre settene, slik at vi tar hensyn til ønsker fra studentene og ønsket fra meg om å gjennomgå oppgaver omkring P og NP.
Jeg har lagt ut løsningsforslag til eksamenene fra 2000 og 2001 med de samme tekstbehandlingsmessige begrensningene som tidligere.
Tilbake til toppen.
Tirsdag 19/11-02
Vi vil regne, i rekkefølge, 2000-3, 2000-2, 2001-5, 2001-4, 2001-3 og 2001-2 så langt vi rekker.
Vi vil begrense oss til 10 minutter pause og slutte 15.55.
Oppgaver til 19/11-02
I det jeg antar at vi blir ferdige med oppgavene fra 1999 den 12/11, fortsetter vi med oppgavesettet fra 2000. Vi starter med å gå igjennom siste oppgave fra 2000 og fra 2001, og deretter fortsetter vi gjennomgåelsen i den rekkefølgen oppgavene står i boka.
Mandag 11/11 blir vi enige om hvordan vi skal legge opp Mandag 18/11, om det blir repetisjon eller eksamensoppgaveregning.
Oppgaver til 12/11-02
Læreboka Oppgave 5.3.1.
Hvis jeg husker rett fra da jeg gikk igjennom denne oppgaven i fjor, oppdaget jeg en oversettelsesfeil fra utgave 1 til utgave 2. Hintet i oppgaven må derfor leses med kreativitet. (I den gamle utgaven startet maskiner til høyre, og ikke til venstre for inputordet.)
Vi går igjennom eksamensoppgavene for 1999, 2000 og 2001 fortløpende, dog slik at vi får sett på et par oppgaver i kompleksitetsteori.
Oppgaver til 5/11-02
Eksamen 29/11-97 Oppgave 4.
Eksamen 28/11-98 Hele settet.
Oppgaver til 29/10-02
Læreboka: 4.3.5, 4.5.1, 4.5.2, 4.5.3.
I 4.3.5 er det ikke meningen å definere en maskin formelt, men å gi en beskrivelse av hvordan den virker.
Eksamen 5/12-92 Oppgave 3.
Eksamen 29/11-97 Oppgaver 1, 2 og 3.
Oppgaver til 22/10-02
Læreboka: 4.2.1, 4.2.2, 4.2.3, 4.2.4.
Eksamen 9/12-88 Oppgave 3
Eksamen 8/12-90 Oppgave 3
Eksamen 5/12-92 Oppgaver 1 og 2.
Oppgaver til 15/10-02
Læreboka: 3.7.1, 4.1.1, 4.1.4, 4.1.6, 4.1.7, 4.1.10.
Vi står til rest med siste oppgave fra forrige gang.
Eksamen 9/12-89 Oppgave 4.
Eksamen 8/12-90 Oppgave 2.
Eksamen 7/12-91 Oppgaver 2 og 3.
Oppgaver til 8/10-02
Læreboka: 3.5.1, 3.5.2, 3.5.5.a), 3.5.7, 3.5.8, 3.5.13, 3.5.14, 3.5.15.
Eksamen 9/12-89 Oppgave 2.
Eksamen 7/12-91 Oppgave 1.
Oppgaver til 1/10-02
Læreboka: 3.3.1, 3.3.2 og 3.4.1
Eksamen 9/12-88 Oppgave 2.
Eksamen 9/12-89 Oppgave 3.
Eksamen 2/3-90 Oppgaver 1 - 6.
Oppgaver til 24/9-02
Læreboka: 3.1.1, 3.1.2, 3.1.3, 3.1.5, 3.1.9.
Eksamen 8/12-90 Oppgave 1.
Oppgaver til 10/9-02
Avsnitt 2.4 i læreboka, oppgaver 1, 2, 4, 5, 7, 8, 11 og 12.
Eksamen 9/12-1988 Oppgave 1.
Oppgaver til 3/9-02
Fra læ:reboka:
2.2.1, 2.2.2, 2.2.6, 2.2.7, 2.2.8
2.3.1, 2.3.3, 2.3.4, 2.3.7.
Oppgaver til 27/8-02
Fra læreboka:
1.7.3, 1.7.4, 1.7.5
1.8.1, 1.8.2, 1.8.3, 1.8.4, 1.8.5
2.1.1, 2.1.2, 2.1.3
For å løse oppgave 1.8.4 anbefaler jeg at man forsøker seg med å definere et nytt regulært uttrykk ved rekursjon over uttrykket for L.
Tilbake til toppen.
Løsninger til 27/8-02.
Oppgave 2.1.3 fant jeg uegnet til presentasjon i dette formatet.
Løsninger til 24/9-02
Jeg ser at dobbelpilen fra word-dokumentet ikke ble helt vellykket i overgangen til html. Den ble en litt forvrengt P. Det får dere leve med.
En gjennomgang av oppgavesettet finner dere på Løsning av Eksamen 25/11-2002.
Tilbake til toppen.
Denne siden er redigert av Dag Normann, Matematisk Institutt.
Sist oppdatert 25/11-02.