Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Kennwort: Herbst 661 1 5

2008

Arbeitsplatz-Nr.:

Erste Staatsprüfung für ein Lehramt an 6ffentlichen Schulen

— Prüfungsaufgaben —
Fach: Informatik (vertieft studiert)
Einzelprüfung: Theoret. Informatik, Algorithmen

Anzahl der gestellten Themen (Aufgaben): 2
Anzahl der Druckseiten dieser Vorlage: 8

Bitte wenden!
Herbst 2008 Einzelprüfungsnummer 66115 Seite 2

Thema Nr. 1

Aufgabe 1: Datentypen

Betrachten Sie das Verhalten von Kellern (stack), Warteschlangen (queue) und Prioritétswarteschlagen
(priorityqueue oder heap), in die Zahlen eingefügt und wieder gelöscht werden.

Für die Prioritäten gilt: x vor y genau dann wennx>y.

in(x) bedeutet, dass die Zahl x eingefügt wird (in der Java API add(E o) oder push(E o))
out() gibt eine Zahl aus und löscht das ausgegebene Element (in der Java API pop() oder poll() ).

Am Anfang sind alle Datentypen leer.
In welcher Reihenfolge werden die Zahlen bei der nachfolgenden Sequenz

in(10), in(9), in(20), in(5), in(2), in(1), out(), out(), in(15), out(), out(), in(12), in(7), out(), out(), out(),
in(3), out(), out(), out()

a) bei einem Keller,

b) bei einer Warteschlange,

c) bei einer Prioritätswarteschlage (mit x>y) ausgegeben?

d) Beschreiben Sie in einer Programmiersprache ihrer Wahl oder in Pseudocode, wie man einen
Keller in einem Array implementieren kann, so dass die Operationen "in" und "out" effizient
(asymptotisch optimal) realisiert werden.

Ihre Beschreibung muss die Deklarationen des Arrays und der relevanten Variablen
und der Methoden/Funktionen enthalten.

Es reicht nicht, z. B. java.lang.stack zu importieren.

Achten Sie dabei auf mögliche Fehler bei der Ausführung der Operationen „in“ und „out“.
Im Fehlerfall kann Ihr Programm mit "exit" beendet werden.

Fortsetzung nächste Seite!
Herbst 2008 Einzelprüfungsnummer 66115 Seite 3

Aufgabe 2: O-Notation

a) Ordnen Sie die nachfolgenden Funktionen (über den positiven natürlichen Zahlen n> 1)
aufsteigend in der O-Notation. (Ein Beweis ist nicht gefordert.)

fi(n)= 10n

f(n) = 0,1 n2

f3(n)= n logn

f4(n) = 0,001 n!

fs(n) = 0,001 n3

fe(n) = 100 logign (Logarithmus zur Basis 10)
b) Zeigen Sie für zwei nach ihrer Ordnung benachbarte Funktionen g und h, dass geO(h) gilt.
Aufgabe 3: Sortierverfahren
Eine Menge von reellen Zahlen (type double) sei in einer Liste (oder wahlweise in einem Array) A
gespeichert.
Betrachten Sie Quicksort in einer Implementierung (Version), bei der jeweils das erste Element

der Liste (oder des betrachteten Abschnitts des Arrays) als Pivotelement gewählt wird.

a) Beschreiben Sie informal die Arbeitsweise von Quicksort.
Geben sie die benötigten Parameter und die Vorgehensweise an.

b) Wie arbeitet das von ihnen unter a) beschriebene Quicksort auf der folgenden Liste (Array) A?
Geben Sie die Reihenfolge der Elemente jeweils nach den Durchläufen/Aufrufen bei Quicksort an.
A= (3,0; 3,14; 0,0; 2,9; 7,7; 2,3; 11,0; 9,1; 5,2; 0,5)

c) Ist Quicksort in der obigen Version das asymptotisch beste Sortierverfahren?
Begründen Sie ihre Antwort!

Aufgabe 4: kürzeste Wege

Gegeben sei der nachfolgend gezeichnete ungerichtete Graph G = (V,E) mit
den Knoten a,...., h.

Die Zahlen an den ungerichteten Kanten geben deren Lange an.

Fortsetzung nächste Seite!
Herbst 2008 Einzelprüfungsnummer 66115 Seite 4

Gesucht ist ein (der) kürzester Weg von a nach h.

a) Beschreiben Sie wie der Dijkstra-Algorithmus auf G arbeitet.
Geben Sie dazu an, in welcher Reihenfolge die Knoten bearbeit werden und welche
Werte dort gespeichert werden.

b) Wie lang ist der der kürzeste Weg von a nach h?

Fortsetzung nächste Seite!
Herbst 2008 Einzelprüfungsnummer 66115 Seite 5

Aufgabe 5: formale Sprachen

Sei L={we {a,b,c,d}*| w=arb4ctds | p,q,r,s>1}.

In welcher Klasse der Chomsky-Hierarchie (regulär, kontextfrei, kontextsensitiv, rekursiv aufzählbar)
liegt L?

Gesucht ist die kleinste Klasse.
Begründen Sie Ihre Antwort!

Aufgabe 6: reguläre Mengen

Zeigen Sie durch Angabe der Konstruktionsvorschrift für endliche Automaten,
dass die Differenz von zwei regulären Sprachen Lı\L> regulär ist.

Aufgabe 7: formale Sprachen

Ist die Sprache L = {aPb4cP | p,q20}
regulär
oder ist sie nicht regular, aber kontextfrei
oder ist sie nicht kontextfrei?

Begründen Sie Ihre Aussagen!

Es darf als bekannt vorausgesetzt werden, dass es für die regulären bzw. die kontextfreien Sprachen
passende Pumping-Lemmas gibt. Man muss das passende Pumping-Lemma ggf. anwenden.

