Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: JE Herbst 66 1 1 5 2009 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik(vertieft studiert) Einzelprüfung: Theoretische Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 7 Bitte wenden! Herbst 2009 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Sei © = {0,1,$} und sei INo = {0, 1, 2,...}. a) Sei “ Ly = {0"$1" | n € INo} U {0°"$1" | n € INo} . Beispiele: 00$111111 € Li, $ € L1, 00081 € Ln. i) Zeigen Sie, dass Lı kontextfrei ist, indem Sie eine kontextfreie Grammatik G angeben mit L(G) = L.. ii) Begründen Sie, warum Ihre Grammatik genau die Sprache L, erzeugt. b) Formulieren Sie das Pumping-Lemma für kontextfreie Sprachen: „Sei L eine kontextfreie Sprache über dem Alphabet 3. Dann gibt ...“ c) Zeigen Sie z. B. mittels Pumping-Lemma für kontextfreie Sprachen, dass die Sprache La = {0"$1°"$0" | n € INo} nicht kontextfrei ist. Beispiel: 00$111111$00 € La Aufgabe 2: a) Definieren Sie die zum Halteproblem für Turing-Maschinen gehörende Menge H. b) Gegeben sei das folgende Problem E: „Entscheide, ob es für die deterministische Turing-Maschine mit der Gödelnummer n eine Eingabe gibt, für die die Turing-Maschine hält.“ Zeigen Sie, dass E nicht entscheidbar ist. Benutzen Sie, dass H aus (a) nicht entscheidbar ist. c) Angenommen, es wurde gezeigt, dass P = NP ist. Zeigen Sie, dass dann jede Sprache Le P sogar NP-vollständig ist. Fortsetzung nächste Seite! Herbst 2009 "Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: a) Geben Sie einen deterministischen endlichen Automaten an (Zeichnung), der die Sprache L3 = {a'b’ | i,j € INo, 1 und j sind durch 3 teilbar} akzeptiert. (INo = {0,1,2,...}) Beispiele: aaabbbbbb € La, aaabbb € Ls, € € La. b) Beweisen oder widerlegen Sie die folgende Behauptung: Ist die Sprache L regulär, dann ist auch jede Obermenge von Z regulär. c) Zu einem Wort w = 014243... Gm, ist suffix(w) = {€, An, Gn—18n, An—2An_14n,..., 014203 ...an} die Menge aller Suffices von w. Beweisen oder widerlegen Sie die folgende Behauptung: Ist die Sprache Z regulär, dann ist auch sufix(L) = U suffix(w) wel Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer: 66115 Seite: 4 Aufgabe 4: Erklären Sie die jeweils wesentliche(n) Idee(n) folgender Informatik-Konzepte in jeweils maximal drei Sätzen: a) Adjazenzliste b) Mergesort c) Lineare Suche d) Rekursive Datenstruktur Aufgabe 5: Gegeben seien n in einem Kreis stehende Kinder, die einen Abzählreim mit k Silben spielen. Dabei wird ausgehend von einem ersten Kind mit jeder weiteren Silbe des Abzählreims im Kreis herum (im Uhrzeigersinn) auf das jeweils nächste Kind gezeigt. Das Kind, auf das bei der letzten Silbe des Reims gezeigt wird, scheidet aus. Anschließend wird mit dessen Nachfolger fortgesetzt und der Abzählreim erneut gesprochen. Der Nachfolger eines Kindes sei dabei das Kind, das im Uhrzeigersinn hinter diesem steht unter der Annahme, dass alle in die Mitte des Kreises schauen. Das Ganze wird so lange durchgespielt, bis nur noch ein Kind übrig ist. Dieses hat gewonnen. Gegeben sei der Abzählreim: 1,2,3,4,5,6,7 eine alte Frau kocht Rüben, eine alte Frau kocht Speck - und du bist weg! Im Kreis stehen dabei in dieser Reihenfolge folgende Kinder: Pia, Kai, Marie, Tina, Peter, Anja, Dieter und Franz a) Wer gewinnt, wenn bei Pia beg nern onnen wird? b) Geben Sie in einer gängigen Programmiersprache oder als Pseudocode einen gut kommentierten Algorithmus an, der ausgehend von einer Menge von n Kindern, einem Kind, das startet, und einem Abzählreim mit k Silben das gewinnende Kind ermittelt. Ihre Lösung soll als Datenstrukturen nur einfache Variablen und Arrays verwenden, aber keine Zeigerstrukturen. c) Welche Laufzeit- und welche Platzkomplexität hat Ihr Algorithmus? Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer: 66115 Seite: 5 Aufgabe 6: Datenstruktur für Intervalle SeiM = {1,2, ... ,‚n} eine Menge aufeinander folgender natürlicher Zahlen. Für jedesi ¢ M sei ein Wert w (1) definiert. Gesucht ist dann ein hinsichtlich Speicherbedarf und Laufzeit effizienter Algorithmus, der zu einem gegebenen Intervall [i,j] miti,j e Mden Wert w(i) + ... + w(j) ,falls i < 3 w(i,j) =y0 ‚falls i > j \w(i) ‚fals i = J berechnet. Der Algorithmus soll aus zwei Phasen bestehen: a) b) 1. Aufbau einer geeigneten Datenstruktur (Preprocessing). 2. Berechnung eines Wertes w (i,j). Formulieren Sie gut kommentiert in einer gängigen Programmiersprache oder als Pseudocode einen Algorithmus, der dieses Problem mit Hilfe eines eindimensionalen Arrays löst, das die Werte w (i)nach i aufsteigend sortiert speichert. Geben Sie mit Begründung die Laufzeit, den der Algorithmus nach dem Preprocessing in Phase 2 benötigt, und den allgemeinen Speicherplatzbedarf an. Formulieren Sie nun gut kommentiert in einer gängigen Programmiersprache oder als Pseudocode einen Algorithmus, der dieses Problem mit Hilfe eines zweidimensionalen Arrays löst. Geben Sie mit Begründung die Laufzeit, die der Algorithmus nach dem Preprocessing in Phase 2 benötigt, und den allgemeinen Speicherplatzbedarf an. Eine effiziente Möglichkeit zur Lösung dieses Problems ist die Verwendung eines so genannten Segmentbaumes. Für das BeispielM = {1,2,3,4,5,6} sieht ein solcher wie folgt aus: 3) Formulieren Sie wiederum gut kommentiert in einer gängigen Programmiersprache oder Pseudocode einen Algorithmus, der das Problem mit Hilfe eines solchen Segmentbaumes löst. Geben Sie dann mit Begründung die Laufzeit, die der Algorithmus nach dem Preprocessing in Phase 2 benötigt, und den allgemeinen Speicherplatzbedarf an. Herbst 2009 Einzelprüfungsnummer: 66115 Seite: 6 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Stufen Sie die folgenden Sprachen über dem Alphabet © = {a,b,c} in die Chomsky-Hierachie ein. Begründen Sie jeweils Ihre Antwort. \ Ly = farb™c® |n,m,k>1} b) Lo = {a"b™c" | m,n > 1} ) Lg = {a"b"c? |n > 1} d) L4 = {(ab)"a(ba)” | n > 1} e) Ls = {w | w codiert eine Turingmaschine, deren Ausführung bei leerer Eingabe hält} a Cc f) Le = {w | w codiert eine Turingmaschine, deren Ausführung bei leerer Eingabe nicht halt } Bei den letzten zwei Aufgabenteilen ist eine sinnvolle Codierung von Turingmaschinen durch Zeichenketten über 2 zugrunde gelegt. Aufgabe 2: a) Es seien L} und La reguläre Sprachen über & = {a,b,c}. Begründen Sie, dass die folgende Sprache dann auch regulär ist: LE = {w | für alle Zerlegungen w = uvz gilt: u € Ly > x € Le} Hinweis: Zeigen Sie zunächst, dass das Komplement von L regular ist. b) Es sei © = {0,...,9} und L C 2* die Menge aller Dezimaldarstellungen von Zahlen, die durch 2009 teilbar sind. Begründen Sie unter Verwendung des aus der Grundschule bekannten schriftlichen Divisionsalgorithmus, dass L regulär ist. Aufgabe 3: He Sprachen dieser Aufgabe sind über dem Alphabet U = {a,b,c} definiert. a) Beweisen oder widerlegen Sie folgende Aussage: Sind L} und La kontextfrei, so auch ihre Differenz Lı \ La. b) Zeigen Sie, dass die Sprache aller Wörter w, die die folgenden zwei Bedingungen erfüllen, kontextfrei ist: - Nach einem b kommt kein c mehr, also w = uw > ve {a,b}*; - Es sind nie mehr c’s als a’s, also w = uv > |ul. > Jule Hier bedeutet |w|, die Zahl der Vorkommen des Symbols x im Wort w. Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer: 66115 Seite: 7 Aufgabe 4: Das Problem der Schulstundenplanung ist wie folgt formuliert: Gegeben: Eine Menge L von Lehrern, eine Menge K von Klassen, eine Menge Z von Zeiten und eine Menge U von „Unterrichten“. Außerdem Funktionen k:U— Kund!:U—L, die jedem Unterricht u € U eine Klasse k(u) und einen Lehrer I(u) zuordnen. Gesucht: Eine Funktion z: U — Z, sodass für alle u,v € U gilt: uxvAz(u) = 2(v) > lu) Al(v) Aku) ¥ kv) d.h. gleichzeitig stattfindende Unterrichte gehören weder zum selben Lehrer, noch zur selben Klasse. Zeigen Sie, dass das Problem der Schulstundenplanung NP-vollständig ist. Für die NP-Schwere können Sie z.B. auf Graphenfärbung reduzieren. Aufgabe 5: Es bezeichne F'(h) die minimale Zahl von Knoten, die ein AVL-Baum der Höhe h enthalten kann. Die Höhe eines Baumes ist die Länge (Zahl der Kanten) des längsten Pfades von der Wurzel zu einem Blatt. Eine isolierte Wurzel hat Höhe 0. Eine Wurzel mit ein oder zwei Blättern als Kinder hat Höhe 1, etc. a) Geben Sie ein Beispiel eines AVL-Baums der Höhe 3 mi heaorti AD Ra bail ny LU. é wii 4 UL ocgr dass kein AVL Baum der Höhe 3 mit weniger als b) Begründen Sie ebenso, dass F(0) = 1, F(1) = 2, F(2) = 4, F(4) = 12. c) Leiten Sie aus diesen Beispielen eine Vorschrift ab, mit deren Hilfe man F(h +2) aus F(h) und F(h + 1) berechnen kann. TI AN D oO cr CD = & »< 5 =, & = ct Qu. 2 a a 9 ee. a oO d) Begründen Sie die Allgemeingültigkeit dieser Vorschrift so genau wie möglich. Aufgabe 6: Die Wäscheleinenaufgabe besteht darin, n Wäschestücke der Breiten bı, ba,...,b„ auf Wäscheleinen der Breite b aufzuhängen. Idealerweise sollte die Zahl der benutzten Leinen möglichst klein werden. Formal ist eine Aufhängung der Wäsche auf ! Leinen also eine Einteilung der Menge {1,...,n} in I! Klassen Lı,...,L,, sodass für alle j = 1...1 gilt Vier, b; < b. Eine Lösung der Wäscheleinenaufgabe ist dann eine Zahl ! und eine Aufhängung der Wäsche auf ! Leinen. Eine Lösung ist umso besser, je kleiner / ist. a) Beschreiben Sie einen sinnvollen Greedy-Algorithmus für das Wäscheleinenproblem. (Also nicht einfach für jedes Wäschestück eine neue Leine) b) Geben Sie ein Beispiel einer Wäscheladung (Instanz des Wäscheleinenproblems), für die Ihr Algorithmus mehr als die minimal mögliche Zahl von Leinen verbraucht. c) Nennen Sie ein Beispiel einer Problemstellung, die mit einem Greedy-Algorithmus optimal gelöst werden kann.