Свойства алгоритма Способы описания Виды алгоритма Что такое алгоритм? - презентация

1 Свойства алгоритма Способы описания Виды алгоритма Что такое алгоритм?

2 Из истории Само слово «алгоритм» происходит от имени великого узбекского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 г. он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился, так что её оригинальное название нам неизвестно. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»).

3 Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль- Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманской рукописи XIII века, написанной в стихах, читаем: "Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм». (материал из Хаба-вики)

4 Алгоритм – это последовательность действий, которые должен выполнить исполнитель для достижения конкретной цели. Алгоритм содержит несколько шагов. Шаг – отдельное законченное действие.

5 Ресурс:Демонстрационный пример реализации линейного алгоритма в учебной среде "Конструктор алгоритмов" (N )

6 Исполнитель - это объект, умеющий выполнять определенный набор действий. (человек, животное, робот, компьютер). Система команд исполнителя (СКИ) – это все команды, которые исполнитель умеет выполнять. Среда исполнителя – обстановка, в которой функционирует исполнитель.

7 Свойства алгоритма Дискретность (прерывность, раздельность) – разбиение алгоритма на шаги; Понятность – каждый шаг алгоритма должен быть понятен исполнителю; Точность - указание последовательности шагов; Результативность - получение результата за конечное число шагов; Массовость – использование алгоритма для решения однотипных задач.

8 Свойства Пример выполнения свойства Пример невыполнения свойства ДискретностьКазнить нельзя, помиловать.Казнить, нельзя помиловать. Детерминированность (точность) На дубе ларец, а в ларце утка, а в утке яйцо, в яйце игла, в игле смерть Кощея. Поди туда, не знаю куда, принеси то, не знаю что. МассовостьКаждой дочери отец привёз по дорогому подарку. Принц мог жениться только на настоящей принцессе. ПонятностьИнструкция по-русски.Инструкция на японском языке. КонечностьМама сварила кашу в горшочке. Каша уже заполнила все улицы, а горшочек всё варил кашу. РезультативностьМышка хвостиком махнула, яйцо и разбилось. Баба била-била, не разбила.

9 Способы описания алгоритма: Словесный (письменно или устно); Графический (стрелками, рисунками, блок – схемами); Программный.

10 СПОСОБЫ ОПИСАНИЯ СЛОВЕСНО- ПОШАГОВЫЙ ГРАФИЧЕСКИЙ- БЛОК-СХЕМА АЛГОРИТМИЧЕСКИЙ ЯЗЫК или ПРОГРАММА

11 СЛОВЕСНО-ПОШАГОВЫЙ 1.Прочесть значение R. 2. Умножить значение R на 3, Умножить результат второго действия на значение R. 4. Записать полученный в предыдущей команде результат как значение S.

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

13 НАЧАЛО ВВОД R S:=3,14*R 2 КОНЕЦ S ВЫВОД S

14 АЛГ ЗАДАЧА(ВЕЩ R,S) АРГ R РЕЗ S НАЧ ВВОД R R:=3,14*R S:=R*R ВЫВОД S КОН

15 Основные символы блок-схем

16 БЛОК НАЧАЛА ИЛИ ОКОНЧАНИЯ ВЫПОЛНЕНИЯ АЛГОРИТМА НАЧАЛО КОНЕЦ

17 БЛОКИ ВВОДА-ВЫВОДА БЛОК ВЫВОДА БЛОК ВЫВОДА НА ПЕЧАТЬ ВЫВОД

18 БЛОК ПРИСВАИВАНИЯ Х:=У+120 ОБРАБАТЫВАЕТ ДАННЫЕ И РАЗМЕЩАЕТ РЕЗУЛЬТАТЫ В ЯЧЕЙКИ ПАМЯТИ С УКАЗАННЫМ ИМЕНЕМ

19 ПАРАМЕТР УСЛОВИЕ ДаНет БЛОК ПРОВЕРКИ УСЛОВИЯ БЛОК ЦИКЛА С ПАРАМЕТРОМ

20 БЛОК ОБРАЩЕНИЯ К ПОДПРОГРАММЕ ОБОЗНАЧАЕТ МОМЕНТ ПЕРЕХОДА К ПОДПРОГРАММЕ N – НОМЕР СТРОКИ, С КОТОРОЙ НАЧИНАЕТСЯ ПОДПРОГРАММА ИЛИ НАЗВАНИЕ ПОДПРОГРАММЫ N

21 Виды алгоритмов: Линейный – содержит несколько шагов и все шаги выполняются последовательно друг за другом; Разветвляющийся – порядок выполнения шагов изменяется в зависимости от некоторых условий; Циклический – определенная последовательность шагов повторяется несколько раз в зависимости от заданной величины (параметра цикла).

22 ЛИНЕЙНЫЙ Начало Оператор 1 Оператор 2 Оператор 3 ВВЕСТИ КОНЕЦ Программа имеет линейную структуру, если все операторы (команды) выполняются последовательно друг за другом. Пример Пример

23 НАЧАЛО ВВОД R S:=3,14*R 2 КОНЕЦ S ВЫВОД S

24 ВЕТВЯЩИЙСЯ НАЧАЛО УСЛОВИЕ ОПЕРАТОР 1ОПЕРАТОР 2 ВВЕСТИ КОНЕЦ Разветвляющий алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

25 КОМАНДА ВЕТВЛЕНИЯ ИМЕЕТ ПОЛНУЮ (1) ИЛИ СОКРАЩЕННУЮ ФОРМУ(2) 1 Серия 1 Условие Серия 2 ДаНет Да Нет Условие Серия 1 2

26 НАЧАЛО ВВОД A,B КОНЕЦ ВЫВОД M A>B M:=AM:=B ДаНет

27 Циклический НАЧАЛО ВВЕСТИ УСЛОВИЕ тело цикла КОНЕЦ ОПЕРАТОР 2 счетчик Циклический алгоритм - описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называют телом цикла.

28 КОМАНДА ПОВТОРЕНИЯ - ЭТО СОСТАВНАЯ КОМАНДА, В КОТОРОЙ ТЕЛО ЦИКЛА ВЫПОЛНЯЕТСЯ НЕСКОЛЬКО РАЗ.

29 ТРИ ТИПА КОМАНД ПОВТОРЕНИЯ: ЦИКЛ «ДЛЯ» ЦИКЛ «ПОКА» ЦИКЛ «ДО» ОТЛИЧИЕ - СПОСОБ ПРОВЕРКИ ОКОНЧАНИЯ ЦИКЛА.

30 НАЧАЛО КОНЕЦ I I

31 НАЧАЛО КОНЕЦ ДаНет I=1,10,2 I ЦИКЛ «ДЛЯ»

32 НАЧАЛО КОНЕЦ I I>10 I:=I+2 ДаНет ЦИКЛ «ДО»

33 Алгоритмические задачи Задание. Волк, коза и капуста. Старик должен переправить на лодке через реку волка, козу и капусту. Лодка может выдержать только старика и одного «пассажира». В каком порядке старик перевезёт «пассажиров»? Не забудь, что волк может съесть козу, а коза – капусту. Найди два варианта решения.

34 Задача. Переправа. К берегу реки, где была лодка, вмещающая только двух человек, подошли два разбойника и два путешественника. Разбойники не решались напасть на путешественников. В случае если на берегу останется один путешественник и два разбойника, они нападут на него. Как надо переправиться через реку разбойникам и путешественникам, чтобы последние смогли избежать нападения?