www.fernstudenten.de

Hallo,

da FMI01 zu den anspruchsvolleren Fächern gehört und für dieses Fach kaum Übungsmöglichkeiten auf Klausurniveau angeboten werden, habe ich ein Skript zur Vorbereitung erstellt.

Die Aufgaben wurden alle bei Fernstudenten veröffentlicht, bei Bedarf habe ich fiktive Zahlenwerte genommen und diverse Aufgaben einfach ausformuliert.

Konzentriert euch weniger auf Shannon-Fano und Huffmann. Konzentriert euch vor allem auf das erste Heft, Matrixberechnung und den Binärbaum.

Vielen Dank an Joanna und Matthias für das Korrekturlesen.
Evtl. ist die Aufgabe 1.2 der Klausur vom 25.03.2006 nicht ganz richtig aber wie schon geschrieben sind Shannon-Fano und Huffmann nicht so wichtig.

Viel Motivation beim Lernen!

Schönen Gruß
Matthias

Vielen Dank für die schöne Aufbereitung.
Ich selbst habe FMI zwar erst für Anfang März geplant, bin mir aber sicher auf die von Dir erstellte Unterlage zurückzugreifen.

nochmal Danke !

Hallo Matthias,

vielen Dank für die gute Aufgabensammlung. Ich konnte sie zur Vorbereitung auf die Klausur sehr gut gebrauchen.

Ein Fehler ist in den Lösungen jedoch enthalten. Bei der Berechnung der mittleren Codewortlänge unterstellst Du immer eine Gleichverteilung der Wahrscheinlichkeiten auf die einzelnen Zeichen. Dies ist jedoch beispielsweise in der Aufgabe 1.2 der Klausur vom 25.3.2006 in Pinneberg nicht gegeben.

Viele Grüße und nochmals besten Dank,
Christian

Hallo,

erst mal Danke für euer Lob. Ein solches Feedback tut immer gut ;-)

Für alle, die es noch nicht mitbekommen haben: AKAD hat seit etwa einer Woche auch eine Musterklausur online gestellt.

Schönen Gruß
Matthias

Hi Sys,

ja, ich danke dir auch recht herzlich Somit hat man für die Klausur echt ne super Übungsgrundlage.

Ich bin gerade bei der Klausurvorbereitung führe nebenbei auch das Review der Sammlung durch.

Bei Aufgabe 1.2, wo es um den Shannon-Fano-Code geht, ist eventuell auch ein Halbierungsfehler drin:

Es bilden sich folgende Summen und Leitung:

100
69
47
28
15
4

Laut Lösung wird in Schritt 2 zwischen 47 und 28 geteilt. Da 47 / 2 = 23.5 ist, sollte doch eigenltich bei 47 und 28 in einen Teil und 15 und 4 in den anderen geteilt werden, da die 23,50 zwischen 28 und 15 liegt. Sehe ich das richtig?

Ich beziehe mich auf Heft 2, Kap 1.2.1.4, Shannon-Fano-Alghritmus Nr. 2

Würde man es anders machen, kommen andere Codewortlängen heraus.

cu & viele Grüße
Dieter

Hallo Dieter,

ich glaube Du irrst Dich. Die Lösung ist m.E. richtig.

Ziel der Kodierung ist es, eine möglichst geringe mittlere Codewortlänge über alle Zeichen (bzw. Minimierung der Redundanz des Codes) zu erreichen. Das Shannon-Fano-Verfahren ordnet daher Zeichen, die eine hohe Auftrittswahrscheinlichkeit haben einen kürzeren Code zu als Zeichen mit geringerer Auftrittswahrscheinlichkeit.

