01142 - Algorithmische Mathematik

Persönliches, subjektives Kursfazit

Sehr, sehr angenehmer Kurs. Ein super Skript und sehr spannende Themen.  Zusammengefasst Grob gesagt geht es hier um den Kurs Analysis 2 und Mathematik 2 aus dem Diplom-Studiengang, welche einfach in einen Kurs gequetscht wurden, ohne den Stoffumfang zu verkleinern*. Daher auch die Art der Klausur (siehe unten). Eine Literaturempfehlung kann ich auch hier abgeben, da sich das Skript an einige Kapitel im Buch anlehnt. Mit dem Unterschied, dass man im Buch etwas mehr Erklärungen findet. Etwas weniger beweislastig, als 1141. Ums "Beweisen Sie, dass..." kommt man aber auch hier nicht herum...

* Nachtrag: nach Meinung einiger anderer Studenten, sind durchaus einige Themen aus Analysis 2 (für Informatiker) und lineare Algebra 2 nicht nur verkürzt worden, sondern komplett unter den Tisch gefallen. Möge sich jeder, anhand der gekürzten Stichworte, ein eigenes Bild machen, da sich an jeder Uni AII und MII in den Themen durchaus unterscheiden können. Falls euch konkrete Themen einfallen, die wirklich fehlen, bitte ich um Nachricht. Würde mir das auch gerne mal anschauen.

Literaturempfehlung

Siehe Literaturempfehlung im Widget. Ein sehr gutes Buch bei dem man merkt, dass die Autoren es einem wirklich beibringen wollen anstatt nur einen weiteren Eintrag ihrer Veröffentlichungs-Liste hinzuzufügen. Wenig Beweise, viel Prosa. Definitiv ein guter Tipp (von dem gleichen Kommilitonen, der mir auch die Teschl-Reihe für Mathe 1 empfohlen hat). Das Skript lehnt sich sehr an einige Kapitel aus diesem Buch an. Im Buch stehen jedoch Themenerklärungen, an denen im Skript gespart wurde. Vor allem die Graphentheorie aus dem Skript wurde durch das Buch entzerrt und (zumindest für mich) erst dann wirklich verständlich.

Die Bücher zur linearen Algebra und Analysis 2 habe ich für die Vorbereitung verwendet. Das Buch von Jänich hat 110 Testfragen zur linearen Algebra, während im Buch von Behrends leider keine Übungen drin sind. Wer sich jedoch mit Analysis 2 überfordert fühlt, findet hier das Thema aus einen anderen Blickwinkel betrachtet.

Klausur- und Organisatorisches

Stand WS 2009: Aufgrund der unglaublichen Masse an Stoff, ist es eine 150% Auswahlklausur. Und somit machbar, wenn die Zeit auch sehr knapp bemessen ist.

Zur Klausurvorbereitung würde ich alle alten Klausuren durcharbeiten und vor allem Wert auf Graphen (Beweis Isomorphie, Eulertouren, kürzeste Wege und minimal aufspannende Bäume), lineare Optimierung mit Simplex (ganz wichtig: macht Simplex bis ihr es nicht mehr sehen könnt! Baut euch ein System auf, so dass ihr schnell schreibt und euch nicht verrechnet. Die Simplex-Aufgaben bringen meist 1/4 der notwendigen Klausurpunkte. Ich hatte in der Klausur fast 2 Seiten voller Rechnungen. Ich poste "mein System" bei Gelegenheit hier), Cholesky und LU Zerlegung (hier auch: üben um schnell zu sein), Dijkstra, stabile Hochzeiten (inkl. bipartite Matchings) und nichtlineare Optimierung (Extremwerte und Newtonverfahren).

Kursinhalt

Kurseinheit 1

Einführung in die Notation im Skript, Beweisarten (Reductio ad absurdum, Kontraposition, vollst. Induktion) und Abbildungen.

Kurseinheit 2

Abbildungen, Mengen, Sur-, In- und Bijektivität. Permutationen, Binomialkoeffizienten, Abschätzungen, Prinzipien von In- und Exklusion. Disrete Wahrscheinlichkeitsrechnung (Wahrscheinlichkeitsraum, bedingte Wahrscheinlichkeiten, Paradoxa, Zufallsvariablen).

Kurseinheit 3

Definition von (gerichteten und ungerichteten) Graphen (Äquivalenzrelationen, Partialordnungen), Isomorphismus, Teilgraphen, (2-)Zusammenhang, Algorithmen, Valenzsequenzen, Breiten- und Tiefensuche, Eulertouren.

Kurseinheit 4

Definition Bäume und Matchings, (minimal, Anzahl von) aufspannende(n) Bäume, Isomorphismus, Prim-Jarnik und Bourivka, bipartites Matching und stabile Hochzeiten (Gale und Shapeley).

Kurseinheit 5

Numerik und lineare Algebra, Kodierung, Fehlerquellen, LU-Zerlegung und Pivotstrategien, Gauss-Jordan, Eigenwerte und Cholesky, Matrixnormen und Kondition.

Kurseinheit 6

Nichtlineare Optimierung, mehrdimensionale Differenzialrechnung, Kurven, partielle Ableitungen, notwendige und hinreichende für Extremwerte, Mannigfaltigkeit und Tangentialräume, Bedingungen für Extrema auf (un-)gleichungsdefinierten Räumen.

Kurseinheit 7

Numerische Verfahren für nichtlineare Optimierung,  Koordinatensuche, steilster Abstieg, Newtonverfahren, konjugierte Richtungen.

Kurseinheit 8

Lineare Optimierung. Modellbildung und Dualitätssatz, Simplexverfahren, 2 Phasen Methode, sowie Sensitivitätsanalyse.

Buchempfehlung