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

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

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

Доступны 3 видеозаписи курса.

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

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

Предварительных знаний для понимания курса не требуется, но заинтересованные слушатели могут заранее познакомиться с популярной статьёй докладчика на эту тему:

А.А.Разборов. Теория сложности в книге "Математическая составляющая".

Organization Committee e-mail:
dubna@mccme.ru