2_1_основы алгоритмизации (1)

1. Основы алгоритмизации

1
Основы
алгоритмизации
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

2. Что такое алгоритм?

Алгоритмизация и программирование, язык Python, 10 класс
2
Что такое алгоритм?
Алгоритм — это точное описание
порядка действий, которые должен
выполнить исполнитель для решения
задачи за конечное время.
Исполнитель – это устройство или
одушёвленное существо (человек),
способное понять и выполнить
команды, составляющие алгоритм.
Мухаммед ал-Хорезми
(ок. 783–ок. 850 гг.)
Система команд исполнителя (СКИ) – это все
команды, которые исполнитель умеет выполнять.
Среда исполнителя – обстановка, в которой
функционирует исполнитель.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
3
Свойства алгоритма
Дискретность — алгоритм состоит из отдельных команд,
каждая из которых выполняется за конечное время.
Понятность — алгоритм содержит только команды,
входящие в систему команд исполнителя.
Конечность (результативность) — для корректного
набора данных алгоритм должен завершаться через
конечное время.
Корректность — для допустимых исходных данных
алгоритм должен приводить к правильному результату.
Общность, то есть один и тот же алгоритм можно
применять для решения целого класса однотипных
задач, различающихся исходными данными.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

4.

Алгоритмизация и программирование, язык Python, 10 класс
4
Эффективность – для решения задачи должны
использоваться ограниченные ресурсы, то есть действия
исполнителя на каждом шаге должны быть достаточно
простыми, чтобы их можно было выполнить точно и за
конечное время.
Однозначность (точность) – каждый шаг алгоритма
должен быть чётко и недвусмысленно определён, т.е.
не должен допускать произвольной трактовки
исполнителем.
Детерминированность (определённость) — при каждом
запуске алгоритма с одними и теми же исходными
данными получается один и тот же результат.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

5. Способы записи алгоритма

1. Словесный (письменно или устно)
2. Псевдокод
3. Графический (стрелками,
рисунками, блок-схемами)
4. Программный (с помощью какогото языка программирования)

6. Способы записи алгоритмов

Алгоритмизация и программирование, язык Python, 10 класс
6
Способы записи алгоритмов
• естественный язык
установить соединение
пока не принята команда «стоп»
принять команду
выполнить команду
завершить сеанс связи
• псевдокод
установить соединение
начало цикла
принять команду
выполнить команду
конец цикла при команда = 'stop'
завершить сеанс связи
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

7. Способы записи алгоритмов

Алгоритмизация и программирование, язык Python, 10 класс
7
Способы записи алгоритмов
• блок-схема
• программа
установить
соединение
принять
команду
выполнить
команду
нет
«стоп»?
да
завершить
соединение
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

8. Элементы блок-схем

Начало
или
конец
алгоритма
Простая команда =
действие = оператор
Ввод
или
вывод
данных
Проверка условия
Обращение к вспомогательному
алгоритму (подпрограмме)
Арифметический цикл

9. Пример 1. Вычисление площади круга

Входные данные: R
Выходные данные: S
Словесное описание алгоритма:
1. Начало. Переход на шаг 2.
2. Ввести R. Переход на шаг 3.
3. Вычислить S= π*R*R. Переход на шаг 4.
4. Вывести S. Переход на шаг 5.
5. Конец.

10. Графическая запись алгоритма

начало
Ввод R
S=3,14*R*R
Вывод S
конец

11.

Пример 2. Вычисление площади
треугольника S=√p(p-a)(p-b)(p-c)
Входные данные: a, b, c
Выходные данные: S
Словесное описание алгоритма:
1. Начало. Переход на шаг 2.
2. Ввести a, b, c. Переход на шаг 3.
3. Вычислить p=(a+b+c)/2. Переход на шаг 4.
4. Вычислить S:=Sqrt(p*(p-a)*(p-b)*(p-c)).
Переход на шаг 5.
5. Вывести S. Переход на шаг 6.
6. Конец.

12.

начало
Ввод a, b, c
P=(a+b+c)/2
S=sqrt(p*(p-a)*(p-b)*(p-c))
Вывод S
конец

13. Виды алгоритмов

1. Линейный
2. Разветвляющийся
3. Циклический
4. Рекурсия

14.

1. Линейный алгоритм – это алгоритм, который
содержит несколько шагов и все шаги
выполняются последовательно друг за другом.

15.

2. Разветвляющийся алгоритм –
алгоритм, в котором в зависимости от
условия выполняется либо одна, либо
другая последовательность действий

16. Неполная форма ветвления

Если условие верно, то выполняется
действие.

17.

1. Ввести числа a и b. Если а>b, то
уменьшить а на 5.

18. Полная форма ветвления

Если условие верно, то выполняется
действие 2, иначе выполняется действие 1.

19.

19
Введите число. Если число четное, то
вычти из него 5, если число нечетное,
то прибавь 10.

20.

3. Циклический алгоритм – это алгоритм,
в котором определенная
последовательность шагов повторяется
несколько раз в зависимости от заданной
величины (условия).
Виды циклов:
• Цикл с условием;
• Арифметический цикл (с определенным
количеством шагов)

21.

21
• Рекурсивный алгоритм – алгоритм,
который обращается сам к себе

22. Сложность вычислений

22
Сложность вычислений
• Сложность вычислений изучает,
сколько ресурсов (время, память)
требуется алгоритму для решения
задачи в зависимости от размера
входных данных.

23.

• Время определяется количеством
элементарных шагов, необходимых для
решения проблемы.
Количество элементарных операций,
зависит не только от размера входных
данных, но и от самих данных.
• Пространственная сложность
алгоритма определяется объёмом
используемой памяти.
23

24. Виды сложности:

24
Виды сложности:
• Худший случай
• Средний случай
• Лучший случай

25.

• Временная сложность алгоритма (в
худшем случае) — это функция размера
входных и выходных данных, равная
максимальному количеству элементарных
операций, проделываемых алгоритмом для
решения задачи.
• Временная сложность алгоритма в
наилучшем случае
25

26. Алгоритмически неразрешимые задачи

26
• Алгоритмически неразрешимые задачи —
это проблемы, для которых не
существует универсального, конечного
набора инструкций (алгоритма)
• Это задачи, соответствующие
невычислимым функциям, например,
знаменитая проблема
остановки машины Тьюринга или
проблема эквивалентности алгоритмов.

27. Доказательство правильности программ

27

28.

Алгоритмизация и программирование, язык Python, 10 класс
Язык программирования — это формальный,
строгий язык, состоящий из набора правил,
предназначенный для записи компьютерных
программ.
Компьютерная программа — это набор
инструкций и данных на языке, который
предназначен для выполнения определенных
задач и получения конкретного результата.
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

29.

Алгоритмизация и программирование, язык Python, 10 класс
Виды языков:
• Профессиональные языки общего назначения
• Языки для программирования сайтов
• Языки для решения задач искусственного
интеллекта
• Языки для обучения программированию
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

30. Что такое алгоритм?

Алгоритмизация и программирование, язык Python, 10 класс
30
Что такое алгоритм?
Что такое исполнитель?
Перечислите свойства алгоритма
Какие способы записи алгоритмов вы
знаете?
Какие виды алгоритмов вы знаете?
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru