Файл: Богданов В.С. Системы математического обеспечения цифровых вычислительных машин учеб. пособие.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 06.08.2024

Просмотров: 46

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

— ІО -

понятиях теории алгоритмов.

Алгоритм - это. предписание, определявшее содержание и

последовательность операция, переводящих исходные данные в искомый результат. Термин "алгоритм"происходит от имени сред­ невекового (IX век) узбекского математика Аль-Хорезми, кото­ рый дал правила выполнения четырех арифметических действий в десятичной системе счисления.

Алгоритм обладает тремя свойствами:

1) определенностьв, или детерминированностьв, то есть

общепонятностьв и точностьв, не оставлявшими места для произ­

вола

или

двоякого

толкования;

 

 

 

 

 

2)

массовостью, то есть возможностью

исходить из

любых ■

исходных данных,

принадлежащих

некоторому,

довольно

обшир­

ному

(иногда даже

бесконечному)

множеству

А

исходных данных

 

3) результативностью, то есть свойством

определять про­

цесс, который для любых допустимых исходных данных, пркяадле­ жащих множеству А , приводит к получению искомого результа­

та,

для алгоритмов характерны таісзе дискретность определяе­ мого ими процесса и простота операций, выполняемых на каждом шагу.

Пример. Алгоритм распознавания символа по номеру места. Задана бесконечная последовательность единиц и нулей.

:І:0 :0 :І:0 :С :0 :0 :І:0 :0 :0 :0 :0 :0 :І:0 :0 :0 : ..

Изучив первые несколько

с и ы е о л о в , можно заметить, что едини­

цы стоят з тех местах,

номера которых соответствуют квадра-

- I I -

там целых чисел. На основании этого можно продлить последова­

тельность до сколь угодно большего номера.

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

Приведенное выше определение алгоритма является содержа­ тельным. Оно не может служить основой для математического ис­ следования, поскольку неясно, что строго понимается под ис -

ходными данными, результатом и общепонятностью. Дать же пояс­

нение слов невозможно, так как потребуются новые пояснения. '

Неясность содержательного описания алгоритма послужило толч­

ком к создании работ по уточнений понятия алгоритма. Несмот­

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

Слово - любая конечная последовательность букв некоторо­

го алфавита. Например, а, аввсва, . . . .

Алфавит - конечный набор поиарно различных символов.

Например, £а, в, с,

I , —

 

Теперь дадим понятие' эквивалентности алгоритмов.

 

. Два алгоритма

и Ag в некотором алфавите d

называ­

ются, эквивалентными,

если совпадают области их применимости

и результаты переработки пии любого слова из общей области применимости. Иначе говоря, если алгоритм Ajприменим к неко­ торому слову Рр то и Ag может быть применим к этому слову , причем оба алгоритма А-£ и должны перерабатывать слово Р в некоторое слово Q. ; . Если же один из алгоритмов не применим

'

- 12 -

О • к некоторому слову В, то и другой не может быть применим к нему.

Одним из уточнений понятия алгоритма является понятие

нормального алгоритма Маркова £ 2 J . Уточнение понятия алго­

ритма Марковым базируется на использовании основного тезиса' теории алгоритмов. Основной тезис - это гипотеза, предполага­

ющая, что всякий алгоритм в алфавите

А эквивалентен

некоторо­

му нормальному алгоритму в этом же алфавите.

 

 

Основной

тезис не

может быть доказан,

так как,

с одной

стороны, здесь

имеется

расплывчатое

понятие

"всякий

алгоритм?

а с другой стороны - точное понятие

"нормальный

алгоритм".

 

 

\

 

 

 

 

 

Однако на него можно смотреть как на закон,

который не

только

не опровергнут,

но и подтвержден всем опытом исполь­

зования

вычислительных

машин.

 

 

 

 

 

§ 3. Определение нормального алгоритма Маркова

 

Задается алфавит А и фиксируется схема подстановок-. Ал­

горитм предписывает,

исходя из произвольного слова Р в алфа­

вите

А,' просмотреть

формулы подставок в том порядке, в

каком

они заданы в схеме,

разыскивая формулу с

левой частью,

входя­

щей в Р. Если такой

формулы не

найдется,

то процесс обривает­

с я ;

в противном случае берется

пзрвая из

таких формул и дела­

ется подстановка ее правой части вместо первого вхождения ее левой части в Р, что дает новоеѵслово Pj в том же алфавите А. Затем переходят к следувщеыу шагу, подразумевая вгшсто слова

-13 -

Р- Pj и т.д . до тех пор, пока не придется оборвать процесс. Оборваться же он монет лишь двумя способами: во-первых, ког­

да будет получено такое слово Рд

 

, что пи одна из левых, час-

.тей формул схемы подстановок не будет в него входить;

во-

вторых,

когда при получении

слова

Рд

придется применить по--

следняй формулу.

 

 

 

 

 

 

Поясним понятие "первое вхождение левой части формулы

подстановок в некоторое слово Р '.

 

 

 

 

 

Рассмотрим два слова

и d

l в

некотором алфавите А.

Если

является частью олова d

l

■, то говорят, что слово t t

входит

в слово d l f или что имеется вхояденкз слова

è t

в сло­

во d l

. В качестве примера моено привести два слова -У-СІС

и dl^ßßacaS. ъ общем случае

è t

монет

входить в слово

d l

несколько раз, так как слово

ßc5

 

входит в слово Qücßc6üß

