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, 2. Teil: Montag, 15.1. um 11:10.

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.