Zum Inhalt springen

  • Beiträge
    72
  • Kommentare
    239
  • Aufrufe
    12.659

Theoretische Informatik als Gasthörer bei der WINGS


kurtchen

1.069 Aufrufe

Wie ich zur theoretischen Informatik kam

 

In meinem Modulbericht zu GdI4 "Algorithmen und Datenstrukturen" hatte ich es schon einmal erwähnt: Ich wollte gerne ein Modul "Künstliche Intelligenz" belegen, was Springer Campus leider bislang so nicht anbietet.

 

Die WINGS Wismar hat ein sehr schönes KI Modul, in dem sowohl klassische KI und als auch künstliche neuronale Netze behandelt werden. Das gefiel mir und so schrieb ich Professor Cleve an, der für dieses Modul zuständig ist und auch das zugrunde liegende Lehrbuch geschrieben hat. Ihn fragte ich, ob ich dieses Modul als Gast- oder Zweithörer belegen könne. Und was gegebenenfalls für Vorwissen nötig sei. Herr Cleve empfahl mir, zunächst Kenntnisse in theoretischer Informatik zu erwerben und hatte auch gleich das passende Modul, das ebenfalls von ihm betreut wurde. So kam es, dass ich mich als Gasthörer bei der WINGS anmeldete.

 

Organisatorisches

 

Die Anmeldung unterscheidet sich bei der WINGS ein wenig von Springer Campus, weil man sich für ein bestimmtes Semester anmelden muss. In diesem Semester soll man auch die Modulprüfung ablegen. Für die Prüfung stehen mehrere Termine zur Verfügung, die allerdings an verschiedenen Standorten angeboten werden. Will man zu einem anderen Termin in die Prüfung gehen, so muss man in der Regel auch einen anderen Standort anfahren.

 

Das Studienbüro ist gut erreichbar und bei organisatorischen Fragen sehr hilfreich. Als Gasthörer hatte ich immer wieder mal eine organisatorische Frage, weil ich mit den Abläufen noch nicht so vertraut war.

 

Etwas verwirrend für mich: Während Springer Campus EINE Online-Plattform für den Studiengang hat, gibt es an der WINGS mehrere: StudIP, Ilias, den OnlineCampus, Wistu und wie sie alle heißen. Es dauerte eine ganze Weile, bis ich halbwegs begriffen hatte, wo ich welche Informationen finde.

 

Das Modul "Theoretische Informatik"

 

Grundlage für das Modul ist das in meinen Augen hervorragende Skript von Professor Jürgen Cleve. Er lehrt an der HS Wismar Grundlagen der Informatik und Künstliche Intelligenz. Sein Skript besteht aus an die 130 Seiten im A4-Format. Wenn man Anhänge, Verzeichnisse und Index abzieht, bleiben ca. 120 Seiten reiner Stoff. Die haben es allerdings ziemlich in sich, weil die Ausdrucksform mathematisch knapp ist, man also mit wenigen Symbolen viel ausdrücken kann. Diese 120 Seiten liest man also nicht mal eben so runter. Mehr als 2-4 Seiten pro Tag waren bei mir selten drin. Damit man bis zum Prüfungstermin "fit" ist, muss man dranbleiben und "den Berg Kieselstein für Kieselstein abtragen".

 

Das Skript gliedert sich in 6 Kapitel:
1. TI - Einführung
2. Grundlagen
3. Automatentheorie
4. Logik
5. Komplexität
6. Berechenbarkeit

 

Es enthält auch einen Vorschlag, wie man sich die Bearbeitung des Moduls zeitlich einteilen soll. Damit bin ich flexibel umgegangen.

 

Außer dem Skript findet man auf der Plattform StudIP Zusatzmaterial, Videos, Übungsaufgaben für die Klausur und einen Link zum Download von JFLAP, einer Software zum Simulieren der verschiedenen Automaten aus dem Kapitel Automatentheorie. Im Unterschied zu Springer Campus, wo alles schön in EINER Plattform beisammen ist, muss man hier aus mehreren Quellen schöpfen. Die Materialien sind aber sehr gut.

 

Mathematische Grundlagen

 

