Einleitung

Dieses Skript dient als Begleitmaterial zum Praktikum „Angewandte Mathematik am Rechner“, welches Teil des Grundstudiums im Fach Informatik an der JGU Mainz ist. Das Praktikum läuft parallel zu den grundlegenden Mathematikvorlesungen im Informatikstudium und hat den Zweck, eine Brücke zwischen der Mathematik und ihrer Anwendung in der Informatik zu schlagen.

Motivation

Mathematische Modelle sind ein wesentlicher Bestandteil aller modernen Natur- und Ingenieurswissenschaften, und die Informatik ist hier keine Ausnahme. Vor allem, wenn es darum geht, neue Verfahren zu erforschen und entwickeln, um schwere, bislang ungelöste Probleme in den Griff zu bekommen, spielen mathematische Abstraktionen fast immer eine Schlüsselrolle. Solide Kenntnisse von mathematischen Modellierungstechniken bilden dann die entscheidende Voraussetzung für den Erfolg.

Eine Anekdote aus der Praxis — PageRank

Vorwarnung: Viele der mathematischen Begriffe, die in diesem Beispiel auftauchen, sind dieser Stelle sicher noch eher mysteriös — wir werden aber im Laufe der nächsten beiden Semester einiges davon näher kennenlernen. Das folgende Beispiel ist nur ein Teaser:
Google's Page Rank
Es gibt eine ganze Menge an prominenten Errungenschaften der modernen Informationstechnik, die im Kern auf cleveren „nicht-trivialen“ mathematischen Modellen beruhen. Während die viele dieser Dinge breit bekannt sind, ist die Mathematik dahinter oft auch in IT-affinen Personenkreisen nicht weniger bekannt (auch wenn die Grundidee gar nicht so kompliziert ist, und das ist sie fast nie).
Ein Klassiker — geradezu ein Paradebeispiel dafür, daß mathematische Analysen nicht nur eine reine akademische Spielerei sind — ist sicher „PageRank“, der ursprüngliche Suchalgorithmus von Google™. Die älteren unter uns werden sich noch an die Zeiten vor Google erinnern — es war eher Glückssache, im Internet die Dinge zu finden, die uns eigentlich interessieren. Die Google-Suche, die dies fundamental verbesserte, basierte (am Anfang — inzwischen ist natürlich noch viel weiterentwickelt worden, und nicht alle Details sind öffentlich bekannt) auf dem PageRank Algorithmus.}
Idee des Algorithmus
Die Kernidee des Algorithmus war es, die Wichtigkeit von Internetseiten anhand der Vernetzungsstruktur des WWWs zu bewerten. Genauer gesagt: Wenn es wahrscheinlich ist, bei einer zufälligen Wanderung durch das Netz (einem „random Walk“) auf die Seite zu stoßen, dann handelt es sich um eine interessantere Quelle. Das ganze läßt sich als Eigenwertproblem großer Matrizen (also 2D Arrays von Zahlen; Eigenwerte treten auf, wenn man Matrizen wiederholt multipliziert) formalisieren (die Zeilen und Spalten entsprechen den Webseiten, wenn ein Link besteht, steht an der entsprechenden Stelle eine 1, sonst eine 0). Aus der Numerik ist bekannt, daß man solche extrem großen Matrizen (\(n \times n\) Einträge, wobei \(n\) die Anzahl aller Webseiten auf der Welt ist) effizient repräsentieren kann, indem man schlicht die Nulleinträge nicht speichert. Danach wird der Eigenvektor zum dominanten Eigenwert durch wiederholtes multiplizieren dieser dünnbesetzten Matrix mit sich selbst berechnet, was sich relativ leicht mit Hilfe eines MapReduce-Algorithmus auf einem Cluster von PCs implementieren kann.}
Impact
Der Effekt für die Praxis ist bis heute spürbar — starke Suchmaschinen sind aus dem modernen Leben gar nicht mehr wegzudenken, und das wiederum wäre nicht möglich gewesen, ohne Methoden aus der höheren Mathematik. Im Prinzip wurden nur grundlegende Konzepte aus der linearer Algebra (Eigenwerte), Statistik (Markov-Kette / Random Walks) und Numerik (Dünnbesetzte lineare Probleme) verwendet; alles dies ist kein Hexenwerk. Diese Grundlagen gut verstanden zu haben ist aber Voraussetzung, um solche Entwicklungen vollziehen zu können. Nebenbei bemerkt: Die Informatik als Disziplin war hier natürlich nicht unbeteiligt — ohne die parallele Algorithmen auf großen verteilten Systemen hätte es natürlich auch nicht funktioniert. Der Durchbruch wurde durch den interdisziplinären Ansatz (moderne Mathematik und Informatik) ermöglicht.}

