Похожие презентации:
Элементы теории алгоритмов
1.
Элементы теорииалгоритмов
ОЗЕРКОВА ИРИНА АЛЕКСАНДРОВНА
2.
Элементы теории алгоритмовПредставление алгоритма
Свойства алгоритмов
Виды алгоритмов
Обоснование алгоритмов
Сложность алгоритмов
Способы создания алгоритмов
Объекты алгоритмов
3.
Определение алгоритмаАлгоритм – это строго определённая последовательность
действий, предназначенная для решения заданной задачи
конкретным исполнителем
4.
Представлениеалгоритма
5.
Виды представленияТекстовое (словесное описание)
Графическое (блок-схема и другие виды схем)
Программа (запись алгоритма на языке программирования или
в машинных кодах)
6.
Свойства алгоритмов7.
Основные свойстваПонятность
Дискретность
Детерминированность
Конечность
Результативность
Массовость
8.
Виды алгоритмов9.
Классификация по структуреЛинейный
Разветвляющийся
Циклический
Рекурсивный
10.
Классификация по назначениюОсновной
Вспомогательный
11.
Классификация подетерминированности
Детерминированный
Вероятностный
Самообучающийся
12.
Обоснованиеалгоритмов
13.
Необходимость обоснованияалгоритмов
1. Конечность и результативность алгоритма не обязательно
означают правильность результата
2. Пробный запуск алгоритма на тестовых данных ничего не
говорит о конечности, результативности и правильности
результатов с реальными данными
14.
Проверкаправильности/неправильности
Поиск контрпримеров
Математическое доказательство
Доказательство на основе конечных автоматов
Математическая индукция
Доказательство от противного
15.
Сложность алгоритмов16.
Модель вычислений в RAM17.
Анализ сложности для разных входныхданных
18.
Виды сложности19.
Необходимости асимптотики дляанализа
20.
Асимптотические обозначения21.
Иллюстрация асимптотическихобозначений
22.
23.
Способы созданияалгоритмов
24.
ЗадачаКоличество решений
Одно решение
Все решения
Точность решения
Точное решение
Приближённое решение
Оптимальность решения
Оптимальное решение
Достаточно хорошее решение
25.
Основные способыПолный перебор
«Жадный» алгоритм
«Разделяй и властвуй»
Динамическое программирование
Перебор с возвратом
Метод ветвей и границ
26.
Полный переборПолный перебор (Brute Force) – осуществляет упорядоченный
перебор всех вариантов решения задачи.
Самый неэффективный (максимальная сложность)
Ищет все подходящие решения
Применяется только тогда, когда всё другое не работает
(например, поиск элемента в неупорядоченном массиве)
27.
«Жадный» алгоритмПредставляет последовательный выбор наилучшего
локального варианта
Ищет одно решение
Эффективнее, чем полный перебор
Может давать оптимальное решение (алгоритмы на графах), а
может не давать (задача о рюкзаке
28.
«Разделяй и властвуй»Заключается в разбиении задачи на задачи меньшего размера
(пример сортировка слиянием, быстрая сортировка)
Ищет одно решение
Приводит к оптимальному решению
Эффективная
29.
Динамическое программированиеИспользует память (одномерные или двумерные массивы) для
хранения промежуточных вычислений
В случае нескольких равноправных решений может дать все
Даёт оптимальное решение
Экономит время за счёт дополнительной памяти
30.
Перебор с возвратомВыполняет откат после неудачно выполненного шага (или
после нахождения решения для перебора оставшихся
вариантов)
Может дать все решения
Решения будут точные
Быстрее, чем полный перебор
31.
Метод ветвей и границМножество решений делится на группы, заведомо
неоптимальные группы отсекаются
Может дать множество решений
Используется для сокращения перебора
32.
Объекты алгоритмов33.
Типы объектовАбстрактные объекты
Реализованные объекты
Для каждого абстрактного типа обычно существует несколько
способов реализации в программном коде
34.
Реализованные объектыВстроенные в систему языка программирования
Определённые программистом
35.
Абстрактные объектыСписок
Очередь
Стек
Дерево
Куча
Множество
Словарь
Граф