Wir beginnen diesen Vortrag mit einem Überblick über Rekursionsbeziehungen, die uns ein direktes mathematisches Modell für die Analyse von Algorithmen bieten. Abschließend untersuchen wir das faszinierende oszillierende Verhalten der Divide-and-Conquer-Rekurrenz, die dem Mergesort-Algorithmus entspricht, und das allgemeine "Master-Theorem" für verwandte Rekurrenzen.

Seit dem 17. Jahrhundert verwenden Wissenschaftler generierende Funktionen, um Rekursionen zu lösen. Wir fahren daher mit einem Überblick über generierende Funktionen fort und betonen ihren Nutzen bei der Lösung von Problemen wie dem Zählen der Anzahl von Binärbäumen mit N Knoten.

Exakte Antworten sind oft umständlich, daher betrachten wir als nächstes einen wissenschaftlichen Ansatz zur Entwicklung von Näherungswerten, die wiederum von Mathematikern und Wissenschaftlern seit Jahrhunderten verwendet werden.

Analytische Kombinatorik. Mit einem Grundwissen über Rekursionen, erzeugende Funktionen und Asymptotik sind Sie bereit, die Grundzüge der analytischen Kombinatorik zu erlernen und zu schätzen, einem systematischen Ansatz, der viele der Details der klassischen Methoden, die wir betrachtet haben, vermeidet. Wir führen unbeschriftete und beschriftete kombinatorische Klassen ein und motivieren unseren grundlegenden Ansatz zu deren Untersuchung mit zahlreichen Beispielen.

Bäume, die Quintessenz rekursiver Strukturen, sind in der Wissenschaft allgegenwärtig und tauchen explizit in unzähligen Computeranwendungen auf. Im Lehrbuch finden Sie eine breite Abdeckung, aber die Vorlesung konzentriert sich auf die Verwendung der analytischen Kombinatorik, um verschiedene Arten von Bäumen aufzuzählen und Parameter zu untersuchen.

Die Untersuchung von Sortieralgorithmen ist die Untersuchung von Eigenschaften von Permutationen. Wir stellen analytisch-kombinatorische Ansätze zur Untersuchung von Permutationen im Zusammenhang mit dieser Beziehung vor.

Von DNA-Sequenzen bis hin zu Web-Indizes sind Strings (Zeichenketten) in modernen Computeranwendungen allgegenwärtig. Daher verwenden wir die analytische Kombinatorik, um ihre grundlegenden Eigenschaften zu untersuchen, und führen dann das Trie ein, eine wesentliche und grundlegende Struktur, die in der klassischen Kombinatorik nicht vorkommt.

Wir betrachten Zeichenketten als Mengen von Zeichen oder als Funktionen von [1..N] nach [1..M], um klassische Belegungsprobleme und ihre Anwendung auf grundlegende Hash-Algorithmen zu untersuchen. Funktionen von [1..N] nach [1..N] sind Zuordnungen, die eine interessante und komplizierte Struktur haben, die wir mit analytischer Kombinatorik untersuchen können.