Алгоритмы. Стандартный набор алгоритмов

1. Алгоритмы

АЛГОРИТМЫ
Лекция №1

2. Зачем изучать алгоритмы?

Стандартный набор
алгоритмов,
разработка новых
алгоритмов,
анализ эффективности
алгоритмов
Основы информатики

3.

«Хорошо обученный в области информатики специалист обязан
знать, как работать с алгоритмами: как их создавать, изменять,
понимать и анализировать. Эти знания позволят не только писать
хорошие компьютерные программы, но и станут основой
универсального мыслительного аппарата, который окажет
неоценимую помощь при постижении других наук, будь то химия,
лингвистика, музыка и т.д. Причину этого можно объяснить
следующим образом: часто говорят, что человек ничего не
понимает, пока не объяснит это кому-либо другому. Я бы
перефразировал это так: человек глубоко не понимает предмет до
тех пор, пока не научит этому компьютер, т.е. выразит что-либо в
виде алгоритма… Попытка формализовать нечто в виде набора
алгоритмов приводит к более глубокому пониманию сути вещей,
чем при их осмыслении традиционным способом».
/Дональд
Кнут
Дональд
Эрвин
Кнут
—
американский
учёный
в
области
информатики, преподаватель и идеолог программирования, автор 19
монографий (в том числе ряда классических книг по программированию) и
более 160 статей, разработчик нескольких известных программных
технологий. Автор всемирно известной серии книг, посвящённой
основным алгоритмам и методам вычислительной математики.

4. Цель дисциплины

Алгоритмическое мышление – это
• Искусство размышлять,
• Умение планировать свои действия,
• Способность предусматривать различные
обстоятельства и поступать соответственно с ними.

5. Понятие алгоритма

Слово «алгоритм» происходит от имени средневекового
арабского учёного Абу Джафар Мохамед ибн Мусы альХорезми, который в IX веке сформулировал правила
вычислений с десятичными числами. Работы аль-Хорезми
были переведены на латинский язы и стали известны в
Европе. Через некоторое время слово «алгоритм» (от имени
автора, которое на латыни писали как Algorithmi) стало
обозначать любую систему вычислений по определённым
правилам.

6. Понятие алгоритма

Многие действия, которые мы выполняем в жизни, можно
записать как последовательность шагов.
Строительство дома
1.Заливка фундамента.
2.Возведение стен.
3. Возведение крыши.
Менять последовательность действий нельзя, иначе стройка
закончится неудачно.

7. Алгоритм открывания двери:

1.
Достать ключ из кармана.
2.
Вставить ключ в замочную скважину.
3.
Повернуть ключ два раза против часовой стрелки.
4.
Вынуть ключ.

8. Алгоритм заваривания зеленого чая:

■ Обдать кипятком заварочный чайник.
■ Насыпать в чайник листья зеленого чая в расчете одна
чайная ложка на чашку чая.
■ Залить чайник кипятком.
■ Дать постоять 2-3 минуты.
■ Слить заварку.
■ Снова залить кипятком.
■ Снова слить заварку.
■ Снова залить кипятком. Чай готов.

9. Определение

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

10.

Алгоритм
Алгоритм – это четко определенный план действий для
исполнителя.
Свойства алгоритма
• дискретность: состоит из отдельных шагов (команд)
• понятность: должен включать только команды,
известные исполнителю (входящие в СКИ)
• определенность: при одинаковых исходных данных
всегда выдает один и тот же результат
• конечность: заканчивается за конечное число шагов
• массовость: может применяться многократно при
различных исходных данных
• корректность: дает верное решение при любых
допустимых исходных данных
10

11. Эффективность алгоритма

Задача. Сложить числа 1+2+3++4+…+99+100.
1-ый алгоритм:
2-ой алгоритм:
Последовательным
сложением: 1 + 2 + 3
+ 4 + … + 99 + 100 =
5050
Разбить все числа на
пары 1 + 100, 2 + 99,
… 50 + 51 и все
суммы равны 101,
поэтому общий
результат равен
50 × 101 = 5050.

12. Способы описания алгоритмов

■ Словесное описание
■ Псевдокод
■ Графический способ
■ На алгоритмическом языке

13. Словесная запись алгоритма

Это удобно и привычно, но есть одна проблема: во всех
естественных языках есть неоднозначность, поэтому исполнительчеловек может понять алгоритм не так, как задумывал его автор.
Особенно трудно разбираться в длинных словесных алгоритмах,
занимающих больше десятка строк.
Пример алгоритма:
Автомат получает на вход трехзначное десятичное число. По
полученному числу строится новое десятичное число по следующим
правилам. Сначала вычисляются сумма старшего и среднего
разрядов, а также сумма среднего и младшего разрядов заданного
числа. Затем полученные два числа записываются друг за другом в
порядке не- возрастания (без разделителей).

14. Пошаговая запись алгоритма

Пример.
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Уменьшить a на величину b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.
Обратите внимание, что ясно определено, что служит исходными
данными для работы этого алгоритма (см. первую строчку — Вход) и
что будет считаться результатом его работы (строчка Результат).
Подумайте, что вычисляет этот алгоритм и что будет, если
применить его к таким исходным данным: a = 19, b = 5.

15. Блок-схемы алгоритмов

Пример.
начало
a, b
a<b
Да
Нет
a←a-b
a, b
конец

16. Ручная прокрутка алгоритмов

Программистам часто приходится разбираться, почему не работает
какой-то алгоритм, свой собственный или даже написанный другим
человеком. Для этого нужно выполнить алгоритм вручную для какихто исходных данных и сравнить результаты каждого шага с тем, что
должно было получиться.
Пример.
a<b
a
b
19
5
Нет
14
5
нет
9
5
Нет
4
5
да
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Уменьшить a на величину b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.

17. Программа. Этапы разработки программы

Программирование – это процесс создания (разработки)
программы, который может быть представлен
последовательностью следующих шагов:
1.
2.
3.
4.
5.
Определение требований к программе
Разработка алгоритма
Написание команд (кода)
Отладка
Тестирование.

18. Определение требований к программе

Подробно описывается исходная информация и
формулируются требования к результату. Т.е. выполняется
постановка задачи.
Кроме того, описывается поведение программы в особых
случаях.
Если программа будет работать в Windows, то нужно
разработать диалоговые окна, обеспечивающие
взаимодействие пользователя и программы.

19. Разработка алгоритма

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

20. Кодирование

После того как определены требования к программе и
составлен алгоритм решения, алгоритм записывается на
выбранном языке программирования.
В результате получается исходная программа.

21. Отладка

Отладка - это процесс поиска и устранения ошибок.
Синтаксические ошибки – нарушение формальных правил
записи на языке программирования. Диагностируются
транслятором.
Семантические ошибки – нарушение правил интерпретации
смыслового значения программы и ее практической
полезности. Выявляются в процессе тестирования.
Этап отладки можно считать законченным, если программа
работает на одном-двух наборах входных данных.

22. Тестирование

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

23.

Комплект тестов должен быть таким, чтобы подвергнуть
проверке:
• все ветви алгоритма,
• Все циклические и рекурсивные структуры,
• Все вырожденные и предельные случаи решения.

24. Система тестов для задачи нахождения корней квадратного уравнения ax2 + bx + c = 0.