Praktische Übungen zur Vorlesung Theoretische Informatik I
Sommersemester 1998
Abgabe: Dienstag, 7. 7. 1998 in der Vorlesung
Aufgabe:
Implementieren Sie einen der folgenden Algorithmen (in C, C++ oder JAVA)!
Der Quelltext ist ausführlich zu dokumentieren.
Geben Sie obere Schranken der Laufzeit Ihres Algorithmus an!
Gruppenbildung (zu 2 - 3 Studenten) ist möglich (und erwünscht).
- Zu beliebig eingegebenem NEA soll der DEA konstruiert werden.(Potenzmengenkonstruktion)
- Zu beliebigem DEA ist der äquivalente minimale DEA gesucht. (Äquivalenzklassenbildung)
- Zu beliebigem Kleene-Term ist der endliche Automat zu finden.
- Zu beliebigem NEA ist der Kleene-Term zu konstruieren. (Gleichungssystem lösen)
- Zu beliebigem Wort w über dem Alphabet X ist der minimale DEA zu konstruieren, der X* w akzeptiert.
- Für einen beliebigen Graph G und eine Zahl k ist zu entscheiden, ob G eine k-Clique enthält.
- Gegeben sind k Klauseln mit je 3 Literalen aus n Variablen. Gesucht ist ein Graph G, so daß die Klauseln
genau dann erfüllbar sind, wenn G eine k-Clique enthält.
R. Winter, 11.06.1998