| Algorithmen und Datenstrukturen [2022/23 WiSe] | ||
|---|---|---|
| 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 |
|