Die Grundlagenveranstaltungen heißen Elementare Logik, Diskrete Strukturen, Automaten und Formale Sprachen sowie Berechenbarkeit und Komplexitätstheorie. Die vom Lehrstuhl betreuten Veranstaltungen sind Diskrete Strukturen und Automaten und Formale Sprachen. Das Ziel der Grundlagenveranstaltungen insgesamt ist die Bereitstellung der Grundbegriffe und -techniken der Informatik, die notwendig sind, komplexe Zusammenhänge und Systeme zu verstehen, zu beschreiben und zu entwickeln.

Diskrete Strukturen

Diese Vorlesung bildet eine organisatorische Einheit (Modul) mit Elementare Logik. Zentral ist der Begriff der Menge. Darauf aufbauend werden Begriffe wie Relationen, Funktionen, Operationen, algebraische Strukturen und Graphen betrachtet. Diese Begriffe spielen in der Informatik eine wichtige Rolle. Es wird gezeigt, wie man mit diesen Begriffen umgeht, wie man über deren Eigenschaften argumentiert und wie man diese Eigenschaften ausnutzen und anwenden kann.

Automaten und Formale Sprachen

Diese Vorlesung bildet eine organisatorische Einheit (Modul) mit Berechenbarkeit und Komplexitätstheorie. In einem ersten Vorlesungsteil werden verschiedene Aspekte von regulären Sprachen betrachtet, und in einem zweiten Vorlesungsteil werden kontextfreien Sprachen untersucht. Darüber hinaus werden für die Stufen der Chomsky-Hierarchie Automaten- und Grammatikmodelle diskutiert.

Es werden Grundkenntnisse und Grundtechniken aus der Mathematik und Informatik vorgestellt und anhand einfacher Beispiele geübt. Dabei kann es sich um bereits bekanntes handeln, oder um neues. Die Vorkurse bieten vornehmlich einen sanften Einstieg in den Vorlesungsalltag, bereiten bereits bekanntes Wissen auf oder greifen auf kommende Vorlesungsinhalte, meist vereinfachend, vor.

Die Vorkurse sind nicht Teil des offiziellen Curriculums; es gibt keine Abschlußprüfung. Die Teilnahme ist daher nicht verpflichtend, die Teilnahme wird aber empfohlen.

Ein weiterer Mehrwert der Vorkurse ist das Kennenlernen der neuimmatrikulierten Studenten untereinander.

Algorithmisches Lernen kann als Teilbereich der Künstlichen Intelligenz bzw. des Maschinellen Lernens angesehen werden. Wie auch in anderen Bereichen der Informatik finden sich unter dieser Rubrik Untersuchungen, welche das prinzipiell Machbare studieren (Lerntheorie) und solche, die eher die auf Rechnern umsetzbare Seite untersucht (Lernalgorithmen, alternierend mit Datenkompression).

• Die Lerntheorie untersucht verschiedene Lernmodelle, um die Möglichkeiten und Grenzen insbesondere des automatisierten Lernens auszuloten. Hierdurch ergeben sich natürliche Querbezüge zur Berechenbarkeitstheorie, und zwar nicht nur vordergründig durch die Betrachtung dessen, was Maschinen grundsätzlich vermögen, sondern auch tiefergründig durch die Anwendung ähnlicher mathematischer Methoden. Deshalb sind Berechenbarkeit und Lerntheorie bei uns auch in einem Modul angesiedelt.
• Die Veranstaltung Lernalgorithmen kümmert sich dahingegeen um die Analyse konkreter Algorithmen (zu bestimmten Lernszenarien), insbesondere fokussierend auf das Lernen formaler Sprachen, genauer deren Beschreibungsmodelle. Mithin ergeben sich Querverbindungen zu Formalen Sprachen, aber auch beispielsweise zur Computerlinguistik. Die Grundfragestellungen sind auch mit denen des fallbasierten Schließens bzw. der Datenkompression verwandt.
• in der Datenkompression werden Möglichkeiten erläutert, verschiedenartige Daten mit möglichst wenigen Bits zu übertragen. Grundidee ist hierbei zumeist, Regelmäßigkeiten in den vorliegenden Daten aufzudecken und diese für eine komprimierte Darstellung auszunutzen. Querbezüge zu gewissen Fragen, die auch bei den Lernalgorithmen und bei Formalen Sprachen angesprochen werden, liegen daher nahe. Für das tiefere Verständnis einiger Verfahren sind allerdings Kenntnisse aus der höheren Analysis unumgänglich.

Aus Sicht der Informatik gliedert sich die Welt in das Berechenbare und das Nichtberechenbare. Die Grenze dazwischen verläuft scharf, denn es gibt nichts drittes. Das Berechenbare umfaßt all das, was unter Anwendung formaler Methoden gelöst werden kann, das Nichtberechenbare ist der ganze Rest. Die Berechenbarkeitstheorie versucht, diese Begriffe zu verstehen und zu erklären.

