Moin,

nach genau 4 Wochen bekam ich gestern Abend meine Note für die Klausur in Theoretische Informatik und Mathematische Logik. Der Kurs ist sehr umfangreich, die Themen sind sehr kompliziert, die Klausur war sehr schwierig - Ich bin mit der 2,7 sehr zufrieden.

Inhaltlich beginnt der Kurs mit der Aussagenlogik, das kennt man großteils schon aus Mathe 1 - wenn ich mich richtig erinnere - und geht dann weiter in die Prädikatenlogik. Dabei geht es grob um eine Beschreibung um was es eigentlich geht, wie man mit den Aussagen und Prädikaten arbeiten kann, wie man sie mit Operatoren verknüpft, um komplexere Aussagen zu bilden, wie man u.A. mit dem Resolutionsverfahren Widersprüche in den Aussagen aufdeckt und wie man Aussagen umformen kann (damit sie evtl. einfacher lesbar sind oder damit das Resolutionsverfahren angewandt werden kann).

Im Rahmen der Prädikatenlogik erfolgt auch ein Ausflug zur Programmierung mit Prolog, das kannte ich schon von meiner Hausarbeit zur Künstlichen Intelligenz für die ich ein Assistenzsystem implementieren musste. Der große Haken: In Prolog sind die Begrifflichkeiten nicht klar definiert. Ein Programm setzt sich grob aus Fakten und Regeln zusammen, d.h. mit Fakten definiert man die Wissensdatenbank und mit Regeln definiert man die tatsächliche Businesslogik und Entscheidungsfindung des Programms. Es wird aber oft auch (u.A. zusätzlich) der Begriff "Prädikat" genutzt, in meiner Hausarbeit habe ich die "kleinen Regeln" als Prädikate definiert und diese Unterscheidung auch dokumentiert. In diesem Kurs ist es also wichtig, dass man sich entweder streng an die im Skript beschriebenen Definitionen hält, oder in der Klausur daran denkt, seine eigenen Begriffskonventionen zu beschreiben, damit der Prüfer das ganze passend interpretieren kann. 

In Lektion 3 werden die Endlichen Automaten, Reguläre Ausdrücke und Reguläre Sprachen behandelt. Das hier ist so ziemlich der Schwerpunkt des gesamten Kurses, mit dem ich auch am meisten Zeit verbracht habe. Reguläre Ausdrücke kannte ich bereits aus dem Job gut, das hat geholfen, um die anderen beiden Dinge etwas besser zu verstehen. Viel kann ich hier aber nicht zu dem Inhalt beschreiben, das würde den Rahmen sprengen. Nur so viel: Endliche Automaten, Reguläre Ausdrücke und Reguläre Sprachen sind 3 Methoden, um Eingabewerte zu verarbeiten. Alle 3 Methoden haben die exakt gleiche Mächtigkeit, d.h. alle Zeichenketten die sich mit einem Endlichen Automaten beschreiben lassen, lassen sich auch mit einer Regulären Sprache oder mit einem Regulären Ausdruck beschreiben. Wenn ihr also Schwierigkeiten habt einen Endlichen Automaten zu Problem xyz zu definieren, versucht eventuell einen Regulären Ausdruck oder die Reguläre Sprache zu dem Problem zu definieren, das hilft dann evtl. die Lösung für den EA zu finden.

Die Lektionen 4 und 5 behandeln die weiteren formalen Sprachen, Turingmaschinen und ein bisschen was extra ... wenn man mit Lektion 3 gut zurechtkam, wird man in diesen beiden Lektionen auf keine Schwierigkeiten stoßen.

Lektion 6 behandelt die Komplexitätstheorie, da geht es u.a. um die Bewertung und den Vergleich von Algorithmen. Ebenso wird das P vs NP Problem vorgestellt und erläutert. Das war schon ziemlich interessant. Man muss sich für die Klausur die ganzen O-Notationen merken, aber das passt schon. Wichtiger ist das Verständnis für die gesamte P und NP-Sache.

Lektion 7 hat mir nochmal schön die Füße weggezogen :D da freut man sich, dass man das ganze komplizierte und formale Zeug verstanden hat.. da kommen die mit Petri-Netzen und Matrizenrechnungen um die Ecke. Die Lektion hat im Endeffekt auch Spaß gemacht, zum Glück kannte ich einige der Konzepte auch schon aus dem Alltag, aber die Berechnungen musste ich mir doch nochmal genauer ansehen - Mathe 2 ist zu lange her.

Zum Abschluss bekommt man in Lektion 8 nochmal einen entspannten Überblick, warum und wofür man das vorhergehende Zeug denn so braucht. D.h. hier geht es um die konkreten Anwendungsfälle wann man die formalen Sprachen nutzt, an welcher Stelle ein Compiler welche Sprache anwendet usw.

Meine Klausurvorbereitung

Das Skript... ist gar nicht mal so hilfreich. Das Skript ist inzwischen 180 Seiten lang, vor ein paar Monaten war es 220 Seiten lang. In den Überarbeitungen des Skripts wurden teilweise einfach Absätze entfernt, ohne die sonstigen Inhalte entsprechend anzupassen. Das heißt manche Themen stehen relativ nackt dar, weil einfach Beispiele zur weiteren Erklärung nicht (mehr) vorhanden sind. Nutzt das Skript am besten nur, um eure Klausurvorbereitung zu planen und euch zu vergewissern auf welche Inhalte ihr die Schwerpuntke setzen müsst.