Im Verfahren erfolgt die Teilung des Wahrscheinlichkeitsfeldes in jedem Schritt so, dass die beiden resultierenden Gruppen in der jeweiligen Summe der Wahrscheinlichkeiten möglicht gleich groß sind. Im Schritt 2 wird daher die Menge der Zeichen {F,E,A,D} in die beiden disjunkten Teilmengen {F} und {EAD} unterteilt. Auf diese Weise steht die Wahrscheinlichkeit von {F} in Höhe von 19% der Summe der Wahrscheinlichkeiten von {EAD} in Höhe von 28% (= 13%+11%+4%) gegenüber, d.h. die Wahrscheinlichkeiten für beide Gruppen sind 9%-Punkte auseinander.

Setzt man hingegen die Teilung - wie von Dir vorgeschlagen - im 2. Schritt so an, dass die Gruppen {FE} und {AD} entstehen, stehen sich 32% (= 19% + 13%) und 15% (= 11% + 4%) gegenüber. Die Differenz beträgt somit 17%-Punkte und ist damit größer als 9%-Punkte, d.h. diese Teilung befindet sich in einem größeren Ungleichgewicht der Wahrscheinlichkeitssummen über die Teilmengen. Die mittlere Codewortlänge wird entsprechend größer.


Viele Grüße
Christian

Hallo Dieter,

ich muss leider meine Antwort von gestern revidieren. Aus den Erläuterungen von Herrn Dr. Hanke aus dem heutigen FMI-Seminar würde ich Dir doch recht geben. Zwar ist die von mir beschriebene (und auch in der Lösung von Matthias enthaltene) Vorgehensweise effizienter, entspricht aber nach den Worten von Herrn Dr. Hanke nicht dem Shannon-Fano-Verfahren.

Gruß
Christian

Für alle die nicht dabei waren und am 1.12. die Klausur schreiben:
Seminar Themen waren:
* DEA zeichnen
* NDEA in DEA umwandeln
* DEA minimieren (wobei ich persönlich die State Merging Methode empfehle, die hier im Forum genannt wird (s. Online Vortrag von Freiburg))
* Kellerautomaten zeichnen bzw. Tafel erstellen
* Aus Inzidenz die Adjazenz Matrix erstellen (über Graph)
* Baum Traversieren
* Term mit Infix, PN und UPN angeben
* Grammatik bestimmen und angeben (Typ 3 / Typ 2)
* Shannon Fano und Hufmann Verfahren

Das Seminar hat sich an der Musterklausur orientiert.
Die Musterklausur sollte man verstanden haben, dann dürfte das Bestehen der FMI Klausur Erreichbar sein.
Allen die mitschreiben viel Erfolg !!!!
Gruß
Peter

Hallo Chris,

danke für deine Erklärung. So habe ich das jetzt auch verstanden.

Leider ist der Algorithmus in wirklich allen Lernquellen so schwammig geschrieben, dass leicht Fehlinterpretationen entstehen.

Am Freitag war ich im Seminar beim Dr. Blaschka und haben die Meinungen über diese Teilung stark unterschieden. Wir haben uns mit Hr. Hanke geinigt, dass wir feste Grenzen setzen, an denen wir die Wahrscheinlichkeiten teilen: 50, 25, 12.5

Ob richtig oder nicht - so wird das in der Klausur akzeptiert

Viele Grüße aus Muc
Dieter

Hallo liebe Nachfolger,

das waren die Themen in der letzten Klausur vom 01.12.07:

Detail:

1. Syntaxdiagrame malen: Wort muss mit abcc enden, Wort muss abcc enthalten (Ich habe zuerst reflexartig den DEA gemalt, was überhaupt nicht verlangt war... :-/ )

2. Binärbaum anhand eines arithmetischen Ausdrucks malen. Siehe Beispielaufgabe in der Musterklausur. Dazu In- und Postorder Ausdruck angeben. Vorteil von Postorder gegenüber Inorder angeben.

3. NEA in einen DEA umwandeln.

4. Shannon Fano, Huffmann und BCD aus einer Häufigkeitstabelle erstellen, Redundanzen berechnen, Redundanz gegenüber BCD prozentual angeben