Der Kern der Berechenbarkeitstheorie ist der Begriff "Anwendung formaler Methoden". Jede mathematische Theorie fußt auf exakt formalisierten Begriffen, und "Anwendung formaler Methoden" entspricht dieser Forderung nicht. Die Berechenbarkeitstheorie kennt viele Formalisierungen von "Anwendung formaler Methoden", und diese sind gleichwertig. Wir sprechen heute von Algorithmenbegriffen. Die Kenntnis verschiedenartiger Formalisierungen der (intuitiven) Idee eines Algorithmus bezeugt dessen Bedeutung.

Im Rahmen der Berechenbarkeitstheorie werden verschiedene Algorithmenbegriffe untersucht. Es werden verschiedene Stufen des algorithmisch Lösbaren definiert und untersucht; darunter sind Entscheidbarkeit und Aufzählbarkeit die wichtigsten. Es wird untersucht, wann ein Problem entscheidbar oder "nur noch" aufzählbar ist, und es werden Eigenschaften solcher Probleme studiert.

Die Algorithmentheorie schließt sich stark an die Komplexitätstheorie an. Hier stehen aber konkrete Probleme im Vordergrund. Vielfach geht es um Probleme, die sich exakt nicht effizient lösen lassen (oder eben ein effizienter Lösungsalgorithmus nicht bekannt oder nicht effizient genug ist), die aber trotzdem irgendwie gelöst werden sollen. Die Algorithmentheorie untersucht algorithmische und analytische Methoden, dennoch vertretbare Lösungen im angestrebten Effizienzmaß zu erhalten.

Es gibt verschiedene Ansätze, hier erfolgreich zu sein:

• Die Lösung muß nicht optimal sein, sollte aber nachweisbar gut sein. Dies führt zu Approximationsalgorithmen.
• Kleine Lösungsgrößen sollen schnell gefunden werden, große Lösungsgrößen dürfen mehr Zeit beanspruchen. Dies führt zu parametrisierten Problemen, die in Parametrisierte Algorithmen untersucht werden.
• Es genügt, fast immer die optimale Lösung (oder eine sehr gute Lösung) zu erhalten, oder es genügt, die optimale Lösung fast immer sehr schnell zu erhalten. Dies führt zu randomisierten Algorithmen. Im letzteren Fall, wenn die Lösung fast immer schnell erhalten wird, sind randomisierte Algorithmen über viele Eingaben betrachtet sehr effizient.

Insbesondere die ersten beiden genannten Veranstaltungen werden regelmäßig abwechselnd angeboten. Sie behandeln beide die Frage, wie man mit NP-harten Problemen algorithmisch umgehen kann. Auch hierzu gibt es entsprechende Komplexitätstheorien, die die Grenzen dieser Ansätze aufzeigen möchten.

Gegenstand der Untersuchungen sind Beschreibungsmodelle wie Automaten und Grammatiken. Aufbauend auf den Kenntnissen der Grundvorlesung werden Eigenschaften verschiedener solcher Beschreibungsmodelle betrachtet.

Typische Fragestellungen sind: Welche Klassen von Sprachen lassen sich durch die Modelle darstellen? Welche mengentheoretischen Beziehungen bestehen zwischen diesen Klassen? Welche algebraischen Eigenschaften besitzen diese Klassen? Lassen sich effiziente Parsingalgorithmen für die Beschreibungsmodelle angeben? Ebenso werden andere Entscheidungs- und Berechnungsaspekte diskutiert. Wie knapp lassen sich Sprachen oder einzelne ihrer Elemente durch die Modelle darstellen ?

Demgemäß gibt es natürliche Berührpunkte mit Vorlesungen über Compilerbau, über semistrukturierte Daten (Baumsprachen), zur Linguistik, zur Algorithmik und zur Komplexitätstheorie.

Das Interesse der Komplexitätstheorie beginnt dort, wo das der Berechenbarkeitstheorie endet. Die Komplexitätstheorie untersucht Probleme in bezug auf ihren Ressourcenverbrauch, klassifiziert Probleme entsprechend und studiert die sich ergebenden Komplexitätsklassen.

Die wohl bekanntesten Komplexitätsklassen sind P und NP. Beides sind Polynomialzeitklassen, allerdings bezüglich verschiedener Algorithmenbegriffe. Die Komplexitätstheorie untersucht die Beziehungen zwischen Komplexitätsklassen verschiedenen Ressourcenverbrauchs, aber zum selben Algorithmenbegriff, oder betrachtet gleichartigen Ressourcenverbrauch bezüglich verschiedener Algorithmenbegriffe, oder variiert beide Parameter.

Weiterhin untersucht die Komplexitätstheorie Eigenschaften der Probleme innerhalb einer Komplexitätsklasse. Allgemein gesprochen: Welche Eigenschaften werden nur durch die Wahl des Algorithmenbegriffs und der Ressourcenbeschränkung erzwungen?

In zum Teil unregelmäßigen Abständen bereichern wir unser Vorlesungsangebot überdies zu weiteren Themen der Theoretischen Informatik und angrenzender Gebiete um weitere Inhalte. Wir versuchen hierbei, der großen thematischen Breite in der Theoretischen Informatik, der aktuellen Forschung sowie dem Anwendungsspektrum in der Praxis gerecht zu werden. Hierfür ist ein eigenes Modul Spezielle Kapitel aus der Theoretischen Informatik vorgesehen.