Goals: Die Studierenden sind mit den wichtigsten Datenstrukturen der Informatik vertraut, kennen die Methoden zur Analyse der Laufzeit von Algorithmen, sind mit den Basisproblem Sortieren und Suchen vertruat und kennen die abhängig von der konkreten Anweung besten Algorithmen, kennen Datenstrukturen für Graphen und können elementare Problem auf Graphen lösen, haben die Methoden zur Suche von Textmustern gelernt, sind in der Lage, der Schwierigkeitsgrad von Problem zu beurteilen.

Inhalt: Grundlagen zu Algorithmen (Eigenschaften, Darstellungsmöglichkeiten), Analyse der Laufzeit von Algorithmen (Lösen von Rekursionsgleichungen, amortisierte Komplexität), Grundlegende Datenstrukturen (Liste, Stack, Queue), Sortierverfahren (Insertion-, Selectin-, Quick-, Heap-, Merge-Sort, Sortieren ohne Schlüsselvergleiche), Manipulation von Mengen (Prioritätswarteschlangen, System von disjunkten Mengen), Suchen (Medianproblem, lineare Listen, Suchbäume), Hash-Verfahren (Hashing mit Verkettung, offenes Hashing, Analyse von Kollisionen), Einfache Graphalgorithmen (Speicherung von Graphen, Breitensuche, Tiefensuche, aufspannende Bäume, kürzeste Wege), Suchen in Texten (Suche nach Wörtern und Mustern, Tries), Komplexität (Turing-Maschinen, Klassen P und NP).

Voraussetzungen: empfohlen sind: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK)

Leistungspunkte: 8 LP

Dauer: ein Semester

Arbeitsaufwand: 240h; davon 90h Präsenzstudium, 15h Prüfungsvorbereitungen, 135h Selbstudium und Aufgabenbearbeitung

Vergabe der LP: Erfolgreiche Teilnahme an den Gruppenübungen und Bestehen der Modulprüfung

Verwendbarkeit:
B.Sc. Angewandte Informatik,
Lehramt Informatik