5. Bitshifter, der um 2 Bits nach links shiftet und immer mit 00 anfügt. (Hat sich das jemand während der Klausur aus den Fingern ziehen können? Bitte bei mir melden...)


Komplex 1:
A:
1. Syntax diagram eines logischen Ausdrucks angeben (AND | OR | NOT)
2. Syntax diagram eines logischen Ausdrucks mit Klammern ausgeben
3. Grammatik für Nr. 2 erstellen und Chomsky Typ nennen

B:
Automat minimieren.

Komplex 2:
Kellerautomaten. Kann dazu (zum Glück) nix sagen.


Unterm Strich war die Klausur dank des sehr guten Seminars von Dr. Blaschka (Dozent mit Qualität!) machbar. Anscheinend hat die letzte Beschwerdewelle anderer Leidtragender gefruchtet.

Viel Spass am Knobeln
Dieter

Hallo,

kann mir jemand verraten, ob sich der DEA in der Komplexaufgabe 1 der Klausur vom 1.12.2007 minimieren lässt. Bei Anwendung des state merging Verfahrens kam man zu dem Ergebnis, dass sich keine Zustände zusammenfassen lassen. Allerdings ging vom Startzustand ein Pfeil (a) in den oberen Bereich mit nur Nicht-Finalzuständen und ein Pfeil (b) in den unteren Bereich mit ausschließlich Finalzuständen. Da man von dem oberen Bereich nie in einen Finalzustand zurückkehren kann; müsste sich dieser doch zusammenfassen lassen. Gilt gleiches auch für den unteren Bereich.

In der Klausur habe ich allerdings geschrieben, dass sich der Automat nicht weiter minimieren lässt. Ich glaube diese Aussage ist falsch. Was habt Ihr für Lösungen ?

Viele Grüße
Christian

Hi Chris,

ich bin mir mit dem DEA auch nicht sicher gewesen. Mit dem State Merging verfahren habe ich den Automaten von 7 auf 5 Zustände minimieren können.

Bei meinem Ergebnis habe ich die oberen Zustände S3,S4 und die unteren S5,S6 zusammen fassen können. Allerdings bin ich mir nicht sicher, ob das richtig ist. Jemand anders hat nämlich den DEA auf 3 Zustände minimieren können....

cu
Dieter

ich habe den Automat auch nicht minimieren können, nach jeder Teilung
beim State Merging Verfahren kamen wieder neue Teilmengen.
Es ist auch egal ob man von den oberen Zuständen in die Finalzustände kommt oder nicht. Weg kommen nur die Zustände, die von S0 überhaupt nicht erreichbar sind.
Es gab wohl keine äquivalente Zustände und daher ist dieser Automat nicht minimierbar gewesen.
Ich glaube das Problem lag daran, dass es bei 2 Übergängen (S0?) kein Rückweg gab.

Mit guter Vorbereitung und dem super Seminar von Herrn Blaschka war die Klausur machbar.
Viele Grüße
Peter

Die Klausur war nach Besuch des Vorbereitungsseminars gut machbar. Allerdings für jemanden, der dieses Seminar nicht besucht hat, weil er die Klausur ein 2. mal geschrieben oder ein früheres Seminar besucht hatte, war die Klausur nahezu unlösbar. Ich denke mal, niemand hätte ohne Vorwarnung in der Kürze der Zeit die letzte Detailaufgabe mit dem 2-fach rechtsschieben lösen können.

In jeder Komplexaufgabe war eine gewaltige "Einserbremse" enthalten.
- Die Minimierung des DEA (Komplex 1) war ein absoluter Sonderfall, der weder in den Unterlagen noch am Seminar behandelt wurde. Was im Endeffekt korrekt ist, bin ich mir immer noch nicht so ganz sicher.
- In der Komplex 2 wurde die Kenntnis eines Mathematischen Algorithmuses vorausgesetzt, mit dem ich spontan beim besten Willen nichts anfangen konnte. Daher schied diese Aufgabe für mich von vornherein aus.

Gruß Jens