Формальные алгоритмы

АЛГОРИТМ

последовательность команд для исполнителя, записанная на формальном языке, приводящая к заданной цели за конечное время. Один и тот же алгоритм для разных исполнителей пишется на разных языках. Человеческие языки называются естественными. Формальный язык отличается от естественного своей строгостью записи. Очень удобным формальным языком для объяснения алгоритмов человеку являются блок-схемы.

МАШИНА ТЬЮРИНГА

Абстрактный исполнитель (абстрактная вычислительная машина).
Машина тьюринга работает по принципу: 1 или 0.

НЕРЕШЁННАЯ ЗАДАЧА ЧЕЛОВЕЧЕСТВА?

• Задачи тысячелетия - семь математических проблем, определённых Математическим институтом Клэя в 2000 году как «важные классические задачи, решение которых не найдено вот уже в течение многих лет».
• Единственная решённая гипотеза Пуанкаре.
  Считается наиболее известной проблемой топологии. Неформально говоря, она утверждает, что всякий трёхмерный «объект», обладающий некоторыми свойствами трёхмерной сферы (например, каждая петля внутри него должна быть стягиваема), обязан быть сферой с точностью до деформации.
  Премия за доказательство гипотезы Пуанкаре присуждена в 2010 году российскому математику Григорию Перельману, опубликовавшему в 2002 году серию работ, из которых следует справедливость гипотезы, но учёный отказался принять эту премию, как раньше отказался от Филдсовской премии.

РАВЕНСТВО КЛАССОВ Р И NP

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