Prüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:

Frühjahr
Kennwort:

2004

66LI2

Arbeitsplatz-Nr.:

ErsteStaatsprüfungfür ein Lehramt an öffentlichenSchulen
Prüfungsaufgaben

Fach:

Informatik (vertieft studiert)

Einzelprüfung:

Automatentheorie, Komplexität, Algorith.

Anzahl der gestelltenThemen (Aufgaben):

2

Anzahl der DruckseitendieserVorlage:

7

Bitte wenden!

Frühjahr2004

Seite:2

Einzelprüfungsnummer
: 66112

fhema Nr. I

Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe I (Automatentheorie und formale Sprachen,30 Punkte)
Gegebensei ein nichtdeterministischerendlicherAutomat
qu ,{o,b} ,6,Qs,{n,
ffr : ({no,Qy,Q2,Qs',Q4,
})
}
wobei 6 durch folgende Tabelle definiert ist. Z. B. geht der Automat aus dem Zustand Qs
(Auswahl der Spalte) durch Lesen eines ,,a" (Auswahl der Zetle) in die Zustände Qs oder g,
über:

{qo, qr}
{qr}

{qz}
{qs}

9z
{qz}
{qs}

tqol

@

a

Qo
a

b
a

9r
{qo}
{qr}

a

9e

Qs

{qa}
{qr }

{qs}
{qs}

a

a

a)

ZeichnenSi e den gegebenennichtdeterministischenendlichenAutomaten.

b)

Wandeln Sie den nichtdeterministischenendlichenAutomaten N, durch Anwendung der
endlichenAutomaten D, um. Zeichin einendeterministischen
Teilmengenkonstruktion
n e nS i e D r .

c)

WendenSie den Table-Filling-Algorithmusoder ein anderesVerfahrenzur Minimalisierung auf D1 an und fassenSie alle äquivalentenZuständezusammen.ZeichnenSie denresultierendenAutomaten.

d) Welche Spracheerkennendie Automaten?GebenSie einen möglichst kurzen regulären
Ausdruckzur BeschreibungdieserSprachean!
Aufgabe 2 (Automatentheorieund formale Sprachen,30 Punkte)
Wir betrachtendie Sprache
L -

a)

{.tb"i

tr, ffi € No, *<t

}

BeweisenSie, dassdieseSprachenicht regulärist.
GebenSie eine kontextfreie Grammatik an, die L erzeugf.

b) GebenSie einenKellerautomatenan, der die Spracheerkennt,und zeichnenSie sein
Übergangsdiagramm.
FortsetzungnächsteSeite!

Frühjahr2004

Seite:3

: 66112
Einzelprüfungsnummer

Aufgabe 3 (Berechenbarkeit,30 Punkte)
a) ErläuternSie informell wie man mit Hilfe einer 1-Band-Turingmaschineeine k-BandTuringmaschinesimulieren kann.
b) BegründenSie, warum WHILE-Programme mächtigerals LooP-Programme sind. (Die
Begriffe LOOP-Programmund FOR-Programmwerden in der Literatur synonym gebraucht.)
c) Erläutern Sie, wie mit Hilfe desReduktionsprinzipsdie UnentscheidbarkeiteinesProblems gezeiglwerden kann.

Aufgabe 4 (Algorithmen, 30 Punkte)
Ein wichtiges Problem im Bereich der Graphalgorithmenist die BerechnungktirzesterWege.
Gegebensei der folgende Graph, in dem Städtedurch Kanten verbundensind. Die Kantengewichte gebenFahrzeitenan. Außer den durch Pfeile als nur in eineRichtungbefahrbargekennzeichnetenStraßensind alle Straßenin beiden Richtungenbefahrbar.

a) GebenSie zu dem obigen Graphenzunächsteine Darstellungals Adjazenzmatix an.
b) BerechnenSie nun mit Hilfe desAlgorithmusvon Dijkstra die kürzestenWege vom Knoten A zu allen anderenKnoten.

Aufgabe 5 (Datenstrukturen,30 Punkte)
Hashtabellenbilden eine effizienteDatenstrukturfür das so genannteWörterbuchproblem,bei
dem auf einerMenge von Objektendie Operationeninsert,deleteund memberbenötigtwerden.
a) SkizzierenSie die drei üblichenVorschläge^)r Behandlungvon Kollisionen beim geHashing.Welche Problemebringendie einzelnenVorschlägemit sich und
schlossenen
weshalbentstehenmancheProblemebei den elaborierterenVorschlägennicht?
FortsetzungnächsteSeite!

Frühjahr2004

Einzelprüfungsnunmer
: 661Lz

Seite:4

b) BeschreibenSie, wie Löschoperationenin Hashtabellenrealisiert werden können. Was ist
hierbei zu beachten?
c) BeschreibenSie eine Hashfunktion für den Fall, dassdie Schlüsselder zu verwaltenden
Objekte Zeichenkettensind (d. h. die Hashfunktion soll aus der Menge der Zeichenketten
in die Menge der Zellenadressenabbilden).BegründenSie die Wahl Ihrer Funktion.
d) Eine Alternative zu Hashverfahrenbilden binäre Suchbäume.Diese könnenjedoch unausgeglichenwerden.Deshalb wurden verschiedeneAnsätzeflir balancierteBäume entwickelt. Stellen Sie eine Art von balanciertenBäumen vor. GebenSie hierzu die Stnrktureigenschaftender balanciertenBäume möglichst präzisean und skizzierenSie knapp, wie
dieseStruktureigenschaft
en bei Einfügeoperationenerhaltenbleiben.

