Vorlesungen
Wird jeden Sommer angeboten, abwechselnd mit T. Kaiser.
Inhalt
Die mathematische Logik geht auf Gottlob Freges Begriffsschrift 1879 zurück und wurde vorangetrieben durch David Hilberts Programm im Zuge der sogenannten Grundlagenkrise der Mathematik zu Anfang des 20. Jahrhundert. Seither hat sie sich zu einer eigenständigen mathematischen Disziplin entwickelt, mit weitreichenden Verknüpfungen zu anderen Gebieten der Mathematik und insbesondere der theoretischen Informatik. Zu den grössten Errungenschaften der mathematischen Logik, und der Mathematik des 20. Jahrhunderts überhaupt, gehören Alan Turings formale Definition des Berechenbarkeitsbegriffes 1936 und Kurt Gödels Beweis der Unmöglichkeit von Hilberts Programm, nämlich seine Unvollständigkeitssätze 1931. Die Vorlesung bietet eine Einführung in die mathematische Logik, insbesondere in die Berechenbarkeitstheorie und die Unvollständigkeitssätze.
Inhaltsverzeichnis
Evaluation
Literatur
Ziegler, Mathematische Logik, Birkhäuser, 2010, Springer
Ziegler, Vorlesungsskript
Ebbinghaus, Flum, Thomas, Mathematical Logic, 1994 Springer
Ebbinghaus, Flum, Thomas, Einführung in die mathematische Logik, 2018, Springer
Shoenfield, Mathematical Logic, Addison-Wesley, 1967
Wird jeden Winter angeboten, abwechselnd mit T. Kaiser
Inhalt
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).
Evaluation
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.
Inhalt
Die Vorlesung behandelt Schaltkreiskomplexität. Boolesche Schaltkreise sind Modell paralleler Berechnungen: die Grösse eines Schaltkreises modelliert die Gesamtarbeit eines solchen Algorithmus', seine Tiefe die parallele Berechnungszeit. Die Vorlesung hat zwei Teile. Der Teil über obere Schranken behandelt parallele Algorithmik und insbesondere Addition, Multiplikation und Division. Wir werden im zweiten Teil zu unteren Schranken sehen, dass Multiplikation in einem präzisen Sinn härter ist als Addition. Dort behandeln wir Andreev's untere Schranke an die Grösse von Formeln, Hastad's Switching Lemma und exponentielle untere Schranken an Schaltkreise konstanter Tiefe, Razborov und Smolenskys exponentielle untere Schranke an die Grösse solcher Schaltkreise mit mod p Zählgattern, und Ratzborovs untere Schranke an monotone Schaltkreise. Die Vorlesung setzt elementare Kenntnisse in Algebra und Zahlentheorie voraus.
Inhaltsverzeichnis
Literatur
Jukna, Boolean Function Complexity Springer
Arora, Barak, Computational Complexity: A Modern Approach,CUP, Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer
Håstad, Wegener, Wurm, Yi. Optimal depth, very small size circuit for symmetric functions in AC0. Here
Bei einem Constraint Satisfaction Problem (CSP) geht es darum, zu entscheiden, ob es eine Zuordnung zu gegebenen Variablen gibt, die sich über einen bestimmten Bereich erstrecken und eine gegebene Menge von Beschränkungen erfüllen. Äquivalent dazu wird nach einem Homomorphismus zwischen gegebenen Strukturen gefragt. Ein berühmtes Beispiel ist das Erfüllbarkeitsproblem für den booleschen Bereich (SAT).
Die Geschichte der CSPs begann vor 50 Jahren, und in den letzten 25 Jahren spielen CSPs in der gesamten Informatik eine wichtige Rolle. Einerseits erlauben sie es, eine Vielzahl von kombinatorischen Problemen (in der Mathematik, Informatik, künstlichen Intelligenz...) auf natürliche und treue Weise zu modellieren. Andererseits sind sie mit allgemeinen algorithmischen Techniken für ihre Lösung oder allgemeinen Gründen für ihre Rechenhärte verbunden. Diese Techniken basieren auf der universellen Algebra.
Der Kurs bietet eine Einführung in den algebraischen Ansatz für CSPs. Kenntnisse der universellen Algebra werden nicht vorausgesetzt, sondern nach Bedarf entwickelt. Auch Kenntnisse der mathematischen Logik werden nicht vorausgesetzt. Die Studierenden sollten jedoch über Grundkenntnisse der Computerkomplexität verfügen, z.B. auf dem Niveau der Theoretischen Informatik II. Die Vorlesung wird von Übungen begleitet. Die Veranstaltung wird in englischer Sprache durchgeführt und richtet sich an Masterstudierende. Details sind auf StudIP zu finden.
Übersetzt mit www.DeepL.com/Translator (kostenlose Version)
Wird jeden Winter angeboten.
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.
Evaluationen
Literatur
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Wird jedes Semester angeboten.
Das Oberseminar ist eine gemeinsame Veranstaltung mit dem Lehrstuhl für Reine Mathematik. 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.
Diese Seite teilen
