Mathematik für die Informatik (2018) [PDF]

• Ein von MIT bereitgestelltes Mathematiklehrbuch für Informatikstudierende, das zentrale mathematische Konzepte von Logik und Beweisen bis hin zu Wahrscheinlichkeit, Rekursion und Graphentheorie systematisch behandelt
• Es besteht aus fünf Teilen zu Beweisen, Strukturen, Zählen, Wahrscheinlichkeit und Rekurrenzen, wobei jeder Teil theoretische Grundlagen zusammen mit Anwendungen in der Informatik behandelt
• Es umfasst für Programmierung und Algorithmusanalyse unverzichtbare Themen wie logische Formeln, mathematische Induktion, Zustandsmaschinen, Graphen und Zufallsvariablen
• Anhand von realen Beispielen und Anwendungsaufgaben wie RSA-Verschlüsselung, Turings Code und dem Monty-Hall-Problem wird gezeigt, wie mathematische Konzepte eingesetzt werden
• Das Lehrbuch wurde gemeinsam von Forschenden von MIT und Google verfasst und unter der Creative-Commons-BY-SA-3.0-Lizenz veröffentlicht, sodass Lernen und Wiederverwendung frei möglich sind

---

Überblick über das Lehrbuch

• Mathematics for Computer Science (MCS) ist das Lehrbuch für den MIT-Studiengang in Informatik und Elektrotechnik im Undergraduate-Kurs (6.042) und dient dazu, logisches Denken und mathematische Modellierungsfähigkeit zu fördern
• Die Autoren sind Eric Lehman (Google Inc.), F. Thomson Leighton (MIT, Akamai Technologies) und Albert R. Meyer (MIT)
• Es handelt sich um die überarbeitete Ausgabe vom 6. Juni 2018, die unter der Lizenz Creative Commons Attribution-ShareAlike 3.0 verbreitet wird

I. Proofs (Beweise)

• Behandelt die Grundprinzipien mathematischer Beweise wie Aussagen, Prädikate, die axiomatische Methode, Widerspruchsbeweise und Beweise durch Fallunterscheidung
• Erklärt die Beziehung zwischen dem Well-Ordering-Prinzip und der Induktion und wendet sie auf Beispiele wie die Primfaktorzerlegung an
• Enthält logische Formeln und Aussagenlogik, das SAT-Problem sowie mathematische Datentypen (Mengen, Funktionen, Relationen)

II. Structures (Strukturen)

• Präsentiert die mathematischen Grundlagen der Informatik mit Schwerpunkt auf Zahlentheorie, Graphentheorie und Netzwerkstrukturen
  • Anwendungen der Zahlentheorie wie Primzahlen, größter gemeinsamer Teiler, modulare Arithmetik und RSA-Verschlüsselung
  • Erläuterung struktureller Modelle wie gerichtete Graphen, partielle Ordnungen, Netzwerk-Routing, einfache Graphen und planare Graphen
• Behandelt Turings Code und den Zusammenhang mit dem SAT-Problem und zeigt die Verbindung zwischen Berechnungstheorie und Kryptographie

III. Counting (Zählen und Kombinatorik)

• Behandelt Summen, Produkte, asymptotische Notation, Kombinationsregeln und erzeugende Funktionen als kombinatorische Rechentechniken
• Enthält praxisnahe Beispiele wie das Schubfachprinzip, das Prinzip der Inklusion und Exklusion und Beispiele mit Pokerhänden
• Zeigt Anwendungen für die Algorithmusanalyse und Folgenberechnung durch erzeugende Funktionen und Lösungsverfahren für lineare Rekurrenzen

IV. Probability (Wahrscheinlichkeit)

• Umfasst die gesamte Bandbreite der Wahrscheinlichkeitstheorie, darunter Wahrscheinlichkeitsräume, bedingte Wahrscheinlichkeit, Zufallsvariablen, Varianz, Stichprobenschätzung und Random Walks
• Enthält Beispiele, die das intuitive Denken herausfordern, wie das Monty-Hall-Problem, Simpsons Paradoxon und das Geburtstagsproblem
• Liefert Grundlagen der Datenanalyse durch Markov- und Tschebyscheff-Ungleichungen sowie Random Sampling

