DM17 - Automatteori og Beregnelighed - 1999

[ QuickJump ^TM: Afl.Opgave 1, Afl.Opgave 2, Spørgetime ]

Informationen på denne side er ment som en hjælp til de studerende på mine DM17 eksaminatoriehold. Det er ikke ment som en erstatning for at møde op til timerne.

   Mine DM17-undervisningstimer ligger om torsdagen kl. 10 til 12 i U49 (hold S1) og kl. 14 til 16 i U49C (hold D1).

   I Netscape kan filerne ses ved tryk på venstre museknap over linket, og de kan hentes hjem til jer selv ved at holde SHIFT nede, mens der trykkes på museknappen. Prøv i øvrigt at trykke på højre museknap over et link.

   Har du kommentarer eller andet til denne side, så skriv.

   Se i øvrigt også Jørgens dm17-side, samt den tidligere instruktors, Lars's, gamle dm17-side.

   Der er en del meningsforstyrende trykfejl i bogen -- for at se en liste over trykfejl, klik her.

Afleveringsopgave 1

Som første afleveringsopgave skal I kigge på opgave 2.4.8 fra bogen, hvor en mængde udsagn skal vises enten at være sande eller falske. Generelt er der brug for en god mængde sund fornuft, men derudover kan sætning 2.3.1 og 2.4.1 samt opgave 2.3.6 være gode at kigge på.
Som lovet er her en liste, der angiver hvorvidt de enkelte udsagn er sande/falske:

a) Falsk.
b) Falsk.
c) Sand.
d) Falsk. (medmindre sproget kun har ét symbol a)
e) Sand.
f) Falsk, hvis |C| er uendelig, sand ellers.
g) Sand.

Afleveringsfristen er sat til 7. oktober 1999 kl. 16.01 -- afleveres senere end dette, vil opgaven ikke blive rettet.
I øvrigt er I meget velkomne til at stille spørgsmål, hvis der er problemer...
Som hjælp til at finde jeres sidste, små fejl, er her en standardbesvarelse til afleveringsopgaven. NB: Alt ansvar fralægges, idet opgaven let kan være behæftet med fejl... Finder du noget, så skriv endeligt.

Afleveringsopgave 2

Som lovet er her en standardbesvarelse til den anden afleveringsopgave. Igen fralægges ethvert ansvar -- finder du noget, der ikke virker rigtigt, eller som måske er direkte forkert, så skriv endeligt.

Spørgetime

Som aftalt holder jeg spørgetime onsdag den 12. januar 2000 kl. 14.15 - vi mødes ved U49A/B/C og prøver at se, om vi ikke kan finde et lokale deromkring...
Spørgsmål til spørgetimen sendes til mig senest den 10. januar kl. 13.30 per email (svalle@imada.sdu.dk) eller afleveres i mit postrum. Indsendte spørgsmål vil blive placeret her på siden efterhånden som de kommer ind.
NB: Du behøver kun at sende spørgsmål ind, hvis du vil være sikker på at få et svar - med andre ord er det nok en rigtig god idé at gøre.

Nuværende spørgsmål:

Må man som en del af en løsning til en opgave som januar 1999 opgave 3e, bruge at fx. "topologisk sortering" fra dm02 kører i poly.tid på en almindelig computer til at sige, at AP ligger i P, eller skal man argumentere helt fra grunden?
Ja, det må man gerne -- det skal blot være ting, der er kendt fra tidligere kurser (dvs. dm02), og hvor der ikke direkte står, at man skal beskrive en Turing-maskine. Fx. vil det i januar 1999 opgave 3b ikke være nok at skrive, at man skal bruge topologisk sortering.
Hvilke referencer m.v. må man lave til sætninger, opgaver m.v. fra bogen?
Se her for en beskrivelse af, hvad I må og ikke må.
I en opgave som januar 1999 opgave 3 c, hvor mange point vil følgende besvarelse give:

Dette følger direkte af e) og kommentaren på side 297 bogen, om at P ligger i NP.
Hvis man har lavet e) rigtigt / forkert (dvs. lidt rigtigt) hhv. ikke lavet e)?
Jørgens svar til dette:
Det er ok at sige, at dette følger direkte af e) og kommentaren på side 297 bogen, om at P ligger i NP.
Det antal point man får for dette vil muligvis afhænge af, hvor lidt man har lavet af e). Hvis man intet har gjort i e) får man nok ikke fuld point for c) på denne måde ellers gør man det nok. Man skal have sandsynliggjort, at man kan lave en TM for e).
Dette svar udelukker ikke, at jeg godt kunne have givet point for c) selvom e) ikke var lavet for en student, som laa lige på vippen (det viser trods alt noget forståelse og fortjener derfor noget).

Ellers er der ikke andet tilbage end at ønske god eksamenslæsning...