Элементы теории алгоритмов

1.

Элементы теории
алгоритмов
ОЗЕРКОВА ИРИНА АЛЕКСАНДРОВНА

2.

Элементы теории алгоритмов
Представление алгоритма
Свойства алгоритмов
Виды алгоритмов
Обоснование алгоритмов
Сложность алгоритмов
Способы создания алгоритмов
Объекты алгоритмов

3.

Определение алгоритма
Алгоритм – это строго определённая последовательность
действий, предназначенная для решения заданной задачи
конкретным исполнителем

4.

Представление
алгоритма

5.

Виды представления
Текстовое (словесное описание)
Графическое (блок-схема и другие виды схем)
Программа (запись алгоритма на языке программирования или
в машинных кодах)

6.

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

7.

Основные свойства
Понятность
Дискретность
Детерминированность
Конечность
Результативность
Массовость

8.

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

9.

Классификация по структуре
Линейный
Разветвляющийся
Циклический
Рекурсивный

10.

Классификация по назначению
Основной
Вспомогательный

11.

Классификация по
детерминированности
Детерминированный
Вероятностный
Самообучающийся

12.

Обоснование
алгоритмов

13.

Необходимость обоснования
алгоритмов
1. Конечность и результативность алгоритма не обязательно
означают правильность результата
2. Пробный запуск алгоритма на тестовых данных ничего не
говорит о конечности, результативности и правильности
результатов с реальными данными

14.

Проверка
правильности/неправильности
Поиск контрпримеров
Математическое доказательство
Доказательство на основе конечных автоматов
Математическая индукция
Доказательство от противного

15.

Сложность алгоритмов

16.

Модель вычислений в RAM

17.

Анализ сложности для разных входных
данных

18.

Виды сложности

19.

Необходимости асимптотики для
анализа

20.

Асимптотические обозначения

21.

Иллюстрация асимптотических
обозначений

22.

23.

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

24.

Задача
Количество решений
Одно решение
Все решения
Точность решения
Точное решение
Приближённое решение
Оптимальность решения
Оптимальное решение
Достаточно хорошее решение

25.

Основные способы
Полный перебор
«Жадный» алгоритм
«Разделяй и властвуй»
Динамическое программирование
Перебор с возвратом
Метод ветвей и границ

26.

Полный перебор
Полный перебор (Brute Force) – осуществляет упорядоченный
перебор всех вариантов решения задачи.
Самый неэффективный (максимальная сложность)
Ищет все подходящие решения
Применяется только тогда, когда всё другое не работает
(например, поиск элемента в неупорядоченном массиве)

27.

«Жадный» алгоритм
Представляет последовательный выбор наилучшего
локального варианта
Ищет одно решение
Эффективнее, чем полный перебор
Может давать оптимальное решение (алгоритмы на графах), а
может не давать (задача о рюкзаке

28.

«Разделяй и властвуй»
Заключается в разбиении задачи на задачи меньшего размера
(пример сортировка слиянием, быстрая сортировка)
Ищет одно решение
Приводит к оптимальному решению
Эффективная

29.

Динамическое программирование
Использует память (одномерные или двумерные массивы) для
хранения промежуточных вычислений
В случае нескольких равноправных решений может дать все
Даёт оптимальное решение
Экономит время за счёт дополнительной памяти

30.

Перебор с возвратом
Выполняет откат после неудачно выполненного шага (или
после нахождения решения для перебора оставшихся
вариантов)
Может дать все решения
Решения будут точные
Быстрее, чем полный перебор

31.

Метод ветвей и границ
Множество решений делится на группы, заведомо
неоптимальные группы отсекаются
Может дать множество решений
Используется для сокращения перебора

32.

Объекты алгоритмов

33.

Типы объектов
Абстрактные объекты
Реализованные объекты
Для каждого абстрактного типа обычно существует несколько
способов реализации в программном коде

34.

Реализованные объекты
Встроенные в систему языка программирования
Определённые программистом

35.

Абстрактные объекты
Список
Очередь
Стек
Дерево
Куча
Множество
Словарь
Граф