V. Recurrences (Rekurrenzen)

• Behandelt zentrale Themen der Algorithmusanalyse wie Türme von Hanoi, Merge Sort und Rekurrenzen des Divide-and-Conquer-Typs
• Erläutert effiziente Berechnungsstrukturen durch Lösungsverfahren für lineare Rekurrenzen und rekursives Denken

Anhang

• Enthält Literaturverzeichnis, Zeichenerklärung und Index und ist damit zum Lernen und Nachschlagen gut geeignet
• Das vollständige Lehrbuch wird auf der MIT-CSAIL-Website kostenlos als PDF bereitgestellt

[GN⁺]

Hacker-News-Kommentare

• Es wird erwähnt, dass Thomson Leighton der Gründer von Akamai ist, und seine Vorlesungsreihe wird empfohlen.
  Das war einer der beeindruckendsten Inhalte über das Internet, die der Kommentator je gesehen hat.

  • Als zusätzliches Material werden die aktuellen Vorlesungsvideos des MIT OCW sowie der Open-Learning-Library-Kurs von Albert Meyer vorgestellt, einem der Autoren des Lehrbuchs.
  • Ergänzend wird angemerkt, dass Akamai sich stärker um die IPv4-Bereiche kümmern sollte, die von Scannern oder Script Kiddies genutzt werden.

• Der Aufbau der einzelnen Abschnitte ist ziemlich standardmäßig, aber es gefällt, dass jede Zitierung Rückverweise auf sämtliche Quellen enthält.
  Es wäre schön, wenn es mehr Bücher gäbe, die auf diese Weise gemacht sind.

  • Die Inhaltsauswahl sei im Gegenteil eher unkonventionell, was sie interessant mache, und der typische MIT-Humor sei darin spürbar.
    Schade sei nur, dass das Schreiben seit 2018 eingestellt wurde.

• Jemand liebt dieses Buch wirklich. Der Schwierigkeitsgrad ist hoch, aber pro Abschnitt konnte er etwa 1 bis 2 Seiten verstehen.
  Er gewann die Einsicht, dass Funktionen endlose Listen von Eingaben und Ausgaben sind, und auch der Humor in der mathematischen Notation blieb ihm im Gedächtnis.
  Er würde es gern vor seinem Tod vollständig verstehen.

  • Die Formulierung, pro Abschnitt „1 bis 2 Seiten zu verstehen“, habe ihn an victorhugoeske Schachtelsätze erinnert und zum Lachen gebracht.
  • „1 bis 2 Seiten“? Als Witz seien es eher „-1 Seite“.

• Es wird die Frage gestellt, ob man nur fünf Bücher nennen könne, die man in der Informatik unbedingt lesen sollte.

  • Mit nur fünf sei das unmöglich, und stattdessen wird eine eigene Top-10-Liste geteilt.
    Darin enthalten sind unter anderem Brookshear, Forta, Stallings, CLRS, Kurose & Ross, Sipser, Aumasson sowie Russell & Norvig.
    Python sei faktisch zur Lingua franca geworden, und auch Matthes’ Python Crash Course 3rd Edition wird empfohlen.
  • Für Menschen ohne Informatikstudium wird TeachYourselfCS.com empfohlen.
    Dort werden auch zwei Kernbücher für Fälle genannt, in denen die Zeit knapp ist.
  • Es hänge davon ab, in welchem Bereich man arbeitet. Das sei eine ähnliche Frage wie „Welche Sprache sollte ich lernen?“.
  • Zu diesem Buch wird angemerkt, dass es sich weniger auf Beziehungen als auf Zahlen zu konzentrieren scheine; empfohlen wird außerdem, type theory und category theory mitzulernen.
  • Eine Liste, der alle zustimmen würden, gebe es nicht. Wichtig sei, selbst zu erkunden und passende Bücher zu Algorithmen, Automaten, Sprachen, Betriebssystemen, Machine Learning und anderen Themen zu finden.

