Галуев Г.А. Математическая логика и теория алгоритмов

Подождите немного. Документ загружается.

Математическая Логика и Теория Алгоритмов стр. 61 из 64

- все уточнения интуитивного понятия алгоритма эквивалентны;

- все алгоритмы в точном определении являются одновременно и алгоритмами в

интуитивном смысле.

Алгоритмы, ставящие в соответствие одному входному своду одно выходное, называ-

ются детерминированными. Алгоритмы обладают следующими свойствами:

- Массовость, то есть способность быть применимым для решения множества

задач.

- Результативность. Это

свойство обеспечивает получение результата конечное

число шагов.

- Определенность. Это свойство обеспечивает при повторном поступлении на

вход алгоритма одного и того же слова получение одного и того же выходного

слова.

Кроме детерминированных алгоритмов существуют алгоритмы самоизменяющиеся,

которые при обработке различных слов могут изменяться, и случайные, в которых

правила могут выбираться

случайным образом.

Алгоритмические языки. Определение и классификация.

Алгоритмические языки предназначены для описания вычислительных процес-

сов, являющихся алгоритмами.

Алгоритмическим языком называется совокупность трех множеств:

1. Множество символов(алфавит языка).

2. Множество правил, позволяющих конструировать правильные сообщения в

символах алфавита(синтаксис языка).

3.Множество правил, позволяющих однозначно толковать смысл правильных

записей в символах алфавита(семантика языка).

Иногда в синтаксисе выделяют подмножество

– так называемую лексику языка,

то есть совокупность слов, допустимых в языке вместе с описанием способа их пред-

ставления. Лексика это набор правильных слов языка.

Наиболее общая классификация делит алгоритмические языки по кругу решае-

мых задач.

Например, языки для описания статистических задач, задач вычислительного харак-

тера и так далее.

Другая классификация делит алгоритмические языки на классы по степени их

зависимости от используемой ЭВМ. В этом случае различают машинно-зависимые и

машинно-независимые языки. Первые делятся на машинно-ориентированные

и ма-

шинные. Вторые – на процедурно-ориентированные и проблемно-ориентированные

языки

. Процедурно-ориентированные языки предназначены для описания алгоритмов

решения задач. При переводе программ с этих языков в машинную программу каждое

слово заменяется эквивалентным ему машинным словом. Проблемно-

ориентированные языки почти не зависят от конкретной машины. Перевод с них в

конкретный машинный язык осуществляется по принципу ''несколько слов в несколь-

ко слов''.

Перевод типа ''слово – слова'' в этих языках невозможен.

Понятие программы.

При определении понятия алгоритма мы использовали такие понятия как ко-

манда, программа и ЭВМ. Уточним в интересующем нас аспекте эти понятия.

В самом общем виде ЭВМ представляет собой автомат, состоящий из памяти и

исполнительного устройства. Исполнительного устройство может выполнять ограни-

Математическая Логика и Теория Алгоритмов стр. 62 из 64

ченный набор достаточно простых команд типа: ''найти в памяти нужное слово'', ''-

выполнить над словами операцию (сложение, умножение, вычитание, деление )'', ''-

направить результат выполнения операции в память''. Ясно, что для выполнения

сколько-нибудь сложных вычислений необходимо составить достаточно длинную по-

следовательность таких простых команд, записать их в память ЭВМ и указать после-

довательность

их выполнения исполнительным устройством. При этом, нужно позабо-

титься, чтобы в нужный момент из памяти извлекались все промежуточные результа-

ты и необходимые исходные данные. Последовательность команд, составленных с

учетом перечисленных обстоятельств, называется машинной программой

или про-

граммой составленной на языке машины.

Понятно, что вести программирование на языке машины для достаточно слож-

ных задач, достаточно длительная и громоздкая процедура. Поэтому реально про-

граммирование осуществляется с использованием рассмотренных выше алгоритмиче-

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

себя специальное устройство ЭВМ –

называемое транслятором.

Различают программы с линейной структурой, с условиями, с циклами и так далее.

Одна и та же задача, вообще говоря, может быть описана различными программами.

Все эти программы будут эквивалентными. Среди всех эквивалентных программ наи-

более эффективной считается та, которая имеет наименьшее число команд и исполь-

зует наименьший объем памяти

С учетом сказанного, в общем случае, программа – это конечное упорядоченное

множество предписаний, записанное в символах алгоритмического языка и представ-

ляющее собой такую форму записи алгоритма решения поставленной задачи, при ко-

торой обеспечивается его наиболее эффективное исполнение.

Математическая Логика и Теория Алгоритмов стр. 63 из 64

Литература.

Основная:

1. С. Клини. Математическая логика. М.: ''Мир'', 1973. стр. 480.

2. Д. Гильберт, П. Бернайс. Основания математики. Логические исчисления и

формализация арифметики. М. : ''Наука'', 1979. стр.557.

3. А. А. Марков , Н. М. Нагорный. Теория алгоритмов. М. : ''Наука''. 1984. стр. 432.

4. И. А. Лавров, Л. Л. Максимова. Задачи по теории множеств, математической ло-

гике и

теории алгоритмов. М.: ''Наука''. 1984. стр. 223.

5. Ю. Л. Ершов, Е. А . Палютин. Математическая логика. М. ''Наука''. 1979. стр.

320.

Дополнительная.

1. Чень Ч., Ли Р. математическая логика и автоматическое доказательство теорем.

М. : ''Наука''. 1983. стр. 358.

2. Мальцев А. И. Алгоритмы и рекурсивные функции. М. : ''Наука''. 1965. стр. 391.

3. Эббинхауз Г. Д. , Якобс К. и другие. Машины Тьюринга и рекурсивные функ-

ции. М. : ''Мир''. 1972. стр. 264.

Математическая Логика и Теория Алгоритмов стр. 64 из 64

Галуев Геннадий Анатольевич

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ

ПО КУРСАМ МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Ответственный за выпуск Галуев Г. А.

ЛР 200565 от 23 июня 1997г. Подписано к печати

Формат 60Х80 1/16 Бумага офсетная.

Офсетная печать. Усл. п.л. - Уч.-изд.л-

Заказ №. экз.

<<С

Издательство Таганрогского государственного

радиотехнического университета

ГСП 17А, Таганрог, 28, Некрасовский, 44

Типография Таганрогского Государственного

радиотехнического университета

ГСП 17А, Таганрог, 28, Энгельса 1