два раза.

 

 

 

 

 

 

Различные нормальные алгоритмы отягчаются друг

от друга

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

дать алфавит и-систему подстановок. '

 

Пример нормального алгоритма Маркова:

 

J

I)

.1 + — *■-+ I

 

АЛ -А +

*■.I

 

J d = I

А = fi.+ J?)

+1

Система подстано-

 

 

3)

I

— ^ -

Б0К*

Здесь стрелки обозначают, что задан алгоритм Наркоза.

Отыщем слово

а

. в которое перерабатывает алгоритм Ат

некоторое слово Р = -^iii * і і

* ij" .

 

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

просматривая

сверху вниз систему под -

- 14 -

стаковок и разыскивая формулы, левые части которых входят в слово Р,и последовательно получающиеся слова Р^- , и подстав­ ляя их правые части вместо вхождения, получим последователь-

■ность слов:

I )

+І1Ш+1

+11ІІ+І1 У і - я подстановка ; +11І+1І1 ■гІІ+іИі +І+Ш І1

^ /

2-я подстановка;

я подстановка.

Q

Данный алгоритм суммиру­ ет число единиц, то есть осуществляет сложение.

Искомое слово

Подробнее с алгоритмами Маркова модно познакомиться в литера­ туре [ 2 ] .

§ 4. Машина Тьюринга

Другое уточнение понятия алгоритма связано со строго формализованным описанием так называемой машины Тьюринга [YJ.

Тьюринг предложил, что в силу того, что алгоритм облада­ ет з?реыя свойствами - детерминированностью, массовостью и ре­ зультативностью, совершенно безразлично, кто его использует:

- 15 -

человек или некоторая машина. Из основных свойств алгоритма вытекают требования к такой машине:

1) она долнна. быть полностью детерминированной, то есть однозначно действовать в соответствии с заданной системой пра­

вил ;

2)допускать ввод различных начальных данных, соответст­ вующих различным задачам данного класса;

3)система правил работы машины и класс задач должны быть согласованы так, чтобы всегда можно было прочитать результат

работы машины.

Уточнение понятия алгоритма Тьюринга также базируется

на основном тезисе теории алгоритмов, согласно которому для всякого алгоритма можно построить некоторую эквивалентную ма­ шину Тьюринга.

Машина Тьюринга (1936-1937 г г .)

- это абстрактное поня­

тие вычислительной машины. Ее работа

напоминает действия вы­

числителя, который, не будучи в состоянии обозреть всю, часто очень громоздкую, систему данных и предписаний, производит каждый раз лишь элементарное действие,' причем только над не­ которой восприЕГмаемой им частью данных.

Машина Тьюринга (см .рис.I) состоит из бесконечной в обо­

их направлениях ленты (материал не оговаривается), разделен­

ной вдоль на клетки. Каждая клетка либо пуста, либо в ней на­

печатан один из символов

взятый из заданного алфавита

 

Пустой клетке соответствует сим-

Число напечатанных символов конечно, но может быть сколь

- 1 6

угодно велико.

Ііашина Тьюринга включает считывавшую (С) и записывающую

(3) головни* которые могут дискретно перемещаться на I ячей­

ку вправо или влево, а также оставаться на месте. Команды на передвижение подаются от управляющего устройства, которое по­

лучает входные сигналы от считывающей головки и может пода­ вать сигнал в записывающую голоьку на стирание или печатание

любого из

синволоз алфавита

і5 в соответствии с

внутренним

состоянием

(Ji .

 

 

 

Управляющее устройство имеет конечное число

fT)+l внут­

ренних состояний

=

и работает в дискретном

времена £ . = О, I ,

2,

 

 

 

 

 

 

 

- 17 -

 

 

 

 

 

 

Таким образом,

УУ является

машиной с

внутренней памятью,

имеющей ГП+1 состояний, входом,

воспринимающим символы

 

,

и двумя выходами,

один из которых выдает

сигналы из алфавита

Л, П, С,

другой -

сигналы из

алфавита S

на

запись

соответст­

вующих символов

і5^ на ленту.

 

 

 

 

 

 

 

 

 

О

 

 

 

 

описана при помощи таблично-

Машина Тьюринга может быть

-заданной функции с /77 строками, число которых равно числу

активных

состояний

с

УУ и /7+ і

столбцами,

число которых рав­

но числу

символов в

алфавите

S' ,

включая пустой

символ St0 .

Строка,

соответствующая символу

(£а , отсутствует,

так

как он

соответствует состоянию покоя.. Некоторой

комбинации

 

<5/

на выходе УУ будет соответствовать

управляющий сигнал

типа

^

, f l

или

c^gSffA, fy S x C .

 

 

 

 

 

 

При некотором входном сигнале

S>J и состоянии покоя

(£0

на выходе будет всегда управляющий

сигнал (^0Sj С , что

оз­

начает прежнее

состояние покоя;

головки

остаются на месте,

на считываемой клетке записывается тот же символ

S1) *

 

Пример машины Тьюринга. Алфавит Н * Л

состояния

-

Гі

Описание алгоритма работы. Машина стирает единицу в той ячейке, где находится головка (если эта ячейка не пуста); или в пер­ вой слева непустой ячейке, передвигает головку на ячейку ле­ вее и останавливается.

ГОС. ПУБЛИЧНАЯ

НАУчі :о -техы ичесная

БИБЛИОі£НА ССОР

Смотрите также файлы