Прикладная теория алгоритмов мало озабочена собственно существованием алгоритмов (обычно это просто подразумевается),
- 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).