Математический аппарат инженера

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

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

Прикладная теория алгоритмов мало озабочена собственно существованием алгоритмов (обычно это просто подразумевается),

- 631 -

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

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

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

Список литературы

Основы математической логики глубоко изложены в монографиях П.С. Новикова «Элементы математической логики» (М., Физматгиз, 1959) и Э. Мендельсона «Введение в математическую логику» (М., «Наука», 1971). Исторический очерк развития математической логики дан в книге А. И. Попова «Введение в математическую логику» (Изд. Ленинградского университета, 1959). Из популярной литературы можно рекомендовать книги

- 633 -

Л.А. Калужнина «Что такое математическая логика» (М., «Наука», 1964), Х. Фрейденталя «Язык логики» (М. «Наука», 1969), А. Гжегорчика «Популярная логика» (М. «Наука», 1972), Дж. Т. Калбертсона «Математика и логика цифровых устройств» (М. «Просвещение», 1965).

Теории автоматов и техническим приложениям математической логики посвящены книги В.М. Глушкова «Синтез цифровых автоматов» (М. Физматгиз, 1962), М. Айзермана и др. «Логика. Автоматы. Алогоритмы» (М. Физматгиз, 1963), А. Гилла «Введение в теорию конечных автоматов» (М. «Наука», 1966), Д.А. Поспелова «Логические методы анализа и синтеза схем» (М. «Энергия», 1968), Р. Миллера «Теория переключательных схем» (М. «Наука», Т. 1, 1970; Т. 2, 1971), А.Д. Закревского «Алгоритмы синтеза дискретных автоматов» (М. «Наука», 1971), Ю.А. Бузунова и Е.Н. Вавилова «Принципы построения цифровых вычислительных машин» (К., «Технiка», 1972).