Алгоритмы. История возникновения

1.

2.

СОДЕРЖАНИЕ ПРЕЗЕНТАЦИИ
1. История возникновения.
2. Понятие алгоритм.
3. Примеры алгоритмов.
4. Исполнители алгоритмов.
5. Что такое программа.
6. Свойства алгоритма.
7. Способы описания алгоритмов.
8. Основные блоки графического описания
алгоритма.
9. Типы алгоритмов.
10. Тест.
11. Задания.

3.

НЕМНОГО ИСТОРИИ
Аль-Хорезми
(786—850 гг. н.э.) —
основатель
алгебры,
от
его
имени
произошел термин «алгоритм».
В мировой науке он был известен своим
трактатом по математике, основанном на
позиционном принципе. Благодаря переводу
этого труда с арабского на латинский язык,
«арабские» цифры навсегда вошли в
мировую математику.
Имя автора в
латинизированной форме Algorismus и
Algorithmus первоначально дало название
правилам
четырех
арифметический
действий,
при
десятичной
системе
счисления.
Впоследствии слово «алгоритм» стало
обозначать всякий регулярный процесс, за
конечное число шагов дающий решение
определённого класса задач.

4.

АЛГОРИТМ
Понятие алгоритм – одно из фундаментальных
в информатике.
Алгоритм
—
это
совокупность
правил
выполнения
определенных действий, обеспечивающих решение задачи.
В жизни мы постоянно выполняем разные алгоритмы.
Составляем распорядок дня, чтобы
многое успеть.

5.

Задача может быть успешно решена
только тогда, когда она очень чётко
описана.
Из приведённого списка задач выберите
те, которые сформулированы чётко. Свой
ответ обоснуйте.
А) «Подсчитать звёзды»;
Б) «сосчитать число окон в своём доме»;
В) «купить книги»;
Г) «одеться»;
Д) «дать подробное описание дороги от
двери своего дома до школы (пешком, на
автобусе или другом транспорте)».

6.

ПРИМЕРЫ АЛГОРИТМОВ
Достаем
кулинарную
книгу
и
строго
следуем
рецепту,
написанному в ней, чтобы блюдо
удалось и можно было угостить
своих друзей.
Соблюдаем правила
дорожного движения
при переходе через
улицу.

7.

ИСПОЛНИТЕЛИ АЛГОРИТМОВ
Алгоритм составляется с учетом исполнителя.
Исполнителем может быть человек, автомат,
компьютер.

8. Характеристики исполнителя:

Сpеда — это «место обитания»
исполнителя.
Система команд – некоторый строго
заданный список команд.
После вызова команды исполнитель
совеpшает соответствующее
элементаpное действие.
Отказы исполнителя возникают, если
команда вызывается пpи недопустимом
для нее состоянии сpеды.

9.

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

10.

Чем исполнитель – машина
отличается от исполнителя –
человека?
Человек может мыслить.
Он сам принимает решения.
Машина работает автоматически. Она
выполняет те команды, которые для неё
предусмотрел человек . Машина работает
автоматически, т.е. действует формально.

11.

ПРОГРАММА
Каждый исполнитель имеет свою систему команд (СКИ).
Программа — это алгоритм, записанный на языке
исполнителя.
Рассмотрим пример: возьмем учебного исполнителя
Черепашку. Пусть этот исполнитель имеет три команды:
вперед(1 см), направо(900), налево (900).
Исходное положение исполнителя:
Какой код программы надо написать,
чтобы Черепашка начертила букву Г ?
Код программы будет выглядеть так:
налево (900)
вперед(1 см)
вперед 1 см
направо(900)
вперед(1см)

12. Выберите примеры исполнителей:

13.

СВОЙСТВА АЛГОРИТМА
(Требования к составлению алгоритма)
1. Дискретность. Процесс решения задачи должен быть разбит
на последовательность отдельных шагов, команд
2. Однозначность (точность, определенность). Команды
алгоритма должны быть точно определены (например, нельзя
написать 3-4 стакана муки, надо указать 3 стакана).
3. Результативность. После выполнения всех команд алгоритма,
должен быть получен результат.
4. Универсальность (массовость). Алгоритм должен быть
применим для решения ни одной конкретной задачи, а для
некоторого класса задач, различающихся исходными данными.
Например, для решения квадратного уравнения с разными
коэффициентами).
5. Понятность. Алгоритм должен быть написан на языке понятном
исполнителю.
6. Детерминированность. Для одних и тех же наборов исходных
данных алгоритм будет выдавать один и тот же результат.

