Die weiteren Vertiefungsmodule

Falls Sie Sich entschieden haben den Bereich "Grundlagen der Informatik" mit mindestens 16 CP in Ihrem Bachelor-Studiengang zu wählen, empfehlen wir Ihnen mindestens eines der folgenden Vorlesungen zu belegen:

Effiziente Algorithmen

Ein zentrales Problem der Informatik ist der Entwurf von ressourcenschonenden Algorithmen. In der Veranstaltung werden deshalb fundamentale Fragestellungen im Entwurf und in der Analyse effizienter sequentieller Algorithmen und Datenstrukturen besprochen. Eine Auswahl der folgenden Themengebiete wird behandelt:

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Grundkenntnisse aus der Stochastik (Modul B-M3)
Benötige Module: B-GL1 (Theoretische Informatik I) und B-GL2 (Theoretische Informatik II)
CP: 9 CP (4 Vorlesungsstunden, 2 Übungsstunden pro Woche)
Rhythmus: jedes SoSe
Empfehlung: ab 4. Semester (Start im WiSe), ab 5. Semester (Start im SoSe)

Logik in der Informatik

In der Diskreten Modellierung haben wir bereits die Logik erster Stufe kennengelernt. In der Tat ist das in der Informatik ein sehr wichtiges und ein sehr mächtiges Werkzeug. Beispielsweise arbeitet ein Informatiker ziemlich oft mit Datenbanken. Wie wir in der Diskreten Modellierung bereits gesehen haben, lassen sich auch Datenbankanfragen als Formeln der Logik erster Stufe ausdrücken. Doch welche Konsequenzen gibt es, falls wir das nicht (!) als eine Formel der Logik erster Stufe ausdrücken können? Alles liegt einer entscheidenden Frage zu Grunde: Im ersten Teil der Vorlesung steht diese Frage im Mittelpunkt. Es werden verschiedene Strategien vorgestellt um nachzuweisen, dass ein Problem nicht als Formel der Logik erster Stufe ausdrückbar ist. Außerdem werden in dieser Vorlesung noch weitere mathematische Resultate zur Logik erster Stufe vorstellt. Wir haben beispielsweise als Eingabe eine Formel der Logik erster Stufe und möchten wissen: Gibt es überhaupt eine Struktur, die diese Formel erfüllen kann? Es wird gezeigt, dass dieses Problem unentscheidbar ist. Weiterhin wird auch die Auswertungskomplexität der Logik erster Stufe betrachtet. D.h. wir haben eine Formel der Logik erster Stufe und wir möchten eine Lösung auf einer Struktur berechnen. In welcher Zeit können wir das algorithmisch lösen? Eine weiteres sehr interessantes Resultat ist das folgende: Wir können mit den Formeln der Logik erster Stufe einen Beweiskalkül bauen und es wird gezeigt, dass wenn wir als Struktur die Standardarithmetik über die natürlichen Zahlen betrachten, dass es dann einen Satz gibt der ''wahr'' ist, aber den wir nicht beweisen können. Zudem können wir nicht alle gültigen Sätze der Logik erster Stufe über der Standartarithmetik rekursiv aufzählen.

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Kenntnisse aus der Diskreten Modellierung (insbesondere das Kapitel zu Logik erster Stufe) und aus der GL-1 (man kann diese Veranstaltung auch parallel zur GL-1 hören)
Benötige Module: (B-MOD (Diskrete Modellierung) und B-DS (Datenstrukturen) ) oder B-GL1 (Theoretische Informatik I) oder B-GL2 (Theoretische Informatik II)
CP: 9 CP (4 Vorlesungsstunden, 2 Übungsstunden pro Woche)
Rhythmus: Alle zwei Jahre im WiSe
Empfehlung: ab 3. Semester (Start im WiSe), ab 4. Semester (Start im SoSe)
Link zur Veranstaltung

Baumzerlegungen, Algorithmen und Logik

