[IAD] - [de] - [Algorithmen und Datenstrukturen]


Algorithmen und Datenstrukturen [2017/18 Winter]
Code
IAD
Name
Algorithmen und Datenstrukturen
Leistungspunkte
8 LP
Dauer
ein Semester
Turnus
jedes Sommersemester
Lehrform
Vorlesung 4 SWS, Übung 2 SWS
Arbeitsaufwand
240 h; davon
90 h Präsenzstudium
15 h Prüfungsvorbereitung
135 h Selbststudium und Aufgabenbearbeitung (eventuell in Gruppen)
Verwendbarkeit
B.Sc. Angewandte Informatik,
Lehramt Informatik
Lernziel Die Studierenden sind mit den wichigsten Datenstrukturen der Informatik vertraut,
kennen die Methoden zur Analyse der Laufzeit von Algorithmen,
sind mit den Basisproblemen Sortieren und Suchen vertraut und kennen die abhängig von der konkreten Anwendung besten Algorithmen,
kennen Datenstrukturen für Graphen und können elementare Probleme auf Graphen lösen,
haben die Methoden zur Suche von Textmustern gelernt,
sind in der Lage, den Schwierigkeitsgrad von Problemen 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-, Selection-, Quick-, Heap-, Merge-Sort, Sortieren ohne Schlüsselvergleiche)
Manipulation von Mengen (Prioritätswarteschlangen, Systeme von disjunkten Mengen)
Suchen (Medianproblem, lineare Listen, Suchbäume)
Hash-Verfahren (Hashing mit Verkettung, offenes Hashing, Analyse von Kollisionen)
Einfache Graphenalgorithmen (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)
Prüfungs
modalitäten
Erfolgreiche Teilnahme an den Übungen (mehr als 50% der Punkte müssen erreicht werden) und erfolgreiche Teilnahme an einer schriftlichen Prüfung
Literatur z. B.:
Sedgewick, R.: Algorithmen, Pearson, 2002
Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms, MIT press, 2001
Kleinberg J., Tardos, E.: Algorithm Design, 2005