Теория систем
<<  Параметры при обработке данных Теория систем  >>
Интерактивное доказательство в информатике
Интерактивное доказательство в информатике
Статьи, на которых построена презентация
Статьи, на которых построена презентация
Случай с математиком
Случай с математиком
Новые идеи доказательства
Новые идеи доказательства
Интерактивное доказательство
Интерактивное доказательство
Как вести интерактивное доказательство
Как вести интерактивное доказательство
Правильная раскраска графа
Правильная раскраска графа
Случайная правильная раскраска
Случайная правильная раскраска
Секретная раскраска
Секретная раскраска
Зачем нужны интерактивные доказательства
Зачем нужны интерактивные доказательства
Проверка ребра
Проверка ребра
Монетами закрыта правильная раскраска графа
Монетами закрыта правильная раскраска графа
Граф не изменился
Граф не изменился
Когда остановиться
Когда остановиться
Поговорим о случайности и теории вероятностей
Поговорим о случайности и теории вероятностей
Отвлечение
Отвлечение
Правило умножения и дополнения
Правило умножения и дополнения
Обобщение результатов
Обобщение результатов
Поговорим о пределах
Поговорим о пределах
«Замечательный предел»
«Замечательный предел»
Результат расчётов в Excel
Результат расчётов в Excel
Убедительство вместо доказательства
Убедительство вместо доказательства
Доказательство с нулевым знанием
Доказательство с нулевым знанием
Использование интерактивного доказательства на практике
Использование интерактивного доказательства на практике
Коммуникационные протоколы
Коммуникационные протоколы
Размеры баз данных
Размеры баз данных
Классификация объемов информации
Классификация объемов информации
Детерминированные протоколы
Детерминированные протоколы
Вероятностные протоколы
Вероятностные протоколы
Вероятностный коммуникационный протокол
Вероятностный коммуникационный протокол
Анализ работы протокола
Анализ работы протокола
Вероятностный коммуникационный протокол
Вероятностный коммуникационный протокол
Задача
Задача
Ответ
Ответ
Вывод
Вывод
Вероятностный коммуникационный протокол WITNESS
Вероятностный коммуникационный протокол WITNESS
Занимательные задачи по проблеме 4 красок
Занимательные задачи по проблеме 4 красок
Задача раскраски любой карты может быть поставлена математически
Задача раскраски любой карты может быть поставлена математически






Презентация «Интерактивное доказательство». Размер 3577 КБ. Автор: Segey Pozdnyakov.

Загрузка...

Интерактивное доказательство

содержание презентации «Интерактивное доказательство.ppt»
СлайдТекст
1 Интерактивное доказательство в информатике

Интерактивное доказательство в информатике

Интерактивное доказательство в информатике. Профессор кафедры ВМ-2 СПбГЭТУ «ЛЭТИ» Поздняков Сергей Николаевич.

2 Статьи, на которых построена презентация

Статьи, на которых построена презентация

Статьи, на которых построена презентация. В первой части презентации цитируется статья «Математическое доказательство: вчера,сегодня, завтра» чл.-корр. РАН Юрия Владимировича Матиясевича, который в 1970 году решил Десятую проблему Гильберта; статья опубликована в журнале «Компьютерные инструменты в образовании» Во второй части использованы материалы цикла статей Юрая Громковича и Фарида Мансуровича Аблаева «Алгоритмы и случайность», опубликованного в журнале «Компьютерные инструменты в школе».

3 Случай с математиком

Случай с математиком

Случай с математиком. Рассказывает Ю.В. Матиясевич Однажды приходит в магазин и видит новую книгу, которая называется «Теория доказательств». Мой коллега в шоке. Почему? Он следит по каталогам, что выйдет нового, и даёт рекомендации по закупке книг в библиотеку, а тут вышла книга по его прямой специальности, но он об этой книге не знал. Напоминаю, это было в советские времена, когда в магазинах не было свободного доступа к книгам, их отделял от покупателей прилавок. Мой коллега просит продавца показать ему книгу, и видит, что у названия есть набранный более мелким шприфтом подзаголовок. Полное название на следующем слайде. Какое?

4 Новые идеи доказательства

Новые идеи доказательства

Новые идеи доказательства.

5 Интерактивное доказательство

Интерактивное доказательство

