Datenstrukturen und Algorithmen (früher Informatik III)

Die Vorlesung bietet eine Einführung in die Konstruktion von Datenstrukturen und Algorithmen. Ziele sind das Kennenlernen und Vergleichen alternativer Implementierungen für abstrakte Datentypen, die Analyse der Korrektheit und des Zeit- und Speicherbedarfs und das Kennenlernen und Anwenden von Entwurfsparadigmen für Algorithmen

Stoffplan

Lineare Datentypen

• ADT Liste
• ADT Stack
• ADT Queue

Nicht-lineare Datenstrukturen I (Bäume)

• Definition und Eigenschaften
• ADT Tree
• Sequentielle Darstellung
• Verkette Darstellung

Anwendungen für Bäume

• Prioritätswartenschlangen und Heaps
• Huffman-Codes

Datenstrukturen zur Darstellung von Mengen

• ADT Set
• ADT Tabelle
• Implementation von Tabellen als lineare Listen
• Implementation von Tabellen mit Zugriff über Hashfunktion
• Implementation von Tabellen durch Bäume
• B-Bäume

Sortierung von Mengen

• Elementare Sortierverfahren
• Effektive Sortierverfahren für Felder
• Optimales Sortieren
• Sortieren mit linearer Komplexität

Nicht-lineare Datenstrukturen II (Graphen)

• Definition und Eigenschaften
• Implementation von Graphen
• Knotendurchlauf
• Minimale spannende Bäume
• Kurzeste Pfade in gerichteten Graphen

Weitere Informationen

Diese Veranstaltung wird abwechselnd mit dem Fachgebiet Datenbanken und Informationssysteme im Wintersemester durchgeführt.