Modul Informatik 2, Medien- und Kommunikationsinformatik (Bachelor) (SPO 4)
Die Studenten lernen viele der in der Informatik immer wiederkehrenden Algorithmen und Datenstrukturen kennen. Weiterhin können sie abschätzen, in welcher Situation bestimmte komplexe Datentypen eingesetzt werden, wie diese funktionieren und welchen Laufzeitaufwand sie besitzen. Sie werden befähigt die Korrektheit von Algorithmen zu beweisen. In der Übung wenden Sie Ihre erlangten Kenntnisse anhand verschiedener Aufgaben an.
Die Vorlesung gliedert sich in mehrere Teile, die inhaltlich aufeinander aufbauen:
- 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.
- 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
- 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
- Quelltext mit vorgegebenen Rahmen und ausführlicher Dokumentation für die Aufgaben.