Algorithmen und Datenstrukturen

Organisationseinheit
Freie Universität Berlin/Mathematik und Informatik/Informatik

Bereich

Pflichtbereich

Zugangsvoraussetzungen

Keine

Qualifikationsziele

Die Studierenden analysieren Algorithmen und Datenstrukturen und ihre Implementierungen bezüglich Laufzeit, Speicherbedarf und Korrektheit und beschreiben verschiedene Algorithmen und Datenstrukturen für typische Anwendungen und wenden diese auf konkrete Beispiele an. Sie können passende Algorithmen und Datenstrukturen für gegebene Aufgaben auswählen und passen diese entsprechend an. Sie erklären, identifizieren und verwenden verschiedene Entwurfsparadigmen für Algorithmen.

Inhalte

Studierende lernen das Maschinenmodell, sowie verschiedene algorithmische Probleme kennen. Sie erarbeiten und üben die Berechnung von Laufzeit, Korrektheit und Speicherbedarf dieser Algorithmen und lernen die asymptotische worst-case Analyse kennen. Darüber hinaus diskutieren sie die Rolle des Zufalls im Kontext des Entwurfs von Algorithmen. Des Weiteren erlernen und üben sie Entwurfsparadigmen für Algorithmen wie Teile und Herrsche, gierige Algorithmen, Dynamische Programmierung und Erschöpfende Suche. Sie lernen Prioritätswarteschlangen und effiziente Datenstrukturen für geordnete und ungeordnete Wörterbücher (z. B. ausgeglichene Suchbäume, Streuspeicher, Skiplisten) kennen und üben den Umgang mit ihnen. Zudem lernen sie Algorithmen für Zeichenketten (digitale Suchbäume und Suchen in Zeichenketten) und Graphenalgorithmen kennen, diskutieren deren Anwendung und üben den Umgang mit ihnen.

Lehr- und Lernformen

Aktive Teilnahme

Vorlesung
4 SWS
Teilnahme empfohlen

-

Übung
2 SWS
verpflichtete Teilnahme

Schriftliche Bearbeitung von Übungsaufgaben. Moderation einer Übung oder eines Teils davon.

Aufwand

Präsenzzeit V	60 Stunden
Vor- und Nachbereitung V	30 Stunden
Präsenzzeit Ü	30 Stunden
Vor- und Nachbereitung Ü	120 Stunden
Prüfungsvorbereitung und Prüfung	30 Stunden

Modulprüfung
Mündliche Prüfung (ca. 20 Minuten) oder Klausur (90 Minuten); die Klausur kann auch in Form einer elektronischen Prüfungsleistung (90 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 Sommersemester

Verwendbarkeit

Bachelorstudiengang Informatik, Bachelorstudiengang Informatik für das Lehramt, Bachelorstudiengang Bioinformatik, Einführungs- und Orientierungsstudium, 30-Leistungspunkte-Modulangebot Informatik im Rahmen anderer Studiengänge, 60-Leistungspunkte-Modulangebot Informatik im Rahmen anderer Studiengänge, Masterstudiengang für das Lehramt an Integrierten Sekundarschulen und Gymnasien mit dem Profil Quereinstieg, Masterstudiengang Wirtschaftsinformatik, Masterstudiengang Computational Sciences