Презентация по информатике на тему "Исполнители алгоритмов", подготовка к ЕГЭ

• 1 слайд

  Исполнители алгоритмов
  Учитель информатики
  МБОУ «СОШ № 36» г. Курска
  Плотникова Наталья Сергеевна
  

• 2 слайд

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

• 3 слайд

  Исполнитель
  1.Исполнитель - это человек или коллектив людей, вооруженных набором инструментов и обученный выполнению некоторой совокупности операций в заданной последовательности.и обученный выполнению некоторой совокупности операций в заданной последовательности
  

• 4 слайд

  Исполнитель
  2. Исполнитель - автоматическое устройство (электронное, электромеханическое и т.п.), изготовленное таким образом, что, будучи включенным в работу, выполняет заданную последовательность операций над некоторым исходным продуктом, преобразуя его в заданный конечный продукт., электромеханическое и т.п.), изготовленное таким образом, что, будучи включенным в работу, выполняет заданную последовательность операций над некоторым исходным продуктом, преобразуя его в заданный конечный продукт.
  

• 5 слайд

  Исполнитель
  Исполнитель алгоритма - некоторая абстрактная или реальная система, способная выполнить действия, предписываемые алгоритмом. Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды формально (не обдумывая). В информатике универсальным исполнителем алгоритмов является компьютер.
  

• 6 слайд

  Исполнитель
  Формальный
  Неформальный
  Круг решаемых задач
  Среда исполнителя
  СКИ
  Режимы работы
  Область, обстановка, условия
  Непосредственное управление
  Программное управление
  

• 7 слайд

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

• 8 слайд

• 9 слайд

  Исполнитель Робот
  
  Система команд исполнителя (СКИ) Робота:
  вверх вниз влево вправо
  вверх ↑, вниз -↓, влево ←, вправо →.
  сверху свободно снизу свободно
  слева свободно справа свободно
  Цикл ПОКА <условие> команда выполняется, пока
  условие истинно, иначе происходит переход на следующую строку.
  В кон­струк­ции
  ЕСЛИ < усло­вие >
  ТО ко­ман­да1
  ИНАЧЕ ко­ман­да2
  КОНЕЦ ЕСЛИ
  вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно)
  Если РОБОТ начнёт дви­же­ние в сто­ро­ну на­хо­дя­щей­ся рядом с ним стены, то он раз­ру­шит­ся и про­грам­ма прервётся.
  

• 10 слайд

  Задачи с остановкой в заданной клетке
  Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?
  
  НА­ЧА­ЛО
  ПОКА<спра­ва сво­бод­но ИЛИ снизу сво­бод­но >
  ПОКА < снизу сво­бод­но >
  вниз
  КОНЕЦ ПОКА
  ПОКА < спра­ва сво­бод­но >
  впра­во
  КОНЕЦ ПОКА
  КОНЕЦ ПОКА
  КОНЕЦ
  1) 14
  2) 17
  3) 19
  4) 21
  

• 11 слайд

  Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?
  
  
  НАЧАЛО
  ПОКА < справа свободно ИЛИ снизу свободно >
  ПОКА < справа свободно >
  вправо
  КОНЕЦ ПОКА
  ПОКА < снизу свободно >
  вниз
  КОНЕЦ ПОКА
  КОНЕЦ ПОКА
  КОНЕЦ
  
  1) 8 2) 15 3) 24 4) 27
  
  

• 12 слайд

  За каждый шаг внешнего цикла Робот проходит путь в виде «сапога», двигаясь вначале вправо до упора, затем вниз до упора:
  Красная клетка – особая, в ней заканчивается один
  внешний цикл и начинается другой.
  а) Робот может попасть в нее, двигаясь вниз из
  клетки, когда справа – стенка;
  б) снизу есть стенка;
  в) снизу стенка есть, справа – нет, тогда выполнится еще один шаг внешнего цикла.
  
  
  
  
  
  
  
  Таких клеток 24, следовательно верный ответ - 3
  

• 13 слайд

  Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?
  НА­ЧА­ЛО
  ПОКА <снизу сво­бод­но ИЛИ спра­ва сво­бод­но>
  ПОКА <спра­ва сво­бод­но>
  ТО
  <впра­во>
  КОНЕЦ ПОКА
  ЕСЛИ <снизу сво­боднo>
  ТО
  <вниз>
  КОНЕЦ ЕСЛИ
  КОНЕЦ ПОКА
  КОНЕЦ
  
  1) 18
  2) 19
  3) 20
  4) 21 
  

• 14 слайд

  Задания этого типа сводятся к тому, чтобы определить те точки (назовем их «особые») в лабиринте, к которым робот вернется пройдя четыре раза по прямой (пока выполняется условие цикла). При этом он, естественно, пройдет по сторонам прямоугольника.
  1) необходимо, чтобы стенки были расставлены так, чтобы Робот упирался в них сначала при движении вниз, затем
  влево, вверх и вправо;
  2) необходимо, чтобы выделенный зеленый
  коридор был свободен;
  3) возможны еще «вырожденные» варианты:
  
  Задачи с остановкой в клетке, из которой начато движение
  