14.

СПОСОБЫ ОПИСАНИЯ АЛГОРИТМА
Так часто бывает, что алгоритм составляет один автор, а
пишет программу другой человек. Алгоритмы бывают очень
сложными и большими по объему. Бывает, что над
алгоритмом трудятся сразу несколько человек. Учитывая все
эти причины и еще ряд других, алгоритмы записывают или
описывают на бумажных или электронных носителях.
Как можно описать алгоритм?
1. Словами. Например, распорядок дня.
2. Графически (блок-схемой). Так
делают программисты.
3. Алгоритмическим языком
(псевдокод) – это учебный язык. Он
применяется во многих тестах по
информатике.
4. Программно.

15. Определение:

Блок-схема – это графическое
изображение алгоритма в виде
определенным образом связанных
между собой нескольких типов
блоков.

16.

ОСНОВНЫЕ БЛОКИ
ГРАФИЧЕСКОГО ОПИСАНИЯ АЛГОРИТМА
Блоки
Что ими обозначают
Начало/конец алгоритма
Ввод/вывод данных
Обработку данных

17.

ОСНОВНЫЕ БЛОКИ
ГРАФИЧЕСКОГО ОПИСАНИЯ АЛГОРИТМА
Блоки
Что ими обозначают
Проверку условия
Начало цикла FOR/ NEXT
Подпрограмму

18.

Алгоритм
Линейный
алгоритм
Алгоритм с
ветвлением
Алгоритм с
повторением

19.

ТИПЫ АЛГОРИТМОВ
Линейный. Команды такого
алгоритма выполняются
последовательно сверху вниз.
Например, нахождение гипотенузы
прямоугольного треугольника по двум
его катетам.

20.

21.

ТИПЫ АЛГОРИТМОВ
Разветвляющийся. В зависимости
от поставленного условия алгоритм
позволяет
выбрать
один
из
вариантов решения задачи.
Примерами могут быть нахождение
корней квадратного уравнения или
богатырь на распутье из русских
сказок
налево
направо
прямо

22. Определение:

Условие – это
высказывание, которое
может быть либо истинным,
либо ложным.
Условия
простые
сложные

23. Простое условие

Включает в себя одно
предложение; два числа, две
переменных или два
арифметических выражения,
которые сравниваются между
собой
Например:
Идет дождь;
5>4;
x*y=3+8).

24. Сложное условие

Последовательность простых
условий, объединенных между
собой знаками логических
операций
И (AND), ИЛИ (OR).
Например: (10>0) AND (8>9);
(x=10) OR (x>=0).

25.

26. Определение:

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

27. Полный выбор

при условие 1: действия 1
при условие 2: действия 2
............
при условие N: действия N
иначе действия N+1

28. Неполный выбор

при условие 1: действия 1
при условие 2: действия 2
............
при условие N: действия N

29. Запись полного выбора в виде блок-схемы:

да
серия команд 1
условие 1
нет
…
условие n
да
нет
серия команд n+1
серия команд n

30. Запись неполного выбора в виде блок-схемы:

условие 1
да
серия команд 1
нет
условие 2
да
серия команд 2
нет
…
условие n
нет
да
серия команд n

31.

ТИПЫ АЛГОРИТМОВ
.
Циклический. В алгоритме встречаются
повторяющиеся действия.
Например, при заучивании стихотворения
вам приходится перечитывать и повторять
одни и те же строки.

32. Определение:

Цикл - это такая
алгоритмическая структура,
в которой серия команд
(тело цикла) выполняется
многократно.

33.

Цикл с предусловием
пока истинно условие,
предписывает выполнять тело
цикла.
Словесный способ записи:
пока условие
тело цикла