Das Grundlagenkapitel ist ein Parforceritt durch Mengenlehre, Relationen und Funktionen. Grundlagen waren bei mir aus dem Modul Mathe1 da. Ich würde sagen, dass man davon ausgeht, dass die meisten Studierenden sich schon einmal mit diesen Themen vertraut gemacht haben. Es ist eher eine knappe Wiederholung, die noch einmal den begrifflichen Boden bereiten soll, für das was kommt. Außerdem werden so verschiedene Konventionen hinsichtlich der Darstellung etabliert, was die weitere Lektüre des Skriptes vereinfacht.

 

Auch die sehr knappe Einführung in Begriffe der Graphentheorie enthielt größtenteils vertrautes. Auch das kannte ich aus Mathe1. Aber hier kamen die ersten für mich neuen Begriffe, z.B. der der Hülle eines Graphen. Dieser Begriff ist hilfreich, wenn man ausdrücken möchte, wie ein Automat durch eine Serie von Konfigurationsübergängen geht.

 

Neu war für mich in erster Linie der Abschnitt über formale Sprachen. Knapp ausgedrückt, hat man eine Sammlung von Zeichen, ein Alphabet. Dieses besteht bei formalen Sprachen oft aus nur wenigen Zeichen, z.B. {0,1} oder {a,b,c} oder etwas in der Art. Wörter entstehen dadurch, dass man Ketten aus Zeichen bildet, also Strings. Eine Sprache entsteht dadurch, dass wir Eigenschaften definieren, die die so erzeugten Strings aufweisen müssen, z.B. mindestens eine Folge von drei Nullen enthalten. Eine Sprache ist also eine Teilmenge der mit dem Alphabet möglichen Strings.

 

Interessanter wird es, wenn reguläre Ausdrücke ins Spiel kommen. Sie erlauben, bestimmte Stringmuster in kompakter Weise zu beschreiben. Das kann man in vielen Programmiersprachen gut brauchen, um z.B. Muster für Suche und Vergleich zu definieren. Zugleich sind reguläre Ausdrücke wichtig, weil sie mit einem bestimmten Automatentyp aus der Automatentheorie in Zusammenhang stehen, den sogenannten endlichen Automaten. Diese können nämlich genau solche Strings erkennen, die sich durch reguläre Ausdrücke beschreiben lassen.

 

Über das Kapitel verstreut sind gelegentlich Übungsaufgaben. Am Ende des Kapitels kommen dann noch mal mehr Aufgaben. Im Gegensatz zu Springer Campus ist die Bearbeitung dieser Aufgaben nicht nötig, um zur Klausur zugelassen zu werden. Man kann seine Lösungen aber per Mail an einen Betreuer schicken. Besser ist es, sie ins Forum von StudIP einzustellen, wo sie auch andere Studierende sehen. Die Aufgaben werden auch dort von einem Betreuer kommentiert, jedenfalls wenn es etwas zu kommentieren gibt. Perfekte Lösungen bleiben auch mal ohne Feedback. Im Vergleich zu Springer würde ich sagen, dass es hier mehr und kleinere Aufgaben gibt. Das ist nicht schlecht, weil man so ähnliche Aufgaben wiederholt übt, was ungemein hilft, die Konzepte zu verinnerlichen.

 

Automatentheorie

 

Dieses Kapitel ist für mich das Kernkapitel des Moduls. Es behandelt zunächst endliche Automaten, abgekürzt DFA für engl. deterministic finite automaton. Einen endlichen Automaten kann man sich vorstellen als eine Maschine, die ein Band einliest, auf dem Zeichen notiert sind. Die Maschine liest das Band genau 1x von Anfang bis Ende. Sie kann nicht vor oder zurück gehen und auch nichts auf das Band schreiben. Sie kann aber in Abhängigkeit vom eingelesenen Zeichen ihren inneren Zustand wechseln. Ist die Maschine am Ende des Bandes in einem Zustand, der als akzeptierend ausgezeichet wurde, so sagt man, die Maschine habe die Zeichenkette akzeptiert. Die Maschine hat erkannt, dass das Wort auf dem Band zu einer Sprache gehört.

 

Natürlich existiert dieser Automat nicht physisch sondern als Konzept. Man beschreibt ihn mathematisch. Mit der Menge von Zeichen, die er verarbeiten kann. Mit der Menge der Zustände, die er einnehmen kann. Mit dem Startzustand. Mit der Menge der Zustände, die als akzeptierend gelten. Und vor allem mit den Regeln für Übergänge von einem Zustand in den anderen in Abhängigkeit vom eingelesenen Zeichen. Deterministisch heißt der Automat, weil die Zustandsübergangsfunktion total ist. In jedem Zustand ist bei jedem eingelesenen Zeichen eindeutig, in welchen neuen Zustand der Automat wechselt. Durch die mathematische Form der Darstellung, kann man so einen Automaten in wenigen Zeilen exakt notieren.

 

Verständlicher wird ein Automat, wenn man ihn graphisch darstellt. Er wird als Graph mit gerichteten Kanten gezeichnet. Die Kanten stehen für Zustandsübergänge, die Knoten für die Zustände.

 

Hier ist ein Beispiel für einen deterministischen endlichen Automaten, der Wörter aus den Buchstaben "a" und "b" akzeptiert, die mindestens 1x die Zeichenkette "aab" enthalten. Das kleine Dreieck links markiert den Startzustand. Die Kreise stehen für die Zustände, die Pfeile für Zustandsübergänge, wenn im jeweiligen Zustand das Zeichen auf dem Pfeil eingelesen wird. Der Doppelkreis rechts steht für den einzigen akzeptierenden Zustand. Wie man sieht, gibt es auch reflexive Kanten. Sie bedeuten, dass der Automat im aktuellen Zustand bleibt. Der Automat ist deterministisch, weil von jedem Zustand aus für jedes mögliche Zeichen genau ein Zustandsübergang existiert.

DFA_aab.png

 

Nach dem DFA wird der NFA eingeführt. Er ist indeterministisch, weil der Folgezustand nicht mehr eindeutig definiert sein muss. Es kann mehrere Folgezustände geben. Der Automat wählt aber nicht zufällig einen davon aus. Vielmehr geht er in JEDEN möglichen Folgezustand. Man kann zeigen, dass ein NFA in einen DFA überführt werden kann. Dafür gibt es sogar ein mechanisches Verfahren. Für viele Probleme ermöglicht der NFA eine kompaktere Darstellung. Aber er kann nicht mehr als der DFA.

 

Die Beschäftigung mit endlichen Automaten ist nützlich, z.B. weil man damit in der Softwaretechnik manche dynamische Systeme gut modellieren kann.

 

Der DFA und der NFA sind in ihren Möglichkeiten begrenzt, weil sie sich nur durch ihren inneren Zustand etwas merken können. Soll ein Automat z.B. 100 Zeichen zählen, braucht er 100 innere Zustände. Aus diesem Grund wird der Kellerautomat eingeführt. Er hat einen Speicher, den Keller, auf den er Zeichen legen kann. Dieser Speicher ist ein Stack. Die Zeichen werden gestapelt und man kann immer nur das oberste Zeichen lesen. Der Kellerautomat kann z.B. vergleichen, ob die Anzahl A's zu Beginn eines Wortes gleich der Anzahl B's am Ende des gleichen Wortes ist. Er kann somit etwas zählen.

 

Die von Kellerautomaten akzeptieren Sprachen lassen sich mit kontextfreien Grammatiken beschreiben. Diese sind nützlich, weil sich die Syntax der meisten Programmiersprachen ebenfalls mit kontextfreien Grammatiken beschreiben lässt.

 

Weil es Sprachen gibt, die nicht kontextfrei sind, braucht man einen mächtigeren Automaten als den Kellerautomaten: Die Turingmaschine. Die Turingmaschine ist deterministisch. Sie liest ein endloses Band ein. Einen Kellerspeicher hat sie nicht. Dafür kann sie auf dem Band schrittweise nach rechts und nach links gehen oder stehen bleiben. Sie kann Zeichen lesen und schreiben. Das Band ist also ihr Speicher. Es enthält eine Folge von Zeichen, einen String. Die Turingmaschine verarbeitet den String, d.h. sie transformiert ihn in einen neuen String. Wenn der String z.B. aus zwei natürlichen Zahlen besteht und die Maschine am Ende die Summe dieser beiden Zahlen auf das Band schreibt, dann kann man sagen, die Maschine hat eine Summe berechnet.

 

