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

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

Подготовил Мустафинов Р.Е

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

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

Ключевые слова

Есть ли у тебя цель в жизни?

Посмотреть весь сезон «С лово пацана. Кровь на асфальте »

Закончить школу с золотой медалью

Получить высшее образование

Научиться водить машину

ЦЕЛЬ

Научиться играть на гитаре

Стать мастером спорта

Сдать экзамен на 100 баллов

что тебе нужно сделать для того, чтобы добиться этой цели?

Не пропускать ни одной серии

Готовиться к каждому уроку

Каждый день решать новый пробный вариант экзаменационной работы

ЗАДАЧИ

Читать дополнительную литературу по предмету

Вести здоровый образ жизни

Не пропускать уроки

алгоритм

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

алгоритм

• Алгоритм – это последовательность действий, которая должна быть выполнена для достижения желаемого результата.

Алгоритм

алгоритм

• Слово «алгоритм» происходит от имени выдающегося математика средневекового Востока Мухаммеда ибн Муссы аль-Хорезми (787–850).
• В переводе с арабского это означает «Мухаммед, сын Мусы из Хорезма».
• Позже в Европе эти приемы назвали алгоритмами, от Algorithmi – латинского написания аль-Хорезми.

Примеры алгоритмов

Пополнение счёта телефона через терминал

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

Примеры алгоритмов

Рисование лошади

Примеры алгоритмов

Вычислительный алгоритм

Среднее арифметическое двух чисел

• Задать два числа
• Сложить заданные числа
• Разделить сумму на 2

Общая схема работы алгоритма

Исходные данные

Алгоритм

Результат

Исполнитель алгоритма

• Исполнитель алгоритма – объект управления, который выполняет алгоритм.

• Кто может быть исполнителем алгоритма?

Человек

Компьютер

Животные

Исполнитель алгоритма

• У каждого исполнителя алгоритма есть определенный набор команд, которые он может выполнить. Этот набор называется СКИ – система команд исполнителя.

Человек

Компьютер

Животные

Исполнитель алгоритма

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

Исполнитель

Неформальный

Формальный

Круг решаемых задач

Область, обстановка, условия

Среда исполнителя

СКИ

Непосредственное управление

Программное управление

Режимы работы

Исполнители алгоритмов

Разработка алгоритма

Разработка алгоритма

Определение объектов,

указанных в задаче

Определение

последовательности

действий

Установление свойств

объектов, отношений

и действий с объектами

Запись

последовательности

действий с помощью

команд СКИ

Определение исходных

данных и результата

Алгоритм – модель деятельности исполнителя алгоритмов

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

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

Как часто мы в своей жизни сталкиваемся с алгоритмами?

Постоянно!

Попробуйте привести пример алгоритма, с которым вы сталкиваетесь ежедневно

Алгоритм «Заварка чая»

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

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

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

Путь решения задачи

разделён на отдельные шаги

Дискретность

Алгоритм состоит из

команд, входящих в СКИ

Понятность

Команды понимаются

Определённость

однозначно

Обеспечивается получение

ожидаемого результата

Результативность

Обеспечивается решение

задач с различными исходными

данными

Массовость

y a = y a = x a Конец " width="640"

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

Начало

x, y

нет

да

x y

a = y

a = x

a

Конец

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

Окрошка «Мясная»

1-1.5 л кваса

300 г огурцов

зелень по вкусу

500 г картофеля

300 г колбасы

сметана

соль

3 яйца

200 г редиса

перец

Рецепт приготовления

Картофель отварить до готовности.

Смешать картофель, колбасу, яйца, редис, огурцы. Посолить, поперчить.

Остудить, почистить. Нарезать кубиками.

Выложить в тарелки.

Колбасу нарезать кубиками.

Залить квасом, посыпать зеленью. Подавать со сметаной.

Яйца нарезать кубиками.

Редис тонко нарезать.

Огурцы нарезать кубиками.

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

Доехать до стадиона

