Automaten und formale Sprachtheorie: Die Hintergründe von regulären Ausdrücken und der Chomsky-Hierarchie
Kategorien
72 Seiten
Informatik
Das P-vs-NP-Problem und Komplexitätsklassen: Erklärung des Millennium-Problems und programmiertechnische Bedeutung
Lambda-Kalkül und der Ursprung der funktionalen Programmierung: Von Alonzo Churchs Theorie zu Lisp und Haskell
Turingmaschinen und Berechenbarkeitstheorie: Alan Turings Gedankenexperiment und das „Halteproblem“
Conways Spiel des Lebens: Ein zellulärer Automat, bei dem aus einfachen Regeln lebensähnliche Komplexität entsteht
Der Vier-Farben-Satz (Four Color Theorem) - Kann jede Karte mit 4 Farben gefärbt werden?
Das Halteproblem (Halting Problem): Das stärkste Programm, das absolut unmöglich zu erschaffen ist
Das Schubfachprinzip und Hash-Kollisionen: Warum völlig verschiedene Daten denselben Hash-Wert erzeugen
Gödels Unvollständigkeitssätze: Der mathematische Beweis für „absolut unbeweisbare Wahrheiten“
Floyds Algorithmus zur Zykluserkennung (Hase-und-Igel-Algorithmus)
Zwei randomisierte Algorithmen: Die Unterschiede zwischen Monte-Carlo- und Las-Vegas-Algorithmen
Grenzen der Primfaktorzerlegung und Erklärung der Big-O(O)-Notation für die Zeitkomplexität
