På denne siden vil du finne en del informasjon om emnet MA-IN118.
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 er kommet i ny utgave.
Det er pensumendringer i forhold til 1998.
Du finner følgende overskrifter på denne siden:
Endret praksis på tirsdager
Kursfakta
Lærebok og støttelitteratur
Faglig innhold
Pensum
Forelesningene
Ukeoppgavene
Alternativ Turingsimulator
Forelesninger
Mandag 10.15 - 12.00 i Auditorium 1, Vilhelm Bjerknes hus.
Første gang: 23/8-99.
Øvelser
Tirsdag 14.15 - 16.00 i Auditorium 1, Vilhelm Bjerknes hus.
Første gang 31/8-99.
Vi vil variere mellom veiledet arbeid med oppgavene individuelt eller i smågrupper, og gjennomgang av oppgavene i plenum.
Eksamen
Torsdag 25/11-99.
Tilbake til toppen.
Oppgavesamling
Eksamensoppgaver MA-IN118, Matematisk Institutt.
Støttelitteratur
Jon Barwise og John Etchemendy:
Turing's world 3.0 for the Macintosh
Med denne boken følger en diskett med programmet "Turing's world 3.0" som kan kjøres på Macintosh. 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.
En versjon av Turing's world for PC er på trappene, men vi vet ikke om den vil være tilgjengelig i år.
I følge en nettadresse jeg fikk av en av dere studenter, kom Turing's world for Windows ut i mars, og bokhandelen har bestilling inne på den.
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.
Hvis erfaringene med den nye utgaven av læreboka tilsier at jeg legger mindre vekt på deler av dette pensumet til eksamen, vil det bli kunngjort her og på forelesningene.
Mandag 30/8 vil jeg fullføre praten om kapittel 1.
Deretter vil jeg forelese fra kapitlene 2.1, 2.2 og deler av 2.3.
Hvis vi får teknikken til å virke, vil jeg bruke Turing's verden til å demonstrere endelige tilstandsmaskiner.
Mandag 6/9 vil jeg fullføre gjennomgangen av avsnitt 2.3 om sammenhengen mellom regulære uttrykk og endelige tilstandsmaskiner.
Deretter vil vi se på pumpeteoremet i Avsnitt 2.4 med anvendelser.
Avsnitt 2.5 er ikke pensum, og avsnitt 2.6 er mest til orientering for oss, uten at vi legger vekt på detaljene.
Mandag 13/9 starter vi opp med kontekstfrie gramatikker, kontekstfrie språk og parsing-trær, det vil si avsnittene 3.1 og 3.2.
Hvis vi får tid vil vi også gi en første innføring i pushdown-automater.
Turing's verden gir ikke støtte til arbeidet med pushdown-automater.
Mandag 20/9 starter vi med å innføre pusdown-automater, og vi vil se på sammenhengen mellom pushdown-automater og kontekstfie språk.
Når Lemma 3.4.2 er utelatt fra pensum, er det fordi beviset er ganske langt og at en gjennomgåelse av det vil ta tid bort fra andre ting som det er viktigere å presentere.
Konsekvensene av dette lemmaet er imidlertid pensum, det vil si Teorem 3.4.1 og alle konsekvenser av dette. En spesielt viktig konsekvens er at snittet mellom et kontekstfritt språk og et regulært språk selv er kontekstfritt. Dette er et viktig verktøy for å kunne utnytte pumpeteoremet for kontekstfrie språk.
Vi kommer til å avslutte forelesningen med å vise pumpeteoremet, men må trolig vente til uken etter med å se på anvendelser.
Mandag 27/9 skal vi først se på pumpeteoremet for kontekstfrie språk.
For å kunne anvende dette pumpeteoremet vil vi i mange tilfeller trenge at snittet mellom et regulært språk og et kontekstfritt språk selv er kontekstfritt.
Jeg vil gi et alternativt bevis på forelesningen som ikke bruker Lemma 3.4.2.
Vi kommer til å hoppe over avsnitt 3.6, og bruker heller tid på deterministiske pushdownautomater og hvordan vi kan konstruere gramatikker som automatisk kan parseres av deterministiske pushdown-automater.
Hvis det blir tid, ønsker jeg å sluttføre det jeg har å si om pushdownautomater på mandag, men det er vel tvilsomt om jeg greier det.
Mandag 4/10 skal vi først se på teknikker for å tilpasse en gramatikk slik at vi kan lage en deterministisk pushdown-automat som aksepterer det tilhørende språket.
Deretter begynner vi på kapitlet om Turing-maskiner. Vi vil se på noen eksempler utviklet i Turing's World.
Mandag 11/10 skal vi fortsette innføringen an Turing-maskiner.
Vi skal både fastlegge noen begreper og se på en del eksempler utviklet i Turings verden.
Mandag 18/10 og Mandag 25/10 er det ikke forelesninger.
Det gies i stedet forelesninger tirsdagene 19/10 og 26/10 samme sted kl. 14.15 - 16.00.
Tirsdag 19/10 vil Herman Ruge Jervell forelese.
Han skal snakke om Turing-maskiner med flere bånd etc., og om ikke-deterministiske Turingmaskiner. Dette svarer til avsnittene 4.3 og 4.5.
Tirsdag 26/10 vil jeg snakke om generelle gramatikker, eller omskrivnings-systemer (rewrite systems) som det også kalles. Dette svarer til avsnitt 4.6.
Mandag 1/11 vil jeg vise hvordan man kan konstruere en universell Turingmaskin og vise uløsbarheten av stoppeproblemet.
Vi vil også se på noen andre uløsbare problemer.
Metodene er generelle, og resultatene gir oss informasjon om fundamentale problemer i forbindelse med programmering og bruk av datamaskiner.
Mandag 8/11 Skal vi se på algoritmer som kan utføres i polynomiell tid, og på hvordan problemer kan reformuleres slik at Turing-maskiner kan studere dem. Vi skal vise at visse problemer er i klassen P av språk som kan avgjøres på polynomiell tid, mens vi skal la problemet stå åpent for en del andre problemer (hvor alle andre også til nå har latt problemene stå åpne).
Tilbake til toppen.
Endret praksis
Fra og med tirsdag 2/11 vil vi slutte med å ha veiledete egenøvelser.
Vi vil gi flere oppgaver, og spesielt eksamensoppgaver.
Oppgaver til 23/11
Læreboka, oppgavene 6.4.1 og 6.4.2
Eksamen 7/12-91
Oppgaver til 16/11
Læreboka, oppgavene 6.1.1 og 6.2.2
Eksamen 5/12-92
Oppgaver til 9/11
Læreboka oppgave 5.3.1
Eksamen 28/11 - 98 Oppgave 5
Eksamen 30/11 - 96 Hele settet
Oppgaver til 2/11
Læreboka:
4.3.3, 4.3.5, 4.5.3 og 4.6.7.
Eksamensoppgaver:
28/11-1998 Oppgavene 1 - 4.
Det blir ingen egenregning fra nå av.
Vi vil først gå igjennom oppgavene fra læreboka, og så eksamensoppgavene så langt vi rekker.
Det vi ikke rekker utsettes til neste uke.
Ingen oppgaver til 19/10 og 25/10, se over
Oppgaver til 12/10:
Læreboka:
Avsnitt 3.7 oppgave 5 (overført fra forrige uke).
Avsnitt 4.1 oppgaver 6 og 7.
Eksamen 29/11-97 oppgaver 2 og 3 a), b).
I den forrige utgaven av læreboka ble # brukt som symbolet for blank rute.
Oppgaver til 5/10:
Læreboka:
Avsnitt 3.5 oppgaver 1, 2, 5a) og 14.
Avsnitt 3.7 oppgave 5.
Eksamen 9/12-89 Oppgave 3.
Oppgaver til 28/9:
Læreboka:
Avsnitt 3.3 oppgaver 1 og 2.
Avsnitt 3.4 oppgave 1.
Avsnitt 3.5 oppgaver 1 og 2. (Disse to oppgavene utsettes en uke fordi vi ikke kom langt nok sist.)
Eksamen 9/12-88 Oppgave 1.
(Oppgavesamlingen er til salgs i Akademika.)
Oppgaver til 21/9:
Avsnitt 3.1 oppgaver 1, 2, 3, 4 og 5.
Avsnitt 3.2 oppgaver 3 og 4.
Oppgaver til 14/9:
Avsnitt 2.3 oppgaver 5, 6 a), 7 a) og b).
Avsnitt 2.4 oppgaver 1, 2, 4, 5, 11 og 12.
Oppgaver til 7/9:
Avsnitt 2.1 oppgaver 1 og 3.
Avsnitt 2.2 oppgaver 1, 2, 3 og 6.
Avsnitt 2.3 oppgaver 1, 3 og 4.
Oppgaver til 31/8:
Avsnitt 1.7 oppgaver 1b, 1c, 2, 4 og 5.
Avsnitt 1.8 oppgaver 1, 2, 3, 4, 5 og 7.
Tilbake til toppen.
Denne siden er redigert av Dag Normann, Matematisk Institutt.
Sist oppdatert 11/08-00.