Тема 7 «Алгоритмизация и основы объективно-ориентированного программирования» (20 ч)

Урок 35. Алгоритм и его формальное исполнение

1 алгоритм from zarechneva

В учебнике дается следующее определение алгоритма:

Алгоритм - это описание детерменированной (строго определенной) конечной последовательности действий, направленных на получение из исходных данных результата за конечное число дискретных шагов с помощью понятных исполнителю команд.

Свойства алгоритма

Результативность. Возможность получения из исходных данных результата за конечное число шагов называется результативностью алгоритма.

Алгоритм сложения целых чисел в десятичной системе счисления:

1. Записать числа в столбик, так чтобы цифры самого младшего разряда чисел (единицы) расположились одна под другой (на одной вертикали).

2. Сложить цифры младшего разряда

3. Записать результат под разрядом. Если полученная сумма больше или равна 10, то перенести десяток в старший разряд.

4. Повторить пункты 2, 3 для всех разрядов

Детерминированность. Последовательность выполнения действий должна быть строго определенной . Исполнитель алгоритма, выполнив очередную команду, должен точно знать, какую команду необходимо исполнять следующей. Это свойство алгоритма называется детерминированностью.

Дискретность. Алгоритм представляет из себя конечный набор команд. Такое разбиение на отдельные простые команды называется дискретностью
 
Массовость. Один и тот же алгоритм может применяться к большому количеству однотипных объектов.

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

Определений алгоритмов много, но все они содержат вышеперечисленные свойства: конечная, четко заданная последовательность команд, приводящая к однозначному результату в однотипных задачах, понятная и выполнимая исполнителем.

Формальное выполнение алгоритмов человеком.

Исполнитель-человек может выполнять алгоритмы формально, не вникая в содержание поставленной задачи, а только строго выполняя последовательность действий, содержащихся в алгоритме.

Предположим, что пользователю необходимо в текстовом редакторе провести редактирование текста. Создадим алгоритм редактирования, в котором объектом является текст, а исполнителем - человек.

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

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

Формальная модель текста разбивает его на страницы, которые включают определенное количество строк, содержащих определенное количество символов (наш текст содержит одну строку). Алгоритм «Редактирование» запишем на естественном языке, который понятен пользователю компьютера:

1. Выделить символы с 1 по 15.
2. Вырезать этот фрагмент и поместить его в буфер обмена.
3. Установить курсор на позицию после 7-го символа.
4. Вставить вырезанный фрагмент текста.

Теперь пользователь может провести редактирование текста, формально выполнив алгоритм «Редактирование».

Выполнение алгоритмов компьютером.

Компьютер может выполнить алгоритм, если он записан на языке, понятном компьютеру. Информацию в компьютере обрабатывает процессор, следовательно, алгоритм должен быть записан на языке, «понятном» процессору, т. е. на машинном языке, представляющем собой логические последовательности нулей и единиц

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

Домашнее задание

1. Выполните задания из презентации к учебнику