Презентация по информатике на тему "Алгоритмы обработки информации" 10 класс

• 1 слайд

  АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ
  ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ
  

• 2 слайд

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

• 3 слайд

  Художник Василий Тропинин «Золотошвейка» (1826)
  
  понимает смысл алгоритма, может его корректировать и изменять, а также отказаться выполнять
  одну и ту же команду выполняет каждый раз по-разному
  неформальный исполнитель сам отвечает за свои действия
  в роли неформального исполнителя чаще всего выступает человек
  
  
  Исполнитель алгоритма
  Исполнитель алгоритма – это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить со­держащийся в нём перечень действий.
  !
  
  не размышляет над выпол­няемыми командами, а строго следует пошаговым инструк­циям алгоритма
  одну и ту же команду всегда выполняет одинаково
  за действия формального исполни­теля отвечает управ­ляющий им объект
  в роли формального исполни­теля чаще всего выступает техническое устройство
  
  
  Неформальный
  исполнитель
  Формальный
  исполнитель
  

• 4 слайд

  Понятие алгоритма
  Алгоритм – точная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения искомого результата за конечное число шагов.
  !
  ПРИМЕРЫ АЛГОРИТМОВ
  Закрыть
  входную дверь ключом
  Нахождение n первых простых чисел
  (метод Эратосфена)
  Построение перпендикуляра
  к прямой
  

• 5 слайд

  Пример 1
  Исполнитель: человек
  Объекты алгоритма: ключ, дверь
  Алгоритм
  «Закрыть входную дверь ключом»
  
  Вставить ключ в замочную скважину.
  Повернуть ключ два раза на 180 градусов против часовой стрелки.
  Вынуть ключ из замочной скважины.
  

• 6 слайд

  Пример 2
  Алгоритм «Нахождение всех простых чисел не больше заданного числа n по методу Эратосфена»
  Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n).
  Присвоить переменной p значение 2 (2 – первое простое число).
  Зачеркнуть в списке числа, кратные p: 2p, 3p, 4p, …
  Найти первое незачёркнутое число в списке, большее чем p, и присвоить p соответствующее значение.
  Повторять шаги 3 и 4, пока возможно (пока p2 ≤ n).
  Незачёркнутые числа и есть все простые числа от 2 до n.
  Простые числа от 2 до 100
  Выполнить
  2
  3
  5
  7
  11
  13
  17
  19
  23
  29
  31
  37
  41
  43
  47
  53
  59
  61
  67
  71
  73
  79
  83
  89
  97
  

• 7 слайд

  Пример 2
  Алгоритм «Нахождение всех простых чисел не больше заданного числа n по методу Эратосфена»
  Простые числа от 2 до 100
  p = 2
  p = 3
  p = 5
  p = 7
  Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n).
  Присвоить переменной p значение 2 (2 – первое простое число).
  Удалить из списка числа, кратные p: 2p, 3p, 4p, …
  Найти первое число в списке, большее чем p, и прис­воить p соответствующее значение.
  Повторять шаги 3 и 4, пока возможно (пока p2 ≤ n).
  Оставшиеся числа и есть все простые числа от 2 до n.
  

• 8 слайд

  Пример 3
  Алгоритм «Построение перпендикуляра к прямой, проходящей через заданную точку O, лежащую на прямой с помощью циркуля и линейки»
  Выполнить
  Провести окружность с центром в точке O и радиусом 1 см.
  Обозначить точки пересечения окружности с прямой: левую - A, правую - B.
  Провести окружность с центром в точке A и радиусом равным AB.
  Провести окружность с центром в точке В и радиусом равным AB.
  Обозначить точки пересечения окружностей: верхнюю - C, нижнюю - D.
  Провести прямую СD.
  

• 9 слайд

  Пример 3
  Алгоритм «Построение перпендикуляра к прямой, проходящей через заданную точку O, лежащую на прямой с помощью циркуля и линейки»
  О
  А
  В
  С
  D
  Провести окружность с центром в точке O и радиусом 1 см.
  Обозначить точки пересечения окружности с прямой: левую - A, правую - B.
  Провести окружность с центром в точке A и радиусом равным AB.
  Провести окружность с центром в точке В и радиусом равным AB.
  Обозначить точки пересечения окружностей: верхнюю - C , нижнюю - D.
  Провести прямую СD.
  