34. Запись цикла с предусловием в виде блок-схемы:

условие
да
тело цикла
нет

35.

Цикл с постусловием
предписывает выполнять тело
цикла до тех пор, пока не
выполнится условие выхода из
цикла.
Словесный способ записи
тело цикла
до условие

36. Запись цикла с постусловием в виде блок-схемы:

тело цикла
нет
условие
да

37.

Цикл со счетчиком
предписывает выполнять тело
цикла для всех значений
некоторой переменной
(параметра цикла) в заданном
диапазоне.
Словесный способ записи
для i от i1 до i2
тело цикла

38. Запись цикла со счетчиком в виде блок-схемы:

счетчик
да
тело цикла
нет

39. ТЕСТ

1. Набор геометрических фигур,
внутри которых записываются шаги
алгоритма называется …
А. блок-схемой
Б. алгоритмом
В. чёрным ящиком

40. ТЕСТ

2. Задание, состоящее из команд
исполнителю называется …
А. задачей
Б. блок-схемой
В. алгоритмом

41. ТЕСТ

3. Алгоритм называется
линейным, если
А. он представлен в виде таблицы
Б. действия выполняются друг за
другом
В. действия повторяются многократно

42. ТЕСТ

4. Алгоритм называется условным,
если
А. выполнение действий зависит от
условия
Б. действия выполняются друг за другом
В. действия повторяются многократно

43. ТЕСТ

5. Алгоритм называется
повторяющимся, если
А. ставится условие
Б. действия выполняются друг за другом
В. действия повторяются, пока не
выполнится данное условие

44.

Составить алгоритм, пронумеровать рисунки:
7
8
1
4
3
2
6
9
5

45. Задание 1. Запишите цифрами правильную последовательность выполнения алгоритма

Пришивание пуговицы
1.
2.
3.
4.
5.
6.
Взять пуговицу.
Взять иголку.
Вдеть нитку в иголку.
Отмотать от катушки и отрезать
нитку.
Пришить пуговицу.
Сделать узелок на конце нитки.

46. Лена любит картошку со сметаной. Расставь по порядку действия её мамы:

1. Посолила картофель.
2. Бросила картофель в кипяток.
3. Зажгла газовую плиту.
4. Очистила картофель.
5. Купила в магазине картофель и сметану.
6. Погасила огонь и слила кипяток.
7. Полила картофель сметаной.
8. Положила картофель на тарелку.
9. Налила воду в кастрюлю и поставила её на
огонь.
5
3
9
4
2
1
6
8
7

47.

48. Исправить алгоритм «Подготовка к рисованию»

Открыть баночку с краской
Надеть халат
Окунуть в нее кисть
Расстелить бумагу на столе
Надеть халат
Открыть баночку с краской
Рисовать на бумаге
Окунуть в нее кисть
Расстелить бумагу на столе
Рисовать на бумаге

49.

1
3
6
2
4
5

50.

ПРИВЕТИК! МЕНЯ ЗОВУТ БЛОКСХЕМЧИК!
Я ПРИГОТОВИЛ ДЛЯ ТЕБЯ ЗАДАНИЕ!
СОБЕРИ БЛОК-СХЕМУ ЛИНЕЙНОГО
АЛГОРИТМА!

51.

Некий злоумышленник за алгорит м получения кипят ка выдал
такую последоват ельност ь дейст вий:
Правильный ответ
1. Налить в чайник воду.
2. Открыть кран газовой горелки.
3. Поставить чайник на плиту.
4. Ждать, пока вода не закипит.
5. Поднести спичку к горелке.
6. Зажечь спичку.
7. Выключить газ.
Исправьте алгоритм,
чтобы предотвратить несчастный случай.

52.

Найдите алгоритм сказки Репка
1
2
3

53. Найди решение в блок-схемах

5
7
+8
+3
Да
:3
< 7 ?
- 4
+ 4
+3
8
Нет
12

54.

Кабы не было зимы
В городах и селах,
Не кружила б малышня
Никогда б не знали мы
Возле снежной бабы,
Этих дней веселых!
Не петляла бы лыжня,
Кабы, кабы, кабы…
Составьте блок-схему к этой песенке.