Die Turingmaschine ist ein einfaches Computermodell. Interessant ist, dass sie zugleich das mächtigste bislang bekannte Computermodell ist. Mächtigkeit bezieht sich hier nicht auf die Verarbeitungsgeschwindigkeit sondern auf das, was prinzipiell mit einer Maschine dieses Typs berechnet werden kann. Jeder Computer kann im Prinzip nur berechnen, was auch auf einer Turingmaschine berechnet werden könnte. Darum ist es interessant, sich mit diesem Automaten zu beschäftigen.

 

TI ist ein FH-Modul. Der Schwerpunkt liegt also hier nicht auf dem Führen von Beweisen. Die Übungsaufgaben laufen meist darauf hinaus, Automaten zu konstruieren, die ein bestimmtes Problem lösen. Mit der Software JFLAP kann man seine Automaten testen, mit verschiedenen Strings füttern und schauen, wie sie diese Schritt für Schritt verarbeiten. Das hat mir sehr viel Spaß gemacht. Und es hat auch schon eine Menge mit Programmierung zu tun. Der erste Schritt zur Lösung ist meist, sich eine Strategie zu überlegen, wie ein Automat ein Problem lösen könnte, eine Art Algorithmus. Dann muss man sich mit den Details der Implementierung rumschlagen, wozu oft auch eine geschickte Behandlung von Sonderfällen gehört.

 

Logik

 

Das Kapitel zur Logik beschäftigt sich nur mit Aussagenlogik. Die mächtigere Prädikatenlogik spielt keine Rolle. Hier hatte ich Vorkenntnisse aus den Modulen "Mathe1" und "Rechnerstrukturen und Betriebssysteme". Trotzdem hat mir dieses Kapitel viel gebracht. Nachdem knapp einführt wird, wie man Aussagen formalisiert, mit Operatoren verknüpft und mit Umformungsregeln umformt, wird die konjunktive- und die disjunktive Normalenform eingeführt. Sie ist eine Art standardisierte Darstellung komplex verknüpfter Aussagen. So weit kannte ich den Stoff.

 

Der nächste und für mich neue Schritt bestand nun darin, die konjunktiv verknüpften Ausdrücke sehr kompakt als Mengen zu schreiben. Die nennt man Klauseln. Aus Klauseln kann man mit einer einfachen Umformung - der Resolution - neue Klauseln erzeugen. Man kann so Widerspruchsbeweise führen. Die Gültigkeit einer Schlussfolgerung kann man prüfen, indem man sie in negierter Form den bisherigen Klauseln hinzufügt und dann einen Widerspruch findet.

 

All dies könnte man auch auf anderem Wege tun, z.B. mit Wahrheitstabellen oder mit Umformungen. Das interessante an Klauseln und am Resolutionsbeweis ist, dass man...

1. effizient mit sehr großen Mengen von Aussagen umgehen kann, was bei Wahrheitstabellen schnell unübersichtlich wird.

2. Resolutionsbeweise gut automatisiert per Software führen kann.

 

Gerade der letzte Punkt ist entscheidend: Man hält das mathematisch-logische Werkzeug in den Händen, um einen automatischen Beweiser zu bauen. Der Stoff dieses Kapitels ist Grundlage für logische Programmiersprachen wie Prolog. Ich vermute, genau aus diesem Grund hat mir Herr Cleve dieses Modul als Grundlage für KI empfohlen. Dieses Kapitel hat mich positiv überrascht, weil ich hier wirklich etwas nützliches und neues gelernt habe, obwohl ich der Ansicht war, über Aussagenlogik schon eine Menge zu wissen.

 

Komplexität

 

Im Kapitel über Komplexität geht es Aufwandsabschätzungen. Platt ausgedrückt, schätzen wir Aufwand, indem wir zählen, wieviele Zuständsübergänge ein Automat durchlaufen muss, um ein bestimmtes Problem zu lösen. Wir zählen die Übergänge in der Regel nicht genau. Vielmehr ordnen wir sie einer Klasse zu. Der Aufwand wächst z.B. linear mit der Größe des Problems oder vielleicht auch quadratisch mit der Größe des Problems. Manches davon war mir aus dem Modul Algorithmen und Datenstrukturen (GdI4) bekannt. Hier wird das Thema Komplexität aber mathematischer und formaler behandelt.

 

