Введение в информационные системы. Брюхомицкий Ю.А. - 97 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

97
4. Последовательность шагов алгоритма детерминирована, т. е. после
каждого шага либо указывается, какой шаг делать дальше, либо дастся команда
остановки, после чего работа алгоритма считается законченной.
5. К алгоритму предъявляется требование результативности, т. е. оста-
новки после конечного числа шагов с указанием того, что считать результатом.
Однако проверить результативность (сходимость) алгоритма
гораздо труднее,
чем требования, изложенные в п.п. 1-4. Сходимость обычно не удается устано-
вить простым просмотром описания алгоритма, а общего метода проверки схо-
димости, пригодного для любого алгоритма и любых данных не существует.
6. Следует различать:
а) описание алгоритма (инструкцию или программу);
б) механизм реализации алгоритма (например в ЭВМ), включающий
средства
пуска, остановки, реализации элементарных шагов, выдачи результа-
тов и обеспечения детерминированности, т.е. управления ходом вычисления;
в) процесс реализации алгоритма, т. е. последовательность шагов, ко-
торая будет порождена при применении алгоритма к конкретным данным.
Пример 7.1. Рассмотрим следующую задачу: дана последовательность
P из n положительных чисел (n – конечное, но произвольное число);
требуется
упорядочить их, т. е. построить последовательность R, в которой эти же числа
расположены в порядке возрастания. Почти сразу же приходит в голову сле-
дующий простой способ ее решения: просматриваем P и находим в ней наи-
меньшее число; вычеркиваем его из P и выписываем его в качестве первого
числа последовательности R
; снова обращаемся к P и снова находим в ней наи-
меньшее число; приписываем его справа к полученной части последовательно-
сти R и так далее, до тех пор, пока в последовательности P не будут вычеркнуты
все числа.
Возникает естественный вопрос: что значит «и так далее». Для большей
ясности перепишем описание способа
решения в более четкой форме, разбив
его на шаги и указав переходы между шагами.
Шаг 1. Ищем в P наименьшее число.
Шаг 2. Найденное число приписываем справа к R (в начальный момент
R пуста) и вычёркиваем его из Р.
Шаг 3. Если в Р нет чисел, то переходим к шагу 4. В противном случае
переходим
к шагу 1.
Шаг 4. Конец. Результатом считать последовательность Р, построенную
к данному моменту.
На первый взгляд такое описание алгоритма представляется достаточно
ясным, чтобы, пользуясь им однозначно получить нужный результат. Однако
это впечатление опирается на некоторые неявные предположения, к правильно-
сти которых люди привыкли, но которые нетрудно нарушить. Например, что
значит «дана
последовательность чисел»? Является ли таковой последователь-
ность
7
⌦3,
5
⌦2, (1,2)
π
? Очевидно, да, но в описании ничего не сказано, как

Страницы