Сложность вычислений: что это такое и зачем это нужно?

Лекция пройдёт в Культурном центре ЗИЛ.

Математическая теория компьютеров возникла ещё в 1930-е годы, то есть задолго до самих компьютеров (конец 1940-х). Была исследована теоретическая разрешимость некоторых задач с помощью этих устройств. Но с появлением компьютеров стало понятно, что важно ещё и время, необходимое для решения задач - и этим занимается теория сложности вычислений. На лекции мы рассмотрим разные её достижения на модельных примерах.