Тема 1. Введение в понятие алгоритма

1. Понятие алгоритма

Работа по решению любой задачи с использованием компьютера делится на следующие этапы:

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

2. Формализация задачи(перевод ее на язык математических формул, уравнений, отношений).

3. Построение алгоритма(составление блок-схемы, псевдокода и т.д).

4. Составление программына языке программирования.

5. Отладка и тестирование программы.

6. Проведение расчетов и анализ полученных результатов.

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

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

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

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

Слово «алгоритм» происходит от algorithmi – латинского написания имени Аль-Хорезми (787-850), выдающегося математика средневекового востока. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком.

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

Действия, которые может выполнять исполнитель называют допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя.

Алгоритмы можно подразделить на два класса: численные и логические.

Численные алгоритмы – это алгоритмы, в соответствии с которыми решение задач сводится к арифметическим действиям.

Логические алгоритмы – это алгоритмы, в соответствии с которыми решение задач сводится к логическим действиям.

Несмотря на различие в определениях, алгоритмы должны обладать определенными свойствами.

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

1. Понятность– исполнитель алгоритма должен знать как его выполнять.

2. Дискретность(прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых шагов. Каждое действие исполняется только после того, как закончилось исполнение предыдущего.

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

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

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

Формально строгие определения понятия алгоритма связаны с введением специальных математических конструкций – формальных алгоритмических систем или моделей вычислений, каковыми являются машины Поста и Тьюринга.

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

3. Формализация понятия алгоритма посредством машины Поста

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

В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Узлы, составляющие машину Поста:

• бесконечная лента, разделенная на клетки, каждая из которых может быть помечена или не помечена меткой V;

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

				_
	V	V	V		V	V

Структура Команд машины Поста:

n K m,

где n – порядковый номер команды, К – действие, выполняемое кареткой, m – номер следующей команды, подлежащей выполнению.

Команды машины Поста:

Команда	Состояние ленты
	до команды	после команды
Движение каретки на одну клетку вправо nm	_ V V V	_ V V V
Движение каретки на одну клетку влево nm	_ V V V V V	_ V V V V V
Нанесение метки из клетки, над которой находится каретка n M m	_ V	_ V V
Стирание метки из клетки, над которой находится каретка n С m	_ V V V V	_ V V V
Проверка наличия метки в клетке, над которой находится головка; если метка отсутствует, управление передается команде m1, а иначе m2 m1 m2 n	_ V V V V V V	_ V V V V V V
Остановка машины n Стоп m	_ V	_ V

Варианты окончания выполнения программы на машине Поста:

1. Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.

2. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда каретка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).

3. Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

Пример 1. Пусть задано исходное состояние каретки и требуется на пустой ленте написать две метки: одну в секцию под кареткой, вторую справа от нее.

Начальное состояние	_
1 М 2	_ V
2  3	_ V
3 M 4	_ V V
4 Стоп 4	_ V V

Пример 2. Пусть на ленте имеется запись из нескольких меток подряд и каретка находится над самой крайней меткой справа. Требуется перевести каретку влево до первой пустой позиции. (Самостоятельный чертеж на доске)

Программа будет иметь следующий вид

12

2

3 Стоп 3

Пример 3.Увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.

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

12

2

3  4

4 V 5

5 Стоп 5

(Отсканировать из информатики стр. 48-49 Информатика Могилева)

Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют:

• неделимые носители информации (клетки – биты), которые могут быть заполненными или незаполненными;

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

Обе машины работают на основе программы. Однако в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста.