Сложность вычислений. Лекция 2 (23.02.2021)

Моделирование РАМ на МТ и обратно. Еще раз о классах P и FP. Классы PSPACE и FPSPACE.Оценка количества шагов алгоритмов разложения на множители, быстрого возведения в степень и алгоритма Евклида.