Grundlagen der Informatik

Inhalte:

• O-Notation und Laufzeitanalyse von Algorithmen, elementare Kombinatorik
• Relationen und Graphen, Graphalgorithmen
• Such- und Sortieralgorithmen
• Codierungstheorie

Materialien

• Boris Hollas: Grundkurs Theoretische Informatik

Die Vorlesungsunterlagen finden Sie in NextCloud. Den Link habe ich per E-Mail bekannt gegeben.

Termin PVL, 1. Teil: Montag, 16.12.2024 ab 13:45 h. 2. Teil: Montag, 13.1.2025 ab 13:45 h.

Algorithmik

Inhalte:

• Landau-Symbole, Laufzeitanalyse.
• Suchverfahren: Binäre Suche, Suchbäume, Hashing, Skipliste, Suffix-Bäume, kd-Bäume.
• Sortierverfahren: Theoretische Laufzeitschranke, Quicksort, Mergesort, Heapsort, Bucketsort.
• Dynamische Programmierung: Editierdistanz, längste gemeinsame Teilfolge, Rucksackproblem, TSP, Viterbi-Algorithmus.
• Greedy-Algorithmen: Bruchteil-Rucksackproblem, Huffman-Kompression, Union-Find-Datenstruktur, Kruskal-Algorithmus.

Literatur:

• Schöning: Algorithmik.
• Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung.
• Jurafsky, Martin: Speech and Language Processing.