Алгоритмы и исполнители

АЛГОРИТМЫ  И ИСПОЛНИТЕЛИ ОСНОВЫ АЛГОРИТМИЗАЦИИ

Ключевые слова • алгоритм • свойства алгоритма • дискретность • понятность • определённость • результативность • массовость • исполнитель • характеристики исполнителя • круг решаемых задач • среда • режим работы • система команд • формальное исполнение алгоритма

Примеры алгоритмов Пополнение счёта телефона через терминал  1) Подойти к терминалу по оплате  платежей 2) Выбрать оператора связи 3) Ввести номер телефона 4) Проверить правильность введённого  номера 5) Вставить денежную купюру в  купюроприёмник 6) Дождаться сообщения о зачислении  денег на счёт 7) Получить чек

Примеры алгоритмов Рисование лошади

Примеры алгоритмов Вычислительный алгоритм Среднее арифметическое двух чисел 1. Задать два числа 2. Сложить заданные числа 3. Разделить сумму на 2 Общая схема работы алгоритма Исходные данные Алгоритм Результат 1.Задать два числа2.Сложить заданные числа3.Разделить сумму на 2Среднее арифметическое двух чисел

Исполнитель алгоритма Исполнитель ­ это некоторый объект (человек, животное,  выполнять  устройство),  техническое  определённый набор команд. способный  Исполнитель  Формальный  Неформальный Круг решаемых задач Среда исполнителя Область, обстановка, условия СКИ Непосредственное управление Режимы работы Программное управление Исполнители алгоритмов Ôàéë "SWF" Формальный НеформальныйИсполнитель Круг решаемых задачСреда исполнителяРежимы работыИсполнители алгоритмовСКИ

Исполнитель Робот

Исполнитель Кузнечик

Разработка алгоритма Разработка алгоритма  Определение объектов,  указанных в задаче Установление свойств объектов, отношений и действий с объектами Определение исходных  данных и результата Определение  последовательности действий  Запись  последовательности действий с помощью команд СКИ  Алгоритм – модель деятельности исполнителя  алгоритмов Разработка алгоритма

Свойства алгоритма Свойства алгоритма Дискретность   Путь решения задачи разделён на отдельные шаги Понятность   Определённость  Алгоритм состоит из команд, входящих в СКИ Команды понимаются однозначно   Результативность  Обеспечивается получение  ожидаемого результата Массовость    Обеспечивается решение задач с различными исходными данными Свойства алгоритмаДискретность  Понятность  Определённость Результативность Массовость

Дискретность  (от  лат.  discretus  –  разделенный,  прерывистый)  означает,  что  путь  решения  задачи  разделён  на  отдельные  шаги  (действия).  Каждому  действию  соответствует  предписание  (команда).  Только  выполнив  одну  к  выполнению следующей.  приступить  команду,  исполнитель  сможет  да a = x Начало x, y  x > y a Конец не т a = y

Понятность  означает,  что  алгоритм  состоит  только  из  команд,  входящих  в  систему  команд  исполнителя,  т.  е.  из  таких  команд,  которые  исполнитель  может  воспринять  и  по  которым может выполнить требуемые действия. Окрошка «Мясная» 1­1.5 л кваса 500 г картофеля 300 г колбасы 3 яйца 200 г редиса 300 г огурцов зелень по вкусу сметана соль перец Рецепт приготовления Картофель отварить до готовности. Остудить, почистить. Нарезать кубиками. Колбасу нарезать кубиками. Яйца нарезать кубиками. Редис тонко нарезать. Огурцы нарезать кубиками. Смешать картофель, колбасу, яйца,  редис, огурцы. Посолить, поперчить. Выложить в тарелки. Залить квасом, посыпать зеленью. Подавать со сметаной.

Определённость  означает,  что  в  алгоритме  нет  команд,  смысл  которых  может  быть  истолкован  исполнителем  неоднозначно;  после  выполнения  очередной  команды  исполнителю  неясно,  какую  команду выполнять на следующем шаге. недопустимы  ситуации,  когда  Доехать до стадиона 1. Идти прямо 2. Повернуть 3. Идти прямо 4. Сесть в автобус 5. Доехать до остановки «Стадион» Данная последовательность действий не обладает свойством  определённости! Какое расстояние нужно пройти прямо? В какую сторону повернуть? В какой автобус сесть?

Результативность  означает,  что  алгоритм  должен  обеспечивать  возможность  получения  результата  после  конечного, возможно, очень большого, числа шагов. При этом  результатом  обусловленный  постановкой  задачи  ответ,  но  и  вывод  о  невозможности  продолжения по какой­либо причине решения данной задачи. считается  только  не  Чтение книги 1. Взять книгу 2. Открыть первую страницу 3. Пока не конец книги выполнять  следующие действия: 3.1 Прочитать текст 3.2 Перелистнуть страницу 3.3 Прочитать текст 3.4 Открыть первую страницу Данная  последовательность  не  обладает свойством результативности. Что нужно  изменить? команд

Массовость означает, что алгоритм должен обеспечивать  возможность  его  применения  для  решения  любой  задачи  из  некоторого класса задач с различными исходными данными. Алгоритм вычисления корней квадратного уравнения.   b x 2,1   4 ac 2 b a 2 Начало Ввод  коэффициентов Вычисление дискриминанта Дискриминант меньше 0? да не т Вычисление значений корней  Вывод корней «Корней нет» Конец

Решето Эратосфена Решето Эратосфена Ôàéë "SWF" Рассмотренная  последовательность  действий  является  алгоритмом, так как она удовлетворяет свойствам: •дискретности  ­  процесс  нахождения  простых  чисел  разбит на шаги; •понятности ­ каждая команда понятна ученику 8 класса,  выполняющему этот алгоритм; •определённости  ­  каждая  команда  трактуется  и  выполняется исполнителем однозначно; имеются указания  об очерёдности выполнения команд; ­  через  некоторое  число  шагов  •результативности  достигается результат; •массовости  ­  последовательность  действий  применима  для любого натурального n. Решето Эратосфена

­  Алгоритм  это  предназначенное  для  описание  исполнителя  конкретного  последовательности  действий,  приводящих  от  исходных  данных  к  требуемому  результату,  которое обладает свойствами: •дискретности •понятности •определённости •результативности •массовости

Возможность автоматизации деятельности человека Решение  задачи  по  готовому  алгоритму  требует  от  заданным  следования  только  строгого  исполнителя  предписаниям. Формальное  исполнение  возможность автоматизации деятельности человека алгоритма  обеспечивает  Процесс решения задачи представляется в виде последовательности операций Создается машина, способная выполнять эти операции в указанной последовательности Человек освобождается от рутинной работы, выполнение которой поручается автомату

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

Самое главное Исполнитель  ­  некоторый  объект  (человек,  животное,  выполнять  устройство),  способный  техническое  определённый набор команд. Формальный  исполнитель  одну  и  ту  же  команду  всегда  выполняет  каждого  формального  исполнителя  можно  указать:  круг  решаемых  задач,  среду,  систему команд и режим работы. одинаково.  Для  Алгоритм ­ предназначенное для конкретного исполнителя  описание  последовательности  действий,  приводящих  от  исходных данных к требуемому результату, которое обладает  свойствами  дискретности,  понятности,  определённости,  результативности и массовости. исполнителя  действовать  формально  обеспечивает  возможность  автоматизации  деятельности  человека. Способность

