Praktische Informatik 2

angeboten in jedem SoSe

• Typische Datenstrukturen identifizieren und problemadäquat einsetzen können.
• Datenstrukturen und Algorithmen in Java umsetzen können.
• Wesentliche Algorithmen der Informatik erklären, anwenden und modifizieren können.
• Algorithmische Alternativen bezüglich der Eignung für ein Problem beurteilen können.
• Grundbegriffe der formalen Verifikation erläutern können.
• Die Komplexität von einfachen Algorithmen analysieren können.
• Eine komplexe Entwicklungsumgebung nutzen können.
• Generische und funktionale Konzepte in eigenen Programmen einsetzen können.
• In Gruppen Probleme analysieren und gemeinsam Lösungsstrategien entwickeln und präsentieren können.

Die Vorlesungen Praktische Informatik 1 und 2 vermitteln essenzielles Grundwissen und Basisfähigkeiten, deren Beherrschung für nahezu jede vertiefte Beschäftigung mit Informatik – sowohl in der industriellen Anwendung, als auch in der Forschung – Voraussetzung ist.

1. Algorithmen: Begriff des Algorithmus – Beschreibung von Algorithmen – Algorithmische Umsetzung kanonischer Operationen auf Datenstrukturen – Grundlegende Strategien: Greedy, Divide-and-Conquer, Backtracking, dynamische Programmierung
2. Komplexität von Algorithmen – O(n)-Notation und asymptotische Analyse
3. Suchen und Sortieren auf Arrays: Binäre Suche – Quicksort und weitere Sortieralgorithmen – Komplexitätsvergleiche
4. Mengen – Multimengen – Relationen – Funktionen: Datenstrukturen und Algorithmen zur Realisierung kanonischer Operationen (z.B. Mengenalgebra)
5. Listen – Stapel – Warteschlangen: Datenstrukturen zur Realisierung (Arrays versus Verkettung und dynamische Speicherallokation für Elemente), Algorithmen zur Realisierung kanonischer Operationen (Listentraversion, Anfügen, Einfügen, Löschen, Suchen, Stack-Operationen, FIFO-Warteschlangenoperationen)
6. Bäume: Binäre Bäume, AVL-Bäume, Rot-Schwarz-Bäume, B-Bäume – Suchen, Einfügen, Löschen, Traversion
7. Hashing: Hash-Array, Hashfunktion, Hash Buckets, offenes Hashing
8. Graphen: ungerichtete, gerichtete, gewichtete Graphen – Repräsentation durch Knoten- und Kantenlisten, durch Adjazenzmatrizen, Adjazenzlisten – Algorithmen auf Graphen: Breitensuche, Tiefensuche, kürzeste Wege auf gewichteten Graphen: Dijkstras Algorithmus, minimal aufspannende Bäume: Algorithmen von Prim et al. und Kruskal
9. Spezifikation von Programmen: Vor- und Nachbedingungen – Invarianten
10. Verifikation: Partielle und totale Korrektheit sequenzieller Programme – Formale Verifikation, z.B. Hoare Logik (Pre-/Postconditions) – Eigenschaftsbeweis durch Strukturelle Induktion

Lehrveranstaltung(en):

• 03-IBGP-PI2 Praktische Informatik 2: Algorithmen und Datenstrukturen

• G. Saake und K.-U. Sattler: Algorithmen und Datenstrukturen. dpunkt.verlag, Heidelberg (2004)
• R. Schiedermeier: Programmieren mit Java. Pearson, München (2005)

Weitere Informationen (Beispielprogramme, Musterlösungen, im WWW verfügbare Literatur) sind auf der Web-Seite der Veranstaltung zu finden.