RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Летняя школа «Современная математика», 2009
26 июля 2009 г. 15:30, г. Дубна
 


Коммуникационная сложность. Лекция 1

А. А. Разборов
Видеозаписи:
Flash Video 479.8 Mb
MP4 479.8 Mb

Количество просмотров:
Эта страница:154
Видеофайлы:61

А. А. Разборов


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Аннотация: На марсоходе и Земле находятся два файла, которые требуется сравнить на предмет наличия расхождений. Можно ли это сделать способом менее дорогостоящим, нежели просто полностью переслав один из них?
Тот же вопрос с той разницей, что марсоходу разрешается подбрасывать монетку, а правильный ответ должен получиться с вероятностью 99.99999%?
На этот раз на Марсе и Земле составили по списку (например, возможных поломок оборудования или областей, где может находиться вода). Есть ли способ узнать о наличии в обоих списках общего элемента более экономный, чем просто переслать один из списков целиком?
И поможет ли на этот раз монетка...
Или, может быть, квантовый компьютер?
Если Вы не в состоянии сходу ответить на эти вопросы и (!!) обосновать свои ответы, приходите на занятия по коммуникационной сложности. Предварительных знаний не требуется, хотя для понимания места коммуникационной сложности в общей картине мироздания (а оно, безусловно, не сводится к развлекательным примерам) было бы полезно посещение двух первых лекций курса Ю.Л. Притыкина.
Цикл лекций

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017