Лекция 2. Элементарный асимптотический анализ

Асимптотики сумм и рекуррентных последовательностей. Теорема Штольца. Оценки и асимптотики для комбинаторных величин. Элементарные оценки факториалов, биномиальных коэффициентов и пр. Формула Стирлинга (без доказательства). Грин Д., Кнут Д. Математические методы анализа алгоритмов. М., Мир, 1989. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998. Odlyzko A. M. Asymptotic Enumeration Methods. Глава из книги Handbook of Combinatorics, vol. 2, R. L. Graham, M. Groetschel and L. Lovasz, eds., Elsevier, 1995, pp. 1063–1229. Лекция №2 в курсе “Асимптотический анализ и теория вероятностей“, осень 2016 Преподаватель курса: Александр Игоревич Храбров Страница лекции на сайте CS центра: