на главную страницу ЛШСМ-2019 к списку курсов ЛШСМ-2019

Александр Александрович Разборов

Теория сложности вычислений

А. А. Разборов планирует провести 3 занятия.

Разнообразные алгоритмы для решения различных задач повсеместно встречаются как в науке и технике, так и в обыденной жизни. В этом курсе мы поговорим об общей дисциплине, которая занимается изучением эффективности или, если угодно, качества алгоритмов вне зависимости от их вида и происхождения.

На лекциии основной упор будет сделан на наиболее общих классических идеях; при этом наше изложение будет довольно неформальным. Мы познакомимся с тьюринговой и булевой сложностью и поговорим про вопрос P vs. NP. Последующие занятия будут посвящены более современным исследованиям, включая применения основных концепций теории сложности за пределами теории алгоритмов в строгом смысле.

Предварительных знаний для понимания курса не требуется, но заинтересованные слушатели могут заранее познакомиться с популярной статьёй докладчика на эту тему: А.А.Разборов. Теория сложности в книге «Математическая составляющая».