Complex Algorithms A

Organisationseinheit
Freie Universität Berlin/Mathematik und Informatik

Bereich

Fachliche Angebote
Informatik
Bereich Scientific Computing

Zugangsvoraussetzungen

Keine

Qualifikationsziele

Die Studentinnen und Studenten beherrschen grundlegende Kenntnisse der 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 haben ein Grundlegendes Verständnis der Theorie der NP-Vollständigkeit. Sie kennen die gängigen Komplexitätsklassen und können einfache Probleme in ihrer Komplexität einordnen. Sie vertiefen diese Fähigkeiten selbstständig in einem ausgewählten Themengebiet der höheren Informatik. Die Studentinnen und Studenten können Komplexere Algorithmen auf eines der folgenden Themen anwenden: Verteilte Systeme, Mustererkennung, Datenbanktechnologie oder Künstliche Intelligenz.

Inhalte

Es werden Aspekte folgender Themen behandelt: 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. Diese werden anschließend exemplarisch vertieft bearbeitet. Es stehen folgenden Themen zur Verfügung:

Verteilte Systeme, Verteilte Algorithmen, Verteilte Datenverwaltung, Suchverfahren für die Lösung kombinatorischer Aufgaben,
Prädikatenlogik und ihre Mechanisierung, Resolution und Theorembeweise, wissensbasierte und Expertensysteme, Diffuse Logik,
Baye’sche Verfahren der Mustererkennung, Clustering, Expectation-Maximization, Neuronale Netze und Lernalgorithmen, Assoziative Netze, Rekurrente Netze. Computer-Vision mit neuronalen Netzen,
Datenbank-Zugriffstechniken und Anfrageoptimierung, Realisierung von Transaktionen, insbesondere Synchronisationsverfahren, die technische, Maßnahmen, die Datenbanksysteme fehlertolerant machen. Verfahren zur effizienten Verwaltung andersartiger großer Datenbestände, insbesondere von XML-Dokumenten, korrekte Implementierung transaktionaler Garantien in Datenverwaltungssystemen.

Lehr- und Lernformen

Aktive Teilnahme

Vorlesung
4 SWS
Teilnahme empfohlen

schriftliche Bearbeitung der Übungsblätter
zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung Ausarbeitung und Präsentation eines Forschungsthemas

Übung
2 SWS
Teilnahme empfohlen

schriftliche Bearbeitung der Übungsblätter
zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung Ausarbeitung und Präsentation eines Forschungsthemas

Seminar
2 SWS
Teilnahme empfohlen

schriftliche Bearbeitung der Übungsblätter
zwei mündliche Präsentationen der Lösung jeweils einer Übungsaufgabe in der Übung Ausarbeitung und Präsentation eines Forschungsthemas

Aufwand

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

Modulprüfung
Klausur (90 Minuten), die auch in Form einer elektronischen Prüfungsleisoder Hausarbeit (ca. 15 Seiten);

Differenzierte Bewertung
nicht differenzierte Bewertung

Modulsprache
Deutsch

Arbeitsaufwand (Stunden)
450

Leistungspunkte (LP)
15

Dauer des Moduls
Ein oder zwei Semester

Häufigkeit des Angebots
Mindestens einmal im Studienjahr

Verwendbarkeit

Masterstudiengang Computational Sciences