Modul Informatik 2, Informatik (Bachelor) (SPO 8)
Die Studenten lernen grundlegende Algorithmen und Datenstrukturen kennen. Sie sollen abschätzen, in welcher Situation spezifische und komplexe Datentypen eingesetzt werden, wie diese funktionieren und welchen Zeitaufwand sie besitzen. Sie können die Korrektheit von Algorithmen beweisen. In der Übung müssen Sie Ihre erlangten Kenntnisse anhand verschiedener Aufgaben anwenden. Sie erlernen theoretische Berechenbarkeitsmodelle und deren Grenzen.
Die Vorlesung gliedert sich in mehrere Teile, die inhaltlich aufeinander aufbauen:
- Im ersten Teil sollen die Studenten Probleme genau definieren, Algorithmen für ein Problem in Pseudocode verstehen und formulieren, den Resourcenverbrauch eines Algorithmus abzuschätzen und die Korrektheit eines Algorithmus beweisen können.
- 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.
- 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.
- 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.
- 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 und Skript.
- 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.
Dr. Martin Holzer
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
- Quelltexte mit vorgegebenen Rahmen und ausführlicher Dokumentation für die Aufgaben.
Vorführen und Diskussioin der Lösungen in den Übungen.
Kern dieser Vorlesung ist die Vermittlung der Grenzen von heutigen Computern, die selbst bei 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.
Die Lehrveranstaltung umfasst unter anderen die folgenden Gebiete der theoretischen Informatik: Elementare Berechnungsmodelle wie Turingmaschinen und WHILE-Programme, die Church-Turing-These, Unentscheidbarkeit, die Theorie der NP-Vollständigkeit und Zero-Knowledge-Beweise.
Für diese Lehrveranstaltung sind elementare Vorkenntnisse zur theoretischen Informatik notwendig (regulären Sprachen, endliche Automaten, O-Kalkül, usw.). Diese Kenntnisse können z.B. in der Vorlesung Theoretische Informatik I erworben werden.
- Tafelanschrieb
- Skript
- Musterlösungen für alle Übungsaufgaben
- D. W. Hoffmann: Theoretische Informatik, 5. Auflage. Hanser, 2022
- M. Sipser: Introduction to the Theory of Computation, 3rd edition. Cengage Learning, Inc., 2012
Die Lehrveranstaltung findet als Vorlesung statt. Zahlreiche Übungsaufgaben vertiefen die vermittelten Gebiete und werden in evtl. zusätzlich angebotenen Tutorien diskutiert.