Modul Informatik 2, Informatik (Bachelor) (SPO 7)

Die Vorlesung gliedert sich in mehrere Teile, die inhaltlich aufeinander aufbauen:

1. Im ersten Teil erwerben die Studenten Grundlagen, um Probleme genau zu definieren, Algorithmen für ein Problem in Pseudocode zu verstehen und zu formulieren, den Resourcenverbrauch eines Algorithmus abzuschätzen und die Korrektheit eines Algorithmus zu beweisen.
2. Darauf aufbauend erlernen die Studenten Such- und Sortierverfahren, wenden die im ersten Teil erworbenen Fähigkeiten darauf an und werden befähigt für ein Problem ein geeignetes Verfahren auszuwählen. Sie lernen die untere Schranke dieser Problem kennen und zu beweisen.
3. Im dritten Teil eignen sie sich detaillierte Kenntnisse über den Aufbau und Implementierung von Operation elementarer Datenstrukturen, wie Warteschlangen, Listen und Binärbäume an. Die Studenten lernen typische Anwendungsbeispiele für diese Datenstrukturen kennen.
4. Der vierte Teil der Vorlesung konzentriert sich auf weiterführende Datenstrukturen und die zugehörigen Algorithmen, wie Hashtabellen und binäre Suchbäume. Sie lernen, wie Suchbäume balanciert werden können.
5. Im abschließende fünften Teil beschäftigt sich die Vorlesung mit den Grundlagen von Graphen. Die Studenten lernen unterschiedliche Repräsentationen von Graphen, wie Adjazenzmatrix und Adjazenlisten, kennen und einzusetzen. Sie erlernen Basisalgorithmen, wie Kürzeste-Pfad-Suche, Union-Find und die Berechnung minimaler Spannbäume.

• Vorlesungsfolien
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. Third Edition. MIT Press.
• Robert Sedgewick: Algorithms in Java. Addison Wesley. Third Edition.

Zusätzliche wöchentliche Übungsaufgaben für die Vor- und Nacharbeit der Vorlesungsinhalte und zur Prüfungsvorbereitung.

Einfache Aufgaben in der Vorlesung.

Die Studierenden vertiefen das in der Vorlesung erworbene Wissen, indem sie ausgewählte Algorithmen in Java implementieren und testen. Dazu verwenden sie jeweils Standard-Entwicklungsumgebungen.

Die zu implementierenden Algorithmen und Datenstrukturen werden in einer abschliessenden Aufgabe kulminiert eingesetzt.

• Übungsaufgaben
• Quelltext mit vorgegebenen Rahmen und ausführlicher Dokumentation für die Aufgaben.

Die Vorlesung vermittelt die Grenzen der Berechnungskraft heutiger Computer, die selbst bei potentiell unendlich viel vorhandenem Speicherplatz auftreten. Themen sind vor allem die Berechen- und Unentscheidbarkeit diverser Probleme. Ebenso wird eine Einführung in die Theorie hartnäckiger Probleme gegeben.

Den Studierenden werden dazu die folgenden Gebiete der theoretischen Informatik vermittelt: elementare Berechnungsmodelle wie Turingmaschinen und WHILE-Programme, die Church-Turing-These, Unentscheidbarkeit sowie eine Einführung in die Komplexitätstheorie. Die P=NP Frage sowie die Ausnutzung hartnäckiger Probleme für sogenannte Zero-Knowledge-Beweise werden ebenfalls besprochen.

Mit dieser Lehrveranstaltung erhalten die Studierenden eine Vorstellung von prinzipiell schwer oder sogar vollständig unlösbaren Aufgabenstellungen. Sie verstehen, dass folglich Kompromisse bei der Qualität der gewünschten Ergebnisse oder der Laufzeit eingegangen werden müssen.

• Tafelanschrieb
• Skript
• Zu allen Übungsaufgaben werden Musterlösungen angeboten.
• D. W. Hoffmann: Theoretische Informatik, 3. Auflage. Hanser, 2015.
• M. Sipser: Introduction to the Theory of Computation, 3rd edition. Cengage Learning, Inc., 2012.

Die Lehrveranstaltung findet als reine Vorlesung statt. Zahlreiche Übungsaufgaben vertiefen die vermittelten Gebiete und werden in evtl. zusätzlich angebotenen Tutorien diskutiert.