11450 - Effiziente Algorithmen Modulübersicht

Modulnummer: 11450
Modultitel:Effiziente Algorithmen
  Efficient Algorithms
Einrichtung: Fakultät 1 - MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik
Verantwortlich:
  • Prof. Dr. rer. nat. habil Meer, Klaus
Lehr- und Prüfungssprache:Deutsch
Dauer:1 Semester
Angebotsturnus: jedes Sommersemester ungerader Jahre
Leistungspunkte: 8
Lernziele:Ein zentraler Aspekt bei der algorithmischen Behandlung von Problemen in der Informatik ist die Effizienz. Wie schnell bzw. kostengünstig lässt sich ein Problem lösen? Dabei wesentlich sind die Auswahl geeigneter Datenstrukturen sowie der zugehörige Algorithmenentwurf. Anschließend daran ist eine Problem- und Algorithmenanalyse unerlässlich, bei denen Korrektheit und Effizienz der verwendeten Methoden untersucht werden.

In der Vorlesung werden wichtige Klassen von Algorithmen vorgestellt und analysiert. Die Studierenden sollen ein vertieftes Verständnis erlangen, welche Datenstrukturen für welche Fragestellungen geeignet sind. Sie sollen einen elementaren Fundus an algorithmischen Techniken erlernen, effiziente Verfahren zu entwerfen und zu analysieren. Schließlich sollen die Grenzen dieser Techniken ausgelotet werden.
Inhalte:In dieser einführenden Veranstaltung werden unterschiedliche Typen von Algorithmen und die ihnen zugrunde liegenden Datenstrukturen und Strategien untersucht. Von Bedeutung sind hierbei Korrektheitsbeweise, die Aufwandsanalyse der Algorithmen sowie der Nachweis oberer und unterer Schranken für die Laufzeit von Lösungsverfahren.
Folgende Themen werden behandelt:
  • die algorithmischen Techniken Greedy, Divide - and - Conquer, dynamische Programmierung
  • Methoden der Aufwandsanalyse, Rekursionsgleichungen
  • obere und untere Laufzeitschranken
  • Graphenalgorithmen: Tiefensuche, Breitensuche, kürzeste Wege, aufspannende Bäume
  • Sortierverfahren
  • Suchverfahren
  • elementare algebraische Algorithmen: Euklidischer Algorithmus, Chinesischer Restklassensatz, diskrete Fouriertransformation, Matrizenmultiplikation
Empfohlene Voraussetzungen:Kenntnis im Umgang mit elementarer Analyse der Laufzeit von Algorithmen, zum Beispiel Kenntnis des Stoffes von Modul
  • 12101: Algorithmieren und Programmieren oder
  • 12868: Algorithmische Diskrete Mathematik
Zwingende Voraussetzungen:keine
Lehrformen und Arbeitsumfang:
  • Vorlesung / 4 SWS
  • Übung / 2 SWS
  • Selbststudium / 150 Stunden
Unterrichtsmaterialien und Literaturhinweise:
  • T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, McGraw & Hill, 2nd Edition, 2002
  • K. Mehlhorn: Datenstrukturen und effiziente Algorithmen, 3 Bände, Teubner 1988 (englische Version: Data Structures and Algorithms)
  • V. Heun: Grundlegende Algorithmen, 2. Auflage, Vieweg, 2003
  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, 3. Auflage, Spektrum Akademischer Verlag 1996
Modulprüfung:Modulabschlussprüfung (MAP)
Prüfungsleistung/en für Modulprüfung:
  • mündliche Prüfung, 30-45 Minuten
Bewertung der Modulprüfung:Prüfungsleistung - benotet
Teilnehmerbeschränkung:keine
Zuordnung zu Studiengängen:
  • M.Sc. / Angewandte Mathematik (universitäres Profil) / Prüfungsordnung 2008
  • M.Sc. / Angewandte Mathematik (universitäres Profil) / Prüfungsordnung 2019
  • B.Sc. / Informatik (universitäres Profil) / Prüfungsordnung 2008 - 1. SÄ 2017
  • M.Sc. / Informations- und Medientechnik (universitäres Profil) / Prüfungsordnung 2008
  • M.Sc. / Informations- und Medientechnik (universitäres Profil) / Prüfungsordnung 2017
  • M.Sc. / Wirtschaftsingenieurwesen (universitäres Profil) / Prüfungsordnung 2008
Bemerkungen:
  • Studiengang Informatik B.Sc.: Wahlpflichtmodul in Komplex „Grundlagen der Informatik“ (Niveaustufe 300)
  • Studiengang Informations- und Medientechnik M.Sc.: Wahlpflichtmodul im Komplex „Methodische Grundlagen"
  • Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Anwendungen“,  Bereich „Informatik“
Veranstaltungen zum Modul:Vorlesung: Effiziente Algorithmen
Übung zur Vorlesung
Veranstaltungen im aktuellen Semester:
  • keine Zuordnung vorhanden

Unsere Webseite verwendet Cookies. Diese haben zwei Funktionen: Zum einen sind sie erforderlich für die grundlegende Funktionalität unserer Website. Zum anderen können wir mit Hilfe der Cookies unsere Inhalte für Sie immer weiter verbessern. Hierzu werden pseudonymisierte Daten von Website-Besuchern gesammelt und ausgewertet. Das Einverständnis in die Verwendung der technisch nicht notwendigen Cookies können Sie jeder Zeit wiederrufen. Weitere Informationen erhalten Sie auf unseren Seiten zum Datenschutz.

Erforderlich

Diese Cookies werden für eine reibungslose Funktion unserer Website benötigt.

Statistik

Für den Zweck der Statistik betreiben wir die Plattform Matomo, auf der mittels pseudonymisierter Daten von Websitenutzern der Nutzerfluss analysiert und beurteilt werden kann. Dies gibt uns die Möglichkeit Websiteinhalte zu optimieren.

Name Zweck Ablauf Typ Anbieter
_pk_id Wird verwendet, um ein paar Details über den Benutzer wie die eindeutige Besucher-ID zu speichern. 13 Monate HTML Matomo
_pk_ref Wird benutzt, um die Informationen der Herkunftswebsite des Benutzers zu speichern. 6 Monate HTML Matomo
_pk_ses Kurzzeitiges Cookie, um vorübergehende Daten des Besuchs zu speichern. 30 Minuten HTML Matomo