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


Algorithmen und Datenstrukturen [2022 Sommer]
Code
IAD
Name
Algorithmen und Datenstrukturen
LP
8
Dauer
ein Semester
Angebotsturnus
jedes Sommersemester
Format
Vorlesung 4 SWS + Übung 2 SWS
Arbeitsaufwand
240 h; davon
90 h Präsenzstudium
15 h Prüfungsvorbereitung
135 h Selbststudium und Bearbeitung der Übungsaufgaben (eventuell in Gruppen)
Verwendbarkeit
B.Sc. Angewandte Informatik
B.Sc. Informatik
Lehramt Informatik
Sprache
deutsch
Lehrende
Christian Schulz
Prüfungsschema
1+1
Lernziele Die Studierenden sind mit den wichtigsten Datenstrukturen der Informatik vertraut, kennen die Methoden zur Analyse der Laufzeiten von Algorithmen, sind mit den Basisproblemen Sortieren und Suchen vertraut und kennen die abhängig von der konkreten Anwendung besten Algorithmen, kennen die 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.
Lerninhalte Grundlagen zu Algorithmen (Eigenschaften, Darstellungsmöglichkeiten)
Analyse der Laufzeit von Algorithmen (Lösen von Rekursionsgleichungen, amortisierte Komplexität)
Grundlegende Datenstrukturen (Liste, Stack, Queue)
Sortierverfahren (Insertionsort, Selectionsort, Quicksort, Heapsort, Mergesort, 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 Graphalgorithmen (Speicherung von Graphen, Breitensuche, Tiefensuche, aufspannende Bäume, kürzeste Wege)
Suche in Texten (Suche von Wörtern und Mustern, Tries)
Teilnahme-
voraus-
setzungen
empfohlen sind: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), und entweder Lineare Algebra 1 (MA4) oder Analysis 1 (MA1) oder Mathematik für Informatik (IMI1 oder IMI2)
Vergabe der LP und Modulendnote Das Modul wird mit einer benoteten Klausur abgeschlossen. Die Modulendnote wird durch die Note der Klausur festgelegt. Für die Vergabe der LP gilt die Regelung aus dem Kapitel Prüfungsmodalitäten, wobei zu den mindest. 50% der Punkte aus den Übungsaufgaben noch mindest. 25% der Punkte bei jedem Pflichtprogrammierblatt kommen.
Nützliche 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
Mehlhorn, K., Sanders, P.: Algorithms and Data Structures, The Basic Toolbox, Springer