«компьютер»? алгоритма? Вопросы и задания Некоторый алгоритм получает из одной цепочки символов  Исполнитель  Черепашка  перемещается  на  экране  Система  команд  исполнителя  Вычислитель  состоит  Система команд исполнителя Конструктор состоит из  Исполнитель  Робот  действует  на  клетчатом  поле,  новую цепочку следующим образом.  Кто может быть исполнителем алгоритма? компьютера, оставляя след в виде линии. между соседними клетками которого могут стоять стены.  Рассмотрите  в  качестве  исполнителя  текстовый  К  чему  может  привести  отсутствие  какого­либо  двух команд, которым присвоены номера: из двух команд, которым присвоены номера: От чего зависит круг решаемых задач исполнителя  В чём важность возможности формального исполнения Что называют алгоритмом? Перечислите основные свойства алгоритма. Приведите примеры алгоритмов, изучаемых вами в Подберите синонимы к слову «предписание». Приведите пример формального исполнителя.   Какие  у  робота,  команды  должны  быть  Сначала записывается исходная цепочка символов, после  Что такое команда, система команд исполнителя? Последовательность чисел строится по следующему   Система команд Черепашки состоит из двух команд: Робот передвигается по клеткам поля и может выполнять  процессор,  на  компьютере.  свойства у алгоритма?  имеющийся  вашем  1 ­ вычти 1 1 ­ приписать 2 нее  записывается  исходная  цепочка  символов  в  обратном  выполняющего функции: Приведите  пример,  когда  человек  выступает  в  роли  школе. алгоритму: Вперёд  n  ­  целое  число)  –  вызывает  (где  n  следующие команды, которым присвоены  номера: Приведите примеры. Охарактеризуйте  круг  решаемых  этим  исполнителем  порядке,  затем  записывается  буква,  следующая  в  русском  формального исполнителя. 2 ­ умножь на 3 2 ­ разделить на 2 а) кассира в магазине? передвижение  Черепашки  на  n  шагов  в  направлении  1 ­ Вверх задач и его среду. первые  два  числа  последовательности  принимаются  А алфавите за той буквой, которая в исходной цепочке стояла  Первая  из  них  уменьшает  число  на  1,  вторая  По первой из них к числу приписывается справа 2,  движения  ­  в  том  направлении,  куда  развёрнуты  её  б) дворника? 2 ­ Вниз на последнем месте. Если в исходной цепочке на последнем  равными 1; по второй число делится на 2. голова и корпус; увеличивает число в 3 раза.  месте  стоит  буква  Я,  то  в  качестве  следующей  буквы  3 ­ Вправо в) охранника? последовательности  число  каждое  Направо  m  (где  m  ­  целое  число)  ­  вызывает  записывается буква А.  При  записи  алгоритмов  для  краткости  указываются  4 ­ Влево Как  будет  преобразовано  число  8,  если  исполнитель  изменение  направления  движения  Черепашки  на  m  Получившаяся  цепочка  является  результатом  работы  принимается равным сумме двух предыдущих чисел. При  выполнении  каждой  такой  команды  Робот  лишь номера команд.  выполнит алгоритм 22212? алгоритма. Например, если исходная цепочка символов была  градусов по часовой стрелке. соседнюю  перемещается  указанном  Запишите  10  этой  Запишите  алгоритм  для  исполнителя  Вычислитель,  Составьте  алгоритм  в  этого  ДОМ,  то  результатом  работы  алгоритма  будет  цепочка  Что  будет  результатом  исполнения  Черепашкой  направлении.  Если  же  в  этом  направлении  между  последовательности. ДОММОДН.  содержащий не более 5 команд: алгоритма:  исполнителя, по которому число 1 будет преобразовано  клетками стоит стена, то Робот разрушается.  Дана  цепочка  символов  КОМ.  Сколько  букв  О  будет  в  а) получения из числа 3 числа 16 В какой клетке должен находиться исполнитель Робот,  в  число  16  (в  алгоритме  должно  быть  не  более  5  цепочке  символов,  которая  получится,  если  применить  чтобы  после  выполнения  алгоритма  3241  в  неё  же  и  б) получения из числа 1 числа 25 команд). алгоритм  к  данной  цепочке,  а  затем  ещё  раз  применить  вернуться? алгоритм к результату его работы? Повтори 8 [ Направо 45 Вперёд 45 ]? В следующее  первых  в  клетку  системе  команд  членов  в

Опорный конспект Алгоритм ­ это предназначенное для конкретного исполнителя  описание последовательности действий, приводящих от исходных  данных  к  требуемому  результату,  которое  обладает  свойствами  дискретности, понятности, определённости, результативности    и   массовости. Свойства алгоритма Дискретность   Понятность   Определённость  Результативность  Массовость    Дискретность  Свойства алгоритмаПонятность  Определённость Результативность Массовость

Электронные образовательные ресурсы 1. http://school­collection.edu.ru/catalog/res/07e215ef­cd48­450d­8cf4­f5777cd832b2/? interface=catalog – решето Эратосфена 2. http://files.school­collection.edu.ru/dlrstore/58e9a0c3­11df­4c94­a5eb­ b0a7b359ea35/9_32.swf ­ исполнители алгоритмов