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

UptoLike

ВУЗ: 

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

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

Рубрика: 

96
конкретных алгоритмов, особенно при их последующем программировании.
Еще важнее – уметь сравнивать различные алгоритмы решения одних и тех же
задач, причем не только по качеству решения, но и по характеристикам самих
алгоритмов (числу действий, расходу памяти и т.д.). Такое сравнение невоз-
можно без введения точного языка для обсуждения всех этих
вопросов. Т.е. са-
ми алгоритмы стали таким же предметом точного исследования, как и те объек-
ты, для работы с которыми они предназначены.
Основные требования к алгоритмам.
1. Любой алгоритм применяется к исходным данным и выдает резуль-
таты. Кроме того, в ходе работы алгоритма появляются промежуточные резуль-
таты, которые используются в
дальнейшем. Таким образом, каждый алгоритм
имеет дело с данными: входными, промежуточными и выходными. При этом
следует уточнить само понятие данных, т.е. указать, каким требованиям долж-
ны удовлетворять объекты, чтобы алгоритмы могли с ними работать.
В теории алгоритмов фиксируют конкретные конечные наборы исход-
ных объектов (называемых элементарными) и конечный набор средств
построе-
ния других объектов из элементарных. Набор элементарных объектов образует
конечный алфавит исходных символов (цифр, букв и т. д.), из которых строятся
другие объекты. Типичным средством построения являются индуктивные опре-
деления, указывающие, как строить новые объекты из уже построенных. Про-
стейшее индуктивное определение – это определение некоторого множества
слов. Слова конечной
длины в конечных алфавитах (в частности, числа) – наи-
более обычный тип алгоритмических данных, а число символов в слове (длина
слова) – естественная единица измерения объема обрабатываемой информации.
Более сложный случай алгоритмических объектов – формулы. Они также опре-
деляются индуктивно и также являются словами в конечном алфавите, однако
не каждое слово в этом алфавите
является формулой. В этом случае обычно
основным алгоритмам предшествуют вспомогательные, которые проверяют,
удовлетворяют ли исходные данные нужным требованиям. Такая проверка на-
зывается синтаксическим анализом.
2. Данные для своего размещения требуют памяти. Память обычно счи-
тается однородной и дискретной, т. е. состоит из одинаковых ячеек, каждая из
которых может содержать один символ
алфавита данных. Таким образом, еди-
ницы измерения объема данных и памяти согласованы. Отдельный вопрос – как
отводится память для каждого из трех видов данных (входных, выходных и
промежуточных).
3. Алгоритм состоит из отдельных элементарных шагов, или действий,
множество которых всегда конечно. Типичный пример множества элементар-
ных действий – система команд ЭВМ. Обычно элементарный
шаг имеет дело с
фиксированным числом символов, однако это требование не всегда выполняет-
ся. Например, в ЭВМ есть команды типа «память – память», работающие с по-
лями памяти переменной длины.

Страницы