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

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 60 из 64
© 2003 Галуев Геннадий Анатольевич
лению. В настоящее время понятию алгоритма, соответствует определение. Вклю-
чающее следующие категории:
1. Алгоритм есть конечная совокупность инструкций
2. Есть некоторый механизм, воспринимающий и исполняющий инструкции.
3. Имеются средства, позволяющие хранить и фиксировать сведения о всех эта-
пах работы алгоритма, хранить промежуточные результаты и выдавать их по
мере необходимости.
4. Все
выполняемые алгоритмом действия являются дискретными.
5. Последовательность операций из которых сформирован алгоритм является де-
терминированной и в каждом шаге выполняется единственным образом.
Если алгоритмы предназначены для реализации на ЭВМ, то это определение не-
обходимо вести ограничение, накладываемые особенностями использования компью-
тера.
Возможным вариантом таких ограничений является следующий:
1. Алгоритм – А
оперирует с конкретными объектами. Эти объекты можно пере-
нумеровать.
2. А- задается конечным аргументом выходным и рабочим алфавитом.
3. В- должно быть составлено таким образом, чтобы определяемый им операции
выполнялись поэтапно.
4. В- должно быть составлено так, чтобы оно исполнялось однозначно.
5. В- должно быть исполнимо то есть применение А к
одному и тому же слову
должно приводить к одним и тем же последовательностям действий и резуль-
татам
6. В- должно быть составлено так, чтобы его исполнение не требовало информа-
ции, отличной от имеющейся во входном слове.
7. Нет никаких ограничений на длину В, длину слов и число шагов. Важно толь-
ко, чтобы они были конечными.
8. Для исполнения В требуется сколь угодно большая, но конечная память.
В целом алгоритм можно описать множеством других определений, например,
через конструктивно задеваемое соответствие в некотором алфавите, через понятие
частичного алгоритма и т.д.
Будем называть алфавитным отображением или оператором всякое соответст-
вие сопоставляющее словам некоторого
алфавита слово в том же алфавите. При на-
личии двух алфавитов первый называется входным, а второй выходным. Алфавитный
оператор называют однозначным, если он ставит в соответствие одному слову вход-
ного алфавита не более одного слова выходного алфавита. Совокупность всех вы-
ходных слов с которыми работает оператор, называется областью его определения.
Эта область может быть конечной или бесконечной. В этом случае оператор задается
в виде таблицы, во втором системой правил. Эта система должна быть конечной и за-
давать соответствие за конечное число шагов.
В алфавитном отображении (операторе) важным является понятие соответст-
вия, а не способа, которым это соответствие задано. В понятии же
алгоритма главным
является способ задания соответствия. Таким образом, это алфавитный оператор
вместе с правилами, определяющими способ его (оператор) выполнения.
Частичным алгоритмом называется
совокупность конечного числа шагов –
команд, выполняемых механически за конечное время и с оцениваемыми конечными
затратами. Примером частичного алгоритма является программа ЭВМ.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
:
: Алгоритмом называется такой частичный алгоритм, который по-
сле конечного числа шагов либо исчерпывает все команды и выдает результат, либо
выдает информацию о невозможности поучения результата.
Всевозможные уточнения приведенных и других определений алгоритма как ока-
залось, являются эквивалентными. В соответствии с упоминавшимся уже ранее тези-
сом Чёрча имеем:

Страницы