FMI11 vom 04.10.2010 (Stuttgart und andere)
Verfasst: 04.10.10 16:29
Seminar (3 Wochen vorher) war bei Prof. Schmatzer, der ganz gut auf die Klausur vorbereitet hat. Graphentheorie kam weder in Seminar noch in der Klausur vor (brauchte nicht gelernt zu werden).
Die Klausur beinhaltete keine besonders schweren, aber auch keine besonders leichten Aufgaben. Von drei Komplexaufgaben mussten zwei ausgewählt werden.
Aufgabe 1.1 (Detail): Automatentafel mit sechs Zuständen war angegeben. Zustandsdiagramm erstellen und minimieren, falls möglich. (Meine Minimierung ergab drei Zustände).
Aufgabe 1.2 (Detail): Deterministische endlicher Automat sollte erstellt werden. E={0,1,2}. Akzeptiert werden sollten alle Wörter, die an der zweitletzten Stelle eine 1 haben. Automatentafel und Zustandsdiagramm zeichnen. Ein Tipp war angegeben: zuerst nicht-deterministischen Automaten erstellen und diesen dann umwandeln.
Aufgabe 1.3 (Detail): Ein nichtdetermistischer Automat sollte erstellt werden, der alle Wörter mit E={0,1} akzeptiert, die auf 10 oder 01 enden. Automatentafel und Zustandsdiagramm zeichnen.
Aufgabe 2 (Komplex): Eine linkslineare Grammatik war angegeben (in Form von Produktionsregeln). Zwei Wörter herleiten (0111 und 010111). Regulären Ausdruck angeben. (Meiner Ansicht nach war das (01)*11) Um welche Sprache handelt es sich?
Aufgabe 3 (Komplex): Habe ich nicht gemacht. Weiß nicht mal annhähernd, worum es ging. Vielleicht kann das jemand ergänzen.
Aufgabe 4 (Komplex): Eine Quelle war angegeben mit 10 Zeichen.* Relative Häufigkeiten waren angegeben. Definition von Entropie hinschreiben und ebensolche berechnen. Code nach Shannon-Fano erstellen. Coderedundanz berechnen.
* Verwirrend war hier, dass zwei Zeichen jeweils zweimal vorkamen mit der gleichen relativen Häufigkeit! Hier kann es sich nur um einen Fehler (Zufall) gehandelt haben, da die relativen Häufigkeiten aller 10 Zeichen addiert 1 ergab.
Die Klausur beinhaltete keine besonders schweren, aber auch keine besonders leichten Aufgaben. Von drei Komplexaufgaben mussten zwei ausgewählt werden.
Aufgabe 1.1 (Detail): Automatentafel mit sechs Zuständen war angegeben. Zustandsdiagramm erstellen und minimieren, falls möglich. (Meine Minimierung ergab drei Zustände).
Aufgabe 1.2 (Detail): Deterministische endlicher Automat sollte erstellt werden. E={0,1,2}. Akzeptiert werden sollten alle Wörter, die an der zweitletzten Stelle eine 1 haben. Automatentafel und Zustandsdiagramm zeichnen. Ein Tipp war angegeben: zuerst nicht-deterministischen Automaten erstellen und diesen dann umwandeln.
Aufgabe 1.3 (Detail): Ein nichtdetermistischer Automat sollte erstellt werden, der alle Wörter mit E={0,1} akzeptiert, die auf 10 oder 01 enden. Automatentafel und Zustandsdiagramm zeichnen.
Aufgabe 2 (Komplex): Eine linkslineare Grammatik war angegeben (in Form von Produktionsregeln). Zwei Wörter herleiten (0111 und 010111). Regulären Ausdruck angeben. (Meiner Ansicht nach war das (01)*11) Um welche Sprache handelt es sich?
Aufgabe 3 (Komplex): Habe ich nicht gemacht. Weiß nicht mal annhähernd, worum es ging. Vielleicht kann das jemand ergänzen.
Aufgabe 4 (Komplex): Eine Quelle war angegeben mit 10 Zeichen.* Relative Häufigkeiten waren angegeben. Definition von Entropie hinschreiben und ebensolche berechnen. Code nach Shannon-Fano erstellen. Coderedundanz berechnen.
* Verwirrend war hier, dass zwei Zeichen jeweils zweimal vorkamen mit der gleichen relativen Häufigkeit! Hier kann es sich nur um einen Fehler (Zufall) gehandelt haben, da die relativen Häufigkeiten aller 10 Zeichen addiert 1 ergab.