55.

НАЧАЛО
Первый блок – это всегда
НАЧАЛО
Ст релки показывают
направление перехода
Города, села
Города и села – это
исходные данные!
Проверяем - там
есть зима ?
Если ДА, то:
ДА
Есть зима?
- малышня кружит
возле снежной бабы,
- лыжня петляет;
- мы знаем веселые
дни (это результат!),
иначе (стрелка НЕТ)…
- малышня НЕ кружит
возле снежной бабы,
- лыжня НЕ петляет;
НЕ знать нам веселья!
В любом случае –
КОНЕЦ!
КОНЕЦ
НЕТ

56.

Вычислить
алгоритм
разветвленной
структуры,
представленный в
Да
виде блок-схемы,
при заданном
x=x-5
входном потоке
исходных данных.
a
0
2
4
6
8
x
-5 -1 3 18 22
начало
ввод: a
x=a*2
x < 10
Нет
x=x+6
вывод: x
конец

57.

Вот алгоритм , который составила
мачеха для Золушки:
Перемой-ка всю посуду.
Да натри полы повсюду,
Дров на месяц наколи,
Кофе на год намели,
Посади среди цветов
Сорок розовых кустов,
И, пока не подрастут,
Подметай дорожки тут

58.

Блок-схема
Рецепт каши из
топора
Начало
Поставить топор вариться
Словесная форма записи
1) Поставить топор вариться
2) Посолить
3) Добавить крупы
4) Варить
5) Сдобрить маслом
Посолить
Добавить крупы
Варить
Сдобрить маслом
Конец

59.

Начало
Жили-были дед и баба,
И была у них курочка Ряба.
Снесла курочка яичко,
не простое, а золотое.
Не плачь, дед
Не плачь, баба.
Я снесу вам
Другое яичко.
Не золотое,
А простое.
Дед бил-бил, не разбил.
Яичко упало и разбилось.
Баба била-била, не разбила
Мышка бежала, хвостиком
махнула.
Дед плачет, баба плачет,
А курочка Ряба кудахчет:
Конец

60. Сказка «Гуси – лебеди»

61.

Эпизод с Речкой
Девочка просит
Речку спрятать
ее и брата
ДА
Поешь
моего простого
киселька
?
НЕТ
Спрячу
Не спрячу
Гуси-лебеди
не найдут
Гуси-лебеди
догонят

62.

Эпизод с Яблоней
Девочка просит
Яблоню спрятать
ее и брата
ДА
Поешь
моего лесного
яблочка
?
НЕТ
Спрячу
Не спрячу
Гуси-лебеди
не найдут
Гуси-лебеди
догонят

63.

Эпизод с Печкой
Девочка просит
Печку спрятать
ее и брата
ДА
Поешь
моего ржаного
пирожка
?
НЕТ
Спрячу
Не спрячу
Гуси-лебеди
не найдут
Гуси-лебеди
догонят

64.

начало
Дети убежали от Бабы-Яги
Встретился сказочный объект
Девочка просит сказочный
Объект спрятать ее и брата
ДА
Выполнишь
просьбу?
НЕТ
Спрячу
Не спрячу
Гуси-лебеди не найдут
Гуси-лебеди догонят
Дети бегут дальше
НЕТ
Добежали
до дома?
ДА
Сказка закончилась
несчастливо
Сказка закончилась
счастливо
конец

65.

начало
К
О
Л
О
Б
О
К
Испекла бабка колобок и поставила его на окошко остужаться
Убежал колобок от деда и бабки и покатился по дорожке
Катится колобок, а навстречу
ему - зверь
НЕТ
Зверь - лиса?
ДА
Колобок поет песенку
Колобок поет песенку
два раза
Катится дальше
Прощай, колобок…
конец

66.

Блок-схема
Да
Надвигается
угроза?
Всполошится, обернётся
в направлении угрозы
Нет
Сидит смирно
Словесная форма записи
Если кругом мирно, то сидит смирно
Если надвигается беда (угроза), то Приподнимет гребешок,
Закричит
Встрепенётся
Обернётся в сторону беды
(угрозы)