Theoretische Grundlagen 2 in mki-B2, Hochschule Reutlingen

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 z₀, Endzustand z₃ 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 = (

3	-2	0	1
2	5	1	0
-1	4	0	3

) und B = (

0	-3	1	4
-2	0	0	9
1	0	-1	-2

). Berechne die Matrix 3A-2B.
ÜA 49: Multipliziere A mit ( 2, 3, -2, 4)^T und multipliziere B^T mit ( 4, -1, -1)^T
ÜA 50: Multipliziere A^T mit B.
ÜA 51: Multipliziere A mit B^T.
Ü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 B^T, 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 B^T
ÜA 55: Berechne die Determinante von A^T B
ÜA 56: Invertiere die Matrix C = (

1	2	3
1	3	4
1	4	-3

).
Ü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 K_i 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 { aⁿb^mc^r | 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)⁴, n!, n^1/3, n^1/4, log n, n^1/10, 8ⁿ, log log n, n^{log n} in eine Reihenfolge f₁, ... f₉ mit f_i = O( f_j ) 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(n^1/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: