Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennwort: | Herbst 4 61 13 Arbeitsplatz-Nr.: 2 0 1 2 Erste Staatsprüfung für ein Lehramt an Öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (Unterrichtsfach) Einzelprüfung: Theoretische Informatik Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 9 Bitte wenden! Herbst 2012 _ Einzelprüfungsnummer 46113 Seite 2 Thema Nr. 1 Aufgabe (Komplexitätstheorie): Sei ImpF die Menge aller aussagenlogischen Formeln, die ausschließlich mit den Konstanten 0 (false) und 1 (true), logischen Variablen xi mit © e N und der Implikation > als Operationszeichen aufgebaut sind, wobei auch Klammern zugelassen sind. Insbesondere sind in /mpF nicht die logischen Operatoren — (not), A (and) und v (or) erlaubt. — Wir betrachten das Problem ImpSAT':: Gegeben: Fe ImpF. Problem: Ist F erfüllbar, d. h., gibt es eine Belegung der Variablen mit Konstanten 0 oder 1, so dass F den Wert 1 annimmt? Zeigen Sie: ImpSAT ist NP-vollständig. Sie dürfen benützen, dass das SAT-Problem (Erfüllbarkeitsproblem der Aussagenlogik) NP-vollständig ist. Fortsetzung nächste Seite! Herbst 2012 Einzelprüfungsnummer 46113 Seite 3 — Aufgabe (Berechenbarkeitstheorie): 1. Zeigen Sie, dass die Abstandsfunktion dist (m,n) = Im - n| primitiv rekursiv ist. Dabei bezeichnet "-" die ganzzahlige Subtraktion! 2. Zeigen Sie, dass die Funktion gsum(n) = ye primitiv rekursiv ist! Hinweis: Sie dürfen zusätzlich zu den Basisfunktionen der primitiven Rekursion die folgenden Funktionen als primitiv rekursiv annehmen: Addition (m + n), Multiplikation (m *n), modifizierte [m-.n, falls n < m, In . . Subtraktion (m+n = | 0 ° ; ) und Gleichheit (m =n). Sie dürfen die erweiterte , SONS Komposition und das erweiterte rekursive Definitionsschema verwenden! Fortsetzung nächste Seite! Herbst 2012 Einzelprüfungsnummer 46113 __ Seite 4 Aufgabe (Berechenbarkeitstheorie): Sei £ = {0,1} ein Alphabet und f : &* — &* die Funktion, die jede 0 aus einem Wort löscht (z.B. gilt f (00100110) = 111). Formal ist f durch die folgenden Gleichungen definiert: fe)=e, fOw)= fw), fdw)=1f(w) Konstruieren Sie eine 1-Band-Turingmaschine M ‚die f berechnet! Geben Sie M als Tupei an und beschreiben Sie die Zustandsübergangsfunktion als Graph, Tabelle oder Liste von Gleichungen! Kommentieren Sie Ihre Konstruktion durch eine informelle Beschreibung Ihrer Lösungsidee! Fortsetzung nächste Seite! Herbst 2012 Einzelprüfungsnummer 46113 Seite 5 Aufgabe (Formale Sprachen und Automatentheorie): Seien © = {a,b,c} und A =({1,2,3},2,6,1{3}) ein nicht-deterministischer endlicher Automat, der durch das folgende Übergangsdiagramm definiert ist: 1. Geben Sie einen regulären Ausdruck r, an, der L(A) darstellt! 2. Berechnen Sie mithilfe der Potenzmengenkonstruktion einen deterministischen endlichen Automaten B mit L(B)=L(A). 3. Sei 2, = u { d}. Geben Sie einen endlichen Automaten C an mit L(C) = z, \ L(A). Fortsetzung nächste Seite! Herbst 2012 Einzelprüfungsnummer 46113 Seite 6 Aufgabe (Reguläre Ausdrücke und Endliche Automaten): Für ein Alphabet £ und eine Sprache L < %* definieren wir die Sprache E(L)= (2125..0n1 [215 29 5.05 2p ELIA... Tg, € L} Damit ist E(L) die Sprache aller Wörter, die dadurch entstehen, dass man bei einem Wort aus L geradzahliger Länge jedes zweite Zeichen entfernt. 1. Geben Sie reguläre Ausdrücke für E(L((ab)*)) und Ei£calb| (aba)*)) an. 2. Gegeben sei folgender DFA N: | Geben Sie einen endlichen Automaten (DFA oder NFA) an, der E(L(N)) akzeptiert. 3. Zeigen Sie, z.B. mittels einer Automatenkonstruktion, die Gültigkeit folgender Aussage: Wenn L regulär ist, dann ist auch F(Z) regulär. Herbst 2012 Einzelprüfungsnummer 46113 Seite 7 Thema Nr. 2 Aufgabe 1: Formale Sprachen 1. Sind die folgenden Sprachen regulär? Begründen Sie Ihre Antwort! (a) Die Menge aller Zeichenketten der Form w o w", wobei w | eine Zeichenkette aus Nullen und Einsen der Länge |w| < 10 | ist und w”°’ das Wort w rückwärts gelesen ist. | (b) Die Menge aller Zeichenketten der Form 01°01/01*/0 für i,j > | 0 über dem Alphabet © = {0,1}. 2. Beweisen oder widerlegen Sie folgende Aussage: Sei X eine reguläre Sprache, dann ist auch jede Sprache Y C X regulär. 3. Löschen und Einfügen in reguläre Sprachen (a) Sei L eine reguläre Sprache über dem Alphabet © = {a,b,c}. Zeigen Sie, dass die Sprache 2’, die entsteht, wenn man aus den Worten w € L alle Vorkommen des Zeichens c entfernt, ebenfalls regulär ist. (b) Sei Z eine reguläre Sprache über dem Alphabet % und sei z ED. Zeigen Sie, dass die Sprache 2’ C (BU {r})" gegeben als L! = {x wx we... 2! wpr* | wp we... we € Lp w € Ds i; > 0} ebenfalls regular ist. 4. Chomsky-Normalform (a) Für welche Grammatiken gibt es eine Chomsky-Normalform? Wann ist eine Grammatik in Chomsky-Normalform? (b) Geben Sie für folgende Sprache eine Grammatik an und bringen Sie sie in Chomsky-Normalform. L = {a”b"c" |n,m >0} Fortsetzung nächste Seite! Herbst 2012 Einzelprüfungsnummer 46113 Seite 8 Aufgabe 2: NP-Vollständigkeit (a) Wann ist ein Problem NP-vollständig? Folgendes Problem wird CLIQUE genannt und ist NP-vollständig: gegeben: Ein Graph G= (V,E),emk>1. Frage: Hat G eine Clique (einen vollständigen Teilgraphen bei dem zwischen je zwei Knoten eine Kante besteht) mit > k Knoten? Folgendes Problem wird KNOTENÜBERDECKUNG genannt: gegeben: Ein Graph G = (V,£), eink >1. Frage: Hat G eine überdeckende Knotenmenge V’ C V (für alle Kanten {u,v} € E gilt ue V'VveEV’) mit höchstens k Knoten? (b) Zeigen Sie, dass KNOTENÜBERDECKUNG E NP. (c). Zeigen Sie, dass G= (V, E) hat eine Clique mit > k Knoten genau dann,wenn G = (V,{{u, v} lu, v € V, {u,v} ¢ E}) eine überdeckende Knotenmenge von héchstens |V| — k Knoten hat. (d) Folgern Sie daraus, dass KNOTENUBERDECKUNG NP-vollstandig ist. Fortsetzung nächste Seite! Herbst 2012 Einzelprüfungsnummer 46113 Aufgabe 3: Entscheidbarkeit und Berechenbarkeit (a) (d) Was ist der Zusammenhang des Konzepts Entscheidbarkeit für Sprachen mit dem Konzept der Berechenbarkeit für Funktionen? Wann sagt man, dass ein Problem P semi-entscheidbar ist? Beweisen oder widerlegen Sie folgende Aussage: Für eine konkrete Instanz / und ein beliebiges Entscheidungsproblem P (z.B. das Postsche Korrespondenzproblem) ist die Funktion fr mit f [wahr falls I eine ja Instanz von P ist, r= | Jalsch sonst. berechenbar. Seien A C 2* und B C T* Sprachen. Welche Eigenschaften muss eine Funktion f : 2* — T* besitzen, um A auf B zu reduzieren? (e) Betrachten Sie die Reduktion A