Eine für mich schöne Übung war die Aufgabe, die Komplexität eines Sortieralgorithmus zu analysieren. Den durfte man sich frei aussuchen. Aus GdI4 kannte ich schon die Komplexitätsklassen vieler einfacher und komplexerer Sortierverfahren. Es wäre somit eine langweilige Aufgabe geworden. Allerdings war dort kurz ein Algorithmus namens Bucketsort erwähnt, der unter bestimmten Voraussetzungen ein Feld in linearer Laufzeit sortieren kann. Es hatte mich schon länger interessiert, wie das funktioniert, denn man kann ja mathematisch beweisen, dass ein Sortierverfahren, dass auf Vergleich basiert, im besten Fall logarithmische Komplexität hat. Wie kann man ohne Vergleiche schneller sortieren? Ja wie kann man überhaupt ohne Vergleiche sortieren? Die Übungsaufgabe war für mich also Anlass, mich mit dem mir bis dahin unbekannten Bucketsort-Algorithmus zu beschäftigen. Das hat wirklich Spaß gemacht.

 

Berechenbarkeit

 

In diesem letzten Kapitel werden die LOOP und die WHILE-Sprache eingeführt. Die LOOP-Sprache hat nur ganz wenige Konstrukte. Sie kann Variablen einen Wert zuweisen, sie um 1 erhöhen oder vermindern. Vor allem kann sie mit dem Befehl LOOP eine Schleife genau n-mal durchlaufen, wobei n zu Beginn festsehen muss. Die Sprache hat also nicht mal ein IF. Man kann es aber mit einem LOOP geschickt simulieren. Trotz der primitiven Möglichkeiten kann diese Sprache schon viel berechnen. Hilbert vermutete sogar, dass die LOOP-Sprache jede Funktion berechnen kann. Widerlegt wurde seine Vermutung durch die Ackermann-Funktion, die nicht mehr LOOP-berechenbar ist.

 

Darum brauchte man die WHILE-Sprache. Sie hat zusätzlich die WHILE-Schleife, die wiederholt eine Bedingung prüfen kann. Mit der WHILE-Sprache kann man nun genau die Probleme lösen, die auch eine Turingmaschine lösen kann.

 

Knapp gesagt geht es in dem Kapitel darum, was gemeint ist, wenn wir sagen, etwas sei berechenbar oder nicht berechenbar. Es gibt verschiedene Konzepte von Berechenbarkeit. Dieses Kapitel wird ein wenig philosophisch. Es geht hier letztlich darum, die Grenzen dessen auszuloten, was mit Computern gerechnet werden kann.

 

Präsenztag und Klausur

 

Module an der WINGS enden mit einem Präsenztag, an dem in der Regel auch die Abschlussklausur geschrieben wird. Anders als bei Springer Campus gibt es an der WINGS keine Möglichkeit, schon in der Bearbeitung eines Moduls ein paar Punkte für die Klausur zu sammeln. Die Note spiegelt allein die Performance in den 2 Stunden der Klausur wieder.

 

Die Präsenzveranstaltung vor der Klausur war bei TI eher eine Art Repetitorium, bei dem viele Übungsaufgaben bearbeitet wurden. Die Lehrform war sehr interaktiv. Automatentheorie nahm etwa die Hälfte der Zeit in Anspruch. Die Ideen der Teilnehmer wurden vom Dozenten direkt in JFLAP eingegeben und mit dem Beamer projeziert. So konnte man sofort sehen, was die Automaten machen und welche Fehler man noch verbessern muss. Die Übungen ließen darauf schließen, dass in der Klausur weniger Wissen abgefragt werden würde. Es schien darum zu gehen, Wissen anzuwenden, indem man Probleme löst. Dazu braucht man ein bisschen Kreatitivät.

 

Die intensive Wiederholung des Stoffes in der Gruppe unmittelbar vor der Prüfung ist eine tolle Vorbereitung. Das finde ich an der WINGS sehr gut gelöst. Die Klausur deckte den Stoff gut ab. Schwerpunkt war Automatentheorie, aber auch Grammatiken, Komplexität und der Resolutionsbeweis kamen dran.

 

