Kombinatorik erklärt
Kombinatorik heißt hier: mit endlichen Strukturen rechnen, bei denen sich die Möglichkeiten nicht mehr aufzählen lassen. Die zwei Linien dieses Bereichs stellen zwei Fragen: Wie viele gibt es?, beantwortet durch Beschreiben, erzeugende Funktionen und Schätzen, und Wann findet eine einfache Regel das Beste?, beantwortet durch die Austauschstruktur der Matroide und die abnehmenden Zusatznutzen submodularer Funktionen.
Jede Linie hat eine eigene Seite mit einem Abhängigkeitsgraphen und ihren Demos. Die Themenfelder unten ordnen die Linien nach Verwandtschaft, der Beziehungsgraph am Ende zeigt, welche Linien sich Bausteine teilen.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Zählen und Erzeugen
Zählen, was sich nicht ausschreiben lässt: Strukturen beschreiben, erzeugende Funktionen ablesen, Wachstum abschätzen und aus dem Zählen ein Verfahren zum Ziehen und Schätzen machen.
Abzählen und erzeugende Funktionen
Wie viele Möglichkeiten gibt es, wie schnell wachsen sie, und wann lohnt sich welches Zählverfahren? Sechzehn Stücke von der Rekursion über erzeugende Funktionen und Symmetrie bis zum Entscheidungsdiagramm und zur Verfahrenswahl.
Zur Linie →Strukturen und Greedy
Wann eine einfache Regel das Beste findet: Die Austauschstruktur der Matroide erklärt, warum Greedy optimal ist, wo es scheitert und was dann noch bleibt.
Matroide und Submodularität
Warum Greedy beim Spannbaum gewinnt, wo dieselbe Regel scheitert und welche Struktur den Unterschied macht. Siebzehn Stücke vom Spannbaum bis zur Verfahrenswahl.
Zur Linie →Wie die Linien dieses Bereichs zusammenhängen
Jede Kante steht für einen belegten Zusammenhang: Ein Verfahren nutzt innen eine Technik der anderen Linie, oder beide gehen dasselbe Problem aus verschiedenen Blickwinkeln an. Die Farbe zeigt das Themenfeld, gestrichelte Kästen sind Linien aus anderen Bereichen, mit denen es Verbindungen gibt. Die jeweilige Linienseite erklärt jeden Zusammenhang unter „Verwandt in anderen Linien“.
Die Kästen sind klickbar und öffnen die jeweilige Seite.
- Zählen und Erzeugen
- Strukturen und Greedy
- Linie eines anderen Bereichs
Weitere Bereiche
Optimierung
Verfahren, die aus sehr vielen Möglichkeiten eine beste oder gut begründete Entscheidung suchen: mit Beweis, mit Heuristik, für Planung und unter Unsicherheit.
Maschinelles Lernen
Verfahren, die aus Daten lernen: Struktur finden, wenn niemand die Antwort vorgibt, vorhersagen, wenn Beispiele vorliegen, und handeln, indem man aus Versuch und Irrtum lernt.
Signalverarbeitung
Verfahren, die aus gemischten oder unscharfen Messungen die ursprünglichen Signale zurückgewinnen oder aus verrauschten Messungen einen Zustand schätzen.
Graphentheorie
Verfahren, die Fragen über Netze selbst beantworten: erreichbar, verbunden, kritisch, zugeordnet, zentral, schmalbandig oder wie sich etwas auf dem Netz ausbreitet.
Spieltheorie
Verfahren für Entscheidungen mit mehreren Beteiligten, die eigene Ziele verfolgen: Anreize und Kooperation, direkte Gegner, Verhandlungen, Märkte und Spiele auf Netzen.
Statistik
Verfahren, die aus Daten auf die Welt schließen: die Mitte der Daten, den Zusammenhang zwischen Größen, die Wirkung einer Maßnahme mit Experimenten und kausalen Diagrammen und die Zeit bis zu einem Ereignis, wenn die Beobachtung vorher endet.
Wertung und Wahl
Verfahren, die aus Vergleichen, Kriterien und Stimmen eine Rangfolge, eine Entscheidung oder eine faire Verteilung machen, dazu die Planung der Turniere, aus denen die Vergleiche kommen.
Simulation
Ein System im Rechner nachbilden und ehrlich angeben, was man daraus schließen darf: mit Zufallsziehungen (Warteschlangen, Monte Carlo), mit Regeln für viele Einzelne (Ausbreitung und Meinungen auf Netzen) und mit Beständen und Rückkopplung in kleinen Zeitschritten (dynamische Systeme).