JBJDM1715

Pensum: Lewis og Papadimitriou 2nd edition: siderne 1-157, 179-209, 221-233, 245-262, 267-309, 317-333 (beviset for NP-komplethed af Hamilton kreds skal ikke kunnes i detaljer). Desuden skal I kunne Cook's sætning (Theorem 7.2.2), men ikke beviset for denne. Herudover er alle ugesedler, samt alle stillede opgaver pensum.

En bemærkning vedrørende kontekstefrie sprog: Husk, at et sprog L over et alfabet med kun et symbol er kontekstfrit hvis og kun hvis det er regulært. Se side 147 tredie afsnit.

Eksamen Fredag den 14. januar 9-13.

Nogle tip til eksamen:

• Det er tilladt at referere til resultater fra lærebogen. Det er altså ikke nødvendigt selv at vise eksistensen af en bestemt Turing maskine, hvis du kan referere til, at en Turing maskine med de ønskede egenskaber er lavet på side ... i bogen, eller at eksistensen følger af Theorem .... Derimod er det ikke tilladt, at referere til en anden bog om emnet! Det er heller ikke tilladt blot at referere til en opgave i bogen, heller ikke selvom den har været stillet. I skal altså selv skrive argumenter ned for alt der ikke nævnes eksplicit som en sætning, lemma, eksempel eller i teksten (minus opgaverne!!) i bogen.
• Det er tilladt at referere til ting man har lært i tidligere kurser (f.ex DM02,DM11).
• Læs ALLE opgaverne igennem før du starter med at regne. På den måde vil du (uanset om du tror det eller ej) uvilkårligt tænke over de andre opgaver, samtidig med, at du regner en anden. Desuden undgår du på den måde at gå igang med en svær opgave, medens du ikke får set på een, der er lettere for dig.
• Se godt efter, hvad der bedes om. Hvis der foreksempel står, at du skal redegøre i store træk for, at der findes en Turing maskine med en eller anden egenskab, så behøver du ikke konstruere denne (ved at angive overgangstabellen, eller tegne pilediagrammet). MEN du skal selvfølgelig give nok information til, at væsentlige detaljer er med. Du kan foreksempel angive hvordan båndindholdet skal/vil se ud på passende valgte tidspunkter og så fortælle i ord, hvorledes dette opnås. Her må der gerne refereres til kendte maskiner fra bogen (f.eks een der ganger to tal sammen, naar de er angivet i unær notation. Lige netop maskiner der regner på unære talrepr. må I gerne referere til, selvom bogen nu bruger binær repræsentation). Man skal selvfølgelig altid argumentere for, at de komponenter man selv foreslår, har den påståede egenskab.

  Hvis du bliver bedt om at bevise (eller som ofte formuleret lidt mildere: argumentére for) en påstand, så skal du medtage nok argumenter (incl. henvisninger til sætninger fra bogen) til, at vi kan se, at du har forstået de væsentlige skridt i beviset.

• Hvis du ikke kan finde ud af, at løse en opgave, men har en ide, så skriv den ned. Husk: du kan ingen point få for det du vidste, men ikke fik skrevet!
• Forsøg altid at begrunde dine påstande, f.eks. med henvisninger til steder i bogen, der understøtter disse.

Held og lykke med eksamen!

 
• About this document ...