Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Квантовые вычисления
14 февраля 2024 г. 13:10–14:35, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
 


Лекция 2. Схемная модель вычислений

В. И. Яшин
Видеозаписи:
MP4 3,216.6 Mb
MP4 1,443.1 Mb
Дополнительные материалы:
Adobe PDF 230.3 Kb

Количество просмотров:
Эта страница:174
Видеофайлы:73
Материалы:26
Youtube:

В. И. Яшин



Аннотация: На Лекции мы продолжили обсуждение различных свойств классических булевых схем. Любая булева операция содержит некоторое число бит на входе и на выходе. Зачастую естественно считать, что все вентили из словаря имеют конечный вход, поскольку физически реализуемые операции над битами как правило локальны. С другой стороны, поскольку классическую информацию дёшево копировать, зачастую удобно считать, что на число линий на выходе вентиля не ограниченно по $n$. Если принять такое соглашение, и если словарь универсален, то любую функцию можно реализовать за линейную глубину. Также, мы показали при помощи подсчёта, что большинство булевых функций требует экспоненциального числа операций. На протяжении курса нас часто будет интересовать не-универсальный класс афинных булевых функций. Такие функции связаны с линейной алгеброй над $\mathbb{Z}_2$ и их просто реализовывать схемами из словаря $\{\mathrm{NOT},\mathrm{XOR}\}$. Над пространством булевых функций можно ввести преобразование Уолша-Адамара-Фурье. Фурье-преобразованиями линейных булевых функций являются в точности $\delta$-функциями. При помощи семейств булевых схем возможно разрешать языки, и сложность языка определяется сложностью построения таких семейств.

Дополнительные материалы: Лекция_2_Задачи.pdf (230.3 Kb)
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024