Abzählen und erzeugende Funktionen erklärt
Wie viele Möglichkeiten gibt es, wenn man sie nicht ausschreiben kann? Diese Linie nimmt die Frage sechzehnmal in die Hand, mit einem gemeinsamen Rückgrat: Man beschreibt die Struktur, liest daraus eine erzeugende Funktion ab, rechnet Koeffizienten aus und liest das Wachstum. Sie beginnt bei Schichtfolgen mit verbotenen Teilfolgen, die eine Rekursion mit kleinem Gedächtnis zählt, und erweitert Stück für Stück, was sich beschreiben lässt: Bäume, Multimengen, beschriftete Strukturen, Verbote, Symmetrie und zuletzt Teilgraphen eines Netzes. Das Beispiel wächst dabei in der Beschreibung, nicht in einer einzigen Instanz.
Zwei Brücken führen zur Optimierung: Dieselbe Rekursion zählt und optimiert, wenn man Summe und Produkt austauscht, und ein Entscheidungsdiagramm fasst gleiche Teilprobleme zusammen, sodass auf ihm gezählt, optimiert und gezogen werden kann. Mehrere Stücke enden mit einem Negativbefund: Das Sieb spart bei Hamiltonkreisen in der Messung Speicher, aber keine Zeit; Kasteleyns Formel rechnet in Gleitkomma ab einer gewissen Brettgröße falsch; und in den gemessenen Fällen ist ein exaktes Verfahren billiger als der Schätzer. Ehrliche Einschränkung: Alles ist gerechnet, nichts stammt aus echten Plänen, Zeiten sind Python-Messungen eines Rechners, und die Aussagen gelten für die gewählten Familien und Größen.
In short: Covers counting combinatorial structures: describing a structure, reading off its generating function and coefficients, and estimating growth. Further demos cover labelled structures, inclusion-exclusion, symmetry, decision diagrams, the Tutte polynomial, estimation and the choice of method.
Hintergrund zum Thema: Schichtplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Aufzählen und Rekursion verständlich erklärt
Warum man gültige Schichtfolgen mit Verbotsregeln nicht einzeln prüfen muss, sondern nur das Ende der Folge im Gedächtnis behält, und wann dieses Gedächtnis selbst zu groß wird: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Das Rückgrat: von der Rekursion zum gleichverteilten Ziehen
Zehn Stücke, die aufeinander aufbauen: Jedes behebt eine Schwäche des Vorgängers, vom Raten einer Rekursion über die erzeugende Funktion und das Wachstum bis zum Ziehen eines Objekts aus einer Menge, die man nur zählen kann.
Die Wurzel ist das Aufzählen mit Rekursion: Sie zählt Folgen mit verbotenen Teilfolgen und merkt sich nur einen kleinen Zustand, zeigt aber kein Wachstum. Daraus folgt die rationale erzeugende Funktion, die Rekursion und Wachstum aus einem Nenner abliest. Wo es keinen endlichen Automaten gibt, bei Bäumen und Klammern, beschreibt die symbolische Methode die Struktur und liefert die Gleichung für die Zählfolge.
Von der symbolischen Methode gehen mehrere Wege weiter. Der Semiring rechnet dieselbe Rekursion mit anderen Operationen und optimiert, statt zu zählen. Multimengen blenden die Reihenfolge aus, beschriftete Strukturen unterscheiden die Elemente, und die Siebformel zieht Verbote ab, statt sie aufzubauen; sie führt mit dem Semiring als Gegenprobe zusammen. Die Verteilung nach einem Parameter, die Asymptotik und das gleichverteilte Ziehen folgen am Ende, und das Ziehen führt Gleichung, Wachstumsrate und Semiring zusammen.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelt umrandet sind Demos aus anderen Linien: die Rucksack-Tabelle der dynamischen Programmierung aus der Exakten Suche und die Permanente aus den Komplexitätsklassen. Doppelt umrandet sind die Siebformel und das gleichverteilte Ziehen, in denen mehrere Stränge zusammenlaufen.
Verwandt in anderen Linien
- Komplexitätsklassen — Die Siebformel-Demo rechnet die Permanente als Summe über Spaltenmengen und nennt sie #P-schwer; warum Zählen im Allgemeinen schwerer ist als Finden, zeigt die Permanente-Demo an der Permanente gegen die Determinante.
- Exakte Suche — Die Rucksack-Tabelle der dynamischen Programmierung liefert den besten Wert; die Semiring-Demo rechnet dieselbe Rekursion in einem zweiten Semiring und liefert zusätzlich die Zahl der besten Mengen.
- Matching-Algorithmen — Die Ungarische Methode sucht die beste Zuordnung; die Siebformel-Demo zählt dagegen, wie viele Zuordnungen mit verbotenen Feldern es gibt, über Turmzahlen und das Ryser-Sieb.
- Ordnung und Abhängigkeit — Die Zulässige-Reihenfolgen-Demo zieht eine Reihenfolge eines Plans mit der Zähltabelle gleichverteilt, weil der naheliegende Zufall verzerrt; dasselbe Muster zeigt die Demo zum gleichverteilten Ziehen am naiven Gang bei Schichtfolgen.
Aufzählen und Rekursion: was man sich merken muss
Verfolgen Sie, wie sich Folgen zählen lassen, die kein verbotenes Stück enthalten, etwa Schichtfolgen ohne drei Nächte hintereinander: alle prüfen, nur gültige Anfänge erweitern oder eine Rekursion mit kleinem Gedächtnis. In einer Python-Messung schafft das Aufzählen mit Abschneiden bei etwa zehn Sekunden Wartezeit Länge 16 bis 17, die Rekursion zählt Länge 10 000 in Sekundenbruchteilen. Der Haken: Nur für Verbote zusammenhängender Teilfolgen ist gezeigt, dass das Gedächtnis klein bleibt.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Rationale erzeugende Funktion: der Nenner verrät es
Sehen Sie, wie sich die Zählfolge einer Regel zu einem Bruch aus zwei Polynomen zusammenfassen lässt: Der Nenner entsteht ohne Zählen; mit dem Zähler verrät der Bruch Rekursion, Anlauf und Wachstum. Der größte Eigenwert ist die Wachstumsrate, daraus folgt meist die Stellenzahl ferner Glieder: bei den Standardregeln 407 Stellen für n = 1000. Der Haken: Die Methode setzt einen endlichen Automaten voraus, Klammern und Bäume ergeben keinen solchen Bruch.
Demo starten →Symbolische Methode: Struktur beschreiben, Zahlen erhalten
Verfolgen Sie, wie man eine Struktur nur beschreibt (Atom, oder, und, Selbstaufruf) und die Zahlen aus der Gleichung fallen, ohne eine Rekursion zu raten: Bei Binärbäumen kommen die Catalan-Zahlen heraus, 16 796 für n = 10. Bei Verschachtelung findet das Raten bis Ordnung 12 keine Rekursion mit festen Koeffizienten. Der Haken: Die Demo rechnet nur eine Sorte unbeschrifteter Bausteine und nimmt jede Gleichung als eindeutig gemeint.
Demo starten →Semiring: dieselbe Rekursion zählt und optimiert
Sehen Sie, wie dieselbe Rekursion über ein Netz von Teillösungen zählt oder optimiert, je nachdem, was Summe und Produkt bedeuten, und die Zahl der besten Lösungen mitliefert. Bei 14 Städten hat das Rundreise-Netz 53 249 Knoten gegen 6 227 020 800 Reihenfolgen. Der Haken: Es braucht die Semiring-Gesetze und zum Zählen ein Netz, das jede Lösung einmal zeigt; bei quadratischem Strafterm rechnet ein Paar je Knoten gelegentlich falsch.
Demo starten →Multimengen und Partitionen: wenn die Reihenfolge egal ist
Verfolgen Sie, wie die erzeugende Funktion mit einem neuen Baustein die Reihenfolge ausblendet: Aus einer Tabelle, wie viele verschiedene Bausteine es je Größe gibt, folgen Zahlpartitionen, Münzwechsel und Bäume ohne Reihenfolge. Die Partitionszahl von 1000 hat 32 Stellen; die Fünfeckszahlen-Rekursion braucht etwa 15-mal weniger Additionen als das Produkt, ist aber nur etwa 5,5-mal schneller. Der Haken: Für allgemeine Tabellen gibt es diese Abkürzung nicht.
Demo starten →Beschriftete Strukturen: wenn die Bausteine Marken tragen
Sehen Sie, wie die exponentielle erzeugende Funktion zählt, wenn die Elemente verschieden sind: Mengenpartitionen mit den Bell-Zahlen, Permutationen, Derangements und Wurzelbäume. Zehn verschiedene Elemente lassen sich auf 115 975 Arten in Blöcke zerlegen, gegen 42 Zahlpartitionen der Zahl zehn. Der Haken: Beschriftet ist nicht einfach n! mal unbeschriftet, das Verhältnis fällt bei Wurzelbäumen bis n = 60 auf 0,0059.
Demo starten →Siebformel: alles zählen, das Verbotene abziehen
Verfolgen Sie, wie man Zuordnungen mit verbotenen Feldern zählt, indem man erst alle zählt und dann das Verbotene abzieht: Die Summanden verdoppeln sich mit jedem Verbot, nach der Zahl der Türme zusammengefasst bleiben wenige. Im Standardfall mit 14 verbotenen Feldern bleiben 5 Turmzahlen ungleich null. Der Haken: Bei Hamiltonkreisen im vollständigen gerichteten Graphen spart das Sieb Speicher, aber keine Zeit, es rechnet für 10 Städte etwa das 13,5-fache der Held-Karp-Schritte.
Demo starten →Zählen nach Parameter: Verteilung statt Gesamtzahl
Sehen Sie, wie eine zweite Variable in der erzeugenden Funktion mitzählt und aus der Gesamtzahl eine Verteilung macht, etwa die Zahl der Nachtschichten aller gültigen Schichtfolgen. Mittel und Streuung folgen aus Ableitungen; ein Momenten-Semiring braucht bei Länge 1000 nach der Zählregel etwa 167-mal weniger Additionen als die Verteilung. Der Haken: Die Normalverteilung ist nur gemessen, und bei den Zyklen von Permutationen fällt der Abstand bis n = 200 nicht.
Demo starten →Asymptotik: Lage und Art der Singularität
Verfolgen Sie, wie die nächste Singularität der erzeugenden Funktion die Wachstumsrate und ihre Art den polynomiellen Faktor festlegt, bei algebraischen Reihen ohne die Zahlen zu rechnen. Die Standardformel für Catalan-Zahlen liegt bei n = 100 um 1,1263 % daneben, der Fehler fällt etwa umgekehrt proportional zu n, gemessen bis n = 1000. Der Haken: Bei Bell-Zahlen und Partitionen fehlt diese Rate, der Quotient zeigt sie nicht.
Demo starten →Gleichverteilt ziehen: zählen, dann entrollen
Sehen Sie, wie man mit den Fortsetzungszahlen ein Objekt gleichverteilt unter allen zieht, ohne alle zu kennen: Jeder Schritt wird mit der Wahrscheinlichkeit der Fortsetzungen dahinter gewählt. Der naive Gang, der unter den erlaubten Schritten gleichverteilt wählt, ist verzerrt, bei Schichtfolgen der Länge 10 mit Abstand 0,363 zur Gleichverteilung. Der Haken: Würfeln und Wegwerfen kostet bei Schichtfolgen je Schritt das 1,178-fache an Versuchen, bei Dyck-Wörtern wächst es nur langsam.
Demo starten →Zwei Stränge: Symmetrie und Diagramm, am Ende die Wahl
Sechs Stücke, die auf dem Rückgrat aufbauen: Das Zählen bis auf Symmetrie setzt die beschrifteten Strukturen voraus, das Entscheidungsdiagramm den Semiring und das Ziehen. Das Schlussstück lässt alle Verfahren der Reihe auf denselben Aufgaben gegeneinander antreten.
Zwei Stränge beginnen hier. Das Zählen bis auf Symmetrie (Burnside und Pólya) zählt Bahnen von Objekten, die sich nur durch Drehen oder Umbenennen unterscheiden; der Isomorphieausschluss lässt eine Suche dann nur einen Vertreter je Bahn ausgeben. Das Frontier-Diagramm fasst dagegen gleiche Teilprobleme zusammen, ohne Symmetrie zu kennen, und ist das Gegenstück dazu (gestrichelte Kante).
Auf dem Diagramm läuft das Tutte-Polynom, das viele Zahlen eines Netzes in einem Polynom bündelt, und der Knuth-Schätzer springt ein, wo auch ein Diagramm zu groß wird. Die Verfahrenswahl führt die Verfahren der ganzen Reihe zusammen und fragt, welches wann gewinnt und woran man das misst.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Gestrichelt umrandet sind Demos aus anderen Linien: der Spielplan der Turnierplanung, Kasteleyns Determinante aus der Planarität, die zufälligen Spannbäume, die Graphfärbung, der Branch-and-Bound-Baum der Exakten Suche und der Verfahrensvergleich der Inversen Probleme. Doppelt umrandet ist die Verfahrenswahl.
Verwandt in anderen Linien
- Spannbäume — Die Spannbäume eines Gitters zählen das Diagramm der Frontier-Demo und das Tutte-Polynom ohne Aufzählen, und die Zahl wird gegen die Determinante von Kirchhoff geprüft, mit der auch die Demo zu zufälligen Spannbäumen zählt.
- Planarität und Zeichnen — Kasteleyns Determinante zählt Dominosteine nur auf planaren Graphen; die Frontier-Demo erreicht dieselben Zahlen über ein Diagramm, das für jeden Graphen gilt (gemessen sind hier Gitter), und in der Verfahrenswahl rechnet Kasteleyn in Gleitkomma ab einem Brett mit zwölf Feldern je Seite falsch.
- Turnierplanung — Die Zirkelmethode erzeugt einen Spielplan; die Demo zum Zählen bis auf Symmetrie zählt, wie viele Pläne es bis auf Umbenennen der Teams gibt (für acht Teams 6 240 Pläne in 6 Bahnen), und der Isomorphieausschluss sucht nur je einen Vertreter.
- Graphen und Netzwerke — Die Färbungs-Demo nennt die chromatische Zahl; die Tutte-Demo zählt dagegen die Färbungen mit k Farben als Einsetzung des chromatischen Polynoms.
- Exakte Suche — Die Größe eines Suchbaums wie in der Branch-and-Bound-Demo am Rucksack schätzt der Knuth-Schätzer über Zufallsabstiege, statt den Baum aufzuzählen; bei unausgeglichenen Bäumen streut diese Schätzung stark.
- Härte und Struktur — Wie groß das Diagramm der Frontier-Demo wird, hängt an der Breite der Frontier bei der gewählten Kantenordnung; welche Breite eine Eliminationsordnung für einen Graphen erreicht, zeigt die Baumweite-Demo.
- Inverse Probleme und Regularisierung — Wie hier die Zählverfahren auf denselben Aufgaben nebeneinander laufen, so treten im Verfahrensvergleich der Inversen Probleme acht Regularisierungsverfahren auf einer gemeinsamen Welt gegeneinander an.
- Netzmodelle — Wie wahrscheinlich ein gegebenes Netz zusammenhängend bleibt, wenn jede Verbindung nur mit Wahrscheinlichkeit p hält, rechnet die Tutte-Demo aus dem Polynom; die Zufallsgraph-Demo fragt, ab welchem mittleren Grad aus einem Zufallsnetz ein großes zusammenhängendes wird.
Zählen bis auf Symmetrie: Burnside und Pólya
Verfolgen Sie, wie Burnside und Pólya Objekte bis auf Symmetrie zählen: Halsketten, die man dreht, Bretter, die man wendet, Graphen, deren Knoten man umbenennt. Zwei Spielpläne, die sich nur im Umbenennen der Teams unterscheiden, zählen als einer. Der Haken: Die Faustformel Gesamtzahl durch Gruppengröße unterschätzt meist die Bahnen, der Fehler schwankt, bei Halsketten in zwei Farben 0,97 % für n = 11, aber 3,03 % für n = 12.
Demo starten →Isomorphieausschluss: Symmetrie im Suchen brechen
Sehen Sie, wie Suchen je Symmetrieklasse möglichst einen Vertreter ausgeben: Bei identischen Behältern spart die Regel, ein Teil nur in einen belegten oder den ersten leeren zu legen, bei m Behältern den Faktor m!, solange fast alle belegt sind. Die Bahnenzahl ist das Orakel dafür, was übrig bleibt. Der Haken: Zwei richtige Regeln zusammen sind nicht eindeutig, bei zehn Teilen mit vielen gleichen bleiben 247 Lösungen für 143 Bahnen.
Demo starten →Frontier und Diagramm: Lösungen zählen, ohne sie aufzuzählen
Verfolgen Sie, wie die Frontier-Methode ein Entscheidungsdiagramm Kante für Kante baut und gleiche Teilprobleme zusammenfasst: Im quadratischen Gitter mit sechs Knoten je Seite stehen 1 262 816 einfache Wege von Ecke zu Ecke in 2 323 Diagrammknoten. Dasselbe Diagramm zählt, optimiert und zieht gleichverteilt. Der Haken: Die Größe hängt an der Kantenordnung, bei vier Knoten je Seite braucht „waagerechte Kanten zuerst“ für dieselben Wege 822 statt 134 Knoten.
Demo starten →Tutte- und chromatisches Polynom: ein Polynom, viele Zahlen
Sehen Sie, wie ein einziges Polynom, das Tutte-Polynom, Spannbäume, Färbungen, azyklische Orientierungen und die Zuverlässigkeit eines Netzes in sich trägt: Es läuft über dieselben Zustände wie die Spannbäume, nur mit einem Polynom als Wert. Beim Gitter mit sechs Knoten je Seite folgen 32 565 539 635 200 Spannbäume aus 6 001 Zuständen. Der Haken: Das Tutte-Polynom ist im Allgemeinen #P-schwer, die Rechnung wächst mit der Breite der Frontier.
Demo starten →Knuth-Schätzer: wenn Zählen zu schwer ist, schätzen
Verfolgen Sie, wie ein Zufallsabstieg durch einen Suchbaum die Zahl der Wahlmöglichkeiten multipliziert und so als Mittel die Größe des Baums oder die Zahl der Lösungen schätzt. Bei den zehn Damen liegt der Median-Fehler nach 3 000 Sondierungen um 1 %. Der Haken: Unausgeglichene Bäume brechen den Schätzer ein, bei einem korrelierten Rucksack-Baum mit 24 Gegenständen liegt er nach 1 000 Sondierungen im Median gut 50 % daneben.
Demo starten →Verfahrenswahl beim Zählen: welches Verfahren, gemessen woran?
Verfolgen Sie, wie die Verfahren der Reihe auf sieben Aufgabenfamilien mit gemeinsamem Schrittzähler gegeneinander antreten, jedes in eigener Einheit: Bei 1 000 000 Schritten Budget gewinnen in 45 Paaren aus Familie und Größe zwölf Bezeichnungen (etwa sieben Grundideen), in vier keines. Schnell kann falsch sein: Kasteleyns Gleitkommaformel stimmt für Dominosteine ab zwölf Feldern je Seite nicht mehr. Der Haken: Die Aussagen gelten nur für diese Familien.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle sechzehn Stücke: Er fragt danach, was man über die Möglichkeiten wissen will und wie sie beschrieben sind, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Der Baum ordnet nach der Frage, nicht nach Güte. Wo mehrere Stücke passen, hilft die Verfahrenswahl; ihre Aussagen gelten nur für die dort gemessenen Familien und Größen.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
Online-Algorithmen
Wie man entscheidet, bevor die Zukunft bekannt ist, und was die Garantie für den schlimmsten Fall im Betrieb kostet: sieben Stücke von Mieten oder Kaufen bis zu Vorhersagen.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.