Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 7. Параллельное умножение и сложение. Коммуникационная сложность.
Обзорный курс по теоретической информатике

Что: Лекция
Когда: Понедельник, 26 октября 2020, 18:30–19:50
Где: Конференция в zoom, Онлайн

Описание

Сложение двух n-битных чисел схемой размера \(O(n)\) и глубины \(O(\log n)\). Умножение двух n-битных чисел схемой размера \(O(n^2)\) и глубины \(O(\log n)\).

Коммуникационные протоколы, комбинаторные прямоугольники. Коммуникационная сложность предиката равенства. Компромисс между временем и памятью для машины Тьюринга, решающей задачу о палиндроме.

Видео

Другие материалы

Текущая версия конспекта.