Algorithmen, Datenstrukturen und Datenabstraktion
| Algorithmen, Datenstrukturen und Datenabstraktion | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Organisationseinheit Freie Universität Berlin/Mathematik und Informatik/Informatik |
|||||||||||
| Ursprung Dies ist ein Verweis auf den Eintrag in inf_bsc_2014 (Algorithmen, Datenstrukturen und Datenabstraktion) |
|||||||||||
Bereich
|
|||||||||||
| Zugangsvoraussetzungen Keine |
|||||||||||
| Qualifikationsziele Studentinnen und Studenten können die Grundbegriffe der Algorithmik definieren. Sie wissen, was ein abstrakter Datentyp ist, und verstehen den Unterschied zwischen Spezifikation und Implementierung. Sie kennen die wichtigsten abstrakten Datentypen und die Datenstrukturen zu deren Implementierung und können diese in Bezug auf ihre Eigenschaften beurteilen und geeignet auswählen und einsetzen. Sie können die Korrektheit von Algorithmen nachweisen und die asymptotische Laufzeit von Algorithmen bestimmen. Sie kennen die Definition und verstehen die praktische Bedeutung von NP-Vollständigkeit für die effiziente Lösbarkeit von Problemen. |
|||||||||||
| Inhalte Die grundlegenden Datenstrukturen Listen, Schlangen, Keller, Bäume; Sortierverfahren (Mergesort, Quicksort, u. a.), Suchverfahren, Auswahlverfahren; Abstrakte Datentypen Prioritätswarteschlange und Wörterbuch und zugehörige Datenstrukturen wie Heaps, Hashtabellen, binäre Suchbäume, B-Bäume u. a.; Algorithmen auf Graphen wie Breiten- und Tiefensuche, topologisches Sortieren, kürzeste Spannbäume, kürzeste Wege; Algorithmen für Zeichenketten; Speicherverwaltung; Allgemeine Lösungsstrategien wie Teile und Herrsche, dynamische Programmierung, Auswählen und Abschneiden, gierige Algorithmen. Mathematische Analyse von Algorithmen bezüglich Laufzeit und Speicherplatz. NP-Vollständigkeit. |
|||||||||||
| Lehr- und Lernformen | Aktive Teilnahme | ||||||||||
| Vorlesung 4 SWS Teilnahme empfohlen |
- |
||||||||||
| Übung 2 SWS verpflichtete Teilnahme |
Schriftliche Bearbeitung der Übungsblätter, zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung |
||||||||||
Aufwand
|
|||||||||||
| Modulprüfung Klausur (120 Minuten); die Klausur kann auch in Form einer elektronischen Prüfungsleistung (120 Minuten) durchgeführt werden. |
|||||||||||
| Differenzierte Bewertung differenzierte Bewertung |
|||||||||||
| Modulsprache Deutsch |
|||||||||||
| Arbeitsaufwand (Stunden) 270 |
|||||||||||
| Leistungspunkte (LP) 9 |
|||||||||||
| Dauer des Moduls Ein Semester |
|||||||||||
| Häufigkeit des Angebots Jedes Wintersemester |
|||||||||||
| Verwendbarkeit Bachelorstudiengang Informatik, Bachelorstudiengang Informatik für das Lehramt |
|||||||||||
| Querverweis zu anderen Studien/Prüfungsordnungen mit dem gleichen Titel |
|||||||||||