Spezialisierung für Einführung in die diskrete Mathematik für die Computerwissenschaft

Zählen ist eine der grundlegenden mathematischen Aufgaben, die uns tagtäglich begegnen. Die wichtigste Frage dabei ist die folgende. Wenn wir etwas zählen müssen, können wir dann etwas Besseres tun, als einfach alle Objekte einzeln zu zählen? Müssen wir eine Liste mit allen Telefonnummern erstellen, um sicherzustellen, dass es genug Telefonnummern für alle gibt? Gibt es einen Weg, um festzustellen, ob unser Algorithmus in einer angemessenen Zeit abläuft, bevor wir ihn implementieren und tatsächlich ausführen? All diese Fragen werden von einem mathematischen Fachgebiet namens Kombinatorik behandelt. In diesem Online-Kurs besprechen wir die meisten kombinatorischen Standardeinstellungen, die bei der Beantwortung von Fragen dieser Art helfen können. Wir werden uns besonders darauf konzentrieren, die Fähigkeit zu entwickeln, diese Einstellungen in realen und algorithmischen Problemen zu unterscheiden. Dies wird dem Lernenden helfen, das neue Wissen tatsächlich umzusetzen. Außerdem werden wir rekursive Techniken für das Zählen besprechen, die für algorithmische Implementierungen wichtig sind. Einer der wichtigsten 'Verbraucher' der Kombinatorik ist die Wahrscheinlichkeitstheorie. Dieser Bereich ist mit zahlreichen Seiten des Lebens verbunden. Einerseits ist er ein wichtiges Konzept im täglichen Leben, andererseits ist er ein unverzichtbares Werkzeug in so modernen und wichtigen Bereichen wie Statistik und maschinelles Lernen. In diesem Kurs konzentrieren wir uns auf die Vermittlung von Grundkenntnissen der Wahrscheinlichkeitsrechnung und einer guten Intuition in diesem Bereich. Die Praxis zeigt, dass eine solche Intuition nicht einfach zu entwickeln ist. Am Ende des Kurses werden wir ein Programm erstellen, das erfolgreich ein kniffliges und sehr kontraintuitives Würfelspiel spielt. Als Voraussetzungen setzen wir lediglich mathematische Grundkenntnisse (z.B. erwarten wir, dass Sie wissen, was ein Quadrat ist oder wie man Brüche addiert), Grundkenntnisse der Programmierung in Python (Funktionen, Schleifen, Rekursion), gesunden Menschenverstand und Neugierde voraus. Unser Zielpublikum sind alle, die in der IT-Branche arbeiten oder dies vorhaben, angefangen bei motivierten Oberstufenschülern.

Wir laden Sie zu einer faszinierenden Reise in die Graphentheorie ein - ein Gebiet, das die Eleganz der Malerei und die Strenge der Mathematik verbindet; es ist einfach, aber nicht anspruchslos. Die Graphentheorie bietet uns sowohl eine einfache Möglichkeit, viele wichtige mathematische Ergebnisse bildlich darzustellen, als auch Einblicke in die tiefgründigen Theorien dahinter.

In diesem Online-Kurs werden wir neben anderen faszinierenden Anwendungen sehen, wie GPS-Systeme die kürzesten Routen finden, wie Ingenieure integrierte Schaltkreise entwerfen, wie Biologen Genome zusammensetzen und warum eine politische Karte immer mit wenigen Farben eingefärbt werden kann. Wir werden die Ramsey-Theorie studieren, die beweist, dass es in einem großen System keine vollständige Unordnung geben kann! Am Ende des Kurses werden wir einen Algorithmus implementieren, der eine optimale Zuordnung von Schülern zu Schulen findet. Dieser von David Gale und Lloyd S. Shapley entwickelte Algorithmus wurde später mit dem Nobelpreis für Wirtschaftswissenschaften ausgezeichnet. Als Voraussetzungen setzen wir lediglich mathematische Grundkenntnisse (z.B. erwarten wir, dass Sie wissen, was ein Quadrat ist oder wie man Brüche addiert), Grundkenntnisse der Programmierung in Python (Funktionen, Schleifen, Rekursion), gesunden Menschenverstand und Neugierde voraus. Unser Zielpublikum sind alle, die in der IT-Branche arbeiten oder dies vorhaben, angefangen bei motivierten Oberstufenschülern.

Ein prominenter Experte auf dem Gebiet der Zahlentheorie, Godfrey Hardy, bezeichnete sie zu Beginn des 20. Jahrhunderts als einen der offensichtlich nutzlosesten Zweige der reinen Mathematik". Nur 30 Jahre nach seinem Tod wurde unter Verwendung der Errungenschaften der Zahlentheorie ein Algorithmus zur Verschlüsselung geheimer Nachrichten entwickelt. Er wurde nach den Namen seiner Autoren RSA genannt, und seine Implementierung ist heute wahrscheinlich das am häufigsten verwendete Computerprogramm der Welt. Ohne es wäre niemand in der Lage, sichere Zahlungen über das Internet zu tätigen oder sich sicher bei E-Mails und anderen persönlichen Diensten anzumelden. In diesem Kurs werden wir mit den Grundlagen der Zahlentheorie beginnen und zu den darauf basierenden kryptographischen Protokollen kommen. Am Ende werden Sie in der Lage sein, die Grundlagen der Zahlentheorie anzuwenden, um Nachrichten zu ver- und entschlüsseln und den Code zu knacken, wenn man RSA unvorsichtig anwendet. Sie werden sogar eine kryptografische Aufgabe bestehen! Als Voraussetzungen setzen wir lediglich mathematische Grundkenntnisse (z.B. erwarten wir, dass Sie wissen, was ein Quadrat ist oder wie man Brüche addiert), Grundkenntnisse der Programmierung in Python (Funktionen, Schleifen, Rekursion), gesunden Menschenverstand und Neugierde voraus. Unser Zielpublikum sind alle, die in der IT-Branche arbeiten oder dies vorhaben, angefangen bei motivierten Oberstufenschülern.

In diesem Online-Kurs werden wir (in Python) gemeinsam effiziente Programme für ein Problem implementieren, das von Lieferunternehmen auf der ganzen Welt millionenfach pro Tag benötigt wird - das Problem des reisenden Handlungsreisenden. Das Ziel bei diesem Problem ist es, alle vorgegebenen Orte so schnell wie möglich zu besuchen. Wie kann man schnell eine optimale Lösung für dieses Problem finden? Wir haben immer noch keine nachweislich effizienten Algorithmen für dieses schwierige Rechenproblem und das ist der Kern des P versus NP-Problems, der wichtigsten offenen Frage in der Informatik. Dennoch werden wir mehrere Lösungen für reale Instanzen des Problems des Handlungsreisenden implementieren. Bei der Entwicklung dieser Lösungen werden wir uns stark auf den Stoff stützen, den wir in den Kursen der Spezialisierung gelernt haben: Beweistechniken, Kombinatorik, Wahrscheinlichkeitsrechnung, Graphentheorie. Wir werden mehrere Beispiele für die Verwendung von Ideen aus der diskreten Mathematik sehen, um mehr und effizientere Lösungen zu erhalten.