Интерактивное доказательство. Это был учебник для студентов-юристов. Как видите, у них тоже есть доказательства. Чем же их доказательства отличаются от доказательств в математике? Когда математик доказывает теорему, он первым делом доказывает её для кого? – для себя. Когда математик проверил доказательство, он может показать его другому математику, который, в свою очередь, может показать доказательство третьему, и так далее. В информатике придумали так называемые интерактивные доказательства которые скорее похожи на доказательства в юриспруденции. Там, чтобы доказывать судье, что обвиняемый невиновен, адвокату вовсе не обязательно верить, что его подзащитный действительно невиновен. Задача адвоката – убедить конкретного человека в невиновности другого человека. Это доказательство по принципу «Я вам докажу». И оказывается, что подобный принцип можно ввести и в информатике.

6 Как вести интерактивное доказательство

Как вести интерактивное доказательство

Как вести интерактивное доказательство. Как вы понимаете, я не могу один провести интерактивное доказательство, поэтому у меня будет содокладчик из числа слушателей (традиционно в английской литературе участники интерактивного доказательства называются “prover” и “veri?er”). Я хочу доказать ему простую теорему: вершины моего графа можно правильным образом раскрасить в три цвета. Докладчик кладёт на слайд-проектор изображение графа.

7 Правильная раскраска графа

Правильная раскраска графа

Правильная раскраска графа. Напомню, что раскраска называется правильной, если концы каждого ребра окрашены по-разному. Конечно, я мог бы просто предъявить всем вам такую раскраску. Я действительно покажу её, но только залу, прошу содокладчика не смотреть на экран. Содоклачик встаёт спиной к экрану. Вот требуемая правильная раскраска графа. Докладчик меняет слайд.

8 Случайная правильная раскраска

Случайная правильная раскраска

Случайная правильная раскраска. Здесь 3 цвета обозначены буквами X, Y, Z. Мы можем этим буквам поставить во взаимно-однозначное соответствие реальные цвета, скажем, красный, жёлтый и зелёный. Существует 6 способов это сделать. Я бросаю кубик, выбираю случайным образом одно из 6 возможных соответствий X Красный Y Жёлтый Z Зелёный и получаю следующую раскраску.

9 Секретная раскраска

Секретная раскраска

Секретная раскраска. Я, однако, не хочу показывать эту раскраску моему содокладчику (докладчик накрывает вершины монетами) Теперь я прошу содокладчика посмотреть на экран и прежде всего убедиться в том, что это тот самый граф, про который я утверждал, что он имеет правильную раскраску вершин в 3 цвета. Содокладчик: «Да, это тот самый граф». Я спрашиваю содокладчика: «Верите ли вы, что монетами закрыта правильная раскраска графа?» Содокладчик: «Пока не очень».

10 Зачем нужны интерактивные доказательства

Зачем нужны интерактивные доказательства

Зачем нужны интерактивные доказательства. Это было интуитивное объяснение, почему в данном случае имело место нулевое знание. Для строгого обоснования надо дать определение этому понятию. Однако для начала спросим себя – зачем вообще был нужен диалог? Действительно, граф конечен, и мой соавтор мог бы сам установить, существует ли требуемая раскраска, например, путём полного перебора всех способов отобразить множество вершин в множество цветов. Но для сколько-нибудь значительного количества вершин такой перебор невозможен на самых мощных современных компьютерах, и, к сожалению, в настоящее время неизвестно существенно более эффективных методов раскраски графов (эта поблема является NP-полной).

11 Проверка ребра

Проверка ребра

Проверка ребра. Я предлагаю содокладчику: «Давайте я Вам покажу раскраску двух концов одного, какого-угодно, ребра, на Ваш выбор? Содокладчик указывает ребро, докладчик снимает монеты, покрывающие его концы, и все видят, что они действительно окрашены по- разному – в зелёный и красный цвета,

12 Монетами закрыта правильная раскраска графа

Монетами закрыта правильная раскраска графа

Вторая случайная раскраска. Я снова спрашиваю содокладчика: «Теперь-то Вы верите, что монетами закрыта правильная раскраска графа?» Содокладчик: «Ешё нет. Я видел цвета концов только одного ребра, и хотел бы проверить и другие рёбра». Я готов на это, но прошу содокладчика снова отвернуться от экрана, снова кидаю кубик, выбираю новое соответствие цветов буквам X, Y, Z X Жёлтый Y Зелёный Z Красный и получаю новую раскраску.

13 Граф не изменился

Граф не изменился

