Inhalt
Die Komplexitätstheorie klassifiziert Berechnungsprobleme gemäss algorithmischen Ressourcen wie Berechnungszeit oder Speicherplatz, die zu ihrer Lösung benötigt werden. Ziel ist ein theoretisches Verständnis davon welche Berechnungsprobleme effiziente Algorithmen erlauben und welche nicht. Eine zentrale Rolle spielt die Klasse P der in polynomieller Zeit lösbaren Berechnungsprobleme. Das zentrale Problem ist das P versus NP Problem, eines der Millenniumsprobleme der Mathematik, und Smale zufolge eines der drei grössten offenen Probleme der Mathematik. Die Vorlesung bietet eine Einführung in dieses Problem und die es umgebende Theorie.
Auf StudIP findet sich ein wöchentlich aktualisiertes Skript des aktuellen Standes.
Vorlesungen
Dienstag 12:00-14:00 IM SR030
Mittwoch 10:00-12:00 IM HS12
Übungen von Johannes Heil
Donnerstag 10:00-12:00 JUR SR154
Literatur
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Das Oberseminar ist eine gemeinsame Veranstaltung mit Tobias Kaiser. Es beinhaltet Forschungsvorträge der Arbeitsgruppen und ihrer Gäste. Fortgeschrittene Studierende, die ihr Wissen in mathematischer Logik und/oder Komplexitätstheorie vertiefen wollen, können hier über ein gemeinsam gewähltes und gemeinsam erarbeitetes Thema vortragen.
Programm TBA
Modelltheorie = Logik + Algebra
Die Vorlesung bietet eine Einführung in die klassische Modelltheorie. Es wird eine breite Methodik vorgestellt um Theorien und ihre Modelle zu analysieren. Besondere Betonung finden Anwendungen und Beispiele, insbesondere aus der Algebra. Die Vorlesung beginnt mit einem Crashkurs in Mengenlehre und Arithmetik unendlicher Kardinalzahlen, behandelt die Theorie Boolescher Algebren, Ultraprodukte, die Back-and-Forth Methode, algebraische und elementare Diagramme, Realisierung und Auslassen von Typen, Quantorenelimination, und Anwendungen davon auf algebraisch abgeschlossene und reel abgeschlossene Körper, und beschreibt schliesslich Theorien mit nur einem abzählbaren Modell (bis auf Isomorphie).
Literatur
Chang, Keisler, Model theory, 3rd edition, North Holland, 1990.
Tent, Ziegler, A Course in Model Theory (Lecture Notes in Logic), Cambridge University Press, 2012.
Marker, Model Theory : An Introduction, Springer Graduate Texts in Mathematics 217, 2010. Here.
Die Vorlesung setzt die Vorlesung des letzten Semesters fort. Sie behandelt Gruppentheorie und Körpertheorie.
Auf StudIP gibt es ein ständig aktualisiertes Skript.
Vorlesung
Dienstags und Donnerstags 10:00-12:00 (JUR) SR 059
Übungen von Daniel Yoon
Montags 10:00-12:00 (WIWI) SR 027
Literatur
M. Artin, Algebra, Pearson, 2013 here
G. Fischer, Lehrbuch der Algebra, 2017 here
S. Bosch, Algebra, Springer, 2023 here
