|
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: | -
Master (universitär) /
Angewandte Mathematik /
PO 2008
-
Master (universitär) /
Angewandte Mathematik /
PO 2019
-
Master (universitär) /
Artificial Intelligence /
PO 2022
-
Abschluss im Ausland /
Informatik /
keine PO
-
Master (universitär) /
Informatik /
PO 2008
- 2. SÄ 2017
-
Abschluss im Ausland /
Informations- und Medientechnik /
keine PO
-
Master (universitär) /
Künstliche Intelligenz Technologie /
PO 2022
-
Bachelor (universitär) /
Mathematik /
PO 2023
-
Bachelor (universitär) - Duales Studium, praxisintegrierend /
Mathematik - dual /
PO 2023
-
Bachelor (universitär) /
Wirtschaftsmathematik /
PO 2007
-
Bachelor (universitär) /
Wirtschaftsmathematik /
PO 2023
-
Bachelor (universitär) - Duales Studium, praxisintegrierend /
Wirtschaftsmathematik - dual /
PO 2023
|
| Bemerkungen: | - Studiengang Informatik M.Sc.: Wahlpflichtmodul im Komplex „Grundlagen der Informatik“ (Niveaustufe 400)
- 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: | |
