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

Vorlesungsunterlagen und Termine für die PVL finden Sie in Moodle 

Algorithmik

Inhalte:

• Landau-Symbole, Laufzeitanalyse.
• Suchverfahren: Binäre Suche, Suchbäume, Hashing, Skipliste, 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.

Die Lehrmaterialien finden Sie in Moodle ilagos.informatik.htw-dresden.de/login/index.php.

Literatur:

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