Über diesen Kurs
4,586

100 % online

Beginnen Sie sofort und lernen Sie in Ihrem eigenen Tempo.

Flexible Fristen

Setzen Sie Fristen gemäß Ihrem Zeitplan zurück.

Stufe „Mittel“

Ca. 20 Stunden zum Abschließen

Englisch

Untertitel: Englisch

100 % online

Beginnen Sie sofort und lernen Sie in Ihrem eigenen Tempo.

Flexible Fristen

Setzen Sie Fristen gemäß Ihrem Zeitplan zurück.

Stufe „Mittel“

Ca. 20 Stunden zum Abschließen

Englisch

Untertitel: Englisch

Lehrplan - Was Sie in diesem Kurs lernen werden

Woche
1
2 Stunden zum Abschließen

Combinatorial Structures and OGFs

Our first lecture is about the symbolic method, where we define combinatorial constructions that we can use to define classes of combinatorial objects. The constructions are integrated with transfer theorems that lead to equations that define generating functions whose coefficients enumerate the classes. We consider numerous examples from classical combinatorics. ...
7 Videos (Gesamt 73 min), 2 Lektüren, 1 Quiz
7 Videos
Symbolic Method11m
Trees and Strings 14m
Powersets and Multisets 13m
Compositions and Partitions 15m
Substitution 6m
Exercises 3m
2 Lektüren
Getting Started10m
Exercises from Lecture 110m
1 praktische Übung
Combinatorial Structures and OGFs4m
Woche
2
2 Stunden zum Abschließen

Labelled Structures and EGFs

This lecture introduces labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. As in Lecture 1, we define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics. ...
7 Videos (Gesamt 85 min), 1 Lektüre, 1 Quiz
7 Videos
Symbolic Method for Labelled Classes 18m
Words and Strings 12m
Labelled trees 15m
Mappings 17m
Summary 4m
Exercises 2m
1 Lektüre
Exercises from Lecture 210m
1 praktische Übung
Labeled Structures and EGFs4m
Woche
3
2 Stunden zum Abschließen

Combinatorial Parameters and MGFs

This lecture describes the process of adding variables to mark parameters and then using the constructions form Lectures 1 and 2 and natural extensions of the transfer theorems to define multivariate GFs that contain information about parameters. We concentrate on bivariate generating functions (BGFs), where one variable marks the size of an object and the other marks the value of a parameter. After studying ways of computing the mean, standard deviation and other moments from BGFs, we consider several examples in some detail. ...
5 Videos (Gesamt 84 min), 1 Lektüre, 1 Quiz
5 Videos
Moment Calculations 24m
OBGF examples 17m
Labelled Classes 19m
Exercises 2m
1 Lektüre
Exercises from Lecture 310m
1 praktische Übung
Combinatorial Parameters and MGFs8m
Woche
4
2 Stunden zum Abschließen

Complex Analysis, Rational and Meromorphic Asymptotics

This week we introduce the idea of viewing generating functions as analytic objects, which leads us to asymptotic estimates of coefficients. The approach is most fruitful when we consider GFs as complex functions, so we introduce and apply basic concepts in complex analysis. We start from basic principles, so prior knowledge of complex analysis is not required. ...
6 Videos (Gesamt 109 min), 1 Lektüre, 1 Quiz
6 Videos
Complex Functions 13m
Rational Functions 19m
Analytic Functions and Complex Integration 23m
Meromorphic Functions 34m
Exercises 3m
1 Lektüre
Exercises from Lecture 410m
1 praktische Übung
Complex Analysis, Rational and Meromorphic Asymptotics4m
Woche
5
1 Stunde zum Abschließen

Applications of Rational and Meromorphic Asymptotics

We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction....
6 Videos (Gesamt 63 min), 1 Lektüre, 1 Quiz
6 Videos
Other Familiar Examples 15m
Restricted Compositions 9m
Supercritical Sequence Schema 14m
Summary 3m
Exercises 2m
1 Lektüre
Exercises from Lecture 510m
1 praktische Übung
Applications of Complex Analysis, Rational and Meromorphic Asymptotics4m
Woche
6
2 Stunden zum Abschließen

Singularity Analysis

This lecture addresses the basic Flajolet-Odlyzko theorem, where we find the domain of analyticity of the function near its dominant singularity, approximate using functions from standard scale, and then transfer to coefficient asymptotics term-by-term....
5 Videos (Gesamt 82 min), 1 Lektüre, 1 Quiz
5 Videos
Standard Function Scale 11m
Singularity Analysis 20m
Schemas and Transfer Theorems 25m
Exercises 2m
1 Lektüre
Exercises from Lecture 610m
1 praktische Übung
Singularity Analysis of Generating Functions4m
Woche
7
1 Stunde zum Abschließen

Applications of Singularity Analysis

We see how the Flajolet-Odlyzko approach leads to universal laws covering combinatorial classes built with the set, multiset, and recursive sequence constructions. Then we consider applications to many of the classic combinatorial classes that we encountered in Lectures 1 and 2....
6 Videos (Gesamt 65 min), 1 Lektüre, 1 Quiz
6 Videos
Labelled Sets 15m
Mappings 11m
Tree-like Classes 16m
Summary 3m
Exercises 2m
1 Lektüre
Exercises from Lecture 710m
1 praktische Übung
Applications of Singularity Analysis4m
Woche
8
1 Stunde zum Abschließen

Saddle Point Asymptotics

We consider the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities. As usual, we consider the application of this method to several of the classic problems introduced in Lectures 1 and 2....
5 Videos (Gesamt 63 min), 1 Quiz
5 Videos
Saddle Point Bounds 9m
Saddle Point Asymptotics 18m
Applications 5m
AC Wrap-up 11m
1 praktische Übung
Saddle-Point Asymptotics6m

Dozent

Avatar

Robert Sedgewick

William O. Baker *39 Professor of Computer Science
Computer Science

Über Princeton University

Princeton University is a private research university located in Princeton, New Jersey, United States. It is one of the eight universities of the Ivy League, and one of the nine Colonial Colleges founded before the American Revolution....

Häufig gestellte Fragen

  • Sobald Sie sich für ein Zertifikat angemeldet haben, haben Sie Zugriff auf alle Videos, Quizspiele und Programmieraufgaben (falls zutreffend). Aufgaben, die von anderen Kursteilnehmern bewertet werden, können erst dann eingereicht und überprüft werden, wenn Ihr Unterricht begonnen hat. Wenn Sie sich den Kurs anschauen möchten, ohne ihn zu kaufen, können Sie womöglich auf bestimmte Aufgaben nicht zugreifen.

Haben Sie weitere Fragen? Besuchen Sie das Hilfe-Center für Teiln..