1.2.4. Процесс обработки данных

Обработка – процесс преобразования информации к такому виду, из которого можно получить знание.

Преобразования, производимые в процессах сбора, передачи и хранения (кодирование, сжатие и т.д.) – это перезапись одной и той же информации, представление ее в разных формах. Ничего нового из этой информации не появляется. В процессе же обработки из имеющейся информации появляется нечто новое.

Пример 1.1. Митя и Алеша вместе собрали 40 грибов. Митя собрал на 10 грибов больше, чем Алеша. Сколько грибов собрал каждый мальчик?

Для того, чтобы ответить на этот вопрос надо решить систему уравнений:

(1.1)

Решить ее, т.е. обработать данную информацию, можно, например, методом Крамера.

Шаг 1. Вычислим определитель матрицы системы  = 1(–1) – 11 = – 2. Он не равен 0, значит, система имеет решение.

Шаг 2. Вычислим определители для каждого неизвестного: _А = 10 – 40 = – 30; _М = – 40 – 10 = – 50.

Шаг 3. Вычисляем каждое неизвестное: ;

Ответ: Митя собрал 25 грибов, а Алеша – 15.

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

Как было сказано в п. 1.1, описание пошагового процесса обработки информации называется алгоритмом.

Более подробно об алгоритмах поговорим в следующей теме.

Тема 2. Алгоритмизация и программирование

2.1. Алгоритм и его свойства

Что такое алгоритм. <TBODY>Алгоритм – точная и понятная инструкция исполнителю совершить некую последовательность действий, направленных на решение поставленной задачи по обработке данных. </TBODY>

Название "алгоритм" произошло от латинской формы имени среднеазиатского математика аль-Хорезми – Algorithmi, написавшего популярную в эпоху средневековья книгу о правилах выполнения арифметических действий, т.е. об алгоритмах вычисления произведения, частного и т.д.

<TBODY>Исполнитель алгоритма — это некоторый абстрактный (воображаемый) или реальный объект, способный выполнить действия, предписываемые алгоритмом. В информатике универсальным исполнителем алгоритмов является компьютер.

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

Слова “инструкция” или “предписание” близки по смыслу слову “алгоритм”, однако они не тождественны ему. Дело в том, что не всякая инструкция может быть названа алгоритмом, поскольку он должен обладать рядом обязательных свойств, которыми произвольное предписание обладать не обязано. Перечислим эти свойства.

1) Конечность – любой алгоритм должен заканчиваться после выполнения конечного (т.е. не бесконечного) числа шагов.

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

Например, еще древние греки знали метод приближенного извлечения квадратного корня из произвольного числа а > 0. Пусть х⁽⁰⁾ – некоторое начальное приближение к . Для вычисления каждого следующего приближения построим рекуррентную формулу:

, k = 0, 1, … (2.1)

называемую алгоритмом Герона.

Вычислим с его помощью , взяв х⁽⁰⁾ = 1.5. Последовательно получим х⁽¹⁾ = 1.4166667; х⁽²⁾ = 1.4142157; х⁽³⁾ = 1.4142136; х⁽⁴⁾ = 1.4142136. Теоретически эти вычисления можно продолжать бесконечно, получая все более точный результат, поэтому формула (2.1), строго говоря, алгоритмом не является.

Для того, чтобы ее с полным правом можно было назвать алгоритмом, надо указать условие окончания вычислений. Например, можно таким условием считать совпадение определенного количества N цифр в двух последовательных значениях х^(k) и х^(k+1). Доказано, что в этом случае при использовании формулы (2.1) у всех последующих приближений первые N цифр будут такими же, как у х^(k+1). В приведенном примере у х⁽³⁾ и х⁽⁴⁾ совпали первые N = 8 цифр. Следовательно, ответ получен с точностью 10^–7, и если она нас устроит, то вычисления можно заканчивать.

2) Определенность – каждая команда алгоритма должна быть четкой, однозначной и не оставлять места для произвола.

Благодаря этому свойству выполнение алгоритма носит чисто механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

Например, не является алгоритмом такая инструкция: слегка подогрейте в маленькой кастрюле немного коньяку, добавьте специи по вкусу. Здесь слова “слегка”, “немного” и т.д. носят неопределенный характер, который каждый исполнитель может трактовать по-своему.

3) Эффективность – все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми, чтобы их в принципе можно было выполнить точно и за разумное время с помощью карандаша и бумаги. Например, нельзя считать простой операцией решение алгебраического уравнения 12-й степени. Поэтому, если в инструкции присутствует такая команда: найти решение уравнения х¹² + 5х¹¹ + 15х¹⁰ + 22х⁵ + 15258 = 0, то такая инструкция эффективной не является, а, следовательно, ее нельзя считать алгоритмом.

4) Результативность – любой алгоритм должен после своей работы выдавать какой-нибудь результат.

Возможна ситуация, что поставленная задача вообще не имеет решения. В этом случае алгоритм должен заканчиваться выдачей сообщения: “нет решения”.

5) Массовость – алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.