• Besonders gut habe der Wahrscheinlichkeitsteil dieses Buches gefallen.
  Das Monty-Hall-Problem werde mit einer „Vier-Schritte-Methode“ so klar erklärt, dass es viel leichter zu verstehen sei als im Film.

  • Es wurde entdeckt, dass die Ausgabe von 2017 in Großbritannien als Print-on-Demand erhältlich ist.
    Das sei gut, um Teile davon als gedrucktes Buch zu lernen.

• Beim Blick ins Inhaltsverzeichnis überraschte es jemanden, dass Kapitel 2 das Well-Ordering Principle ist.
  Anders als bei Zermelos Satz wirke der Ansatz ungewohnt, die Ordnung der natürlichen Zahlen vorauszusetzen.
  Üblicherweise habe er gelernt, zuerst die Ordnung aus den Peano-Axiomen zu definieren und danach das Prinzip zu beweisen.

  • Es wird erklärt, dass das Well-Ordering Principle, das Axiom of Choice und Zorn’s Lemma äquivalent sind.
    Auch auf den reellen Zahlen gebe es eine Wohlordnung, doch man könne diese Ordnung nicht tatsächlich ausdrücken, was interessant sei.
    Zitiert wird auch der Witz: „Das Auswahlaxiom ist offensichtlich wahr, das Wohlordnungsprinzip offensichtlich falsch, und bei Zorns Lemma weiß ich es nicht.“
  • In der CS-Ausbildung werde das meist nur als Grundlage der vollständigen Induktion behandelt und in späteren Algorithmusvorlesungen kaum noch erwähnt.

• Das Schubfachprinzip aus Abschnitt 15.8 wird mit Dijkstras Ansatz noch einmal erklärt.
  Wenn 500.000 Menschen in Boston jeweils zwischen 1 und 200.000 Haare haben, beträgt der Durchschnitt 2,5 Menschen pro Haaranzahl, also müsse es mindestens 3 Menschen mit derselben Haarzahl geben.
  Interessant sei, dass sich das allein mit der einfachen Tatsache lösen lässt, dass der Durchschnitt nicht größer als das Maximum sein kann.

• Jemand sagt, dies sei das erste Buch in Aufgabenheft-Form, dem er begegnet sei, und fragt sich, ob es Lösungen gibt.
  Er habe einige Aufgaben gelöst, konnte die Antworten aber nicht überprüfen.

  • Im Discrete-Math-Kurs von Math Academy werden beim Einreichen von Antworten die Lösungen angezeigt, und es gibt auch eine Funktion für Spaced Repetition.
  • Ohne Lösungen sei Selbststudium schwierig; auch Susanna Epps Discrete Mathematics With Applications sei eine gute Alternative.
  • Solche Aufgaben ließen sich mit LLMs leicht lösen, heißt es.
  • Es wird eine Erfahrung geteilt, bei der ein LLM tatsächlich Fehler in einem Beweis gefunden hat. Gemini habe auf einen falschen Beweis hingewiesen und sei dabei nützlich gewesen.
  • Dass Universitäten keine Lösungssammlungen veröffentlichen, liege daran, dass sie Aufgaben wiederverwenden. Ein begrenzter Pool werde über Jahre hinweg immer wieder benutzt.

• Es wird für das sehr nützliche Material gedankt.

• Jemand freut sich, dank Hacker News die gesuchte PDF gefunden zu haben.
  Er bittet um Empfehlungen für einen Screenreader, der PDFs lesen kann.

  • Es wird die Frage aufgeworfen, ob es überhaupt einen Reader gibt, der PDFs mit LaTeX-Formeln lesen kann.
    Die Person sagt, sie selbst könne die meisten mathematischen Symbole ebenfalls nicht lesen.