«Что такое доказательство?»: взгляд из теоретической информатики Страница 1 из 3

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







Чтобы объяснить, о какого рода доказательствах пойдет речь, рассмотрим пример: есть компьютерная программа, авторы которой утверждают, что программа делает что-то определенное (конкретные примеры будут чуть позже). Программу можно запустить и получить ответ. А как можно удостовериться, что программа делает то, что должна делать? Хорошо бы, если кроме ответа программа выдавала бы доказательство того, что этот ответ правильный.

Рассмотрим более конкретный пример: мы хотим иметь программу, которая в двудольном графе находит паросочетание максимального размера вместе с доказательством его максимальности.







Напомним, что граф называется двудольным, если его вершины можно покрасить в два цвета так, что ребра графа соединяют вершины разных цветов. Паросочетанием в графе называется такое множество ребер, что никакие два из них не имеют общего конца. Множество вершин графа называется покрывающим, если каждое ребро графа имеет как минимум один конец в этом множестве. Теорема Кенига гласит, что в двудольном графе размер максимального паросочетания совпадает с размером минимального покрывающего множества. Таким образом, чтобы доказать, что паросочетание является максимальным, можно предъявить, покрывающее множество, размер которого совпадает с размером данного паросочетания. Действительно, это покрывающее множество будет минимальным, поскольку каждое покрывающее множество обязано покрыть хотя бы один конец каждого ребра этого паросочетания. Например, в графе на рисунке паросочетание (M1, G3), (M2, G2), (M4,G1) будет максимальным, поскольку есть покрывающее множество размера 3, которое состоит из G2, G3 и M4. Отметим, что проверить такое доказательство гораздо проще, чем вычислять максимальное паросочетание: достаточно проверить, что размер паросочетания совпадает с размером покрывающего множества и проверить, что все ребра покрыты.

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


  • 1034
  • 31/03/2014


Поделись



Подпишись



Смотрите также