• Идти прямо

• Повернуть

• Идти прямо

• Сесть в автобус

• Доехать до остановки «Стадион»

Данная последовательность действий не обладает свойством определённости!

Какое расстояние нужно пройти прямо?

В какую сторону повернуть?

В какой автобус сесть?

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

Чтение книги

• Взять книгу
• Открыть первую страницу
• Пока не конец книги выполнять следующие действия:

3.1 Прочитать текст

3.2 Перелистнуть страницу

3.3 Прочитать текст

3.4 Открыть первую страницу

Данная последовательность команд не обладает свойством результативности. Что нужно изменить?

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

Алгоритм вычисления корней квадратного уравнения .

Начало

Ввод

коэффициентов

Вычисление

дискриминанта

Дискриминант

меньше 0?

да

нет

Вычисление

значений корней

Вывод корней

«Корней нет»

Конец

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

• дискретности
• понятности
• определённости
• результативности
• массовости

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

• 1. Дискретность (алгоритм должен состоять из отдельных шагов (действий), следующих в определенном порядке);
• 2. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
• 3. Понятность (каждая команда должна определять однозначное действие исполнителя);
• 4. Однозначность (Единственность толкования правил выполнения действий).
• 5. Конечность (исполнение алгоритма должно завершиться за определенное число шагов);

Алгоритм

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

Возможность автоматизации деятельности человека

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

Формальное исполнение алгоритма обеспечивает возможность автоматизации деятельности человека

Процесс решения задачи представляется

в виде последовательности операций

Создается машина, способная выполнять

эти операции в указанной последовательности

Человек освобождается от рутинной работы,

выполнение которой поручается автомату

Автоматизация деятельности человека

Автоматизация гостиниц.

Автоматизация торговли.

Профессиональная система «UCS-Shelter». Автоматизированы такие процессы как бронирование, поселение, выселение, работа со счетами гостей.

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

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

Автоматизация производства

Вопросы и задания

Можно ли назвать данную последовательность алгоритмом «знакомство с достопримечательностями центра Перми»? И почему?

• 1. Приехать в г. Пермь
• 2. Найти скульптуру «Пермяк – соленые уши»
• 3. Следовать по пешеходному туристическому маршруту «Зеленой линии» до скульптуры «Пермский медведь»

Решето Эратосфена

Решето Эратосфена

Рассмотренная последовательность действий является алгоритмом, так как она удовлетворяет свойствам:

• дискретности - процесс нахождения простых чисел разбит на шаги;
• понятности - каждая команда понятна ученику 8 класса, выполняющему этот алгоритм;
• определённости - каждая команда трактуется и выполняется исполнителем однозначно; имеются указания об очерёдности выполнения команд;
• результативности - через некоторое число шагов достигается результат;
• массовости - последовательность действий применима для любого натурального n .

Задача 1

• У исполнителя Альфа две команды, которым присвоены номера:
• 1. прибавь 1;
• 2. умножь на b
• ( b  — неизвестное натуральное число;  b  ≥ 2).
• Выполняя первую из них, Альфа увеличивает число на экране на 1, а выполняя вторую, умножает это число на  b . Программа для исполнителя Альфа — это последовательность номеров команд. Известно, что программа 11211 переводит число 6 в число 82. Определите значение  b .

Правильный ответ: 10

Задача 2

• У исполнителя Делитель две команды, которым присвоены номера:
• 1. раздели на 2
• 2. вычти 3
• Первая из них уменьшает число на экране в 2 раза, вторая уменьшает его на 3. Исполнитель работает только с натуральными числами. Составьте алгоритм получения  из чиcла 76 числа 5 , содержащий не более 5 команд. В ответе запишите только номера команд.
• Если таких алгоритмов более одного, то запишите любой из них.

Правильный ответ: 11212

Задача 3

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

1 – Вверх 2 – Вниз 3 – Вправо 4 – Влево

При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то Робот разрушается.

