Du finner følgende overskrifter på denne siden:
Generell informasjon
Kursfakta
Lærebok og støttelitteratur
Faglig innhold
Pensum
Forelesningene
Ukeoppgavene
Alternativ Turingsimulator
På denne siden vil du finne en del informasjon om emnet MA-IN118 relevant for høsten 2001. De komplette hjemmesidene for de to foregående årene kan du finne på 1999 og 2000
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.
UNDERVISNINGEN STARTER OPP MANDAG 10/9
Grunnet studentsvikt på et hovedfagskurs er det blitt mulig å gi mer regulær undervisning i MA-IN 118 likevel. Med unntak av en uke i november vil det bli gitt ukentlig undervisning, og mesteparten av pensun vil bli dekket.
Vi starter opp mandag 10/9 kl. 10.15 - 12.00 i auditorium 3 i VB, og vil også normalt benytte tiden tirsdager 14.15 - 16.00 i seminarrom B 71 (MERK! NYTT STED). Jeg tar sikte på tirsdag 18/9 som første tid for oppgaveregning.
Vi vil anta at studentene kjenner til regulære språk og endelige tilstandsmaskiner, både deterministiske og ikke-deterministiske.
Grunnet allerede fastlåste planer vil det være en uke i november, uke 46, hvor det ikke gies undervisning.
SAMARBEID MED SLI
Studentene kan også følge forelesningene i SLI 110.
Informasjon om SLI 110 står på forelesningskatalogens side 226.
Det er forelesningene i beregnbarhet, Onsdag kl 14.15 - 16.00 i seminarrom 706, Niels Treschows hus (den laveste av de to HF-høyblokkene) og grupperegning Tirsdag 8.15 - 10.00 i seminarrom 408 (samme hus) som er tilpasset MA-IN 118-studentene.
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: 10/9-01.
Øvelser
Tirsdag 14.15 - 16.00 i Auditorium 1, Vilhelm Bjerknes hus.
Første gang 18/9-01.
Eksamen
Mandag 26/11-00.
Sted: Store Lesesal, Toppen av Fysikkbygget.
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 17.09.01
Vi kommer til å snakke kort om pumpeteoremet for regulære språk, men kommer til å utsette detaljer i beviset til gjennomgåelsen av de tilhørende oppgavene tirsdag 18/9.
Vi vil innføre kontekstfrie gramatikker og se på noen eksempler. Jeg tar sikte på gå igjennom avsnittene 3.1 og 3.2 og regner også med å få tid til å definere pushdownautomater.
Mandag 24.09.01
Vi vil repetere definisjonen av pushdown-automater og gi en presis definisjon av hvordan en pushdown-automat virker og av hvilket språk den gjenkjenner.
Vi skal vise i detalj at ethvert kontekstfritt språk kan gjenkjennes av en pushdown-automat.
Vi skal vise hvordan man kan konstruere en kontekstfri gramatikk for språket gjenkjent av en vilkårlig pushdown-automat, men vi må utelate noen detaljer i beviset av tidshensyn.
En viktig anvendelse av dette teoremet er at snittet mellom et regulært språk og et kontekstfritt språk er kontekstfritt.
Mandag 01.10.01
Vi vil gå igjennom pumpeteoremet for kontekstfrie språ:k med noen anvendelser.
Etter pausen vil vi snakke om deterministiske pushdownautomater og om hvordan vi kan tilrettelegge en kontekstfri gramatikk slik at den kan parseres av en deterministisk pushdownautomat.
Mandag 08.10.01
Vi skal starte på kapittelet om Turing-maskiner og jeg regner med å dekke avsnitt 4.1 i læreboka.
Vi kommer til å illustrere noen Turingmaskiner ved hjelp av Turings verden.
Mandag 15.10.01
Vi repeterer definisjonen av Turingmaskiner og lærebokas forslag til hvordan man kan presentere Turingmaskiner.
Vi definerer begrepene "beregnbar", "avgjørbar" og "semiavgjørbar" og knytter dem til de betegnelsene læreboka benytter. Vi vil se på et par eksempler.
Videre vil vi se på om vi får noen større regnekraft om vi gir Turinmaskinene utvidete muligheter i form av flere lesehoder, flere bånd å regne på m.m.
Hvis vi får tid, vil vi ta en begynnende prat om ikke-deterministiske Turingmaskiner. Disse vil spille en stor rolle i drøftelsen av P = NP-problemet mot slutten av semesteret.
Mandag 22.10.01
Denne uken vil vi snakke om ikke-deterministiske Turingmaskiner og om generelle gramatikker.
Forelesningen er delvis en forberedelse til kapitlet om P = NP og delvis en illustrasjon av hvordan semiavgjørbare språk ser ut.
Mandag 29.10.01
Denne uken vil vi se på konstruksjonen av en universell Turingmaskin i første time. I andre time vil vi vise uløsbarheten av stoppeproblemet og av en del andre beslektede problemer.
I den ene anvendelsen av uløsbarheten av stoppeproblemet stoppet vi opp med følgende:
Mengden av representasjoner av Turingmaskiner som ikke stopper uansett input er en uavgjørbar mengde.
Bevis
La Turingmaskinen M og ordet w være gitt.
Konstruer maskinen N som til input v gjør følgende:
-- Undersøk om v = w.
-- Hvis svaret er JA, kjør M.
-- Hvis svaret er NEI, gå inn i en uendelig løkke
N unlater å stoppe uansett input hvis og bare hvis M ikke stopper på w.
Dermed har vi redusert stoppeproblemet til dette problemet, så dette problemet er selv uløsbart.
Mandag 05.11.01
Vi definerer kompleksitetsklassen P, ser på noen problemer som ligger i P, et problem som ikke ligger i P og noen problemer som tilsynelatende ikke ligger i P.
Et viktig aspekt er å diskutere hvordan reelle problemstillinger kan representeres som formelle språk.
Mot slutten vil vi definere kompleksitetsklassen NP og begynne prosessen med å: se at de problemene vi ikke avgjorde om lå i P eller ikke faktisk ligger i NP.
Dette vil vi trolig måtte fortsette på den siste forelesningen, som er 19/11-01.
Det blir IKKE forelesning 12/11-01.
Mathias Barra, en av studentene i fjor, sendte meg adressen til en side ved KTH i Stockholm hvor en rekke approksimasjonsresultater for problemer som faller inn under klassen NP er behandlet. Den viser hvor vidt klassen NP sprer seg når det gjelder problemstillinger. Jeg har ikke testet om adressen er oppegående også i år.
Tilbake til toppen.
Tirsdag 20.11.01
Eksamen 25/11-2000, hele settet.
Vi blir enige om hvilke av disse oppgavene og de som måtte stå til rest fra to uker tilbake vi skal prioritere. Jeg anbefaler at vi gjennomgår oppgave 5, som blir den eneste øvelsesoppgaven om P og NP vi rekker å se på.
Tirsdag 06.11.01
Lewis og Papadimitriou: Oppgaver 5.3.1, 5.3.2 og 5.3.3.
Så langt jeg kan huske fra i fjor, så har forfatterne ikke passet på å justere formuleringen av 5.3.1 a) og hintet i 5.3.5 b) til konvensjonene i den nye utgaven av læreboka. Det blir en ekstra utfordring å reformulere hjelpepåstandene slik at konklusjonen holder.
Vi gir ingen nye eksamensoppgaver foreløpig, før vi ser hvor langt vi kommer uken før.
Neste uke er det ingen oppgaveregning, da foreleseren befinner seg i Tyskland.
Tirsdag 30.10.01
Lewis og Papadimitriou: Oppgaver 4.5.1 og 4.6.2.c)
Eksamen 28/11-98 Oppgave 4.
Det står mange oppgaver til rest fra tidligere uker.
Blir det tid til overs tar vi en fagprat.
Tirsdag 23.10.01
Lewis og Papadimitriou: Oppgaver 4.2.1, 4.2.3 og 4.2.4.
Eksamen 8/12-90 Oppgave 3
Eksamen 7/12-91 Hele settet (Vi rekker trolig ikke mer enn første oppgaven denne dagen).
Tirsdag 16.10.01
Lewis og Papadimitriou: Oppgaver 4.1.1, 4.1.5, 4.1.6, 4.1.7, 4.1.9 og 4.1.10.
Eksamen 9/12-88 Oppgave 3
Eksamen 9/12-89 Oppgave 1
Eksamen 8/12-90 Oppgaver 2 og 4.
Vær oppmerksom på at konvensjonene for hvordan båndet på en Turingmaskin skal se ut, er litt anderledes i de eldre eksamensoppgavene.
Det er ikke noe utvalgt endesymbol for å markere venstre ende av båndet. De gamle Turingmaskinene kunne dette utfor kanten.
Dobbelkryss # markerer blank rute.
Man starter en beregning med lesehodet på den første blanke ruten til høyre, og ikke som nå, til venstre.
Tirsdag 09.10.01
Lewis og Papadimitriou: Oppgaver 3.5.1, 3.5.5a), 3.5.7, 3.5.8, 3.5.14, 3.5.15, 3.7.1 og 3.7.5.
3.5.17 d) viste seg å være for vanskelig, så den vil vi droppe. Jeg vil snakke litt om hvordan den kan løses.
Eksamen 9/12-89 Oppgaver 2 og 4.
Tirsdag 02.10.01
Lewis og Papadimitriou: Oppgaver3.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 Oppgave 6
Eksamen 8/12-90 Oppgave 1
Tirsdag 25.09.01
Lewis og Papadimitriou: Oppgaver 3.1.1, 3.1.3 og 3.2.4.
Eksamen 9/12-88 (Obs! 99 var feiltrykk) Oppgave 1.
Eksamen 2/3-90 Oppgaver 1, 3, 4 og 5.
Tirsdag 18.09.01
Lewis og Papadimitriou:
Oppgaver 2.3.4, 2.3.6, 2.3.7, 2.3.12, 2.1.4.a, 2.4.1, 3.4.2 og 2.4.5.
Tilbake til toppen.
Denne siden er redigert av Dag Normann, Matematisk Institutt.
Sist oppdatert 20/11-01.