Ansonsten empfehle ich, die einzelnen Themen wirklich so zu lernen, wie ihr sie von anderen Lernmitteln vorgesetzt bekommt. Zum Beispiel spielt die Unterscheidung vor Moore- und Mealy-Automaten in Lektion 3 gar keine Rolle, in den meisten Büchern aber schon => Also habe ich auch geübt wie man einen Moore- in einen Mealy-Automaten überträgt und andersrum. Das gleiche gilt für die Unterscheidung von Nichtdeterministischen und Deterministischen Endlichen Automaten, es wird zwar erwähnt, dass sie gleich mächtig sind, aber die Übertragung von einem in das andere wird im Skript nicht behandelt - in den meisten Büchern aber schon.

- Theoretische Informatik für Dummies

Ist ok. Falls man mit dem Skript gut arbeiten kann, ist dieses Buch evtl. eine gute und schnelle Ergänzung, um zu überprüfen ob man die Themen wirklich einigermaßen gut verstanden hat.

- Grundkurs Theoretische Informatik

Top. Ausführliche Beschreibung von Endlichen Automaten, den Sprachen und der Komplexitätstheorie. Ein guter Weg um sich an die formalen Beschreibungen zu gewöhnen.

- Theoretische Informatik - ganz praktisch + 100 Übungsaufgaben zu Grundlagen der Informatik, Band I: Theoretische Informatik

Mein Favorit was die gekaufte Literatur betrifft. Der Schreibstil gefällt mir. In den Übungsaufgaben muss man so unendlich viele Automaten zeichnen und beschreiben... ist schon ganz cool, danach sitzen die Automaten auch wirklich. 

- Vorlesungsreihe auf YouTube

Die habe ich eher genutzt, um mich nach einem anstrengenden Tag Abends berieseln zu lassen als aktiv mitzuarbeiten. Aber hat mir ganz gut gefallen.

- Repetitorium in MyCampus

Das ist für mich gerade noch rechtzeitig bzw. etwas spät online gegangen. Sehr cool und es ist genau das was der Kurs gebraucht hat. Ich habe am Ende nicht mehr alle Aufgaben gelöst, aber ist gut. Ich hoffe sie ändern noch die Formatierung, damit Frage und Antwort nicht auf der gleichen Seite im PDF stehen, sonst muss man so sehr darauf achten nicht zu tief zu scrollen und sich damit selbst zu spoilern.

- Discord

Im Channel zur Theoretischen Informatik herrscht ein reger Austausch. Es kamen von anderen Usern immer wieder Fragestellungen, die mir gezeigt haben was für krasse Lücken ich noch habe. Teilweise wurde ich auch einfach an Themen erinnert, die ich bis dahin einfach schon wieder vergessen hatte. Der Discord-Server hat wirklich geholfen.

- ChatGPT

Zu Petri-Netzen konnte ich nicht wirklich viele Materialien finden. Die Bücher zur Theoretischen Informatik beschäftigen sich eher mit allen anderen Themen aus diesem Kurs. Der AI ein paar Fragen hinzuwerfen oder auch um Aufgaben zu bitten war sehr hilfreich.

Einige Fragen die ich gestellt habe:

• Hallo, erstell mir bitte 5 Klausurfragen zum Thema Petrinetze.

• Was bedeutet Lebendigkeit im Bezug auf Petrinetze?

• Gibt es einen Zusammenhang zwischen Lebendigkeit und Terminierung in Petrinetzen?

• Gibt es einen Zusammenhang zwischen Deadlock-Freiheit und Terminierung?

• Hallo, kannst du anhand des Pumping Lemmas erklären warum "a^nb^nc^2n" keine kontextfreie Sprache ist?

• Kannst du die Antwort auch in Umgangssprache formulieren? (😁) 

Vor allem kann man ja auch wieder Bezug auf die gestellten Aufgaben nehmen und seine Antwort bewerten lassen. Mega gut.

Und sonst so ...

Ich schreibe noch an meinem Projektbericht für die Android-App aus Mobile Software Engineering. Hier hat sich alles etwas verzögert, die Details beschreibe ich dann im passenden Blogeintrag.

Im Job wurde (endlich) ein Projekt abgenommen mit dem ich mich die letzten 6 Monate beschäftigt habe und das extrem anstrengend war. Das war einer der Gründe warum es in diesem Jahr deutlich langsamer als geplant voran geht. Ab jetzt werde ich mich zum Feierabend an den Kurs zu den Betriebssystemen setzen, das sollte etwas entspannter und flüssiger vorangingen als Theoretische Informatik.

Letztens habe ich mir auch schon den Inhalt zum Kurs Deep Learning angesehen, dort geht es noch einmal tief in die Technik - den Kurs hebe ich mir für in ein paar Monaten auf.

Anyway. Ich gönne mir jetzt nochmal ein kleines kühles, um zu feiern. Und ...  schreibe natürlich den Projektbericht weiter.

Bis dann!