Вторая проверка. Докладчик снова накрывает вершины монетами Я опять предлагаю содокладчику проверить, что граф не изменился, и снова выбрать любое ребро. Содокладчик указывает другое ребро, докладчик снимает монеты, покрывающие его концы, и все снова видят, что они действительно окрашены по-разному – в красный и жёлтый цвета.

14 Когда остановиться

Когда остановиться

Когда остановиться? Я снова спрашиваю содокладчика: «Ну а теперь-то Вы верите, что монетами закрыта правильная раскраска графа?» Содокладчик: «Всё ещё нет. Я снова вижу цвета концов только одного ребра, и при этом я не могу быть уверен, что сейчас концы того ребра, которое я выбирал ранее, по-прежнему раскрашены по-разному» Я согласен повторить всю процедуру, включающую бросание кубика, ещё много раз. На первый взгляд кажется, что такое повторение бесполезно: в каждом раунде содокладчик видит раскраску концов только одного ребра и не может проверить, что правильность раскраски не нарушается где-либо в другом месте.

15 Поговорим о случайности и теории вероятностей

Поговорим о случайности и теории вероятностей

Отвлечение первое: поговорим о случайности и теории вероятностей. Задача де Мере о честных ставках в игре в кости. Бросаются 4 кубика (кости). Что чаще выпадает: ни одной «6» или по крайней мере одна «6».

16 Отвлечение

Отвлечение

Отвлечение первое: поговорим о случайности и теории вероятностей. Если кубик один, то «6» выпадает в одном из шести раз. Честные ставки 5:1. Если кубиков два, то «6» (по крайней мере одна) выпадает 11 раз из 36 возможных, то есть, уже не в пять раз реже, а примерно в два. Честные ставки 25:11.

17 Правило умножения и дополнения

Правило умножения и дополнения

Правило умножения и дополнения. Посчитаем для трех костей. Сопоставим каждому выпадению трех костей один из маленьких кубиков в кубе 6x6x6. Например, верхний жёлтый кубик соответствует выпадению «1» на всех трех костях. Красные кубики соответствуют случаям, когда хотя бы на одной кости выпала «6», жёлтые – случаям без «6». Жёлтых кубиков 5x5x5=125 Красных 6x6x6 – 5x5x5= = 6^3 – 5^3 = 216 – 125=91 Честные ставки 125:91.

18 Обобщение результатов

Обобщение результатов

Обобщение результатов. Для четырех кубиков можно попробовать применить тот же приём: нарисовать четырёхмерный куб 6x6x6x6, разрезать его на маленькие кубики, каждый из которых будут соответствовать одной из возможных комбинаций выпадения костей, и посчитать нужные кубики. Но проще обощить рассуждения и формулу, которая получается соединением правил «умножения» и «дополнения»: «жёлтых» кубиков 5x5x5x5=625 «красных» кубиков 6x6x6x6 – 5x5x5x5= = 6^4 – 5^4 = 1296 – 625 = 671 Каков вывод?

19 Поговорим о пределах

Поговорим о пределах

Отвлечение второе: поговорим о пределах. Можно ли предсказать какова будет величина 6^n – 5^n при бросании n кубиков? Ответ: очень большая – стремится к бесконечности. Рассмотрим тогда относительную величину выпадений тех или иных комбинаций, разделив их на общее число комбинаций. Это отношение называется «вероятностью выпадения» по крайней одной «6» при бросании n костей: p=(6^n – 5^n)/6^n=1 –(5/6)^n ? 1.

20 «Замечательный предел»

«Замечательный предел»

«Замечательный предел». Понятно, почему выражение (5/6)^n=(1 – 1/6)^n стремится к нулю: мы перемножаем числа, меньшие единицы Но что будет, если с увеличением показателя степени увеличивать основание степени? Уменьшение результата, происходящее от перемножения чисел меньше 1, будет компенсироваться увеличением перемножаемых чисел! Какой предел будет у выражения (1 – 1/n)^n ?

21 Результат расчётов в Excel

Результат расчётов в Excel

Результат расчётов в Excel. Предел (1 – 1/n)^n=1/e где e-новая константа (после знакомого уже числа «пи») e=2,71828… Примерно предел равен одной трети.

22 Убедительство вместо доказательства

Убедительство вместо доказательства

