Höhere Algorithmik

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

Bereich

Studienbereich Theoretische Informatik

Zugangsvoraussetzungen

Keine

Qualifikationsziele

Die Studentinnen und Studenten beherrschen die gängigen Entwurfstechniken für Algorithmen und können Algorithmen mit ihrer Hilfe entwerfen. Sie können Algorithmen in Bezug auf ihren Laufzeit- und Speicherbedarf analysieren und dabei auch fortgeschrittene Analysemethoden verwenden. Sie verstehen die Theorie der NP-Vollständigkeit. Sie kennen die gängigen Komplexitätsklassen und können einfache Probleme in ihrer Komplexität einordnen.

Inhalte

Es werden Themen wie:

Wege- und Flussprobleme in Graphen,
String-Matching,
randomisierte Algorithmen,
amortisierte Analyse,
das „Master-Theorem“ zur Analyse von teile-und-herrsche-Rekursionsgleichungen,
NP-Vollständigkeit,
Approximationsalgorithmen für schwere Probleme,
zahlentheoretische Algorithmen (einschließlich RSA-Kryptosystem),
Arithmetische Algorithmen und Schaltkreise sowie schnelle Fourier-Transformation behandelt.

Lehr- und Lernformen

Aktive Teilnahme

Vorlesung
4 SWS
Teilnahme empfohlen

Bearbeitung der Übungsblätter Zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung

Übung
2 SWS
Teilnahme empfohlen

Bearbeitung der Übungsblätter Zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung

Aufwand

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

Modulprüfung
Klausur (90 Minuten), die Klausur kann auch in Form einer elektronischen Prüfungsleistung (90 Minuten) durchgeführt werden, oder mündliche Prüfung (20 bis 25 Minuten)

Differenzierte Bewertung
differenzierte Bewertung

Modulsprache
Deutsch (ggf. Englisch)

Arbeitsaufwand (Stunden)
300

Leistungspunkte (LP)
10

Dauer des Moduls
Ein Semester

Häufigkeit des Angebots
Jedes Wintersemester

Verwendbarkeit

Masterstudiengang Informatik

Querverweis zu anderen Studien/Prüfungsordnungen mit dem gleichen Titel