• 15 слайд

  Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
  НА­ЧА­ЛО
  ПОКА < снизу сво­бод­но > вниз
  ПОКА < слева сво­бод­но > влево
  ПОКА < свер­ху сво­бод­но > вверх
  ПОКА < спра­ва сво­бод­но > впра­во
  КОНЕЦ
   
  1) 1
  2) 2
  3) 3
  4) 4
  
  

• 16 слайд

• 17 слайд

  Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ оста­но­вит­ся в той же клет­ке, с ко­то­рой он начал дви­же­ние?
   
  НА­ЧА­ЛО
  ПОКА < снизу сво­бод­но > вниз
  ПОКА < слева сво­бод­но > влево
  ПОКА < свер­ху сво­бод­но > вверх
  ПОКА < спра­ва сво­бод­но > впра­во
  КОНЕЦ
   
  1) 1
  2) 2
  3) 3
  4) 4
  
  

• 18 слайд

  Исполнитель Вычислитель
  У исполнителя Вычислитель три команды, которым присвоены номера:
  вычти 1
  умножь на 3
  прибавь 3
  Первая из них уменьшает число на экране на 1, вторая — утраивает его, а третья увеличивает на 3.
  Запишите порядок команд в алгоритме получения
  из числа 5 числа 23 за наименьшее число команд.
  
  Например, 211 — это алгоритм:
  2. умножь на 3
  1. вычти 1
  1. вычти 1,— который преобразует число 7 в 19.
  

• 19 слайд

  Исполнитель Вычислитель
  вычти 1
  умножь на 3
  прибавь 3
  Запишите порядок команд в алгоритме получения
  из числа 5 числа 23 за наименьшее число команд.
  5
  -1
  *3
  +3
  4
  15
  8
  -1
  *3
  +3
  -1
  *3
  +3
  -1
  3
  12
  7
  14
  45
  18
  7
  24
  11
  +3
  *3
  *3
  +3
  -1
  23
  I
  II
  III
  Ответ: 321
  Для решения данной задачи полезно построить дерево.
  

• 20 слайд

  Исполнитель Вычислитель
  Есть 2 команды, которым
  присвоены номера:
  Прибавь 1
  Умножь на 2
  Запишите порядок команд
  в программе преобразования
  числа 3 в число 63, содержащей
  не более 8 команд, указывая
  лишь номера команд. Если
  таких программ более одной,
  то запишите любую из них.
  1 2 1 2 1 2 1 2
  63 62 31 30 15 14 7 6 3
  Такую задачу удобнее решать «с конца». Тогда дерево будет не таким большим, но необходимо заменить команды на противоположные:
  Вычти 1
  Раздели на 2
  Очевидно, что делить на 2
  можно только четные числа, тогда:
  

• 21 слайд

  У исполнителя Калькулятор две команды, которым присвоены номера:
  1. прибавь 3
  2. умножь на 4
  Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.
  
  

• 22 слайд

   В зависимости от координат (a,b) команды Сместиться на (a,b) Чертёжник меняет направление своего движения относительно последнего (текущего) положения.
  * Если обе координаты положительные, то Чертёжник переходит в I четверть координатной плоскости (движется вправо и вверх).
  * Если первая координата отрицательная, а вторая положительная, то Чертёжник переходит во II четверть координатной плоскости (движется влево и вверх).
  * Если обе координаты отрицательные, то Чертёжник переходит в III четверть координатной плоскости (движется влево и вниз).
  * Если первая координата положительная, а вторая отрицательная, то Чертёжник переходит в IV четверть координатной плоскости (движется вправо и вниз). 
  Что нужно знать
  Чертежник
  

• 23 слайд

  Исполнитель Чертежник перемещается на координатной плоскости, оставляя за собой след в виде линии. Может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертежника из точки с координатами (x, y) в точку с координатами (x+a, y+b).
  Например, если Чертежник находится в точке с координатами (4, 2), то команда сместиться на (2, -3) переместит Чертежник в точку (6, -1). Цикл
  ПОВТОРИ число РАЗ
  последовательность команд
  КОНЕЦ ПОВТОРИ
  Означает, что последовательность команд будет выполнена указанное число раз(число должно быть натуральным)
  
  Исполнитель Чертежник
  

• 24 слайд

  Чертёжнику был дан для исполнения следующий алгоритм:
  
  Повтори 3 раз
  Сместиться на (–3, –2) Сместиться на (2, 1) Сместиться на (3, 0)
  конец
  
  Какую команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение?
  
  1) Сместиться на (–3, –6)
  2) Сместиться на (–6, 3)
  3) Сместиться на (6, –3)
  4) Сместиться на (3, 6)
  Задачи с возвращением
  в начальную точку, координаты и число повторений цикла известны
  