В какой клетке должен находиться исполнитель Робот, чтобы после выполнения алгоритма 2314 в неё же и вернуться?

А

В

Правильный ответ: в клетке В

Проверь себя!

• Пройди онлайн-тест по теме «Алгоритмы и исполнители»:
• https:// onlinetestpad.com/hpbitemev53jy

• Не забудь отправить результат теста учителю на почту:
• [email protected]

• Остались вопросы по теме? Задай их учителю в группе vk.com/pschool3inf

Спасибо за внимание!

Самое главное

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

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

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

Способность исполнителя действовать формально обеспечивает возможность автоматизации деятельности человека.

Вопросы и задания

Некоторый алгоритм получает из одной цепочки символов новую цепочку следующим образом.

Сначала записывается исходная цепочка символов, после нее записывается исходная цепочка символов в обратном порядке, затем записывается буква, следующая в русском алфавите за той буквой, которая в исходной цепочке стояла на последнем месте. Если в исходной цепочке на последнем месте стоит буква Я, то в качестве следующей буквы записывается буква А.

Получившаяся цепочка является результатом работы алгоритма. Например, если исходная цепочка символов была ДОМ, то результатом работы алгоритма будет цепочка ДОММОДН.

Дана цепочка символов КОМ. Сколько букв О будет в цепочке символов, которая получится, если применить алгоритм к данной цепочке, а затем ещё раз применить алгоритм к результату его работы?

Система команд исполнителя Конструктор состоит из двух команд, которым присвоены номера:

Система команд исполнителя Вычислитель состоит из двух команд, которым присвоены номера:

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии.

1 - приписать 2

1 - вычти 1

Система команд Черепашки состоит из двух команд:

2 - разделить на 2

Вперёд n (где n - целое число) – вызывает передвижение Черепашки на n шагов в направлении движения - в том направлении, куда развёрнуты её голова и корпус;

2 - умножь на 3

Направо m (где m - целое число) - вызывает изменение направления движения Черепашки на m градусов по часовой стрелке.

По первой из них к числу приписывается справа 2,

Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза.

по второй число делится на 2.

При записи алгоритмов для краткости указываются лишь номера команд.

Что будет результатом исполнения Черепашкой алгоритма:

Как будет преобразовано число 8, если исполнитель выполнит алгоритм 22212?

Запишите алгоритм для исполнителя Вычислитель, содержащий не более 5 команд:

Повтори 8 [ Направо 45 Вперёд 45 ]?

Составьте алгоритм в системе команд этого исполнителя, по которому число 1 будет преобразовано в число 16 (в алгоритме должно быть не более 5 команд).

а) получения из числа 3 числа 16

б) получения из числа 1 числа 25

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

1 - Вверх

2 - Вниз

3 - Вправо

4 - Влево

При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то Робот разрушается.

В какой клетке должен находиться исполнитель Робот, чтобы после выполнения алгоритма 3241 в неё же и вернуться?

Кто может быть исполнителем алгоритма?

К чему может привести отсутствие какого-либо свойства у алгоритма?

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

Приведите примеры.

Что называют алгоритмом?

В чём важность возможности формального исполнения

От чего зависит круг решаемых задач исполнителя

Перечислите основные свойства алгоритма.

«компьютер»?

алгоритма?

Приведите пример формального исполнителя.

Какие команды должны быть у робота, выполняющего функции:

Подберите синонимы к слову «предписание».

Приведите примеры алгоритмов, изучаемых вами в

Приведите пример, когда человек выступает в роли формального исполнителя.

а) кассира в магазине?

школе.

б) дворника?

в) охранника?

Последовательность чисел строится по следующему алгоритму:

Что такое команда, система команд исполнителя?

первые два числа последовательности принимаются равными 1;

каждое следующее число последовательности принимается равным сумме двух предыдущих чисел.

Запишите 10 первых членов этой последовательности.

А

В

Опорный конспект

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

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

Дискретность

Понятность

Определённость

Результативность

Массовость