Leider ist die höhere Mathematik, die an der Universität unterrichtet wird, leider oft als unanschaulich und praxisfern verschrieen. Viele Studierende geben in diesem Gebiet frühzeitig auf, und später im Studium und Beruf fehlt es dann an methodischen Grundlagen, falls doch einmal die richtig komplizierten Probleme auftauchen (in den ersten Semestern erscheint das alles weit weg — man ist ja erstmal sehr froh, die grundlegenden Techniken von Programmieren und Softwareentwicklung zu erlernen; Lücken in der Mathmatik rächen sich erst viel später).

Da müssen wir etwas tun! Wenn das Problem ist, daß die Mathematik unanschaulich und praxisfern erscheint, dann ist eine mögliche Lösung, praktische und anschauliche Beispiel zu erarbeiten, um dieser Wahrnehmung entgegenzuwirken. Machen wir das: Das Praktikum „Angewandte Mathematik am Rechner “ und das hier vorliegende, dazugehörige Skript sollen dazu beitragen, die mathematischen Modelle besser zu verstehen. Dazu schauen wir uns einige Aspekte an, die im klassischen Kanon der mathematischen Gundausbildung oft etwas zu kurz kommen:

Anschauung: In der reinen Mathematik werden in der Regel vor allem abstrakte, logische Strukturen betrachtet. Oft wird weitgehend darauf verzichtet, anschauliche Beispiele und Analogien zum Verständnis heranzuziehen. Für Studierende einer stärker anwendungsorientierten Disziplin wie der Informatik ist dies eine zusätzliche Hürde, die nicht selten demotivierend wirken kann. Wir schauen uns daher in dieser Veranstaltung wann immer möglich anschauliche, bildliche Beispiele und Analogien für die mathematischen Modelle an. Hierzu verwenden wir vor allem Methoden aus der Computer Graphik), um dies direkt am Rechner umsetzen zu können. Aus Gründen der Einfachheit beschränken wir uns auf 2D Computer Graphik.

Algorithmik: In der reinen Mathematik geht es in der Regel um Aussagen — was ist wahr und was ist falsch? Wie man konkrete Berechnungen durchführt, spielt eine geringere Rolle. Für den Informatiker ist dies eine subtile Quelle von Verwirrung, aus zwei Gründen: Zum einen fragt man sich oft, wie man abstrakte Modelle praktisch umsetzen und einsetzen kann (also, wie man Sachen mit konkreten Algorithmen wirklich ausrechnet). Hierzu werden wir uns Beispiele für praktische Algorithmen und Datenstrukturen, die die Mathematik in den Rechner bringen, anschauen. Zum anderen gibt es auch subtile Unterschiede zwischen mathematischen Konzepten und deren algorithmischen Pendants. So ist eine Funktion in Phython oder C++ fast, aber nicht genau, das gleiche wie eine Funktion in der Mathematik. Auch diese Probleme wollen wir in diesem Skript näher beleuchten.

Anwendungen: Wozu dient das alles? Viele Studierende stellen sich am Anfang des Studiums die Frage, wozu die ganzen mathematischen Konzepte eigentlich gut sein sollen (es erscheint doch eher als strapaziöse Reise in den akademischen Elfenbeinturm). Die starke Abstraktion trägt besonders dazu bei, daß man vor lauter Bäumen den Wald nicht sieht. Daher hat diese Veranstaltung das Format eines Praktikums: Wir wollen die Konzepte direkt auf konkrete Probleme anwenden. Neben einer Motivation, die zum allgemeinen Wohlbefinden beitragen mag, lernt man auch, mit Methoden der höheren Mathematik praktisch zu arbeiten. Und das wollen wir am Ende, neben den analytischen Fähigkeiten, ebenfalls gut beherrschen.

Ok, nach so viel motivierenden Worten, gehen wir an die Arbeit. Als ersten müssen wir noch kurz klären, wie man dieses Skript am besten benutzt.