Убедительство вместо доказательства. Вернёмся к задаче про раскраску графа Пусть в графе было n рёбер, и допустим, что он не имеет правильной раскраски. Тогда вероятность обнаружения этого за один раунд не меньше, чем 1/n, если все рёбра выбираются с одинаковой вероятностью. Соответственно, вероятность обмана не больше, 1–1/n в одном раунде, и не более, чем (1–1/n)^m, если было проведено m раундов. Например, если m = 1000n, то вероятность обмана будет не больше, чем (1–1/n)^1000n = ((1–1/n)^n)^1000 ? 1/e^1000=0,0000… Таким образом, после 1000n циклов у содокладчика будет выбор между двумя альтернативами: или поверить в существование правильной раскраски, или признать, что он стал свидетелем события с ничтожно малой вероятностью.

23 Доказательство с нулевым знанием

Доказательство с нулевым знанием

Доказательство с нулевым знанием. Это был один из простейших примеров интерактивного доказательства. В нём есть такой аспект, который называется нулевое знание. Я, вроде бы, убедил содокладчика, что у рассматриваемого графа имеется правильная раскраска. Но что конкретно он узнал от меня? Для некоторых, быть может, даже для всех рёбер он узнал, что есть раскраски, в которых концы этих рёбер окрашены в такие-то конкретные цвета. Однако существование таких раскрасок является следствием существования какой-то раскраски, ибо мы всегда можем применить престановку цветов. Таким образом, я сообщил содокладчику ровно один бит информации – то, что граф имеет раскраску, но не сообщил больше ничего.

24 Использование интерактивного доказательства на практике

Использование интерактивного доказательства на практике

Использование интерактивного доказательства на практике. Задача. Имеются два компьютера, соединенные каналом связи. Назовем их Alice и Bob. Эти компьютеры оперируют с идентичными базами данных. Наша задача построить надежный и быстрый алгоритм проверки идентичности этих баз данных.

25 Коммуникационные протоколы

Коммуникационные протоколы

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

26 Размеры баз данных

Размеры баз данных

Размеры баз данных. Размеры современных баз данных огромны и продолжают расти. Крупнейшие мировые пользователи сейчас начинают внедрять системы хранения емкостью около 10–15 миллионов гигабайт (10–15 петабайт). В научно-исследовательской лаборатории IBM Алмаден в штате Калифорния разрабатывается цифровое хранилище, которое будет содержать в себе порядка 200 000 жестких дисков и иметь суммарный объем в 120 миллионов гигабайт (120 петабайт). Содержательно базы данных – это системы сложно устроенных таблиц, но с точки зрения компьютера –это последовательности битов.

27 Классификация объемов информации

Классификация объемов информации

Классификация объемов информации. Напомним двоичную шкалу классификация объема информации: бит – это один двоичный разряд, базовая единица измерения информации. Байт – единица информации, равная восьми битам. Увеличительные приставки кратны 1024=2^10, то есть килобайт равен 1024 байтам, мегабайт – 1024 килобайтам или 1 048 576=2^20 байтам, гигабайт – 2^10 мегабайтам или 2^30 байтам, терабайт – 2^10 гигабайтам или 2^40 байтам и петабайт – 2^10 терабайтам или 2^50 байтам. Пользуясь двоичной шкалой представляют информацию операционные системы компьютеров. Но в обыденной жизни нам удобна десятичная шкала классификации, поэтому часто говорят и пишут: килобайт – это тысяча байтов, мегабайт – это тысяча килобайтов, гигабайт – это тысяча мегабайтов, и т.д.

28 Детерминированные протоколы

Детерминированные протоколы

Детерминированные протоколы. Математиками доказано, что при конструировании детерминированных протоколов по сравнению содержимого компьютеров Alice и Bob требуется передавать n битов информации и этот объем передачи нельзя уменьшить ни какими предварительными вычислениями на компьютерах Alice и Bob. Вдобавок отметим, что при существующих Интернет-технологиях передача терабайтов и петабайтов информации без ошибок практически нереальна.

29 Вероятностные протоколы

Вероятностные протоколы

Вероятностные протоколы. Сейчас мы перейдём к описанию вероятностных протоколов по сравнению содержимого компьютеров Alice и Bob, которые оказываются во много раз эффективнее детерминированных.

30 Вероятностный коммуникационный протокол

Вероятностный коммуникационный протокол