Angenommen wir arbeiten in einem Betrieb und bekommen von unserem Vorgesetzten den Auftrag ein bestimmtes Problem in ein Programm umzusetzen. Doch das Problem ist NP-vollständig. Wir haben in der Theoretischen Informatik 1 bereits gelernt, was es für ein Problem bedeutet NP-vollständig zu sein und wissen auch wie wir das feststellen können. Doch was ist nun, wenn wir dieses Problem lösen müssen? Hier helfen uns Baumzerlegungen weiter. Zum einen betrachten wir zunächst NP-vollständige Probleme (wie z.B. Independet-Set, Vertex Cover oder das Clique Problem). Wenn wir in diesen Problemen nur den Graphen durch einen Baum ersetzen, dann stellen wir plötzlich fest, dass die Probleme ''total einfach'' sind. In dem Konzept der Baumzerlegungen wird versucht, in einem Graphen eine baumähnliche Struktur zu erkennen und diese dann effizient aufzulösen. Es werden Algorithmen ausgearbeitet, die Probleme bei gegebener Baumzerlegung effizient lösen können. Darüber hinaus wird eine höherstufige Logik eingeführt: Die monadische Logik zweiter Stufe. Das ist eine Erweiterung der Logik erster Stufe, wobei wir hier einstellige Relationen quantifizieren können. In der Tat besteht eine enge Beziehung zwischen den Baumzerlegungen und den Formeln der monadischen Logik zweiter Stufe, die im Detail in der Vorlesung behandelt wird.

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Kenntnisse aus der Diskreten Modellierung (insbesondere das Kapitel zu Logik erster Stufe) und aus der GL-1
Benötige Module: (B-MOD (Diskrete Modellierung) und B-DS (Datenstrukturen) ) oder B-GL1 (Theoretische Informatik I) oder B-GL2 (Theoretische Informatik II)
CP: 8 CP (3 Vorlesungsstunden, 2 Übungsstunden pro Woche)
Rhythmus: Alle zwei Jahre im SoSe
Empfehlung: ab 4. Semester (Start im WiSe), ab 5. Semester (Start im SoSe)

Approximationsalgorithmen

Der erste Teil der Veranstaltung behandelt effiziente Optimierungsalgorithmen. Insbesondere werden Greedy-Algorithmen und Matroide, dynamische Programmierung und die lineare Programmierung (Simplex und Interior Point Verfahren) beschrieben und im Detail analysiert. Der zweite Teil ist der Approximation von NP-harten Optimierungsproblemen gewidmet, wobei auf der linearen Programmierung aufbauende Heuristiken eine wichtige Rolle spielen. Des weiteren werden neben maßgeschneiderten- Heuristiken für fundamentale Optimierungsprobleme (wie etwa das Travelling Salesman Problem, Bin Packing Scheduling und Clustering Probleme) auch allgemeine Entwurfsprinzipien (lokale Suchverfahren, Branch and Bound, genetische Algorithmen, Lin-Kernighan und Kernighan-Lin) vorgestellt. Der dritte Teil der Vorlesung befasst sich mit der Frage, welche Approximationsgüte mit effizienten Algorithmen überhaupt erreicht werden kann. Dazu wird das Konzept der PCP Komplexitätsklassen (Probabilistically Checkable Proofs), das PCP Theorem und lückenbewahrende Reduktionen zwischen Optimierungsproblemen eingeführt.

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Grundkenntnisse aus der Stochastik (Modul B-M3)
Benötige Module: B-GL1 (Theoretische Informatik I)
CP: 8 CP (3 Vorlesungsstunden, 2 Übungsstunden pro Woche)
Rhythmus: eineinhalbjährlich
Empfehlung: ab 4. Semester (Start im WiSe), ab 5. Semester (Start im SoSe)

Überblick über die Module im Bereich "Grundlagen der Informatik" im Bachelor-Studiengang: