12458 - Algebraische Rechenmodelle Modulübersicht

Modulnummer: 12458
Modultitel:Algebraische Rechenmodelle
  Algebraic Computational Models
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 Wintersemester gerader Jahre
Leistungspunkte: 8
Lernziele:Kennenlernen und Verständnis von alternativen (zur Turingmaschine), Zugängen zu Berechenbarkeit und Komplexität.
Einblicke in die Bedeutung der Anwendung tiefliegender Methoden beim Entwurf und der Analyse von Algorithmen.
Inhalte:Eine Reihe algorithmischer Fragestellungen sind mit Hilfe des Modells der Turingmaschine nicht adäquat modellierbar. Dies gilt vor allem für Probleme, die überabzählbare Strukturen involvieren.
Die Vorlesung behandelt algebraische Rechenmodelle, mit deren Hilfe Algorithmen über Strukturen wie den reellen und den komplexen Zahlen formuliert und untersucht werden können. Solche Algorithmen sind beispielsweise Gegenstand in der berechenbaren Geometrie, der Computeralgebra oder der numerischen Mathematik.

Die Vorlesung gibt einen Einblick in algorithmische und methodische Fragen, die bei derartigen Modellen eine zentrale Rolle spielen. Im Einzelnen werden folgende Themen behandelt:
  • Algebraische Schaltkreise, das Berechnungsmodell von Blum-Shub-Smale
  • Reelle Komplexitätsklassen: P, NP, NP-Vollständigkeit über den reellen Zahlen
  • Nullstellenexistenz univariater Polynome: Satz von Sturm, Regel von Descartes
  • Systeme von Polynomgleichungen: Lösbarkeit über den reellen und den komplexen Zahlen
  • Sätze von Tarski, Lojasiewicz; zylindrische Dekomposition semi-algebraischer Mengen
  • Untere Schranken
  • Gröbnerbasen; Algorithmus von Buchberger
  • Diskrete Fouriertransformation
Empfohlene Voraussetzungen:Solide Kenntnisse über die Grundlagen der Theoretischen Informatik.
Zwingende Voraussetzungen:keine
Lehrformen und Arbeitsumfang:
  • Vorlesung / 4 SWS
  • Übung / 2 SWS
  • Selbststudium / 150 Stunden
Unterrichtsmaterialien und Literaturhinweise:
  • Blum, Cucker, Shub, Smale: Complexity and Real Computation, Springer, 1998
  • Bürgisser, Clausen, Shokrollahi: Algebraic Complexity Theory, Springer, 1997
Weitere Literatur wird während der Veranstaltung bekannt gegeben.
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
  • Abschluss im Ausland / Informatik / keine Prüfungsordnung
  • M.Sc. / Informatik (universitäres Profil) / Prüfungsordnung 2008
  • Abschluss im Ausland / Informations- und Medientechnik / keine Prüfungsordnung
  • M.Sc. / Informations- und Medientechnik (universitäres Profil) / Prüfungsordnung 2008
  • M.Sc. / Informations- und Medientechnik (universitäres Profil) / Prüfungsordnung 2017
  • B.Sc. / Mathematik (universitäres Profil) / Prüfungsordnung 2019
  • B.Sc. / Wirtschaftsmathematik (universitäres Profil) / Prüfungsordnung 2007
  • B.Sc. / Wirtschaftsmathematik (universitäres Profil) / Prüfungsordnung 2019
Bemerkungen:
  • Studiengang Informatik M.Sc.: Wahlpflichtmodul im Komplex „Grundlagen der Informatik“ (Niveaustufe 400)
  • Studiengang Informations- und Medientechnik M.Sc.: Wahlpflichtmodul im Komplex „Methodische Grundlagen“
  • Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Analysis / Algebra / Kombinatorik“
  • Studiengang Mathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung“, im begrenzten Umfang
  • Studiengang Wirtschaftsmathematik B.Sc.: Wahlpflichtmodul im Komplex „Vertiefung“, im begrenzten Umfang
Veranstaltungen zum Modul:
  • Vorlesung Algebraische Rechenmodelle
  • Übung zur Vorlesung
  • Zugehörige Prüfung
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