Вероятностный коммуникационный протокол one-bit-WITNESS. Компьютеры Alice и Bob содержат двоичные последовательности x = x1 x2… x_n и y = y1 y2… y_n Вероятностный этап. Компьютер Alice с вероятностью 1/n выбирает число i из множества 1, 2,…, n. Детерминированный этап. Компьютер Alice отправляет компьютеру Bob выбранный номер i и один бит (0 или 1), являющийся значением x_i i-ого бита своей последовательности x. Компьютер Bob, получив от Alice бит (0 или 1), являющийся значением x_i и номер i, выполняет следующие операции: сравнивает значение полученного бита x_i-ого бита со значением y_i своего i-ого бита последовательности y Если x_i=y_i, тогда Bob выдает ответ «последовательности x и y равны. Если x_i <>y_i, тогда Bob выдает ответ «последовательности x и y не равны».

31 Анализ работы протокола

Анализ работы протокола

Анализ работы протокола one-bit-WITNESS. Первый случай. Если последовательности x и y одинаковы, то протокол one-bit-WITNESS всегда выдаст правильный ответ. Второй случай. Подсчитаем вероятность правильной работы протокола one-bit-WITNESS, если x <>y. Рассмотрим два крайних случая: (а) последовательности x и y совпадают во всех битах кроме одного и (б) у последовательностей x и y все биты различны кроме одного. В случае (а) вероятность правильного ответа «последовательности x и y не равны» равна 1/n, а вероятность ошибки (выдачи ответа «последовательности x и y равны») составляет 1–1/n. В случае (б) вероятность правильного ответа «последовательности x и y не равны» равна (n-1)/n=1–1/n, а вероятность ошибки составляет 1– (n–1)/n=1/n.

32 Вероятностный коммуникационный протокол

Вероятностный коммуникационный протокол

Вероятностный коммуникационный протокол one-bit-WITNESS(10). Определим вероятностный протокол one-bit-WITNESS(10) – модификацию протокола one-bit-WITNESS. Работа one-bit-WITNESS(10) состоит в том, что он несколько раз проводит серию независимых проверок x=y ?, запуская коммуникационный протокол one-bit-WITNESS. Если все варианты проверок заканчиваются результатом «последовательности x и y равны», то ответ протокола one-bit-WITNESS(10) будет «последовательности x и y равны». Если хотя бы один вариант проверки заканчивается результатом «последовательности x и y не равны», то ответ протокола one-bit-WITNESS(10) будет «последовательности x и y не равны».

33 Задача

Задача

Задача. Подсчитайте число передаваемых бит и вероятность правильной работы протоколов one-bit-WITNESS и one-bit-WITNESS(10), повторяющего сто раз работу протокола one-bit-WITNESS, если n=10^16, а последовательности x и y различны в 10^5 битах.

34 Ответ

Ответ

Ответ.

35 Вывод

Вывод

Вывод. Общий итог рассмотрения протокола one-bit-WITNESS и его модификации one-bit-WITNESS(10) не утешителен. При требованиях высокой надежности и экономности передачи информации они не подходят. Повторения протокола one-bit-WITNESS увеличивают вероятности правильного результата, однако, если число повторений k слишком велико (например близко к n), то мы сильно ухудшаем время работы и сильно увеличиваем общий объем пересылаемой информации. Можно ли разработать вероятностный протокол, который по числу пересылаемой информации сравним с протоколом one-bit-WITNESS и при этом во всех случаях гарантирует большую надежность?

36 Вероятностный коммуникационный протокол WITNESS

Вероятностный коммуникационный протокол WITNESS

Вероятностный коммуникационный протокол WITNESS. Такой протокол существует Читайте о нем в книге Громковича «Теоретическая информатика» или в журналах «Компьютерные инструменты в школе» за 2012 год.

37 Занимательные задачи по проблеме 4 красок

Занимательные задачи по проблеме 4 красок

Занимательные задачи по проблеме 4 красок, с которой началась лекция.

38 Задача раскраски любой карты может быть поставлена математически

Задача раскраски любой карты может быть поставлена математически

Задача раскраски любой карты может быть поставлена математически как раскраска вершин графа. В каждой области карты берется по точке – вершине графа, дугами соединяются те точки, для которых области имеют общую границу ненулевой длины (участок линии, но не точку) Далее, если раскрасить вершины графа так, чтобы соединенные ребром вершины были раскрашены по-разному, то, раскрасив соответствующие области карты в цвета этих вершин, мы получи раскраску карты, в которой любые две области, имеющие границу ненулевой длины, окрашены в разные цвета.

39

40

41

42

43

44

«Интерактивное доказательство»
Загрузка...
Сайт

5informatika.net

115 тем
5informatika.net > Теория систем > Интерактивное доказательство.ppt