Sommerkurs in mathematischen Grundlagen der Informatik

Sommerkurs in mathematischen Grundlagen der Informatik

Was sind die theoretischen Grenzen der Rechenleistung? Welche Probleme lassen sich mit Computern lösen? Welche können das nicht? Und wie können wir mit mathematischer Sicherheit über die Antworten auf diese Fragen nachdenken? Dieser Kurs untersucht die Antworten auf diese Fragen und dient als Einführung in die Diskrete Mathematik, Berechenbarkeitstheorie und Komplexitätstheorie. Nach Abschluss des Kurses fühlen sich die Studenten wohl dabei, mathematische Beweise zu schreiben, über diskrete Strukturen zu argumentieren, Aussagen in Logik erster Ordnung zu lesen und zu schreiben und mit mathematischen Modellen von Computergeräten zu arbeiten. Während des gesamten Kurses lernen die Studenten einige der aufregendsten mathematischen und philosophischen Ideen des späten neunzehnten und zwanzigsten Jahrhunderts kennen. Zu den spezifischen behandelten Themen gehören formales mathematisches Korrekturschreiben, Aussagenlogik und Logik erster Ordnung, Mengenlehre, binäre Beziehungen, Funktionen (Injektionen, Surjektionen und Bijektionen), Kardinalität, grundlegende Graphentheorie, das Schubfachprinzip, mathematische Induktion, endliche Automaten, reguläre Ausdrücke, das Myhill-Nerode-Theorem, kontextfreie Grammatiken, Turing-Maschinen, entscheidbare und erkennbare Sprachen, Selbstreferenz und Unentscheidbarkeit, Verifizierer und die Frage P versus NP. Studenten mit erheblicher Erfahrung im Korrekturschreiben werden ermutigt, stattdessen CS154 zu belegen. Studenten, die an zusätzlicher Übung und Unterstützung im Kurs interessiert sind, werden ermutigt, sich gleichzeitig für CS103A anzumelden. Voraussetzung: CS106B oder gleichwertig. CS106B kann gleichzeitig mit CS103 eingenommen werden.