Hallo zusammen, es ist wieder soweit. Vor einigen Minuten befand ich mich noch in der Prüfung des wohl schwersten Moduls meiner bisherigen Studienlaufbahn. Das Modul? Formale Methoden der Informatik I (FMI23).

Der Tragödie erster Teil

Am Anfang lief ja alles noch gut. Gerade hatte ich das Datenbankmodul in (persönlicher) Rekordzeit hinter mir, so freute ich mich auf etwas neues. Dieses neues sollte nach meinem Wandkalender FMI23 sein. Davor hatte ich zwar schon etwas Respekt, aber ich wollte es mir nicht nehmen lassen, gleich damit anzufangen. Die ersten Seiten und Kapitel waren erwartungsgemäß. Ein paar mathematische Voraussetzungen wie Algebraische Strukturen und Isomorphie (was ich zum Glück noch aus dem Studium kannte, die Akad flog hier lediglich drüber - "nice-to-know") und dann hieß mich auch schon das Kernthema willkommen: Abstrakte Automaten. Wie kann man eigentlich wissen, wie schwierig bestimmte Problemstellungen sind bzw. ob sie überhaupt lösbar sind? Dazu verwandelt man ein Problem aus der realen Welt in eine Folge von simplen Symbolen und füttert sie in einen dieser Automaten, welcher einem dann eine Antwort darauf ausspuckt. Die einfachsten der Automatenfamilie sind endliche (nicht)deterministische Automaten, gefolgt von den komplizierteren Kellerautomaten (ja, die heißen wirklich so) und am Ende der Fahnenstange steht die Turing-Maschine, von der man sicherlich ab und an mal gehört hat.

Der erste Studienbrief behandelte endliche Automaten, reguläre Sprachen, Typ-3-Grammatiken nach Chomsky und die von vielen meiner Programmierkollegen gehassten regulären Ausdrücke. Hier lief noch alles ganz komfortabel. Nicht allzu einfach, genau richtig.

Der Tragödie zweiter Teil

Einige Zeit und viele kleiner gezeichneten Automaten später, nahm ich mich dem 2. Brief an, Themen: Kellerautomaten, Typ-2-Grammatiken und Kontextfreie Sprachen. Hier hat das Tempo schon etwas zugenommen, da Kellerautomaten zwar komplexere Probleme lösen können, aber auf der anderen Seite selbst komplizierter aufgebaut sind. Hier musste ich auch etwas mehr Zeit reinstecken und hab das Ganze auch erst vor nicht allzu langer Zeit 100% verstanden (was witzig ist, da ich selbst schon oft diese sog. Pushdown Automata programmiert habe, siehe State Design Pattern). Der Schwierigkeitsgrad war hier moderat schwer, also noch gnädig wie ich finde. Doch dann erklärte uns die Feuer-Nation den Krieg und alles änderte sich. Doch dann kam Brief Nummer 3...

Der Tragödie dritter Teil

Plötzlich befand ich mich im Schneckentempo. Themen wie formale Turing-Maschinen sind schon eine Klasse für sich, aber dann noch Komplexitäts- und Berechenbarkeitstheorie! Höhere Mathematik war bereits in den vorigen Briefen zu genüge enthalten, aber hier platzt es aus allen Nähten. Die (O)-Notation und die TMs gingen ja noch, aber v.a. die Beweise zu NTIME, DSPACE, etc. in der 2. Hälfte des Briefs waren mir zumindest in dieser Zeitspanne noch zu hoch, weshalb ich hier noch nicht alles komplett verstanden hab. Ich frage mich nur, wie hier jemand ohne mathematische Vorkenntnisse reinkommen soll? Die MAT-Module in diesem Studiengang bereiten jedenfalls nicht auf die hier vorkommenden Beweise vor.

Der letzte Akt: Das Große Finale

Heute war ich also in der Prüfung mit ca. 80% Wissen und hab sie ganz gut gemeistert denke ich. Zum Glück existieren Komplexaufgaben, die man sich aussuchen kann, so musste ich nicht alles aus dem letzten Brief mitnehmen. 

Abschließend kann ich sagen, dass FMI23 bisher das anspruchsvollste Modul meiner bisherigen Studienlaufbahn gewesen ist (ja, Mathe an der Uni damals inklusive!), da es höhere Mathematik und abstrakte Konzepte der Informatik vereint. 

Glücklicherweise war das Modul aber auch sehr interessant, v.a. wenn man sich wie ich für Compiler und deren Bestandteile interessiert (wie Lexer, Syntaxbäume, etc.). Hat sich also gelohnt, bin aber auch erleichtert, dass jetzt mit PRG24 wieder was einfaches kommt (Hausarbeit über Objektorientierung).

Abschließend noch meine Eindrücke:

Schwierigkeitsgrad: 5 / 5

Highlights: Süße kleine Automaten zeichnen, Programmiersprachen und Compiler besser verstehen, Turing-Maschinen, Antworten auf die Frage "Was lässt sich überhaupt mit einem Computer lösen?"