С. Л. Гольдштейн А. В. Кибардин информатика для физиков часть Введение Учебное пособие

ЧАСТЬ 2. Математические основы информатики

2.1 Теория формальных структур данных и алгоритмов их обработки

Основные понятия теории алгоритмов

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

• 
  выделении автономных этапов (шагов) вычислительных процессов;
  
• 
  формальной записи содержания каждого из них;
  
• 
  назначении порядка выполнения выделенных автономных этапов вычислительного процесса;
  
• 
  проверке правильности выбранного алгоритма по реализации заданного метода вычислений.
  

Результаты алгоритмизации вычислительного процесса формализуются в виде определенной вычислительной схемы, задающей алгоритм решения данной задачи.
Вычислительная схема – некоторая последовательность операций и форма записи результатов этих операций.
Чтобы подготовить какой-либо алгоритм для решения задачи на ЭВМ. необходимо его записать по определенным правилам в формализованном виде на конкретном алгоритмическом языке.
Задачи на ЭВМ решаются по заранее составленной программе. В соответствии с ГОСТ 19781-83 программа – это данные, предназначенные для управления конкретными компонентами системы обработки данных в целях реализации определенного алгоритма.
В более простом виде программой называют алгоритм, записанный на каком-либо алгоритмическом языке. Если говорить о программе для ЭВМ, то такая запись представляет собой наряду с описаниями типов и структуры данных задаваемые для ЭВМ инструкции: в какой последовательности, над какими данными и какие операции должна выполнять машина и в какой форме выдавать результат. Задание для ЭВМ таких инструкций обеспечивают операторы.
Оператор – это совокупность символов, указывающих операцию и значения или местонахождение ее операндов (данных, к которым применяется эта операция).