Aufgabe 6 (Systementwurf, 30 Punkte)
a) GebenSie exemplarischdrei Design-Pattern(oder Entwurfsmuster)an, erläuternSie deren Einsatzgebietund Funktionsweiseund diskutierenSie anhanddieserBeispiele verschiedenemögliche Arten von Design-Pattem.
b) Erstellen Sie ein Klassendiagramm(im Sinne der UML) für die Prüfungsverwaltungan
einer Hochschule.Sie sollten dabei zumindestStudenten,Prüfer, mündliche Prüfungen,
schriftliche Prüfungenund Prüfungsftichermodellieren.Nutzen Sie die Möglichkeiten der
Vererbungund bemühenSie sich um eine möglichst flexible Modellierung. Begründen
Sie dabeieinzelneEntwurßentscheidunsen.

-5Frühjahr2004

Einzelprüfungsnummer
: 661L2

Thema Nr. 2
Sämtliche Teilaufgaben sind zu bearbeiten!
Aufgabe I : (Arraysumme)
a) SchreibenSie eine Methode in Javaoder einer anderenimperativenProgrammiersprache,
die als Parameterein Integer-Array (beliebigerLänge) erwartetund als Wert die Summe
der Array-Elementezurück gibt. Es wird nicht nur die Korrektheit des Programms,sondern auch der Programmierstilbewertet!
b) GebenSie die Schleifeninvariante
an, die man für einenKonektheitsbeweisdesProgrammsim Hoare-Kalkül benutzenwürde.
c) An welchen Stellen im Programmmuss die Schleifeninvariantegelten?
-/

Aufgabe 2: (Breitensuchein Binärbäumen)
BenutzenSie eine funktionale ProgrammierspracheIhrer Wahl.
a) Definieren Sie einen Datentyp für einen Binärbaum,dessenKnoten mit Integerwerten
behaftetsind.
b) ProgrammierenSie eine Funktion, die einen solchenBinärbaum als Parametererwartet
und seineKnotenwertein einer Liste in Breitenordnungzurück gibt. Es wird nicht nur die
Konektheit des Programms,sondernauch der Programmierstilbewertet!
Aufgabe 3: (Endliche Automaten)
Wir betrachtenden folgendenendlichenAutomaten:

Ao
/

\

('ä---r\-'

.

o

$

a) Der Automat ist nichtdeterministisch.Es gibt ein Verfahren,mit dem man einen deterministischenaus einem nichtdeterministischenAutomatengewinnt.
i)
ii)

BeschreibenSie dasPrinzip diesesVerfahrenskurz.
Wenn der nichtdeterministischeAutomat n Zuständehat, wieviele Zuständekann
der abgeleitetedeterministischeAutomat im schlimmstenFall haben?

b) Wenden Sie dasKonstruktionsverfahrenauf den obigen Automaten an. Minimieren Sie
das Ergebnis,indem Sie alle unerreichbarenZuständedurchstreichen.Der deterministischeAutomat muss nur als Grafik angegebenwerden.
c) BeschreibenSie mit einemregulärenAusdruckdie Sprache,die diesebeidenAutomaten
erkennen.
FortsetzungnächsteSeite!

Seite:5

Einzelprüfungsnurrmer
: 66tLz

Frühjahr2004

Seite:6

Aufgabe 4 : (Abstiegsfunktion)
Hier ist eine Funktion (in Haskell kodiert), die angibt, ob die ihr übergebeneganzeZahl gerade oder ungeradeist:
even
even

. z Int
x = if

x<O th€n
ef.se

even (-x)
if x==O tb.en
e].se

True
if x,=:1

tben False
e].se even

(x-2)

GebenSie eine Abstiegsfunktionlt an,die die Terminierung von even für alle Eingabewerte
belegt:
a) GebenSie die Funktionsvorschriftvon h an.
b) Zeigen Sie, dassh die Eigenschafteneiner Abstiegsfunktionerflillt.

Aufgabe 5: (Sortieren)
In dieserFragebetrachtenwir Verfahren zum SortiereneinesArrays von Werten aus einer
total geordnetenMenge.
a) Wie ist präzisedefiniert,dasseineFunktiong in O (f (")) ist?
b) Beim Heapsort-Verfahrenbringt eine Funktion heapfy das Eingabe-Array in eine bestimmteForm. BeschreibenSie diese"Heap-Eigenschaft"
kurz und präzise.
c) Zu welcher O-Klasse gehörendie folgendenbeiden Sortierverfahren?
Bitte eine kurze Begründungangeben.
i) Quicksort
ii) Heapsort

Aufgabe 6: (Formale Sprachen)
Wir betrachtendie folgende Sprachesyrnmetrischer Zeichenfolgenüber dem Alphabet {0, 1} :
{"r.

. . r n r n . . . r r l n >o n ( V r : 0 ( ' i 1 n : r , e t 0 , 1 } ) }

a) Zuwelcher Typklasse(Typ 0-3) gehörtdieseSprache?
b) Wann ist eine Grammatik eindeutig?
c) GebenSie eine eindeutigeGrammatik für die Sprachean.
d) Mit welcherArt von Automatenlässtsich dieseSpracheerkennen?
GrenzenSie die Automatenartso präzisewie möglich ein.
FortsetzungnächsteSeite!

Frühjahr2004

: 66112
Einzelprüfungsnummer

Aufgabe 7: (NP-Vollständigkeit)
a) Was bedeutetes für ein Problem,NP-hart zu sein?
b) DefinierenSie präziseden Begriff der NP-Vollständigkeit.
c) BegründenSie den folgendenSatz:

(Ä NP-vollständigA AeP)

€=+ P-ffP

Seite:7