Какими свойствами алгоритма не обладает кулинарный рецепт
САМОЕ ГЛАВНОЕ
Алгоритм — это конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости.
Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.
Один и тот же алгоритм может быть записан разными способами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д.
Для задачи, имеющей алгоритмическое решение, можно придумать множество различных способов её решения, т. е. алгоритмов. Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.
Алгоритм состоит из команд. Команда — это отдельная инструкция в описании алгоритма. Шаг алгоритма — это отдельное действие, которое исполнитель выполняет по команде. Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении.
Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффективность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.
Вопросы и задания
1. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.
2. Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает?
3. Переформулируйте описание способа проведения перпендикуляра к прямой в заданной точке так, чтобы оно стало алгоритмом.
4. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?
Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.
5. Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2.
Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа х?
6. Как известно, для каждого исполнителя набор допустимых действий всегда ограничен, иначе говоря, не может существовать исполнителя, для которого любое действие является допустимым. Докажите это утверждение, предположив, что такой исполнитель существует.
7. Перечислите известные вам способы записи алгоритмов.
8. Приведите примеры задач и оптимальных способов записи алгоритмов их решения.
9. Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму:
1) вычисляется сумма первой и второй цифр числа;
2) вычисляется сумма второй и третьей цифр числа;
3) вычисляется сумма третьей и четвёртой цифр числа;
4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел;
5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.
Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.
Опишите систему команд этого исполнителя.
Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?
Укажите минимальное и максимальное значения результата работы этого исполнителя.
При обработке некоторого числа х автомат выдаёт результат 1418. Укажите наименьшее и наибольшее значения х, при которых возможен такой результат.
10. Подготовьте краткое сообщение об одном из учёных (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.), внёсших вклад в развитие теории алгоритмов.
11. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.
12. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?
13. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.
14. Какой алгоритм считается эффективным?
15. Постройте эффективный алгоритм возведения числа х в степень n = 152.
Cкачать материалы урока
Источник
Дискретность.
Алгоритмы кулинарных рецептов состоят из отдельных действий, которые
обычно нумеруются. Разделение алгоритма на последовательность шагов
является важным свойством алгоритма и называется дискретностью.
Алгоритм должен представлять процесс решения задачи как последовательное
выполнение некоторых простых шагов. При этом для выполнения каждого шага
алгоритма требуется конечный отрезок времени, то есть преобразование исходных
данных в результат осуществляется во времени дискретно. Каждому
действию соответствует предписание (команда). Образованная
структура алгоритма оказывается дискретной: только выполнив одну команду,
исполнитель сможет приступить к выполнению следующей.
Результативность.
Алгоритмами известные из начальной школы являются правила сложения,
вычитания, умножения и деления столбиком. Применение этих алгоритмов
независимо от количества разрядов в числах и, соответственно, количества
вычислительных шагов алгоритма всегда приводит к результату.
Получение
из исходных данных результата за конечное число шагов называется результативностью алгоритма. Это
означает, что неправильный алгоритм, который не достигает цели,
вообще не нужно считать алгоритмом.
Таким образом, алгоритм
должен обеспечивать возможность получения результата после конечного, возможно,
очень большого, числа шагов. При этом результатом считается не только
обусловленный постановкой задачи ответ, но и вывод о невозможности продолжения
по какой-либо причине решения данной задачи.
Пример 2: Алгоритм сложения целых чисел в десятичной системе счисления:
- Записать числа в столбик, так чтобы цифры самого младшего разряда
чисел (единицы) расположились одна под другой (на одной вертикали). - Сложить цифры младшего разряда.
- Записать результат под горизонтальной чертой на вертикали единиц,
если при этом полученная сумма больше или равна величине основания
системы счисления (в данном случае 10), перенести десятки в старший
разряд десятков. - Повторить пункты 2 и 3 для всех разрядов с учетом переносов из младших разрядов.
Массовость.
Алгоритмы сложения, вычитания, умножения и деления могут быть применены
для любых чисел, причем не только в десятичной, но и в других
позиционных системах счисления (двоичной, восьмеричной,
шестнадцатеричной и др.). Возможность применения алгоритма к большому
количеству различных исходных данных называется массовостью. Как вы уже знаете, само слово «алгоритм» происходит от «algorithmi» – латинской формы
написания имени выдающегося математика IX века аль-Хорезми, который
сформулировал правила выполнения арифметических операций.
Таким образом, массовость
означает, что алгоритм должен обеспечивать возможность его применения для
решения любой задачи из некоторого класса задач с различными исходными данными.
Детерминированность (определенность).
При управлении самолетом используются сложные алгоритмы, исполнителями
которых являются пилот или бортовой компьютер.
Последовательность
выполнения действий, например, при взлете должна быть строго
определенной (например, нельзя отрываться от взлетной полосы, пока
самолет не набрал необходимую взлетную скорость). Исполнитель алгоритма,
выполнив очередную команду, должен точно знать, какую команду
необходимо исполнять следующей. Это свойство алгоритма называется детерминированностью. Любое
правило
(команда) алгоритма должно быть строго
и недвусмысленно определено и описано для каждого случая.
В алгоритме нет команд, смысл которых может быть истолкован
исполнителем неоднозначно; недопустимы ситуации, когда после выполнения
очередной команды исполнителю неясно, какую команду выполнять на следующем
шаге. В каждый момент времени следующий шаг работы однозначно
определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же
результат (ответ) для одних и тех же исходных данных.
Выполнимость и понятность.
После включения компьютера начинают выполняться алгоритмы тестирования
компьютера и загрузки операционной системы. Исполнителем этих алгоритмов
является компьютер, поэтому они должны быть записаны на понятном
компьютеру машинном языке.
Каждый исполнитель обладает определенным набором, системой команд, которые он может выполнить. Алгоритм должен быть понятен исполнителю, т.е. должен содержать
только те команды, которые входят в систему его команд. Алгоритм
состоит только из команд, входящих в систему команд исполнителя, т.е. из таких
команд, которые исполнитель может воспринять и по которым может выполнить
требуемые действия.
Пример 3: Рецепт заваривания кофе:
Если алгоритм обладает перечисленными выше свойствами, то
работа по нему будет производиться исполнителем формально (т.е. без всяких
элементов творчества с его стороны). На этом основана работа
программно-управляемых исполнителей, например промышленных роботов.
Робот может выполнять работу токаря, если он умеет делать все
операции токаря (включать станок, закреплять резец, перемещать резец, замерять
изделие и т.д.). От исполнителя не требуется понимание сущности алгоритма, он
должен лишь точно выполнять команды, не нарушая их последовательности.
Источник
Цель занятия: познакомить учащихся
с понятием алгоритма, исполнителями алгоритмов,
примерами алгоритмов в жизни, алгоритмическим
способом решения задач, закрепить полученные
знания с помощью электронного теста, развивать
навыки самоконтроля.
Ход урока
- Организационный момент.
- Подготовка к изучению нового материала.
(ознакомление с планом и целью занятия) . - Изучение нового материала. (просмотр
электронного урока с использованием мультимедиа
проектора) . Слайды + текст лекции. - По ходу урока учащиеся конспектируют
определения и отвечают на вопросы. - Закрепление темы занятия (работа уч-ся на
компьютере) . Электронный тест с последующей
самопроверкой. Решение алгоритмических задач. - Подведение итогов. Выставление оценок с учетом
процентного выполнения теста. - Задание на дом. (выучить определения, привести
примеры алгоритмов из жизненной практики.)
Изучение нового материала.
Один из важнейших этапов решения задач на
ЭВМ – составление алгоритма. О том, что такое
алгоритмы, какими общими свойствами они обладают
и как исполняются, мы и поговорим на этом уроке.
В 1983 году отмечалось 1200-летие со дня рождения
одного из величайших ученых Средней Азии и
средневекового Востока Мухамада ибн Мусы
аль-Хорезми. Он написал ряд трактатов по
арифметике и алгебре, в том числе книгу
“Арифметика индусскими цифрами” – о
счете с помощью десяти цифр и правилах
арифметических действий с числами.
Имя ученого аль-Хорезми превратилось в понятие
algorithmi, первоначально обозначавшее десятичную
систему исчисления и правила арифметических
действий в этой системе. Отсюда и возник
современный научный термин “алгоритм”.
Каждый из нас ежедневно использует различные
алгоритмы: инструкции, правила, рецепты и т.п.
Обычно мы это делаем не задумываясь. Например,
открывая дверь ключом, никто не размышляет над
тем, в какой последовательности выполнять
действия. Однако чтобы научить кого-нибудь
открывать дверь, придется четко указать и сами
действия, и порядок их выполнения. То же
потребуется и при указании маршрута поездки.
Сравним эти алгоритмы. На первый взгляд, между
ними нет ничего общего. Одно дело – открывать
дверь, другое – ехать в гости. Но если
приглядеться внимательно, можно заметить
существенное сходство между ними. Прежде всего,
это строгий порядок выполнения действий.
Демонстрация слайда 1.
/Приложение/
Мы можем теперь сказать, что алгоритм – это
организованная последовательность действий.
Данную формулировку, конечно, нельзя считать
определением алгоритма. Например, мы не
объяснили, что означают слова
“организованная” и “действия”. Скажем
сразу: абсолютно строгого определения алгоритма
не существует. Алгоритм – это одно из тех
основных понятий (категорий) математики, которые
не обладают формальным определением в терминах
более простых понятий, а абстрагируются
непосредственно из опыта.
На слайде еще одно задание. Выполните его,
используя для записи ответа любой текстовый
редактор или бумагу и карандаш.
Демонстрация слайда 2. /Приложение/
Сравните свой ответ с правильным.
Правильный алгоритм:
- Налить в чайник воду.
- Зажечь спичку.
- Открыть кран газовой горелки.
- Поднести спичку к горелке.
- Поставить чайник на плиту.
- Ждать, пока вода закипит.
- Выключить газ.
Демонстрация слайда 3. /Приложение/
Рассмотренные нами алгоритмы составлены для
исполнения человеком. Но человек далеко не
единственный возможный исполнитель алгоритмов.
Все живые существа и даже отдельные клетки
исполняют различные алгоритмы. Способны на это и
созданные человеком устройства –
роботы-манипуляторы и станки с программным
управлением. Но прежде чем составлять алгоритм
решения задачи, нужно узнать, какие действия
предполагаемый исполнитель способен выполнить.
Поясним сказанное на примере. Допустим, нужно
решить квадратное уравнение.
Десятикласснику требуется минимум инструкций,
потому что он уже знает способ решения.
Восьмикласснику понадобятся намного более
сложные инструкции, потому что он этого еще не
проходил.
Теперь мы можем уточнить понятие алгоритма: это
организованная последовательность действий,
допустимых для некоторого исполнителя.
Рассмотрим информационный процесс
редактирования текста. При работе с текстом
возможны различные операции: удаление,
копирование, перемещение или замена его
фрагментов. Что необходимо для того, чтобы
преобразовать текст?
- Первое. Требуется исполнитель.
- Второе. Процесс должен быть разбит на этапы,
понятные исполнителю. - Третье. Должно быть определено начальное
состояние текста и его требуемое конечное
состояние.
Теория алгоритмов имеет большое практическое
значение. Алгоритмический тип деятельности
важен не только как одна из эффективных форм
труда человека. Через алгоритмизацию, через
расчленение сложных действий на всё более
простые, на действия, выполнение которых
доступно машинам, пролегает путь к автоматизации
различных процессов.
Далее под алгоритмом будет пониматься конечная
последовательность указаний, адресованных
исполнителю, четко и однозначно задающая процесс
решения задач какого-либо типа во всех деталях и
позволяющая получить за конечное число шагов
результат, однозначно определяемый исходными
данными.
Такое свойство алгоритма, как однозначность
результата при заданных исходных данных,
называется определенностью
(детерминированностью) .
Заметим, что большинство алгоритмов могут
выполняться при достаточно разнообразных
наборах исходных данных, то есть использоваться
для решения не какой-либо одной задачи, а целого
класса подобных задач. Это свойство алгоритма
называется массовостью.
С алгоритмами человек встречается на каждом
шагу.
Пример 1. Дан угол. Необходимо провести
биссектрису. (Есть способ, как, пользуясь
линейкой и циркулем, можно решить эту задачу.)
Пример 2. Даны два целых числа. Необходимо
найти их разность. (Имеется правило, в котором
ясно изложен весь порядок действий с цифрами
данных чисел.)
В приведенных примерах речь идет о том, как
сложную работу представить в виде
последовательности простых действий. Вычитание
многоразрядных чисел сводится к действиям с
цифрами. При делении угла пополам выполняются
несложные построения линейкой и циркулем.
Однако высказанные соображения следует
дополнить. Ведь правила вычитания формулируются
для любых многоразрядных чисел, а не для каких-то
конкретных двух. Инструкция проведения
биссектрисы тоже такова, что, пользуясь ею, можно
разделить пополам любой угол. То есть каждому
алгоритму присуща массовость –
пригодность для решения не какой-либо одной, а
целого класса задач.
Далее под алгоритмом будет пониматься конечная
последовательность указаний, адресованных
исполнителю, четко и однозначно задающая процесс
решения задач какого-либо типа во всех деталях и
позволяющая получить за конечное число шагов
результат, однозначно определяемый исходными
данными.
Такое свойство алгоритма, как однозначность
результата при заданных исходных данных,
называется определенностью
(детерминированностью) .На этом занятии мы
познакомились с такими важнейшими понятиями, как
алгоритм, исполнитель, система команд
исполнителя, узнали основные свойства
алгоритма.
Закрепление темы:
Алгоритмические задачи
№1. Старик должен переправить на лодке через
реку волка, козу и капусту. Лодка может выдержать
только старика и одного “пассажира”. В каком
порядке старик перевезет пассажиров? Не забудь,
что волк может съесть козу, а коза – капусту.
Найди 2 варианта решения.
Алгоритм решения задачи:
| 1 вариант | 2 вариант |
| 1) __________________________ | 1) _________________________ |
| 2) _________________________ | 2) _________________________ |
| 3) __________________________ | 3) _________________________ |
и т.д.
№2 Два мальчика и двое взрослых должны
переправиться на другую сторону реки на плоту,
который выдерживает либо двух мальчиков, либо
одного мальчика и одного взрослого. Как
осуществить переправу? Найди несколько способов
решения этой задачи.
Алгоритм решения задачи:
| 1 способ | 2 способ | 3 способ | |
| 1 шаг | |||
| 2 шаг | |||
| 3 шаг | |||
| 4 шаг | |||
| 5 шаг |
Обозначения: 1м- один мальчик, 2м – два мальчика,
1в – один взрослый.
1. Практикум по решению задач
Злоумышленник поменял местами действия в
алгоритме вычисления среднего арифметического
из квадратного корня трёх чисел:
Присвоить а значение (а2+в2+с2)
/3.
Вести а,в,с
Сообщить “Среднее арифметическое квадратов
равно”
Сообщить а.
Восстановите правильный порядок действий.
2. Исправьте следующий алгоритм решения
уравнения (х-2) (х+2) =0:
Присвоить х значение +-2.
Сообщить “Корни уравнения равны”.
Сообщить первое значение х.
Сообщить второе значение х.
3. Автомобиль проехал три участка пути разной
длины с разными скоростями. Составьте алгоритм
нахождения средней скорости автомобиля.
4. Проснувшись утром, школьник почувствовал
недомогание. Находившийся рядом злоумышленник
тут же составил для него следующий алгоритм:
Измерить температуру.
Если температура выше 370, то:
Вызвать врача.
Пойти в школу.
Несмотря на недомогание, школьник исправил
этот алгоритм, добавив всего две строки. Какие
строки добавил школьник?
5. Запишите в виде алгоритмов правила
определения знака:
А) произведения двух действительных чисел;
Б) суммы двух действительных чисел.
6. В записи алгоритма вычисления значения
выражения (х2- 5х+5) / (х6- 4х2+3)
Злоумышленник одно действие поставил не на
свое место. Вот как стал выглядеть алгоритм:
- ввести х
- если х6- 4х2 + 3=0, то:
- сообщить “При таком х значение выражения не
определено”. - иначе:
- присвоить у значение (х2- 5х +5) /(х6-
4х2+3) . - конец ветвления.
- сообщить у.
Верните действие на свое место.
Электронный тест
1.Которые из документов являются алгоритмами?
а) Правило правописания приставок,
оканчивающихся на з,с(да)
б) Программа телепередач
в) Кулинарный рецепт приготовления блюда
г) Инструкция по сборке проданного в
разобранном виде шкафа
2. В каких случаях правильно заканчивается
предложение: Алгоритм – это
а) конечная последовательность действий,
приводящая к искомому результату при любых
допустимых исходных данных
б) указание на выполнение действий
в) конечный набор понятных некоторому
исполнителю команд, выполнение которых приводит
к однозначному решению поставленной задачи
г) программа в машинных кодах
3. Расчлененность алгоритма на отдельные
элементарные действия – это
а) Дискретность
б) Определенность
в) Массовость
г) Детерминированность
4. Которые из документов являются алгоритмами?
А) Каталог книг в библиотеке
Б) Порядок набора международного телефонного
номера
В) Рецепт приготовления клея
Г) Настенный календарь на текущий год
Подведение итогов. Выставление оценок с учетом
процентного выполнения теста.
Задание на дом. (выучить определения, привести
примеры алгоритмов из жизненной практики.)
Источник