Содержание
- 2. Определения Для оценки сложности алгоритма используется O-символика. На основе этой оценки можно привести следующую классификацию алгоритмов,
- 3. Определения Простые задачи (решаемые) – это задачи, решаемые за полиномиальное время. Труднорешаемые задачи – это задачи,
- 4. Классификация задач 1. P-задачей (полиномиальной задачей) называется задача, которую можно решить за полиномиальное (от длинны входа)
- 5. Классификация задач 3. NP-полной называется задача из класса NP, к которой можно свести любую другую задачу
- 6. Классификация задач 4. Класс EXPTIME – класс задач, решаемых за экспоненциальное время. 5. Класс EXPTIME-полных задач
- 7. Задача коммивояжера Имеется n пунктов, расстояния между которыми известны. Требуется объехать все пункты, посетив каждый по
- 8. Методы разработки алгоритмов Рассмотрим несколько методов: Метод декомпозиции (пример: игра “Ханойская башня”). Динамическое программирование. Поиск с
- 9. Метод декомпозиции Этот метод имеет также название «разделяй и властвуй» или метод разбиения. Этот метод наиболее
- 10. Ханойская башня Даны три стержня, на один из которых нанизаны n колец, причем кольца отличаются размером
- 11. Динамическое программирование Идея: чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить
- 12. Динамическое программирование Формулы вычисления: и т.д. содержат вычисления одних и тех же значений многократно, т.е. решаются
- 13. Динамическое программирование Динамическое программирование обычно придерживается двух подходов: нисходящее динамическое программирование: задача разбивается на подзадачи меньшего
- 14. Поиск с возвратом Это метод нахождения решения задачи, в которой требуется полный перебор всех возможных вариантов
- 15. Поиск с возвратом Незначительные модификации метода поиска с возвратом, связанные с представлением данных или особенностями реализации,
- 16. Обход конём шахматной доски Задача. На шахматной доске размера nxn в позиции (x0, y0) находится конь.
- 17. Обход конём шахматной доски Создадим массивы a[1..8], B[1..8] и занесём в них возможные ходы коня: a:
- 18. Метод ветвей и границ Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960
- 19. Метод ветвей и границ Если значение целевой функции на найденном решении меньше рекорда, то происходит смена
- 20. Метод альфа-бета отсечения Метод «ветвей и границ» можно ещё улучшить, если ввести не одну оценку, а
- 21. Повторение: - Алгоритмы работы с графами - Поиск в тексте - Кодирование и сжатие данных
- 22. Поиск в глубину (порядок обхода) Поиск в глубину для полного обхода графа с n вершинами и
- 23. Поиск в ширину (волновой алгоритм) Поиск в ширину для полного обхода графа с n вершинами и
- 24. Топологическая сортировка (ТС) Это сортировка элементов, для которых определено отношение частичного порядка, т.е. порядок задан не
- 25. Кратчайшие пути в графе Задача 1: Поиск кратчайшего расстояния от одной из вершин графа до всех
- 26. Алгоритм Дейкстры
- 27. Кратчайшие пути в графе Алгоритм Беллмана – Форда – это алгоритм нахождения кратчайшего пути от одной
- 28. Кратчайшие пути в графе Задача 2: Поиск кратчайших путей между всеми парами вершин графа (без циклов
- 29. Алгоритм Флойда-Уоршелла - результат
- 30. Переборные алгоритмы Задача 3: Переборные алгоритмы основаны на методах обхода графа. Поскольку существует два метода обхода
- 31. Переборный алгоритм (поиска в глубину)
- 32. Поиск в тексте Пусть задан массив Txt из n элементов, называемый текстом и массив Wrd из
- 33. Алгоритм Кнута, Морриса и Пратта Алгоритм основывается на том факте, что после частичного совпадения начальной части
- 34. Алгоритм Боуера, Мура, Хорспула Алгоритм БМХ считается наиболее быстрым среди алгоритмов, предназначенных для поиска подстроки в
- 35. Сжатие данных Степень избыточности данных зависит от типа данных. Другим фактором, влияющим на степень избыточности является
- 36. Способы уменьшения избыточности данных: Изменение содержимого данных. Изменение структуры данных. Одновременное изменение как структуры, так и
- 37. Обратимые методы Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым.
- 38. Методы сжатия без потери информации Методы сжатия без потерь делятся на две категории: 1. Статистические методы
- 40. Скачать презентацию