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

Раздел 5: Алгоритмы
5.1 Понятие алгоритма
5.2 Представление алгоритма
5.3 Создание алгоритма
5.4 Итерационные структуры
5.5 Рекурсивные структуры
5.6 Эффективность и правильность
5-

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

Представление алгоритма
Требует четко определенных примитивов
Коллекция примитивов представляет собой язык программирования.
5-

Рисунок 5.2 Как сложить птичку из квадратного листа бумаги
5-

Рисунок 5.3 Примитивы оригами
5-
Примитив = Синтаксис + Семантика
Семантика
определяет символьное
представление примитива
Синтаксис
определяет значение примитива

Примитивы псевдокода
Присваивание
(имя) ? (выражение)
Условный выбор
if (условие) then (действие)
5-

Примитивы псевдокода (продолжение)
Цикл с предусловием
while (условие) do (действие)
Процедура
procedure имя (параметры)
5-

Рисунок 5.4 Процедура приветствия в псевдокоде
5-

Шаги общего плана решения проблемы
1. Понять проблему.
2. Разработать план решения задачи.
3. Осуществить свой замысел.
4. Оценить точность решения и его потенциал, как инструмента для решения других проблем
5-

Пинок в дверь
Попробуйте решить проблему с конца
Облегчите решение связанных задач
Отбросьте некоторые проблемные ограничения
Решите сначала части проблемы (методология «снизу вверх»)
Используйте поэтапное уточнение: разделите проблему на более мелкие проблемы (методология «сверху вниз»)
5-

Проблема возраста детей
Некто A хочет определить возраст троих детей некоего B
B сообщает A, что произведение возрастов его детей равно 36.
A сообщает, что нужна ещё подсказка.
B сообщает A сумму возрастов детей.
A повторяет, что ему нужна ещё подсказка.
B говорит A, что старший из детей играет на пианино.
A сообщает B возраст всех трёх детей..
Сколько лет детям?
5-

Рисунок 5.5
5-

Итерационные структуры
Цикл с предусловием:
while (условие) do
(тело цикла)
Цикл с постусловием:
repeat (тело цикла) until(условие)
5-

Рисунок 5.6 Алгоритм последовательного поиска, сформулированный с помощью псевдокода
5-

Рисунок 5.7 Операции процедуры управления повторяющимися действиями
5-

Рисунок 5.8 Структура цикла типа while-do
5-

Рисунок 5.9 Структура цикла типа repeat-until
5-

Рисунок 5.10 Сортировка списка имён Fred, Alex, Diana, Byron и Carol в алфавитном порядке
5-

Рисунок 5.11 Алгоритм сортировки методом вставки, написанный в псевдокоде
5-

Algorithm Efficiency
Measured as number of instructions executed
Big theta notation: Used to represent efficiency classes
Example: Insertion sort is in Θ(n2)
Best, worst, and average case analysis
5-

Классы сложности
5-

Рисунок 5.18 Работа алгоритма сортировки методом вставки в наихудшем случае
5-

Рисунок 5.19 График продолжительности работы алгоритма сортировки методом вставки для наихудшего случая
5-