Глава 36. Алгоритмическая разрешимость

Возникает вопрос: существует ли какая-либо стандартная форма алго­ритма, решающая данный класс задач? В ряде случаев на этот вопрос теория алгоритмов дает отрицательный ответ.

Пример

Доказана неразре­шимость ряда задач: невозможность решения в радика­лах алгебраических уравнений выше четвертой степени, невозмож­ность трисекции угла с помощью циркуля и линейки и т. п.

Алгоритмическую неразрешимость следует понимать в том смыс­ле, что не существует Единого алгоритма для решения проблемы в целом. Но это вовсе не означает неразрешимость более узких классов задач данной проблемы.

С точки зрения инженерной практики проблема алгоритмичес­кой разрешимости выглядит совсем иначе, чем с позиций самой мате­матики. В силу конечности реального времени, отводимого на реше­ние задачи, и ограниченных возможностей средств вычислительной техники даже простые алгоритмы могут оказаться практически нереализуемыми, если они требуют выполнения слишком большого числа операций.

Пример

Задачи выбора оптимальных вариантов при про­ектировании, игровые задачи и алгоритмы, основанные на простом переборе и т. п.

Но в то же время алгоритмическая неразрешимость проблемы в целом не является препятствием для решения частных задач, относящихся к этой проблеме.

Пример

Среди алгебраических уравнений выше четвертой степени могут оказаться такие, которые решаются не только в радикалах, но и в целых числах. Более того, можно определить корни уравнения с достаточной для прак­тики степенью приближения, вовсе отказавшись от стремления найти решение в радикалах.

Аналогичный подход выработала практика и к задачам, которые относятся к нерешенным проблемам.

Пример

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

В отличие от алгоритмов, практические способы, исполь­зуемые для решения таких задач, относящихся к нерешенным проб­лемам, называют Псевдоалгоритмами.

< Предыдущая		Следующая >