Mathematische Grundlagen

Dieser Kurs ist eine Einführung in die Wahrscheinlichkeitsrechnung und Statistik im Hinblick auf ihre wesentliche Bedeutung für einige Teilgebiete der Informatik.

Zunächst lernen die Schüler Wahrscheinlichkeit anhand vielerlei anschaulicher Beispiele als mathematisches Konzept kennen. Darauf aufbauend führen wir weitere grundlegende Konzepte wie Erwartungswert, Standardabweichung, bedingte Wahrscheinlichkeiten, wichtige Wahrscheinlichkeitsverteilungen wie die Bernoulli- oder Poisson-Verteilung und die Maximum-Likelihood-Methode ein.

Anschließend wenden wir die neu gewonnen Erkenntnisse auf einige den Schülern schon bekannte Problemstellungen an. Insbesondere werden wir die erwartete Laufzeit einiger Algorithmen bestimmen sowie randomisierte, also bewusst von zufälligen Ereignissen abhängige, Algorithmen schreiben und die Vorteile dieser Technik verstehen.

Kenntnisse in linearer Algebra sind für viele informatische Themen unverzichtbar. In diesem Kurs erhalten die Teilnehmer eine Einführung in die wichtigsten Grundlagen. Dazu gehören:

• Vektoren
• Geraden und Ebenen
• Lineare Unabhängigkeit
• Matrizen
• Determinanten
• Eigenwerte

Die Teilnehmer gewinnen ein Verständnis für folgende Themen:

• Reguläre Ausdrücke
• Deterministische endliche Automaten
• Nichtdeterministische endliche Automaten
• Produktautomaten
• Die Potenzmengenkonstruktion
• Pushdown-Automaten
• Kontextfreie Grammatiken
• Kontextsensitive Grammatiken
• Die Thompsonkonstruktion

Im ersten Teil dieses Kurses lautet das Thema Komplexitätstheorie. Hier untersuchen wir, wie schnell und mit wie viel Speicherplatzverbrauch bestimmte Probleme grundsätzlich algorithmisch gelöst werden können, also unabhängig von einer konkreten Programmiersprache. Dazu führen wir die Turingmaschine als wichtigstes allgemeines Modell von Computern ein und können damit die Komplexitätsklassen P, PSPACE, NP und EXPTIME definieren und untersuchen. Anschließend lernen wir, wie ein algorithmisches Problem formal auf ein anderes zurückgeführt (reduziert) werden kann, was es uns noch ermöglicht, das berühmte P≟NP-Problem kennenzulernen.

Der zweite Teil behandelt mit der Berechenbarkeitstheorie die Frage danach, welche Probleme grundsätzlich algorithmisch lösbar (berechenbar) sind. Hierzu führen wir mit dem Halteproblem den Prototyp eines algorithmisch nicht lösbaren Problems ein. Anschließend beweisen wir mittels der im ersten Teil bereits kennengelernten Reduktionstechnik die Nichtberechenbarkeit einiger weiterer interessanter Probleme wie etwa des Postschen Korrespondenzproblems.

Dieser Kurs ist eine Einführung in die mathematische Logik. Dabei betrachten wir hauptsächlich die Aussagenlogik sowie die Prädikatenlogik erster Stufe genauer.

Die Teilnehmer werden die Syntax und Semantik dieser Logiken erlernen, und wie sie Sachverhalte mit diesen formalisieren. Danach gehen wir insbsondere auf Erfüllbarkeit, Resolution, den Sequenzenkalkül und Fragen der Definierbarkeit ein.

Nicht zuletzt nehmen wir uns in diesem Kurs auch die Zeit, nachzuvollziehen, welch maßgeblichen Einfluss die mathematischen Logik auf die geschichtliche Entwicklung der Informatik hatte.

In diesem Kurs werden die Schüler zwei Programmiersprachen kennenlernen, die sich deutlich von den ihnen bisher bekannten unterscheiden.

Einerseits die Sprache Haskell als den wichtigsten Vertreter funktionaler Programmiersprachen. Wir werden üben, Programme in dieser Sprache zu schreiben und sie auf ihre Vor- und Nachteile gegenüber imperativen Sprachen wie Python oder Java hin untersuchen. Insbesondere werden wir sehen, wieso diese Sprache für Big Data-Anwendungen so praktisch ist. Schließlich werden wir mit Scala noch eine Programmiersprache kennenlernen, die versucht, objektorientiertes mit funktionalem Programmieren zu vereinen, sowie die Java-Stream-API, mit der es möglich ist, innerhalb von Java funktionalen Code zu schreiben.

Als Zweites lernen wir die logische Programmiersprache Prolog kennen. Auch hier werden wir lernen, wie man Programme in dieser Sprache schreibt und wo dies gegenüber imperativen Sprachen von Vorteil und wo von Nachteil ist. Dann werden wir auch einige Beispiele sehen, wo Prolog sinnvoll in der Praxis eingesetzt wird.