Программирование и основы алгоритмизации. Тема 5.1. Алгоритмы и структуры данных

Программирование и основы алгоритмизации
2
Роль алгоритмов и структур данных
Модель процессов
Алгоритмы
Модель объектов
Предметная область
Структуры
данных
Программы

Программирование и основы алгоритмизации
3
Понятие алгоритма
Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.
Дональд Эрвин Кнут

Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени.
Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм должен выдавать один и тот же результат для одних и тех же исходных данных.
Конечность — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
Масштабируемость — алгоритм должен быть применим к разным наборам исходных данных.
Результативность — завершение алгоритма определенными результатами.
Эффективность — завершение алгоритма определенными результатами за определенное число шагов (время).
Программирование и основы алгоритмизации
4
Свойства алгоритма

Легенда. В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света...
Программирование и основы алгоритмизации
5
Пример алгоритма - задача о Ханойских башнях

Программирование и основы алгоритмизации
6
Решение задачи о Ханойских башнях
Число шагов алгоритма вычисляется по формуле 2N − 1, где N − число колец .
Для перекладывания 64-х колец потребуется 18 446 744 073 709 551 615 шагов.
При скорости в одно перекладывание в секунду, потребуется около 584 542 046 091 лет.

Программирование и основы алгоритмизации
7
Эффективность алгоритмов
Временные фукции сложности
Полиномиальные
(P-задачи)
Экспоненциальные
(NP-задачи)

=
Программирование и основы алгоритмизации
8
Трансвычислительные задачи
Не существует системы обработки данных, искусственной или естественной, которая могла бы обрабатывать более 2*1047 бит в секунду на грамм своей массы.
Ханс Бреммерман
1093 бит
Предел Бреммермана
Трансвычислительные задачи

Программирование и основы алгоритмизации
9
Представления алгоритмов
Блок-схема
Псевдокод
Ввод N
I = 1
F = 1
ЦИКЛ ПОКА I <= N
F = F * I
ВСЁ-ЦИКЛ
Вывод F
Начало
Ввод N
I = 1
F = 1
I <= N
F = F * I
Вывод F
Конец
Да
Нет

Программирование и основы алгоритмизации
10
Блок-схемы алгоритмов
ГОСТ 19.701-90 (ИСО 5807-85). Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.
Наименование
Терминатор
Процесс
Решение
Предопределенный процесс
Данные
Соединитель
Комментарий
Обозначение
Функция
Элемент отображает вход из внешней среды или выход из нее (наиболее частое применение − начало и конец программы).
Выполнение одной или нескольких операций, обработка данных любого вида
Отображает решение с одним входом и двумя или более альтернатив-ными выходами, из которых только один может быть выбран.
Символ отображает выполнение процесса, который определен в другом месте программы
Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Символ отображает выход в часть схемы и вход из другой части этой схемы.
Используется для более подробного описания шага, процесса или группы процессов.

Программирование и основы алгоритмизации
11
Классы алгоритмов
Сортировка
Алгоритмы
Поиск
Оптимизация
Обходы графов

Программирование и основы алгоритмизации
12
Сортировка массивов
Код
Наименование
Цена
44
Яблоки
35.50
55
Апельсины
29.90
12
Бананы
22.00
...
...
...
Ключ
Уникальный
Неуникальный
Сортировка - упорядочение массива в соответствии со значениями ключа