Gebrauchsanleitung

Das Praktikum „Angewandte Mathematik am Rechner“ besteht aus drei Komponenten:

Skript: Dieser Text hier (Wahlweise als PDF oder online as Webseite; wenn Sie dies hier lesen, haben Sie das sicher schon herausgefunden).
Vorlesung/Präsenzveranstaltung: In der „Präsenzveranstaltung“ besprechen wir die Inhalte aus dem Skript. Neben einer kleinen Vorlesung wollen wir hier auch Ideen diskutieren und Übungsaufgaben zusammen rechnen (damit das klappt, muß man die entsprechenden Kapitel im Skript vorher lesen).
Praktikumsaufgaben: Zur Veranstaltung gehören \(2\times6\) Praktikumsaufgaben (sechs in jedem der beiden Semester).

Das eigentliche Ziel ist es, die Praktikumsaufgaben zu lösen. Um den mathematischen Hintergrund besser zu verstehen, soll die Vorlesung und das Skript und die Vorlesung helfen. Hier werden Konzepte aus den Grundvorlesungen der Mathematik wiederholt und der Bezug zur Informatik sowie die praktische Umsetzung genauer erklärt. Um das ganze wirklich zu verstehen, muß man die Sachen natürlich selbst umsetzen.

Wie gehe ich vor?
Hier ist der Algorithmus zum Bearbeiten des Praktikums:

Vorbereitung I: Kapitel im Skript lesen (in den Praktikumsaufgaben angegeben). Am besten macht man dies zu Hause in Ruhe
Vorbereitung II: Im Skript sind kleinere Übungsaufgaben eingestreut. Diese müssen zur Vorbereitung bearbeitet werden. Dies kann man während des Lesens erledigen; am besten ist natürlich die Arbeit in einer kleinen Gruppe, in der auch nochmal die Inhalte diskutiert werden.
Präsenzveranstaltung: Als nächstes steht der Besuch der Präsenzveranstaltung auf dem Plan. Hier werden die Konzepte nochmal zusammengefaßt und Übungsaufgaben diskutiert. Hier ist sehr wichtig, vorbereitet teilzunehmen, damit man möglichst viel mitnimmt (es gibt zwar keine Noten dafür, aber man kann lernt sonst weniger).

Praktikumsaufgaben vorführen: Ups. Die zwei Wochen sind um. Nun muß jede Gruppe Ihre Lösung präsentieren. Dazu gibt es alle 14 Tage feste Gesprächstermine mit einem Tutor. Am Ende wird festgehalten, wie viel der Aufgabenstellung erfolgreich gelöst wurde (die Bewertung gilt für jeden Studenten individuell). Zum Bestehen müssen insgesamt 50\% der Aufgaben erfolgreich bearbeitet werden sowie mindestens 30\% jeder Aufgabe.

...und das ganze Wiederholt sich um 14-Tages-Rhythmus bis alle Aufgaben gelöst sind. Die ganze Zeit über steht auch ein elektronisches Diskussionsforum zur Verfügung um Ideen und Hintergründe mit Kommilitonen zu diskutieren (und Verbesserungsvorschläge zur Veranstaltung zu posten).

Leseplan

Das Praktikum ist wie folgt aufgebaut (ganz links steht die laufende Semesterwoche):

Das Vorgehen ist nun recht einfach:

Lesen Sie vor jeder Theorieveranstaltung (grün) das entsprechende Kapitel im Skript. Dies ist immer das Kapitel mit der gleiche Nummer.
Die Inhalte aus der Theorieveranstaltung und dem Skript dienen zur Vorbereitung auf die Übungsaufgaben, die in der selben Woche ausgegeben werden.
Bearbeiten Sie die Aufgaben, nachdem Sie die Theorieveranstaltung besucht haben (es sind dann zwei Wochen Zeit).

Updates

Im Laufe des Semesters können sich die Inhalte späterer Veranstaltungen noch leicht ändern; die Nummerierung bleibt aber konsistent. Einige Kapitel sind auch noch nicht fertiggestellt; diese werden rechtzeitig vor der entsprechenden Theorieveranstaltung (mindestens eine Woche eher) verfügbar gemacht. Im Nachgang der Theorieveranstaltung findet auch noch eine Diskussion zu offenen Fragen statt; ggF. wird zusätzliches Material online bereitgestellt (Forum verfolgen).