• 10 слайд

  Свойства алгоритма
  Дискретность
  Детерминированность
  Понятность
  Результативность
  Массовость
  Дискретность
  Выполнение алгоритма разбивается на последовательность законченных дейст­вий-шагов. Только выполнив одно действие, можно приступать к выполнению следующего. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма – команда.
  Детерминированность
  Каждая команда алгоритма определяет однозначное действие исполнителя, и недвусмысленно указывает, какая команда должна выполняться следую­щей. Многократное выполнение алго­ритма при одном и том же наборе входных данных, дает одинаковые промежуточные и выходной результаты.
  Понятность
  Алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неодно­знач­но, т. е. запись алгоритма должна быть настолько чёткой и полной, чтобы у исполнителя не возникло потребности в принятии каких-либо самостоятельных решений.
  Результативность
  При точном исполнении команд алгоритма процесс должен прекратиться за конеч­ное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть установление того факта, что задача решений не имеет.
  Массовость
  Алгоритм пригоден для решения любой задачи из некоторого класса задач, т. е. алгоритм правильно работает на неко­тором множестве исходных данных, которое называется областью примени­мости алгоритма.
  Алгоритм – конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости.
  !
  

• 11 слайд

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

• 12 слайд

  Способы записи алгоритмов
  словесная запись алгоритма
  на естественном языке
  запись алгоритма на языке программирования
  с помощью блок-схемы –
  стандартных графических объектов
  (геометрических фигур)
  запись алгоритма с помощью
  формул, рисунков, таблиц
  Сложение смешанных дробей
  
  Привести дробные части чисел к наименьшему общему знаменателю.
  Сложить только целые части.
  Отдельно сложить дробные части.
  Сложить результаты, полученные в п.2 и п. 3.
  Если при сложении дробных частей получилась неправильная дробь, выделить целую часть из этой дроби и прибавить к полученной целой части.
  Сократить полученную дробь.
  
  Нахождение максимума
  из 10 целых чисел
  Нахождение НОД
  
  Program NOD;
  var a, b, n: integer;  
  Begin  
  writeln ('Введите два числа: ');
  readln (a, b);  
  while a <> b do
  if a>b then a := a - b
  else b := b – a;
  n:= a; 
  writeln ('НОД = ', n);
  End.
  Шахматный этюд
  
  Мат в два хода.
  Белые начинают и выигрывают
  №
  Белые
  Черные
  1
  Ф f1-a1
  K h8-g8
  2
  Ф a1-a8
  №
  Белые
  Черные
  1
  Ф f1-a1
  g6-g5
  2
  K f6-f7
  №
  Белые
  Черные
  1
  Ф f1-a1
  С h7-g8
  2
  K f6-g6
  Решение:
  

• 13 слайд

  Правила выполнения блок-­схем, внешний вид графических блоков и их назначение определяются стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения».
  Блок-схема
  

• 14 слайд

  Понятие сложности алгоритма
  Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.
  Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его ис­полнении.
  Сложность алгоритма – количество элементарных шагов (действий) в вычислительном процессе этого алгоритма.
  !
  Для решения задачи могут быть разработаны алгоритмы, имеющие разную сложность. Лучшим среди них считается алгоритм, имеющий наименьшую сложность.
  Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.
  

• 15 слайд

  Временная сложность
  «Найти книгу с секретом»
  Сложность алгоритма выражают в виде функции от объёма входных данных.
  Задание. Оцените сложность алгоритмов:
  «Поиск в телефонной книге»
  В сейфе оказался клочок страницы с фамилией и первой цифрой номера телефона. Надо найти страницу с нужной фамилией в телефонном справочнике, в котором 1000 страниц .
  Сложность алгоритма будет O(log2n).
  Таким образом, в книге объёмом в 1000 страниц страница с нужной фамилией находится не больше, чем за O(log21000) ≈ 10 раз.
  
  В данном случае, за счет сортировки имен по алфавиту, можно сократить поиск, применив метод половинного деления (открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое).
  При линейном поиске – последовательной проверки всех книг подряд – сложность, в худшем случае, будет равна количеству книг, т.е. O(n) = 1000.
  В старинной библиотеке в одном из 1000 томов, посвященных кладам и тайникам, спрятана книга-сейф. Надо найти ее.
  