• 25 слайд

  Выполнив алгоритм
                    Повтори 3 раз
                    Сместиться на (-3,-2) Сместиться на (2,1) Сместиться на (3,0)
                    конец
  Чертёжник переместиться из точки A в точку B. Каждая из ломаных линий одного цвета соответствует однократному прохождению одного из трёх повторений цикла.
  Первый способ.
  

• 26 слайд

  Возвращение Чертёжника  в исходную точку A из точки B соответствует варианту ответов 2) Сместиться на (-6,3), что наглядно видно из графика:
  Ответ: 2
  

• 27 слайд

  Пусть Чертежник находится в точке (х,у), по команде сместиться на (а,b) он перемещается в точку (x+a, y+b). В начальном положении перо Чертежника находится в точке (0,0).
  ЕГЭ 2015
  Второй способ.
  После выполнения алгоритма Чертежник окажется в точке (6,-3),
  чтобы попасть в начальную точку (0,0) надо сместиться на (-6,3).
  
  Ответ: 2
  

• 28 слайд

  Третий способ - универсальный
  Повтори 3 раз
  Сместиться на (–3, –2) Сместиться на (2, 1) Сместиться на (3, 0)
  конец
  
  Запишем общее изменение координат Чертежника в результате выполнения этого алгоритма:
  ∆𝑥=3∗ −3+2+3
  ∆𝑦=3∗ −2+1+0
  
  Чертежник окажется ∆𝑥=3∗2=6
  ∆𝑦=3∗ −1 =−3
  в точке (6, -3)
  Следовательно, для возврата в исходную точку Чертежник должен переместиться на вектор (-6, 3)
  
  Ответ: (-6, 3)
  
  

• 29 слайд

  Задачи с возвращением
  в начальную точку, координаты и число повторений цикла неизвестны
  Чертежнику был дан для исполнения алгоритм (буквами a, b, n обозначены неизвестные числа, n>1)
  НАЧАЛО
  сместиться на (-3, -3)
  ПОВТОРИ n РАЗ
  сместиться на (a, b)
  сместиться на (27, 12)
  КОНЕЦ ПОВТОРИ
  сместиться на (-22, -7)
  КОНЕЦ
  Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что после выполнения программы Чертежник возвратиться в исходную точку.
  

• 30 слайд

  Используем универсальный способ
  НАЧАЛО
  сместиться на (-3, -3)
  ПОВТОРИ n РАЗ
  сместиться на (a, b)
  сместиться на (27, 12)
  КОНЕЦ ПОВТОРИ
  сместиться на (-22, -7)
  КОНЕЦ
  ∆𝑥=-3+n*(a+27)-22=0
  ∆𝑦=-3+n*(b+12)-7=0
  𝑛∗ 𝑎+27 =25 𝑛∗ 𝑏+12 =10 НОД (25, 10) = 5
  Ответ: 5
  
  

• 31 слайд

  Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм:
  По­вто­ри 7 paз
  Сме­стить­ся на (−1, 2) Сме­стить­ся на (−2, 2) Сме­стить­ся на (4, −4) Конец
  
  Ка­ко­вы ко­ор­ди­на­ты точки, с ко­то­рой Чертёжник на­чи­нал дви­же­ние, если в конце он ока­зал­ся в точке с ко­ор­ди­на­та­ми (0, 0)?
  
  1) Сме­стить­ся на (7, 0)
  2) Сме­стить­ся на (−7, 0)
  3) Сме­стить­ся на (0, −7)
  4) Сме­стить­ся на (0, 7)
  

• 32 слайд

  Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм:
  Сме­стить­ся на (−1,1) По­вто­ри 4 раз
  Сме­стить­ся на (3,1) Сме­стить­ся на (0, 2) Сме­стить­ся на (−1, 4) конец
   
  На какую ко­ман­ду можно за­ме­нить этот ал­го­ритм?
   
  1) Сме­стить­ся на (8, 28)
  2) Сме­стить­ся на (7, 29)
  3) Сме­стить­ся на (−8, −28)
  4) Сме­стить­ся на (−7, −29)
  
  
  
  

• 33 слайд

  Чертёжнику был дан для исполнения следующий алгоритм:
  Сместиться на (3,-3)
  Повтори N раз
  Сместиться на (27, 17)
  Сместиться на (a, b)
  конец
  Сместиться на (–27, –17)
  Чему должно равняться N, чтобы Чертежник смог вернуться в исходную точку, из которой он начал движение?
  4 2) 5 3) 6 4) 7
  
  
  

• 34 слайд

  Источники для подготовки
  к ЕГЭ
  Образовательный портал для подготовки к экзаменам «Решу ЕГЭ»
  http://inf.reshuege.ru/
  Сайт Константина Полякова
  http://kpolyakov.spb.ru/
  ФИПИ – открытый банк заданий
  http://www.fipi.ru/
  http://cdosh46.ru/video-uroki.html
  
  
  

• 35 слайд

  Спасибо за внимание!
  Удачи на экзаменах!