Об этом курсе
Недавно просмотрено: 4,213

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Промежуточный уровень

Прибл. 20 часа на выполнение

Английский

Субтитры: Английский

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Промежуточный уровень

Прибл. 20 часа на выполнение

Английский

Субтитры: Английский

Программа курса: что вы изучите

Неделя
1
2 ч. на завершение

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 видео ((всего 73 мин.)), 2 материалов для самостоятельного изучения, 1 тест
7 видео
Symbolic Method11мин
Trees and Strings 14мин
Powersets and Multisets 13мин
Compositions and Partitions 15мин
Substitution 6мин
Exercises 3мин
2 материала для самостоятельного изучения
Getting Started10мин
Exercises from Lecture 110мин
1 практическое упражнение
Combinatorial Structures and OGFs4мин
Неделя
2
2 ч. на завершение

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 видео ((всего 85 мин.)), 1 материал для самостоятельного изучения, 1 тест
7 видео
Basics13мин
Symbolic Method for Labelled Classes 18мин
Words and Strings 12мин
Labelled trees 15мин
Mappings 17мин
Summary 4мин
Exercises 2мин
1 материал для самостоятельного изучения
Exercises from Lecture 210мин
1 практическое упражнение
Labeled Structures and EGFs4мин
Неделя
3
2 ч. на завершение

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 видео ((всего 84 мин.)), 1 материал для самостоятельного изучения, 1 тест
5 видео
Basics19мин
Moment Calculations 24мин
OBGF examples 17мин
Labelled Classes 19мин
Exercises 2мин
1 материал для самостоятельного изучения
Exercises from Lecture 310мин
1 практическое упражнение
Combinatorial Parameters and MGFs8мин
Неделя
4
2 ч. на завершение

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 видео ((всего 109 мин.)), 1 материал для самостоятельного изучения, 1 тест
6 видео
Roadmap13мин
Complex Functions 13мин
Rational Functions 19мин
Analytic Functions and Complex Integration 23мин
Meromorphic Functions 34мин
Exercises 3мин
1 материал для самостоятельного изучения
Exercises from Lecture 410мин
1 практическое упражнение
Complex Analysis, Rational and Meromorphic Asymptotics4мин
Неделя
5
1 ч. на завершение

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 видео ((всего 63 мин.)), 1 материал для самостоятельного изучения, 1 тест
6 видео
Bitstrings16мин
Other Familiar Examples 15мин
Restricted Compositions 9мин
Supercritical Sequence Schema 14мин
Summary 3мин
Exercises 2мин
1 материал для самостоятельного изучения
Exercises from Lecture 510мин
1 практическое упражнение
Applications of Complex Analysis, Rational and Meromorphic Asymptotics4мин
Неделя
6
2 ч. на завершение

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 видео ((всего 82 мин.)), 1 материал для самостоятельного изучения, 1 тест
5 видео
Prelude22мин
Standard Function Scale 11мин
Singularity Analysis 20мин
Schemas and Transfer Theorems 25мин
Exercises 2мин
1 материал для самостоятельного изучения
Exercises from Lecture 610мин
1 практическое упражнение
Singularity Analysis of Generating Functions4мин
Неделя
7
1 ч. на завершение

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 видео ((всего 65 мин.)), 1 материал для самостоятельного изучения, 1 тест
6 видео
Labelled Sets 15мин
Mappings 11мин
Tree-like Classes 16мин
Summary 3мин
Exercises 2мин
1 материал для самостоятельного изучения
Exercises from Lecture 710мин
1 практическое упражнение
Applications of Singularity Analysis4мин
Неделя
8
1 ч. на завершение

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 видео ((всего 63 мин.)), 1 тест
5 видео
Saddle Point Bounds 9мин
Saddle Point Asymptotics 18мин
Applications 5мин
AC Wrap-up 11мин
1 практическое упражнение
Saddle-Point Asymptotics6мин

Преподаватели

Avatar

Robert Sedgewick

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

О Принстонский университет

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....

Часто задаваемые вопросы

  • Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.

Остались вопросы? Посетите Центр поддержки учащихся.