Содержание
- 2. Алгоритмы: Анализ и Построение Об алгоритмах на примерах Процесс решения задачи может быть условно разбит на
- 3. Алгоритмы: Анализ и Построение Об анализе задачи Половина дела сделана, если знать, что исходная задача имеет
- 4. Алгоритмы: Анализ и Построение Если определенные аспекты решаемой задачи можно выразить в терминах какой-либо формальной модели,
- 5. Алгоритмы: Анализ и Построение Практически любую область математики или других наук можно привлечь к построению модели.
- 6. Алгоритмы: Анализ и Построение Для задач с символьными или текстовыми данными можно применить модели символьных последователь
- 7. Алгоритмы: Анализ и Построение Когда построена (подобрана) подходящая модель исходной задачи, то естественно искать решение в
- 8. Алгоритмы: Анализ и Построение Инструкции могут выполняться в алгоритме любое число раз, при этом они сами
- 9. Алгоритмы: Анализ и Построение Пример модели . Модель управления светофорами на сложном перекрестке дорог Нужно создать
- 10. Алгоритмы: Анализ и Построение Графическая модель Модель в виде графа поможет в решении задачи управления светофорами
- 11. Алгоритмы: Анализ и Построение Задача раскраски произвольного графа минимальным количеством цветов принадлежит к классу переборных задач,
- 12. Алгоритмы: Анализ и Построение Три подхода к решению задачи. Если граф небольшой, можно найти оптимальное решение,
- 13. Алгоритмы: Анализ и Построение "Жадный" алгоритм раскраски графа. Пример рационального эвристического алгоритма В этом алгоритме сначала
- 14. Алгоритмы: Анализ и Построение Этот алгоритм назван "жадным" из-за того, что каждый цвет применяется к максимально
- 15. Алгоритмы: Анализ и Построение Например, для раскраски вершин 1,2,3,4,5 графа можно было бы применить два цвета,
- 16. Алгоритмы: Анализ и Построение Применим описанный алгоритм для закраски вершин графа нашей задачи, при этом первой
- 17. Алгоритмы: Анализ и Построение AC AD BD DC ED EC EB EA DA BA AB BC
- 18. Алгоритмы: Анализ и Построение Можно использовать результаты из общей теории графов для оценки качества полученного решения.
- 19. Алгоритмы: Анализ и Построение Переход от алгоритма к программе greedy - жадный procedure greedy ( var
- 20. Алгоритмы: Анализ и Построение procedure greedy ( var G: GRAPH; var newclr: LIST ) ; var
- 21. Алгоритмы: Анализ и Построение ФП_iCAM
- 22. Алгоритмы: Анализ и Построение Абстрактный тип данных LIST ТИП ДАННЫХ область допустимых значений переменной Операции, которые
- 23. Алгоритмы: Анализ и Построение Абстрактный тип данных SET ОПЕРАТОРЫ MAKENULL(A); Сделать множество A пустым UNION(A, В,
- 24. Алгоритмы: Анализ и Построение Рекомендации по разработке программ Планируйте этапы разработки программы. - сначала черновой набросок
- 25. Алгоритмы: Анализ и Построение Применяйте инкапсуляцию. - Все процедуры, реализующие АТД, поместите в одно место программного
- 26. Алгоритмы: Анализ и Построение Используйте и модифицируйте уже существующие программы. - Один из неэффективных подходов к
- 27. Алгоритмы: Анализ и Построение Разрабатывайте свои инструменты. Инструмент (tool) — это программа с широким спектром применения.
- 28. Алгоритмы: Анализ и Построение В контексте расписания экзаменов: вершины графа — это аудитории, цвета — время
- 29. Алгоритмы: Анализ и Построение Программируйте на командном уровне. Часто бывает, что в библиотеке программ не удается
- 30. Общность и эффективность решения задачи Общие решения - менее эффективны. Более узкие решения (одной задачи, например,
- 31. Задача об упаковке рюкзака: Множество вещей {P∍p | p=(v,w)}Упаковать вещи так, чтобы суммарная ценность V была
- 32. СВОДИМОСТЬ Переборная задача П1 сводится к переборной задаче П2, если метод решения П1 можно преобразовапть к
- 33. Полиномиальная и экспоненциальная сложность Функция f(n) есть O(g(n)), если |f(n)| ≤ c| g(n)|. Полиномиальный (полиномиальной временнόй
- 34. Алгоритмы: Анализ и Построение Сортировка вставкой Вход: последовательность из n чисел (a1, а2,...,аn ). Выход: перестановка
- 35. Алгоритмы: Анализ и Построение
- 36. Алгоритмы: Анализ и Построение end end
- 37. Алгоритмы: Анализ и Построение Инварианты цикла (loop invariant) В начале каждой итерации цикла for подмассив А
- 38. Алгоритмы: Анализ и Построение Анализ алгоритма Время работы процедуры Insertion__Sort зависит от набора входных значений: для
- 39. Алгоритмы: Анализ и Построение Время работы алгоритма для того или иного ввода измеряется в количестве элементарных
- 40. Алгоритмы: Анализ и Построение Insertion_Sort(A) время количество раз 1 for j ← 2 to length[A] c1
- 41. Алгоритмы: Анализ и Построение Даже если размер входных данных является фиксированной величиной, время работы алгоритма может
- 42. Алгоритмы: Анализ и Построение Если элементы массива отсортированы в порядке, обратном требуемому (в порядке убывания), то
- 43. ПОРЯДОК роста функции Огрубляем оценку роста an2 +bn +c , отбрасывая члены меньших порядков и опуская
- 44. Алгоритмы: Анализ и Построение Рассматриваются как наилучший, так и наихудший случаи. Наихудший случай наиболее интересен по
- 45. Построение алгоритма методом разделяй и властвуй Рекурсивные алгоритмы. Задача разбивается на подзадачи. Затем эти задачи меньшего
- 46. Динамическое программирование Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи,
- 47. В общем случае задача решается в три шага - Разбиение задачи на подзадачи меньшего размера. -
- 48. Пример динамического программирования — алгоритм, позволяющий решить задачу о перемножении цепочки матриц. Пусть имеется последовательность (цепочка),
- 49. (А1(А2(А3А4))) , (А1((А2А3) А4)) , ((А1(А2А3)) А4) , (((А1А2) А3) А4) . то способ вычисления их
- 50. Матричное умножение обладает свойством ас-социативности, поэтому результат не зависит от расстановки скобок. От того как расставлены
- 51. Время вычисления матрицы С преимущественно определяется количеством произведений скаляров. Это количество равно pqr. Это и есть
- 52. ПРИМЕР. Перемножаются три матрицы (А1, A2, A3). Предположим, что размеры этих матриц равны 10 х 100,
- 53. Если вычислять результат в порядке, заданном выражением (А1 (A2 A3)), то сначала понадобится выполнить 100 *5
- 54. Первый этап применения парадигмы динамического программирования — найти оптимальную вспомогательную подструктуру, а затем с ее помощью
- 55. Обозначим для удобства результат перемножения матриц Ai A(i+1) … Aj через Ai.j, где i≤j. Заметим, что
- 56. Предположим, что в результате оптимальной расстановки скобок последовательность Ai … Aj разбивается на подпоследовательности Ai,k ,
- 57. Для решения любой нетривиальной задачи об оптимальном произведении последовательности матриц всю последовательность необходимо разбить на подпоследовательности
- 58. Организация больших массивов Алгоритмы размещения и поиска данных. Определить алгоритмы вычисления функций РАЗМЕСТИТЬ, НАЙТИ и УДАЛИТЬ
- 59. Hash-таблицы Массив большой и, например, не помещается весь в оперативной памяти, но в каждый момент времени
- 60. Какой должна быть хорошая hash-функция?
- 61. Алгоритмы: Анализ и Построение
- 62. Алгоритмы: Анализ и Построение
- 64. Скачать презентацию