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

Что такое алгоритм?
Каждый из нас ежедневно использует различные алгоритмы: инструкции, правила, рецепты и т.п. Обычно мы это делаем не задумываясь.
Например, открывая дверь ключом, никто не размышляет над тем, в какой последовательности выполнять действия. Однако чтобы научить кого-нибудь открывать дверь, придется четко указать и сами действия, и порядок их выполнения.
То же потребуется и при указании маршрута поездки.

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

Использование понятия "алгоритм"
В науке использовать понятия "алгоритм" начал немецкий ученый филосов, математик Лейбниц в 17-м веке.
Первые известные алгоритмы — это правила выполнения арифметических действий с числами. В них четко определены объекты (числа в десятичной записи) и элементарные шаги (сложить, вычесть, перемножить два однозначных числа).
Го́тфрид Ви́льгельм Ле́йбниц
(1646 —1716)

Эволюция значения "алгоритм"
Сначала определение понятия алгоритма было проблемой математики, однако с течением времени теория алгоритмов стала развиваться за счет влияния открытий не только в математике, но и в информатике. В настоящее время алгоритм является одним из главных понятий информатики.

Значительный вклад в развитие теории алгоритмов внесли:
Английский математик Алан Тьюринг в 1936 году предложил абстрактную вычислительную «Машину Тьюринга», которая позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследованиях
А́лан Мэ́тисон Тью́ринг
(1912 —1954)

Значительный вклад в развитие теории алгоритмов внесли:
Американский математик Эмиль Пост предложил абстрактную вычислительную машину – «Машину Поста», которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Эмиль Леон Пост
(1897 —1954)

Выдающийся американский математик Алонзо Чёрч разработал теорию лямбда-исчисление, последовавшей за его знаменитой статьёй 1936 года, в которой он показал существование «неразрешимых задач» (теорема Чёрча — Тьюринга)
Впоследствии Чёрч и Тьюринг показали, что лямбда-исчисления и машина Тьюринга имели одинаковые свойства, таким образом доказывая, что различные «механические процессы вычислений» имеют одинаковые возможности.
Alonzo Church
Алонзо Чёрч
(1903— 1995)
Значительный вклад в развитие теории алгоритмов внесли:

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

Верно ли, записан алгоритм …
Налить воду в чайник
Открыть кран газовой горелки
Поставить чайник на плиту
Ждать, пока вода не закипит
Поднести спичку к горелке
Зажечь спичку
Выключить газ

Свойства алгоритмов
Для любого алгоритма справедливы общие закономерности - свойства алгоритма

Детерминированность алгоритма
Это определенность (однозначность, единственность) толкования правил выполнения действий. То есть при задании одних и тех же исходных данных несколько раз алгоритм будет выполняться абсолютно одинаково и всегда будет получен один и тот же результат.
Пример детерминированности алгоритма - список товаров для покупки.
Как указание купить все эти товары в любом порядке.
Это недетерминированный алгоритм.
Как указание купить все эти товары
в данном порядке.
Это детерминированный алгоритм.

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

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

Формальность алгоритма
Это понятность алгоритма, каждая команда должна определять однозначное действие исполнителя, не допуская разных толкований
Пример формальности алгоритма – алгоритм мытья рук. Ребенок в детском саду, действует формально, то есть не задумываясь строго выполняет картинки-инструкции

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

Пример алгоритма
Подойти к реке.
Войти в реку.
Идти по дну, пока не выйдешь на другой берег.
Выполним ли этот алгоритм,
если человек подошёл к реке Волге?

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

Исполнитель алгоритма
- это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд

Рассмотрим пример:
Имеется исполнитель - старик. Он должен переправить на лодке через реку волка, козу и капусту.
Лодка может выдержать только старика и одного пассажира. В каком порядке старик перевезет пассажиров? Не забудь, что волк может съесть козу, а коза – капусту.
Перед нами “гипотетический” человек, который, строго руководствуясь алгоритмом, решает задачу.
Составим для данного исполнителя алгоритм решения задачи

Алгоритм решения задачи

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

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

Исполнитель
Среда исполнителя
Система команд исполнителя (СКИ)
Система отказов (ошибок) исполнителя

Система команд исполнителя (СКИ)
Команда – это указание исполнителю совершить некоторое действие.
После вызова команды исполнитель совершает соответствующее элементарное действие.
Совокупность команд из некоторого строго заданного списка, которые данный исполнитель может выполнять, называется системой команд исполнителя (СКИ).

Система команд исполнителя
(СКИ) стиральной машинки
Замачивание
Стирка
Полоскание
Отжим
Сушка

Система отказов исполнителя
Отказ «Не понимаю» возникает, если подается команда, не входящая в СКИ.
Отказ «Не могу» возникает, если команда из СКИ не может быть выполнена в конкретных условиях среды.
Стиральная машина не может выполнить команду «гладить» так как ее нет в системе команд

Среда исполнителя
- область, обстановка, условия и объекты (данные), над которыми исполнитель может выполнять действия, формируют среду исполнителя

Задача
Опишете для робота - повара среду исполнителя
Напишите для робота - повара СКИ и алгоритм приготовление чая

Решение Задачи
СКИ:
налить кипяток
помешать
налить молоко
насыпать сахар
насыпать заварку
Алгоритм :
насыпать заварку
налить кипяток
насыпать сахар
налить молоко
помешать

Вопросы:
Будет ли выполнятся алгоритм, если исполнителю вместо сахара подсунуть соль?
2. Какие команды нужно поменять местами, чтобы результат выполнения алгоритма изменился?

Типы исполнителей
Формальные
Не формальные

1.Загадай число.
2.Умножь на 5.
3.Прибавь 8.
4.Умножь на 2.
5.Отними 16.
6.Отбрось крайнюю правую цифру и получишь загаданное число.
6
6*5=30
30+8=38
38*2=76
76-16=60
6Ø → 6
Выполните
предложенные действия:
Вы выступили в роли формального исполнителя

Исполнители
Формальные Не формальные

Не формальный исполнитель
Неформальный исполнитель (экскурсовод) не может выполнять одни и те же команды (действия) совершенно одинаково.

Формальный исполнитель
Формальный исполнитель всегда одинаково выполняет одну и ту же команду.
Для каждого формального исполнителя можно указать:
• круг решаемых задач;
• среду;
• систему команд;
• систему отказов;
• режимы работы.

Режимы работы исполнителя