.png)
Теоретическая информатика — раздел математики, изучающий, что можно и что нельзя вычислить, передать по каналам связи, о чём можно и о чём нельзя договориться на расстоянии. Его истоки связаны с математической логикой и основаниями математики.
Теория сложности вычислений, как правило, имеет дело не с конкретными алгоритмическими задачами, а с целыми классами задач, которые объединяются в зависимости от моделей вычислений и необходимых для решения этих задач ресурсов. Широкой публике известен вопрос о равенстве классов P и NP (одна из «проблем тысячелетия»): существует ли полиномиальный по времени алгоритм для конкретной задачи — распознавания тавтологий логики высказываний. Хотя до сих пор на многие естественные вопросы ответ еще не получен, известно внушительное количество неожиданных соотношений между сложностными классами (IP=PSPACE, MIP=NEXP, PCP-теорема и др.). Более точно сложность конкретных функций изучается на языке булевых схем (это теоретическая основа микросхем) — стандартной модели вычислений, в которой сложность можно сформулировать очень точно как количество требуемых операций.
В данном направлении работают Э.А. Гирш, Д.М. Ицыксон и А.С. Куликов.
Все ли теоремы имеют короткие доказательства? Вопрос этот открыт даже в «простом» случае логики высказываний (в которой есть только логические переменные и связки), где он эквивалентен равенству сложностных классов NP и co-NP. Хотя в общем случае вопрос не разрешён, экспоненциальные нижние оценки известны для ряда конкретных систем доказательств. «Программа Кука» по изучению сложности доказательств состоит в получении новых экспоненциальных нижних оценок для всё более мощных систем доказательств. Концепции и методы, применяемые в этих системах, относятся к разнообразным областям математики: алгебре, геометрии, комбинаторике.
В данном направлении работают Э.А. Гирш и Д.М. Ицыксон.
Многие возникающие на практике задачи (например, составление расписаний, доставка грузов, верификация аппаратного и программного обеспечения) являются NP-трудными. Это, в частности, означает, что мы до сих пор не знаем алгоритмов, которые решали бы эти задачи за приемлемое в худшем случае время. Тем не менее, эти задачи надо решать — к возможным подходам относятся «слабоэкспоненциальные» алгоритмы, параметризованные алгоритмы, приближенные алгоритмы.
В данном направлении работают И.А. Близнец и А.С. Куликов.
Вычислительная геометрия — дисциплина на стыке теоретической информатики и дискретной геометрии, занимающаяся задачами о вычислениях на дискретных геометрических объектах. Её главная цель — создание доказуемо корректных и эффективных алгоритмов для таких задач, а также анализ их сложности, в частности, доказательство NP-полноты. Часто (но не всегда) задачи имеют прямое практическое применение. Часто для того, чтобы создать эффективный алгоритм, сначала требуется исследовать свойства геометрических объектов, с которыми предстоит иметь дело, что является отдельной задачей дискретной геометрии.
В данном направлении работают К.В. Вяткина и Е.А. Храмцова.
Дискретная математика, или комбинаторика, изучает самые простые структуры — конечные множества, системы их подмножеств (например, графы), конечные слова, конечные системы целых чисел и т.п. Для изучения важных и естественных вопросов о них применяются как элементарные собственно комбинаторные методы, так и теории, имеющие дело с более богатыми структурами — алгебра, теория вероятностей, топология, эргодическая теория и др. Великий математик XX века И.М. Гельфанд говорил, что комбинаторика станет центральной частью математики будущего. Взаимное проникновение дискретной и непрерывной математики сейчас столь велико и значимо, что предсказание можно назвать сбывшимся.
В данной области работают А.М. Вершик, М.В. Карев, Д.В. Карпов, Ф.В. Петров, С.А. Пузынина и Сасвата Шанниграхи.
Одной из основных задач математической логики является разработка и изучение формальных моделей различного рода языковых явлений — от семантических и грамматических проблем в естественных языках до дедуктивных и алгоритмических свойств математических теорий и семантики языков программирования. В частности, на счету математической логики формализация понятий «доказательства» и «вычислимой функции», а также получение классических результатов о дедуктивной невыводимости (например, континуум-гипотезы в рамках аксиоматической теории множеств) и алгоритмической неразрешимости (скажем, элементарной теории групп). Логические методы позволяют достаточно точно описывать синтаксис и семантику различных языков, а затем успешно изучать их как математические объекты. Математическая логика интересуется как дедуктивно-алгоритмической, так и выразительной функцией языков. Её применения разнообразны и включают среди прочего информатику, лингвистику и формальную философию. Она тесно связана с основаниями математики и информатики. К числу ключевых логических понятий относятся «доказуемость», «вычислимость», «выразимость» и «истинность».
В данной области работает С.О. Сперанский.