Aufgabe 8: Turingmaschinen

a) Konstruieren Sie eine deterministische Turingmaschine M mit L(M)=L.
Beschreiben Sie zusätzlich, wieM arbeitet (Stil: M liest a's und speichert ....)

L= {aP bd cP d9 | pq >1}.

b) Welche Zeit- und welche Speicherkomplexität hat Ihre Turingmaschine M?
Es reicht die Angabe einer geeigneten Funktion f(n) mit n=2p+2q für die Länge der Eingabe.
Die O-Notation darf verwendet werden.
Erläutern Sie die Schranken für M.
Herbst 2008 Einzelprüfungsnummer 66115 Seite 6

Thema Nr. 2

Aufgabe 1: AVL-Bäume

a) Fügen Sie nacheinander dieZahllen 9 87 246153
in einen anfangs leeren AVL-Baum ein.
Repräsentieren (zeichnen) sie alle AVL-Bäume jeweils vor einer notwendigen Rotation
und beschreiben Sie die Rotationen (z.B. LL-Rotation für die Zahlen ....)

b) Konstruieren Sie einen AVL-Baum mit 12 Knoten mit maximaler Tiefe (Höhe) und
begründen Sie Ihre Lösung.

Aufgabe 2: abstrakte Datentypen

Gegeben sei ein abstrakter Datentyp ADT mit den folgenden Operationen (über den ganzen Zahlen)
empty() Kreiert die leere Struktur
isempty() Testet auf Leerheit

insert(x) Einfügen des Elements x
deletemin() Löschen des Elements mit dem kleinsten Wert
deletemax() Löschen des Elements mit dem größten Wert

Entwerfen/beschreiben Sie eine Datenstruktur für eine effiziente Realisierung des ADT mit
höchstens O(log n) Kosten je Operation.

Aufgabe 3: Wegealsorithmen

Ein gerichteter Graph G sei durch die folgende Entfernungsmatrix gegeben.

Ss a b c d e f t
25 80 45
13| 25| 70
6 70

40
31
30

Ss
a
b
6
d
e
f
t

(i) Konstruieren Sie eine Zeichnung für G. (Tipp: Zeichnen Sie s ganz links und t rechts.)
(ii) Berechnen Sie die kürzesten Wege ab s mit dem Dijkstra-Algorithmus.
Protokollieren Sie, in welcher Reihenfolge der Dijkstra-Algorithmus den Knoten ihre
kürzeste Entfernung zuweist.
(iii) Markieren (oder notieren) Sie den kürzesten Weg von s nach t und berechnen Sie seine Länge.

Fortsetzung nächste Seite!
Herbst 2008 Einzelprüfungsnummer 66115 Seite 7

Aufgabe 4: Automaten und formale Sprachen

Gesucht ist die Menge L aller Dezimalzahlen über % = {0,1,2,3} (mit führenden Nullen),
die durch 2 oder (logisches oder) durch 3 teilbar sind.

Beschreiben Sie L durch einen Automaten oder durch eine Grammatik.

In welcher Klasse der Chomsky-Hierarchie liegt L? Geben Sie die kleinstmögliche Klasse
der Chomsky-Hierarchie an.

Aufgabe 5: Klammersprachen
Sei L die Menge der Wörter w e { (,),a, b}*

die an beliebigen Stellen die Zeichen „a“ oder „‚b“ haben können und die bezüglich „(“ und „)‘“ korrekt
geklammert sind.

(i) Ist L regular?
(ii) Ist L kontextfrei?
(iii) Ist L entscheidbar?

Begründen Sie ihre Entscheidung.

Aufgabe 6: entscheidbare oder rekursive Sprachen

Zeigen und begründen Sie:
Die symmetrische Differenz X® Y= {w| weX und weY oder weX und weY}

zweier entscheidbarer Sprachen ist entscheidbar.
Tipp: Es wird keine formale Konstruktion verlangt; es reicht eine informale "high-level" Argumentation.

(Die rekursiven Sprachen sind definiert durch .... Daher haben sie die folgende Eigenschaften..... Somit
kann man für X ® Y konstruieren ...)“

Aufgabe 7: NP-Vollständigkeit

Das k-Färbbarkeitsproblem auf Graphen ist das Problem, ob man die Knoten eines ungerichteten Graphen
G=(V,E) so mit höchstens k Farben färben kann, dass benachbarte Knoten verschiedene Farben haben.

Es ist bekannt (und kann vorausgesetzt werden), dass das 3-Färbbarkeitsproblem auf Graphen NPvollständig ist.

Ist auch das 4-Färbbarkeitsproblem NP-vollständig?
Begründen Sie ihre Antwort!

Tipp: Ergänzen Sie einen neuen Knoten und viele Kanten.

Fortsetzung nächste Seite!
Herbst 2008 Einzelprüfungsnummer 66115 Seite 8

Aufgabe 8: Klassifikation

Gegeben seien die folgenden Klassen von Sprachen:

: die kontextfreien Sprachen, CFL

NP

: die rekursiv aufzählbaren (oder positiv semi-entscheidbaren) Sprachen, RE
: die regulären Mengen, REG

die rekursiven oder entscheidbaren Sprachen, REK

Bonuw»

Ordnen Sie diese Klassen bezüglich der bekannten und bewiesenen Inklusionen
und begründen Sie Ihre Antwort in der Form: Die Klasse X wird durch
Maschinen des Typs x definiert und diese sind ein Spezialfall von Maschinen des Typs y für Y.

Wo gelten echte Inklusionen und warum?

Tipp: Komplexitätsklassen, z. B. mit exponentiellem Aufwand (Zeit- oder Speicherplatz)
sind echte Teilmengen der rekursiven Sprachen REK.