Prüfung FMI20 06.04.2019
Verfasst: 07.04.19 17:48
Hallo Zusammen,
anbei die Fragen welche von der FMI20 Prüfung am 06.04.2019 dran kamen (an was ich mich ca. noch so erinnern kann):
Detailaufgaben:
A.1:
Erstelle ein DEA {0,1} wo nur Zeichen akzeptierte, wo die Anzahl 1-Zeichen ein Vielfaches von 3 ist. Z.B. 010101, 000, 111000111. Automatentafel + Zustandsgraph
A.2:
Erstell eine rechtslineare Typ 3 Grammatik von Aufgabe 1 und Worte ableiten.
A.3:
Erstelle eine kontextfreie Grammatik, welche die Sprache L={0m+n 1n | mit m, n>0} und gebe die Produktionsregeln an + Worte ableiten.
A.4:
O-Notationen, Ausdrücke vereinfachen und nach wachsender Komplexität sortieren.
A.5:
Zero-Knowledge-Beweis erläutern + Beispiel aufzeigen, welches es erklärt.
Komplexaufgaben:
B.1: Endliche Automaten
1.1: Es war ein NEA Automatentafel gegeben, daraus einmal das Zustandsdiagramm zeichnen und dann den NEA in einen DEA umwandeln.
1.2: Es war ein DEA Zustandsdiagramm gegeben, von diesem die Automatentafel erstellen und dann DEA minimieren.
1.3: Typ 3 Grammatik + Produktionsregeln des DEA aus 1.2 erstellen. Sowie Gleichen dazu aufstellen lösen, mit dem Ziel daraus den Reguläre Ausdruck aufzuschreiben.
B.2: Kellerautomaten
1.1: Deterministischer Kellerautomat erstellen, mit L={0m+2n 1m 0| n >= 0, m >0}, Zustandsdiagramm + Automatentafel angeben. Sowie Worte ableiten und Konfigurationsfolge angeben.
1.2: Kontextfreie Grammatik zu 1.1 angeben und Produktionsregeln aufzeigen + Worte ableiten.
B.3 Turing Maschine
1.1: Funktionsweise einer Turing Maschine erläutern (auf die Definition eingehen und die Symbole erläutern)
1.2: Eine Turing Maschine entwickeln und Konfigurationsfolge angeben etc. habe ich nicht gemacht.
Alles in allem wieder eine faire Prüfung.
Zur Vorbereitung würde ich zum einem intensiv die AKAD-Unterlagen FMI 101 + FMI 102 empfehlen und kauft euch das Buch: „100 Übungsaufgaben zu Grundlagen der Informatik“, ISBN: 978-3-486-73179-8“ von Lukas König, Friederike Pfeiffer-Bohnen und Hartmut Schmeck.
Dies beinhaltet nicht nur zusätzliche Aufgaben und Erklärungen, sondern auch gute Links zu Vorlesungen, wo alle Themen rund um Endliche Automaten, Sprachen etc. drankommen. Darüber hinaus ist YouTube euer bester Freund, da es viele gute Videos zu dem Stoff gibt. Aber beachten, was ihr Können müsst (und auch die Form), steht immer in den AKAD heften.
Noch ein heißer Tipp, laut AKAD-Online Tutorium Video 2 (siehe AKAD Campus), kommen in der Prüfung nur Typ 2 und Typ 3 Grammatiken dran (also die Typ 0 und 1 nach Chomsky müsst ihr euch wohl nicht antun).
Nun wünsche ich euch viel Erfolg beim Lernen und beim Studium.
Grüße,
Antonio
anbei die Fragen welche von der FMI20 Prüfung am 06.04.2019 dran kamen (an was ich mich ca. noch so erinnern kann):
Detailaufgaben:
A.1:
Erstelle ein DEA {0,1} wo nur Zeichen akzeptierte, wo die Anzahl 1-Zeichen ein Vielfaches von 3 ist. Z.B. 010101, 000, 111000111. Automatentafel + Zustandsgraph
A.2:
Erstell eine rechtslineare Typ 3 Grammatik von Aufgabe 1 und Worte ableiten.
A.3:
Erstelle eine kontextfreie Grammatik, welche die Sprache L={0m+n 1n | mit m, n>0} und gebe die Produktionsregeln an + Worte ableiten.
A.4:
O-Notationen, Ausdrücke vereinfachen und nach wachsender Komplexität sortieren.
A.5:
Zero-Knowledge-Beweis erläutern + Beispiel aufzeigen, welches es erklärt.
Komplexaufgaben:
B.1: Endliche Automaten
1.1: Es war ein NEA Automatentafel gegeben, daraus einmal das Zustandsdiagramm zeichnen und dann den NEA in einen DEA umwandeln.
1.2: Es war ein DEA Zustandsdiagramm gegeben, von diesem die Automatentafel erstellen und dann DEA minimieren.
1.3: Typ 3 Grammatik + Produktionsregeln des DEA aus 1.2 erstellen. Sowie Gleichen dazu aufstellen lösen, mit dem Ziel daraus den Reguläre Ausdruck aufzuschreiben.
B.2: Kellerautomaten
1.1: Deterministischer Kellerautomat erstellen, mit L={0m+2n 1m 0| n >= 0, m >0}, Zustandsdiagramm + Automatentafel angeben. Sowie Worte ableiten und Konfigurationsfolge angeben.
1.2: Kontextfreie Grammatik zu 1.1 angeben und Produktionsregeln aufzeigen + Worte ableiten.
B.3 Turing Maschine
1.1: Funktionsweise einer Turing Maschine erläutern (auf die Definition eingehen und die Symbole erläutern)
1.2: Eine Turing Maschine entwickeln und Konfigurationsfolge angeben etc. habe ich nicht gemacht.
Alles in allem wieder eine faire Prüfung.
Zur Vorbereitung würde ich zum einem intensiv die AKAD-Unterlagen FMI 101 + FMI 102 empfehlen und kauft euch das Buch: „100 Übungsaufgaben zu Grundlagen der Informatik“, ISBN: 978-3-486-73179-8“ von Lukas König, Friederike Pfeiffer-Bohnen und Hartmut Schmeck.
Dies beinhaltet nicht nur zusätzliche Aufgaben und Erklärungen, sondern auch gute Links zu Vorlesungen, wo alle Themen rund um Endliche Automaten, Sprachen etc. drankommen. Darüber hinaus ist YouTube euer bester Freund, da es viele gute Videos zu dem Stoff gibt. Aber beachten, was ihr Können müsst (und auch die Form), steht immer in den AKAD heften.
Noch ein heißer Tipp, laut AKAD-Online Tutorium Video 2 (siehe AKAD Campus), kommen in der Prüfung nur Typ 2 und Typ 3 Grammatiken dran (also die Typ 0 und 1 nach Chomsky müsst ihr euch wohl nicht antun).
Nun wünsche ich euch viel Erfolg beim Lernen und beim Studium.
Grüße,
Antonio