Алгоритмы и их свойства (лекция 1)

1.

Алгоритмы и структуры данных
Лекция 1. Алгоритмы и их свойства

2.

3.

4.

5.

6.

7.

8.

9.

Способы записи алгоритма
Словесный (естественный язык, ЕЯ)
Ограниченный естественный язык (ОЕЯ)
Схематический (графический)
Псевдоязык (в том числе языки программирования)
Алгоритмы и структуры данных
6

10.

Использование естественного языка
Наиболее простой способ - ЕЯ (естественный язык)
Пример алгоритма для приготовления кипятка
1. взять чайник
2. открыть крышку
3. если есть вода, перейти к шагу 5
4. налить воды
5. поставить на огонь
6. дождаться струи пара
Алгоритмы и структуры данных
7

11.

Использование естественного языка
Достоинства:
1. Понятен всем носителям языка
2. Не требует специального синтаксиса
3. Легко поддаётся редактированию
Недостатки:
1. Неоднозначен (некоторые слова и выражения могут толковаться
по-разному)
2. Трудно изучаем для иностранцев, не владеющих языком
3. Несёт в себе избыточность в плане количества информации
Алгоритмы и структуры данных
8

12.

Использование ограниченного естественного языка
Мы можем устранить неоднозначность, оставив только однозначные слова.
Пример
1. Посмотреть налево
2. Посмотреть направо
3. Перейти дорогу
Каждое слово может быть командой или параметром. В примере слова
Перейти, Посмотреть относятся к командам, а остальные - к параметрам.
Хороший пример командного языка: армейский. В условиях боевых действий нет времени задумываться о смысле заданий.
Алгоритмы и структуры данных
9

13.

Использование схем и диаграмм
Элементы блок-схем строятся (согласно ГОСТ 19.701-90) из следующих
элементов:
Пуск-останов
Ввод-вывод
Процесс
условие
Цикл
Предпроцесс
Алгоритмы и структуры данных
12

14.

Использование схем и диаграмм
Линейный алгоритм - это такой, в котором все операции выполняются
последовательно одна за другой
Рис. 1
блоков
в
алгоритме
Размещение
линейном
Алгоритмы и структуры данных
10

15.

Использование схем и диаграмм
Алгоритмы разветвленной структуры применяются, когда в зависимости от
некоторого условия необходимо выполнить либо одно, либо другое действие.
Рис. 2 Фрагмент алгоритма
Рис.
3
разветвления
Алгоритмы и структуры данных
Пример
10

16.

Использование схем и диаграмм
Схемы, рисунки и диаграммы часто бывают более наглядны, но могут требовать и пояснений.
Алгоритмы и структуры данных
10

17.

Использование схем и диаграмм
Цикл, для которого нельзя указать число повторения, и проверка
окончания которого происходят по достижению нужного условия,
называется итерационным.
Рис. 4 Цикл с
предусловием
Рис.
5
постусловием
Алгоритмы и структуры данных
Цикл
с
10

18.

Использование псевдоязыка
Псевдоко́д —
компактный
(зачастую
неформальный)
язык
описания алгоритмов, использующий ключевые слова императивных языков
программирования, но опускающий несущественные подробности и
специфический синтаксис. Псевдокод обычно опускает детали, несущественные
для понимания алгоритма человеком. Такими несущественными деталями могут
быть описания переменных, системно-зависимый код и подпрограммы. Главная
цель использования псевдокода — обеспечить понимание алгоритма человеком,
сделать описание более воспринимаемым, чем исходный код на языке
программирования. Псевдокод широко используется в учебниках и научнотехнических
публикациях,
а
также
на
начальных
стадиях
разработки компьютерных программ.
если (условие) то
действия1
иначе
действия2
Алгоритмы и структуры данных
14

19.

Использование псевдоязыка
Псевдоязык очень напоминает алгоритмический язык программирования,
но использует обобщённые для многих языков конструкции
1: procedure Euclid(a, b)
2:
3:
4:
5:
r ← a mod b
while r ≠ 0 do
a← b
b← r
▷НОД а и b
▷ответ получен, если r равно 0
r ← a mod b
end while
8:
return b
9: end procedure
6:
7:
Штанюк А.А. (НГТУ::ИРИТ)
▷НОД - b
Алгоритмы и структуры данных
14

20.

Использование псевдоязыка
Блок IF
Блок WHILE
1: if quality ≥ 9 then
1: sum ← 0
a ← perfect
3: else if quality ≥ 7 then
4:
a ← good
5: else if quality ≥ 5 then
6:
a ← medium
7: else if quality ≥ 3 then
8:
a ← bad
9: else
10:
a ← unusable
11: end if
2: i ← 1
2:
3: while i ≤ n do
sum ← sum + i
i← i+ 1
6: end while
4:
5:
Блок REPEAT
1: sum ← 0
2: i ← 1
3: repeat
sum ← sum + i
i← i+ 1
6: until i > n
4:
5:
Штанюк А.А. (НГТУ::ИРИТ)
Алгоритмы и структуры данных
15

21.

Использование псевдоязыка
Блок FOR
1: sum ← 0
1: s ← 0
2: for i ← 1, n do
2: p ← 0
sum ← sum + i
4: end for
3: for i ← 1, 10 do
3:
s← s+ i
p← p+ s
6: end for
4:
5:
Алгоритмы и структуры данных
16

22.

23.

24.

25.

26.

27.

Асимптотический анализ алгоритмов
Для представления временной сложности алгоритмов в основном
используют три асимптотических нотации:
1. Θ-нотация (нотация тета большое);
2. O-нотация (нотация о большое);
3. Ω-нотация (нотация омега большое).
Алгоритмы и структуры данных
18

28.

Нотация «O» большое , O
Обозначение Ο(n) — это формальный способ определения верхней
границы времени выполнения алгоритма. Применяется для измерения
временной сложности в худшем случае или наибольшего времени,
требующегося для завершения алгоритма.
O(g(n)) = { f(n): существуют
такие константы c и n0,
что 0 ≤ f(n) ≤ cg(n) для
любых n ≥ n0 }
Алгоритмы и структуры данных
18

29.

Омега-нотация, Ω
Обозначение Ω(n) — это формальный способ определения нижней
границы времени выполнения алгоритма. Применяется для измерения
временной сложности в лучшем случае или наименьшего времени,
требующегося для завершения алгоритма.
Ω(g(n)) = { f(n): существуют
такие положительные
константы c и n0,
что 0 ≤ cg(n) ≤ f(n) для
всех n ≥ n0 }
Алгоритмы и структуры данных
18

30.

Тета-нотация, θ
Обозначение θ(n) — это формальный способ определения нижней и верхней
границ времени выполнения алгоритма. Выглядит она так:
Θ(g(n)) = { f(n): существуют
такие положительные константы c1,
c2
и
n0,
что 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) для
любых n ≥ n0 }
Алгоритмы и структуры данных
18