Wie können wir sicher sein, dass ein Objekt mit bestimmten Anforderungen existiert? Eine Möglichkeit, dies zu zeigen, besteht darin, alle Objekte durchzugehen und zu prüfen, ob mindestens eines von ihnen die Anforderungen erfüllt. In vielen Fällen ist der Suchraum jedoch riesig. Ein Computer kann zwar helfen, aber eine Argumentation, die den Suchraum eingrenzt, ist sowohl für die Computersuche als auch für die Arbeit mit bloßen Händen wichtig. In diesem Modul lernen wir verschiedene Techniken kennen, um zu zeigen, dass ein Objekt existiert und dass ein Objekt unter allen anderen Objekten optimal ist. Wie üblich werden wir das Lösen vieler interaktiver Rätsel üben. Wir werden auch einige Computerprogramme zeigen, die uns helfen, ein Beispiel zu konstruieren.

Wir werden zwei leistungsstarke Methoden zur Definition von Objekten, zum Nachweis von Konzepten und zur Implementierung von Programmen kennenlernen - Rekursion und Induktion. Diese beiden Methoden werden in der diskreten Mathematik und der Informatik häufig verwendet. Insbesondere werden Sie sie häufig in Algorithmen finden - zur Analyse der Korrektheit und Laufzeit von Algorithmen sowie zur Implementierung effizienter Lösungen. Für einige Berechnungsprobleme (z.B. die Erforschung von Netzwerken) sind rekursive Lösungen die natürlichsten. Die Hauptidee von Rekursion und Induktion besteht darin, ein gegebenes Problem in kleinere Probleme desselben Typs zu zerlegen. Die Fähigkeit, solche Zerlegungen zu erkennen, ist eine wichtige Fähigkeit sowohl in der Mathematik als auch in der Programmierung. Wir werden diese Fähigkeit verfeinern, indem wir gemeinsam verschiedene Probleme lösen.

Die mathematische Logik spielt eine entscheidende und unverzichtbare Rolle bei der Erstellung überzeugender Argumente. Wir verwenden die Regeln und die Sprache der mathematischen Logik beim Schreiben von Code, beim Überlegen und Treffen von Entscheidungen und bei der Verwendung von Computerprogrammen. Diese Woche lernen wir die Grundlagen der mathematischen Logik kennen und üben knifflige und scheinbar kontraintuitive, aber dennoch logische Aspekte der mathematischen Logik. Dies wird uns helfen, lesbaren und präzisen Code zu schreiben und unsere Gedanken streng und präzise zu formulieren.

"Es gibt Dinge, die sich nie ändern". Dieser Satz ist nicht nur eine philosophische Aussage, sondern erweist sich auch als wichtige Idee in der diskreten Mathematik und der Computerwissenschaft. Eine Eigenschaft, die während eines Prozesses erhalten bleibt, nennt man eine Invariante. Invarianten werden häufig bei der Analyse des Verhaltens von Algorithmen, Programmen und anderen Prozessen verwendet. Die Fähigkeit, die richtige Invariante zu finden, ist eine wichtige Fähigkeit, die wir in diesem Modul gemeinsam entwickeln werden.

In diesem Modul betrachten wir ein bekanntes 15er-Puzzle, bei dem man die Ordnung zwischen 15 quadratischen Teilen in einem quadratischen Kasten wiederherstellen muss. Es stellt sich heraus, dass das Verhalten dieses Rätsels durch die Mathematik bestimmt wird: Es ist lösbar, wenn und nur wenn die entsprechende Permutation gerade ist. Um zu verstehen, was dies bedeutet und warum es wahr ist, werden wir die grundlegenden Eigenschaften von geraden und ungeraden Permutationen kennen lernen - ein wichtiger Begriff in der Algebra und der diskreten Mathematik. Gemeinsam werden wir eine Reihe von einfachen Methoden für die Arbeit mit Permutationen anwenden. Sie werden diese dann als Bausteine verwenden, um ein Programm zu implementieren, das jede beliebige Konfiguration dieses Spiels in einem Wimpernschlag löst!