Formale Grundlagen der Informatik

4 SWS Seminaristischer Unterricht und 2 SWS Praktikum

Gesamtaufwand: 240 Zeitstunden, davon ca. 70 Stunden Kontaktzeit

• Matrizenrechnung (s. z.B. Lineare Algebra)
• vollständige Induktion
• Grundlegende Programmierkenntnisse in einer imperativen Programmiersprache

Die Studierenden erwerben die mathematisch-logischen und formalen Grundlagen der Informatik. Sie sind in der Lage, diskrete Sachverhalte formal zu modellieren, die Gültigkeit von Aussagen logisch abzuleiten und grundlegende Berechnungsmodelle anzuwenden, um die prinzipielle Lösbarkeit und die theoretischen Grenzen von Problemen zu beurteilen. Sie sind in der Lage,

• Sachverhalte in der Sprache und mit diskreten Modellen (Relationen, Graphen, Rekursionen, Permutationen, Kombinatorik u.a. ) zu formulieren (Modellbildungskompetenz)
• Lösungsverfahren für Probleme in solchen Modellen auszuwählen, und sie sicher, formal korrekt und kreativ auch im Programmierkontext einzusetzen,
• den Wahrheitsgehalt formaler Aussagen zu beurteilen und mithilfe geeigneter Beweisstrategien argumentativ zu belegen oder zu widerlegen,
• zahlentheoretische Grundlagen anzuwenden, um die Korrektheit und Funktionsweise elementarer Verfahren aus der Codierung nachzuvollziehen und zu überprüfen,
• formale Sprachen als Grammatik darzustellen, in die Chomsky-Hierarchie einzuordnen und akzeptierende Automaten- oder Maschinenbeschreibungen zu entwerfen,
• funktionale Berechnungsmodelle wie das Lambda-Kalkül zur formalen Auswertung anzuwenden und Lösungsverfahren in einer funktionalen Programmiersprache zu implementieren und
• ausgewählte Entscheidungsprobleme mit den Grundbegriffen der Berechenbarkeit und Komplexität einzuordnen, z.B. aus der Graphentheorie und Kombinatorik.

Das Modul führt in die diskreten mathematisch-logischen und formalen Grundlagen der Informatik ein:

• Grundlagen der Aussagenlogik und elementare Beweistechniken (z.B. Widerspruchsbeweise, Induktion)
• Mengen, Relationen und Operationen auf ihnen (Definition, Darstellungsformen, Relationen: Eigenschaften, Äquivalenz- und Ordnungsrelationen, Bezug zu relationalen Datenbankmodellen)
• Kombinatorik (Bijektions- Produkt und Summenregel, mit/ohne Wiederholung, mit/ohne Beachtung der Reihenfolge, Kombinationen der Typen zur Aufgabenlösung, Schubfachprinzip)
• Grundbegriffe der Graphentheorie (Darstellung, Typen, Isomorphie, Euler- und Hamiltonkreise, Bäume, planare Graphen, Färbungen, Matchings)
• Zahlentheorie und Codierung (Teilbarkeit, Primzahlen, (erweiterter) Euklidischer Algorithmus, Modulo-Arithmetik, Restklassenringe und endliche Körper)
• Rekursionen (Modellierung, Lösung linearer Rekursionen mit konstanten Koeffizienten)
• Formale Sprachen, Chomsky-Hierarchie und entsprechende Berechnungsmodelle (Deterministische und nichtdeterministische Endliche Automaten, Turing-Maschinen)
• Lambda-Kalkül und Konzepte der funktionalen Programmierung (z.B. Typinferenz) als zu den maschinenbasierten Modellen alternative Grundlage der Informatik und Programmierung
• Entscheidbarkeit, Berechenbarkeit und NP-Vollständigkeit von Problemen, Church-These und Reduktionsbeweise

Folien, Skript, Tafel, Beamer, Just in Time Teaching, Peer Instruction, Livecoding, Praktische Übungen

Standardlehrbücher der Diskreten Mathematik, der theoretischen Informatik und funktionalen Programmierung, z.B.:

• Haftendorn, Mathematik sehen und verstehen, Springer
• Beutelspacher, Diskrete Mathematik für Einsteiger, Vieweg
• Teschl, Mathematik für Informatiker, Bd.1, Springer
• Hopcroft, Ulmann: Einführung in die Automatentheorie, formale Sprachen und Komplexität
• David Thrane Christiansen: Functional Programming in Lean
• Greg Michaelson: An Introduction to Functional Programming Through Lambda Calculus