Theoretische Grundlagen 2 in mki-B2, Hochschule Reutlingen
Dozent |
PD. Dr. K. Reinhardt
| Ort | Raum 4-118
|
Zeit | Do 9:15-12:30
| Umfang | 4 Semesterwochenstunden
|
Beginn | 2.10.08
| Übungen | in die Vorlesung integriert
|
Inhalt:
2.10.08: Formale Sprachen, Grammatiken, Chomsky-Hierarchie, endliche Automaten,
Seiten 2-8 in [Lan04],
9.10.08: ÜA 1-6, NEA => DEA
Seiten 9-10 in [Lan04],
16.10.08 Reguläre Grammatik => NEA, Reguläre Ausdrücke,
Seiten 10 - 11 in [Lan04],
23.10.08 RA => NEA, Seiten 11 - 12
Minimierung Seite 17 obere Hälfte in [Lan04]
oder Seiten 2 und 7 hier
30.10.08:
Abschlusseigenschaften, 18 unten in [Lan04]
oder Seite 4 hier,
Pumping (nur Idee) Seiten 14-15
06.11.08:
Petrinetze: Jahreszeitenbeispiel,
Animation,
Editor ,..
13.11.08: Reversibilität, Kontaktfreiheit, Beschränktheit, Petrinetzsprache,Vektoradditionssystem
20.11.08: Parikh-vektor, Lebendigkeit, deadlock
27.11.08: Vektoren:
Skalarprodukt ,
Kreuzprodukt ,
Matrix
04.12.08:
Lineares_Gleichungssystem ,
Inverse_Matrix
11.12.08: Codierung: Entropie, erwartete Codewortlänge, Fano, Huffman, Applet ,
18.12.08: Kontextfreie Sprachen:
Chomsky-Normalform Seiten 20,21 in [Lan04],
Abschlusseigenschaften, Satz von Parikh Seite 24 in [Lan04],
CYK-Algorithmus Seiten 25,26 oder hier
8.1.09: Analyse von Algorithmen, O-Notation
Folien 7-20,
Graphalgorithmen,
Folien 1-9, 18-21, 29-37, 88-,
15.1.09:
Komplexitätsklassen P, NP, NP-vollständige Probleme Seiten 57-63 in [Lan04]
8.1.09:
Berechenbarkeit Turing- Loop-, While-,
Unentscheidbarkeit des Halteproblems
Seite 37... in [Lan04]
Übungsaufgaben:
ÜA 1:
Konstruiere einen endlichen Automaten (Tabelle oder graphische Darstellung),
der die Sparche aller Wörter über dem Alphabet {a,b,c}, die die
folgende Eigenschaft haben, akzeptiert:
Zwischen zwei Vorkommen eines a muss ein b kommen und
zwischen zwei Vorkommen eines b muss ein a kommen.
ÜA 2:
Konstruiere einen endlichen Automaten (Tabelle oder graphische Darstellung),
der die Sparche aller Wörter über dem Alphabet {a,b,c,d}, die die
folgende Eigenschaft haben, akzeptiert:
Wenn an einer Stelle ein b unmittelbar nach einem a kommt,
so muss irgendwann später ein c kommen.
ÜA 3:
Konstruiere einen endlichen Automaten (Tabelle oder graphische Darstellung),
der die Sparche aller Wörter über dem Alphabet {a,b,c}, die die
folgende Eigenschaft haben, akzeptiert:
Die Anzahl der a's ist ungerade und die Anzahl der b's ist durch 3 teilbar.
ÜA 4:
Konstruiere eine Grammatik, die die Spache aus
ÜA 1: erzeugt.
ÜA 5:
Konstruiere eine Grammatik, die die Spache aus
ÜA 2: erzeugt.
ÜA 6:
Konstruiere eine Grammatik, die die Spache aus
ÜA 3: erzeugt.
ÜA 7:
Konstruiere einen endlichen Automaten,
der die Wörter über dem Alphabet {0,1} akzeptiert,
die eine Binärzahl darstellen, die bei Division mit 5 den Rest 1 hat.
ÜA 8:
Konstruiere einen endlichen Automaten,
der die Wörter über dem Alphabet {.,0,1,2,3,4,5,6,7,8,9} akzeptiert,
die ein Präfix der Dezimaldarstellung von 1/7 sind.
D.h. das Wort fängt mit einem "." an.
ÜA 9:
Konstruiere einen deterministischen endlichen Automaten,
der die Wörter über dem Alphabet {0,1} akzeptiert,
die an 4-t letzter Stelle eine 0 haben.
ÜA 10:
Konstruiere einen nicht-deterministischen endlichen Automaten,
der die Wörter über dem Alphabet {a,c,e,n,r,t} akzeptiert,
in denen "tataren" als Infix (d.h. Teilwort) vorkommt.
ÜA 11:
Konstruiere den deterministischen Automaten zu dem in letzter Aufgabe.
ÜA 12:
Konstruiere einen endlichen Automaten,
der die Wörter über dem Alphabet {0,1} akzeptiert,
die rückwärts gelesen eine Binärzahl darstellen,
die bei Division mit 3 den Rest 2 hat.
(D.h. die niederwertigen Bits werden nun zuerst gelesen, die Sprache
ist genau spiegelbildlich zur Sprache im ersten Beispiel in der Vorlesung.)
(knifflig)
ÜA 13:
Konstruiere einen nichtdeterministischen endlichen Automaten zur
Grammatik S -> 1Z | 2Z | 3Z | 4Z | 5Z | 6Z | 7Z | 8Z | 9Z | 0 | 0P ,
Z -> 0 | 0Z | 1 | 1Z | 2 | 2Z | 3 | 3Z | 4 | 4Z | 5 | 5Z | 6 | 6Z | 7 | 7Z | 8 | 8Z | 9 | 9Z | .A , P -> .A ,
A -> 0 | 0A | 1 | 1A | 2 | 2A | 3 | 3A | 4 | 4A | 5 | 5A | 6 | 6A | 7 | 7A | 8 | 8A | 9 | 9A
.
ÜA 14:
Beschreibe die Sprache der Wörter über dem Alphabet {a,b, ...z}
in denen sowohl "bombe" als auch "freiheit" vorkommt, durch einen regulären Ausdruck.
ÜA 15:
Beschreibe die Sprache der Wörter über dem Alphabet {a,b,c}
in denen ab nicht vorkommt, durch einen regulären Ausdruck.
ÜA 16:
Beschreibe die Sprache der Wörter über dem Alphabet {a,b}
in denen eine gerade Anzahl von a's vorkommt, durch einen regulären Ausdruck.
ÜA 17:
Beschreibe die Sprache der Wörter über dem Alphabet {a,b}
in denen eine gerade Anzahl von a's, die jeweils immer duch eine
ungerade Anzahl von b's getrennt sind, vorkommt, durch einen regulären Ausdruck.
ÜA 18:
Welche Sprache beschreibt folgender reguläre Ausdruck:
(a|b)*(b|c)*(c|d)* (Beschreibung mit Worten)
ÜA 19:
Welche Sprache beschreibt folgender reguläre Ausdruck:
((a(b(aa)*b)*(a|ba(aa)*b))|(b(a(bb)*a)*(b|ab(bb)*a)))* (knifflig,
es genügt einige Beispielwörter zu finden und dann die
Antwort durch Beobachtung zu erraten, z.B. liegt abababab in der Sprache?)
ÜA 20:
Welche Sprache beschreibt folgender reguläre Ausdruck:
(0|1(01*0)*1)* (knifflig,
es genügt einige Beispielwörter zu finden und dann die
Antwort durch Beobachtung zu erraten)
ÜA 21:
Konstruiere den Automaten für L(abc) unter
Verwendung des Automaten für L(ab) aus der Vorlesung.
ÜA 22:
Konstruiere den Automaten für L(b u lambda).
ÜA 23
Konstruiere den Automaten für L(b u a*).
ÜA 24:
Konstruiere den Automaten für L((a u b)*) unter
Verwendung des Automaten für L(a u b) aus der Vorlesung.
ÜA 25:
Konstruiere den Automaten für das Komplement von L((a u b)*)
über dem Alphabet {a,b,c}
ÜA 26:
Konstruiere einen Automaten für den Schnitt von
L((a u b)*a(a u b)*) und L((a u b)*b(a u b)*).
ÜA 27:
Minimiere den Automaten mit Startzustand z0, Endzustand z3
und Übergangstabelle
delta | z0 | z1 | z2 | z3 | z4 |
a | z1 | z1 | z3 | z0 | z3 |
b | z2 | z4 | z1 | z1 | z0 |
ÜA 28:
Konstruiere den Automaten für das Komplement von der Sprache aus ÜA 10:
ÜA 29-37
( am 20.11. von 35 bis 37) :
ÜA 38:
Welche Markierung hat das Petrinetz aus ÜA 29 nach einer Schaltfolge w,
die den Parikh-Vektor (8, 5) hat (d.h. t1 schaltet insgesamt 8 mal und
t2 schaltet insgesamt 5 mal), erreicht?
ÜA 39:
Konstruiere ein Petrinetz für die Sprache zum regulären Ausdruck
(a b* c d*)*
ÜA 40:
Verändere das Petrinetz aus ÜA 39 so, daß es nicht reversiebel und nicht beschränkt ist, ohne die Sprache zu ändern.
ÜA 41:
Konstruiere ein Petrinetz bei dem a mindestens drei mal so oft schalten muß wie b
und c nur schalten kann wenn a öfter als drei mal so oft wie b geschaltet hat.
ÜA 42:
Ist folgendes Netz beschränkt?
ÜA 43: Ist es stark lebendig?
ÜA 44: Ist es reversibel?
ÜA 45:
Berechne das Skalarprodukt der Vektoren
( 3, -2, 4)T und ( 4, -1, -1)T und die Länge
des Vektors ( 4, -1, -1)T
ÜA 46:
Berechne einen Vektor, der orthogonal zu ( 3, -2, 4)T und ( 4, -1, -1)T ist.
ÜA 47:
Berechne einen Vektor, der orthogonal zu ( 3, -2, 4)T und ( 4, -1, -1)T ist und zusätzlich die Eigenschaft hat, ( 42, 0, 0)T
plus eine Linearkombination der ersten beiden zu sein.
(knifflig, erfordert 3 Schritte.)
Lösung
ÜA 48:
Gegeben seien die Matitzen A = (
) und B = (
).
Berechne die Matrix 3A-2B.
ÜA 49:
Multipliziere A mit ( 2, 3, -2, 4)T
und multipliziere BT mit ( 4, -1, -1)T
ÜA 50:
Multipliziere AT mit B.
ÜA 51:
Multipliziere A mit BT.
ÜA 52:
Formuliere Ax = (1,5,1)T als lineares Gleichungssystem
und bestimme alle möglichen Lösungen.
ÜA 53:
Gegeben sei ein Petrinetz mit 3 Transitionen, 4 Plätzen und der Inzidenzmatrix
BT, in dem eine Schaltfolge w von der Anfangsmarkierung
(6,6,6,60)T zur Markierung
(3,0,1,99)T führt.
Wie lautet der Parikh-Vektor von w? (D.h. wie oft schaltet welche Transition?)
ÜA 54:
Berechne die Determinante von A BT
ÜA 55:
Berechne die Determinante von AT B
ÜA 56:
Invertiere die Matrix C = (
).
ÜA 57:
Drei Firmen Bakti (B), Goldi (G) und Kari (K) führen neue Zahnpasten auf dem Markt ein.
Zu Beginn sind die Marktanteile wie folgt: B hat 40%, G hat 20%, und K hat 40%.
Während eines Jahres behält B 85% seiner Kunden, verliert 5% an G und 10% an K;
G behält 75%, verliert 15% an B und 10% an K
K behält 90% und verliert je 5% an B und G.
Welchen Anteil hat jede Firma nach dem ersten und nach dem zweiten Jahr?
ÜA 58:
Bei welchen anfänglichen Marktanteilen ändert sich nichts?
ÜA 59:
Gegeben seien die folgenden 3 Abbildungen Ki von {a,b,c,d} nach {0,1}*:
x | K1(x) | | | | x | K2(x) | | | | x | K3(x) |
a | 0 | | | | a | 01 | | | | a | 0 |
b | 11 | | | | b | 10 | | | | b | 10 |
c | 101 | | | | c | 011 | | | | c | 111 |
d | 001 | | | | d | 110 | | | | d | 110 |
Welche davon sind Codes? Welche sind Präfixcodes?
Decodiere jeweils, wenn möglich, die Nachricht 0101010101111001110.
ÜA 60:
Gegeben seien die folgenden Wahrscheinlichkeiten für das Alphabet {a,b,c,d,e,f}:
P(a)=0,25; P(b)=0,0625; P(c)=0,0625; P(d)=0,0625; P(e)=0,4375; P(f)=0,125.
Wie groß ist die Entropie?
ÜA 61:
Konstruiere dazu einen Fano-Code. Wie ist die erwartete Codewortlänge?
ÜA 62:
Konstruiere dazu einen Huffman-Code. Wie ist die erwatete Codewortlänge?
ÜA 63:
Von der Grammatik S -> ABcBA, A -> aaSaa, A -> a, B ->BB, B -> b, B -> bcb
soll die erste Regel 2 mal, die zweite Regel ein mal, die 4. und die 6. ein mal
und die 3. und die 5 so oft wie möglich verwendet werden.
Gib zwei Beispielwörter and, die dabei erzeugt werden können.
Wie sind deren Parikh-Vektoren?
ÜA 64:
Mit obiger Grammatik wurde ein Wort aus 47 a's, 41 b's und 24 c's erzeugt.
Wie oft wurde dabei welche der 6 Produktionsregeln verwendet.
ÜA 65:
Bringe obige Grammatik in Chomsky Normalform.
ÜA 66:
Prüfe mit dem CYK-Algorithmus, ob das Wort aabbabba von der Grammatik
S -> AB, A -> a, A -> CB, B -> b, B -> AS, C -> BA erzeugt werden kann.
ÜA 67:
Konstruiere eine kontextfreie Grammatik für die Sprache
{ anbmcr | n=m+r oder 2n=m-r mit n,m,r>0}.
ÜA 68:
Konstruiere einen Huffman-Code für das Alphabet {a,b,c,d,e,f,g,h} mit
P(a)=0,05; P(b)=0,08; P(c)=0,15; P(d)=0,3; P(e)=0,2; P(f)=0,1; P(g)=0,07; P(h)=0,05.
ÜA 69:
Bringe die Funktionen
(log n)4,
n!,
n1/3,
n1/4,
log n,
n1/10,
8n,
log log n,
nlog n
in eine Reihenfolge f1, ... f9 mit
fi = O( fj ) für j>i.
ÜA 70:
Wie lautet die geschlossene Form in O-Notation für die Rekursionsgleichung
T(n)=T(n-1)+n, T(0)=1 ?
ÜA 71:
Wie lautet die geschlossene Form in O-Notation für die Rekursionsgleichung
T(n)=2T(n-1)+1, T(0)=0 ?
ÜA 72:
Wie lautet die geschlossene Form in O-Notation für die Rekursionsgleichung
T(n)=T(n/2)+1, T(1)= 0?
ÜA 73:
Wie lautet die geschlossene Form in O-Notation für die Rekursionsgleichung
T(n)=T(n1/2)+c, T(2)= c?
Zu Beginn jeder Übungsstunde geht eine Votierliste um.
Der Dozent bestimmt zufällig, wer von denen die eine Aufgabe votiert haben,
vorrechnet.
Bei besonders gut oder besonders schlecht vorgerechneten
Aufgaben gibt es Zusatzpunkte bzw. Abzug.
Die Übungsnote ist 5 - 5*Prozentsatz der votierten Augaben
und geht zu 20% in die Gesamtnote ein. (Die anderen 80% kommen von der
Klausur
am 28. Januar 10:30-12:30 Aula.)
Alle 29 Teilnehmer haben bestanden. Es wurden Punktzahlen von 35 bis 92 erreicht.
Durchnittliche Klausur-Punktzahl: 67 Notendurchschnitt: 1,9
Musterlösung
Literatur/Skripte:
[Lan04] K.J.Lange:
Theoretische Informatik Vorlesungsskript Uni-Tübingen, 2004.
Hopcroft,J.E.; Ullmann,J.D.: Einfuhrung in die Automatentheorie formale Sprachen und Komplexitatstheorie, 4.Auflage, Oldenbourg Verlag 2000.
Schoning,Uwe: Theoretische Informatik - kurz gefaßt,3.Auflage Spektrum 1997.
Asteroth,A.; Baier,C. : Theoretische Informatik, Pearson Studium 2003
John E. Hopcroft, Rajeev Motawi, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson
Dietmar Wätjen:
Theoretische Informatik, Vorlesungsskript TU Braunschweig
Petrinetze-Skript Duisburg
Petrinetze-Skript Darmstadt
Baumgarten, B.:
Petrinetze, Grundlagen und Anwendungen.
BI-Wiss.-Verl., 1990
Reisig, W.:
Petrinetze, Eine Einführung.
Springer-Verlag, 1985 (zweite Auflage: Springer-Verlag 1991)
Starke, P.:
Analyse von Petri-Netz-Modellen.
Teubner, 1990