Das Klausurergebnis kam nach knapp 2 Wochen. Schlecht war es nicht, aber ganz zufrieden war ich am Ende auch nicht. Das lag aber keinesfalls am Modul oder an der Klausur sondern daran, dass ich der Meinung war, bei dieser Prüfung ein bisschen hinter meinen Möglichkeiten zurückgeblieben zu sein.

 

Fazit

 

Das Modul "Theoretische Informatik" hat mir sehr viel Spaß gemacht. Die von Herrn Cleve gewählte Form der Darstellung, bei der es weniger ums Beweisen sondern vor allem um das Lösen von Problemen mit Automaten geht, finde ich für ein FH-Modul genau richtig. Das Skript ist verständlich geschrieben und lässt meiner Meinung nach auch solchen Studierenden eine faire Chance, die sich mit dem eher trockenen Stoff der TI nicht anfreunden können.

 

Sehr gut war auch das Feedback zu den Aufgaben durch Herrn Cleve. Oft hat er Rückfragen gestellt, Einwände formuliert, meine Aufmerksamkeit auf Spezialfälle gelenkt. Auf die Weise hat er mich angeregt, neu über meine Lösung nachzudenken. Das war viel besser als einfach nur Punkte zu verteilen. Es hat etwas für sich, dass die Übungsaufgaben NUR Übungsaufgaben sind und weder für die Note noch für die Zulassung zur Prüfung eine Rolle spielen. Das führt zu einem freieren Umgang mit der Übung. Statt auf Punkte zu zielen, geht es allein um den Stoff. Das hat mir gut gefallen.

 

Ich studiere gerne bei Springer Campus. Aber das Konzept der WINGS ist auch nicht schlecht. Diejenigen unter euch, die Wirtschaftsinformatik studieren möchten, mit etwas weniger zeitlicher Flexibilität bei Prüfungen zurecht kommen und BWL etwas stärker gewichten wollen, sollten sich das Angebot der WINGS einmal anschauen.

4 Kommentare


Empfohlene Kommentare

Wenn ich schon auf Master-Niveau wäre, würde ich mir wahrscheinlich auch mal das Modul "Automatentheorie" aus dem Weiterbildungsmaster Informatik der HS Trier anschauen. Das ist auf 10 ECTS angelegt und basiert auf dem Lehrbuch "Grundkurs theoretische Informatik" von Vossen und Witt. Die Themen sind im Prinzip die gleichen, aber es scheint mathematisch noch etwas tiefer zu gehen. Ist ja auch mehr Zeit angesetzt. Das hätte mich auch interessiert, aber das hätte ich zeitlich parallel zum Bachelorstudium nicht geschafft. In erster Linie wollte ich ja die Voraussetzungen schaffen, um im nächsten Semester "Künstliche Intelligenz" belegen zu können.

Link zu diesem Kommentar

Danke für den Bericht. Schön, dass es geklappt hat, als Gasthörer dein Wunschmodul zu ergänzen.

 

Interessant fand ich besonders deine Vergleiche mit Unterschieden zwischen WINGS und Springer Campus.

Link zu diesem Kommentar

Solche Vergleiche sollte man natürlich nicht überbewerten. Ich habe an der WINGS ja lediglich EIN Modul kennengelernt. Und das war auch noch eines, das mich inhaltlich sehr interessiert hat. Aber es war schon interessant, mal einen kleinen Einblick zu bekommen, wie es an einer anderen FH läuft. Ich fühle mich auf jeden Fall ermutigt, so etwas zu wiederholen, falls ich wieder einmal ein interessantes Angebot sehe.

Link zu diesem Kommentar

Erstelle ein Benutzerkonto oder melde Dich an, um zu kommentieren

Du musst ein Benutzerkonto haben, um einen Kommentar verfassen zu können

Benutzerkonto erstellen

Neues Benutzerkonto für unsere Community erstellen. Es ist einfach!

Neues Benutzerkonto erstellen

Anmelden

Du hast bereits ein Benutzerkonto? Melde Dich hier an.

Jetzt anmelden


×
  • Neu erstellen...