• 16 слайд

  X40
  Задание. Найти
  Пример 4
  Алгоритм «Возведение числа в натуральную степень (xn)»
  Запишем n в двоичной системе счисления.
  Заменим каждую 1 парой букв КХ, а каждый 0 – буквой К.
  Вычеркнем крайнюю левую пару КХ.
  Полученная строка, читаемая слева направо, даёт правило быстрого вычисления хn, если букву К рассматривать как операцию возведения результата в квадрат, а букву X – как операцию умножения результата на х. Вначале результат равен х.
  К
  Х
  К
  К
  Х
  К
  К
  К
  возведение результата в Квадрат
  К
  умножение результата на Х
  Х
  1
  0
  1
  0
  0
  0
  40 = 2
  х2
  х4
  х5
  х10
  х20
  х40
  

• 17 слайд

  Алгоритм – конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости.
  Исполнитель алгоритма – субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.
  Один и тот же алгоритм может быть записан разными способами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д.
  Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.
  

• 18 слайд

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

• 19 слайд

  Вопросы и задания
  Задание 1. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам:
  Складываются первая и вторая, а также вторая и третья цифры исходного числа.
  Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
  Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711.
  Решение:
  Единственный способ разбить запись 1711 на два числа – это 17 и 11.
  Чтобы число было меньше, надо чтобы сумма первой и второй цифр была наименьшей, в данном случае 11.
  Сумма значений двух последних цифр равна 17. Не трудно заметить, что 17 = 8 + 9 = 9 + 8. Других вариантов нет.
  Тогда 11 = 2 + 9 = 3 + 8. Выбираем пару, которая даст меньшее число.
  Ответ: 298.
  

• 20 слайд

  Вопросы и задания
  Задание 2. Подсчитайте сложность алгоритма сложения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе – из m десятичных цифр.
  Решение:
  Сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое – из m цифр требует не более max(n, m) сложений и не более max(n, m) запоминаний (в случае перехода через десяток).
  Т.е. данный алгоритм имеет сложность порядка O(n+m).
  Выражение показывает только порядок величины – постоянные факторы в нем не учитываются.
  

• 21 слайд

  8
  3
  3
  3
  3
  3
  Вопросы и задания
  Задание 1. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать? Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.
  Графический способ решения:
  

• 22 слайд

  Информационные источники
  https://img2.goodfon.ru/original/1920x1080/a/91/zamok-klyuch-otverstie-svet.jpg
  http://biblo-ok.ru/biblio-ok/Kartiny1/79.files/image001.jpg
  http://cheeseberry-sibir.ru/photos/vyshivka-na-odejde-izgotovlenie-6259-large.jpg
  http://europeansectionarcipreste.blogspot.ru/2011_11_01_archive.html
  http://www.imasitalia.com/wp-content/uploads/2016/04/fogli.jpg
  http://atotarho12.narod.ru/clipart/k/kar/karanda44.png
  https://s-media-cache-ak0.pinimg.com/originals/73/96/fd/7396fd0a921a5f895bafd81830adcaa5.jpg
  https://chessok.net/zadachi/1165-reshit-legkuyu-dvuhhodovku.html
  http://pikabu.ru/story/metod_byistrogo_umnozheniya_karatsubyi_4226758
  http://ozon.ru. Сейф-книга "Вид на реку"
  https://openclipart.org/image/800px/svg_to_png/171487/1344190891.png
  http://vamotkrytka.ru/_ph/54/2/531435092.gif
  http://www.gifmania.ru/Animated-Gifs-Veb-dizayn/Animations-Geometry/Images-Geometric-Stars/Geometric-Stars-89830.gif
  http://www.freeiconspng.com/free-images/potion-icon-png-15620