[Страница 50] Математический аппарат инженера (Виталий Петрович Сигорский) - Litvek

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

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

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

- 631 -

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

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

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

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

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

- 633 -

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

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

Основы многозначной логики изложены в работе С.В. Яблонского «Введение в теорию функций k-значной логики», вошедшей в монографию «Дискретная математика и математические вопросы кибернетики» (М. «Наука», 1975). Теоретические и прикладные вопросы многозначных элементов и структур рассматриваются в монографиях В.П. Сигорского и др. «Многоустойчивые элементы дискретной техники» (М. «Энергия», 1966), и Ю.Л. Иваськива «Принципы построения многозначных физических систем» (К. «Наукова думка», 1971), а также в сборниках (под рад. В.П. Сигорского) «Многозначные элементы и структуры» (М. «Советское радио», 1967) и «Многоустойчивые элементы и их применение» (М. «Сов. Радио», 1971). С методами синтеза схем на пороговых элементах можно ознакомиться по книгам М. Дертузоса «Пороговая логика» (М. «Мир», 1967) и Е.А. Бутакова «Методы синтеза релейных устройств из пороговых элементов» (М. «Энергия», 1970).

Абстрактной теории алгоритмов посвящена фундаментальная монография А.И. Мальцева «Алгоритмы и рекурсивные функции» (М. «Наука», 1965). Более популярное изложение дано в книгах: З.В. Алферова «Теория алгоритмов» (М. «Статистика», 1973) и Б.А. Трахтенброт «Алгоритмы и вычислительные автоматы» (М. «Сов. Радио», 1974). Прикладные вопросы теории алгоритмов освещены в справочнике В.Т. Кулика «Алгоритмизация объектов управления» (К. «Наукова думка», 1968).

При изучении математической логики полезно воспользоваться задачником С.Г. Гиндикина «Алгебра логики в задачах» (М. «Наука», 1972), который содержит также краткие сведения по теоретическим вопросам. Много полезных сведений читатель найдет в книге Н.И. Кондакова «Логический словарь-справочник» (М. «Наука», 1975), которая содержит обширный список литературы по математической логике.

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -