Modul Informatik 2, Medien- und Kommunikationsinformatik (Bachelor) (SPO 4)
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.