Введение

Академическое подраздел информатики

В теоретической информатике и математике теория вычислений — это область, изучающая, какие задачи могут быть решены на модели вычисления с помощью алгоритма, насколько эффективно они могут быть решены или в какой степени (например, приближенные решения в сравнении с точными). Эта область делится на три основных направления: теория автоматов и формальных языков, теория вычислимости и теория вычислительной сложности, объединенные вопросом: "Каковы фундаментальные возможности и ограничения компьютеров?". Для проведения строгого исследования вычислений, ученые-компьютерщики работают с математической абстракцией компьютеров, называемой моделью вычисления. Существует несколько моделей, но наиболее часто изучаемой является машина Тьюринга. Ученые-компьютерщики изучают машину Тьюринга, поскольку её легко формализовать, анализировать и использовать для доказательства теорем, а также потому, что она представляет собой то, что многие считают наиболее мощной возможной "разумной" моделью вычисления (см. тезис Черча — Тьюринга). Может показаться, что потенциально бесконечная емкость памяти — это нереализуемый атрибут, но любая разрешимая задача, решаемая машиной Тьюринга, всегда потребует лишь конечного объема памяти. Следовательно, в принципе, любую задачу, которую можно решить (разрешить) с помощью машины Тьюринга, можно решить на компьютере с конечным объемом памяти.

История

Теорию вычислений можно рассматривать как создание моделей различного рода в области компьютерных наук. Поэтому в ней используются математика и логика. В прошлом веке она выделилась в самостоятельную научную дисциплину, отделившись от математики. К числу пионеров теории вычислений относятся Рамон Лулль, Алонзо Черч, Курт Гёдель, Алан Тьюринг, Стивен Клини, Рожа Петер, Джон фон Нейман и Клод Шеннон.

Теория формального языка

Теория языков — это раздел математики, посвященный описанию языков как набора операций над алфавитом. Она тесно связана с теорией автоматов, поскольку автоматы используются для порождения и распознавания формальных языков. Существует несколько классов формальных языков, каждый из которых допускает более сложную спецификацию, чем предыдущий, например, иерархия Хомского, и каждому из которых соответствует класс автоматов, способных его распознать. Поскольку автоматы используются в качестве моделей вычислений, формальные языки являются предпочтительным способом спецификации для любой задачи, требующей вычисления.

Теория вычислимости

Теория вычислимости в основном занимается вопросом о том, насколько проблема разрешима на компьютере. Утверждение о том, что проблема останова не может быть решена машиной Тьюринга, является одним из важнейших результатов в теории вычислимости, поскольку представляет собой пример конкретной задачи, которую легко сформулировать, но невозможно решить с помощью машины Тьюринга. Значительная часть теории вычислимости строится на основе результата, полученного для проблемы останова. Другим важным шагом в теории вычислимости стала теорема Райса, которая утверждает, что для всех нетривиальных свойств частичных функций невозможно определить, вычисляет ли машина Тьюринга частичную функцию, обладающую этим свойством. Теория вычислимости тесно связана с областью математической логики, называемой теорией рекурсии, которая снимает ограничение на изучение только моделей вычислений, сводимых к модели Тьюринга. Многие математики и теоретики вычислений, изучающие теорию рекурсии, называют её теорией вычислимости.

Теория вычислительной сложности

Теория сложности рассматривает не только возможность решения проблемы на компьютере, но и эффективность этого решения. Рассматриваются два основных аспекта: временная сложность и пространственная сложность, которые отражают соответственно количество шагов, необходимых для выполнения вычислений, и объем памяти, требуемый для этих вычислений. Чтобы проанализировать, сколько времени и памяти требует данный алгоритм, специалисты по компьютерным наукам выражают время или память, необходимые для решения проблемы, как функцию от размера входных данных. Например, поиск конкретного числа в длинном списке становится сложнее по мере увеличения размера списка. Если в списке n чисел, и список не отсортирован и не проиндексирован, то для поиска нужного числа может потребоваться проверка каждого элемента. Таким образом, для решения этой проблемы компьютеру необходимо выполнить количество шагов, которое линейно зависит от размера проблемы. Чтобы упростить анализ, специалисты по компьютерным наукам используют нотацию «Большое О», которая позволяет сравнивать функции, игнорируя особенности аппаратного обеспечения и учитывая только асимптотическое поведение при больших размерах задач. В нашем предыдущем примере можно сказать, что для решения проблемы требуется шагов. Вероятно, самая важная нерешенная проблема в информатике – вопрос о том, можно ли эффективно решить широкий класс задач, обозначаемый NP. Это обсуждается подробнее в разделе «Классы сложности P и NP», а проблема «P против NP» является одной из семи задач тысячелетия, сформулированных Институтом математики Клэя в 2000 году. Официальное описание проблемы было дано лауреатом премии Тьюринга Стивеном Куком.