Содержание
- 2. Любая вычислимая функция может задаваться разными алгоритмами (разными программами для выбранного универсального исполнителя) и может быть
- 3. Примеры алгоритмически неразрешимых задач. Пример 1. Вычисление функции h(n), которая для любого натурального числа n равна
- 4. Пример 3. Проблема Эйлера - любое четное число не меньше четырех можно представить в виде суммы
- 5. Методы доказательства алгоритмической неразрешимости Прямой метод использует диагональный метод Кантора. Заключается он в следующем: из предположения
- 6. Диагональный метод Кантора Теорема Кантора о несчетности множества действительных чисел: множество натуральных чисел и множество действительных
- 7. 1 0, a1,1a1,2a1,3a1,4a1,5a1,6a1,7. . . 2 0, a2,1a2,2a2,3a2,4a2,5a2,6a2,7. . . 3 0, a3,1a3,2a3,3a3,4a3,5a3,6a3,7. . . 4
- 8. Строим число 0, b1b2b3b4b5 . . ., ставя на n-ое место цифру bn, такую, что bn
- 9. Теорема: множество арифметических функций n-переменных несчетно. Док-во (с помощью диагонального метода): Для доказательства несчетности множества достаточно
- 10. Теорема: вычислимых функций счетное множество. (Множество машин Тьюринга счетно). Таким образом, каждая машина Тьюринга вполне определяется
- 11. Оценка мощности множества невычислимых арифметических функций. Невычислимых арифметических функций несчетное множество.
- 12. Эти задачи часто используют для доказательства неразрешимости других проблем путем сведения к ним. Нумерация алгоритмов Существует
- 13. Проблема остановки. Не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма (его номеру) и исходных
- 14. Теорема. Не существует машины Тьюринга Т0 , которая решает проблему самоприменимости. Возьмем в качестве внешнего алфавита
- 15. Машина T1 построена по машине T0 вполне конструктивными средствами и применима к кодам несамоприменимых машин и
- 16. Проблема останова МТ и доказательство её неразрешимости Одна из первых задач, для которой была доказана неразрешимость.
- 17. Доказательство. Рассмотрим множество всех алгоритмов, получающих на вход натуральное число, и возвращающих в качестве результата натуральное
- 18. Вычислимая функция F(a,x) двух натуральных аргументов как бы перечисляет ВСЕ вычислимые функции с одним натуральным аргументом.
- 19. Неразрешимость проблемы останова можно интерпретировать как несуществование общего алгоритма для отладки программ, точнее, алгоритма, который по
- 20. Основы анализа сложности алгоритмов
- 21. Критерии оценки эффективности алгоритмов: Процессорное время (вычислительная сложность) Память (максимальное количество ячеек задействованных алгоритмом) Каждое вычислительное
- 22. Модель абстрактного вычислителя - машина с произвольным доступом к памяти (RAM) Модель состоит из памяти и
- 23. Неудобно оценивать алгоритм по фактическому количеству элементарных операций на тех или иных входных данных. Задача анализа
- 24. Формальное описание: Размер входа определяется для каждой задачи индивидуально. 1) в задачах обработки одномерных массивов размером
- 25. Конкретная проблема задается N словами памяти по α битов каждое Nα = N*α Программа, реализующая алгоритм
- 26. Не всегда количество элементарных операций, выполняемых алгоритмом на одном входе длины N, совпадает с количеством операций
- 27. Для нахождения среднего значения, сначала определяются всевозможные группы, на которые следует разбить входные данные так, чтобы
- 28. 1. Количественно-зависимые Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит
- 29. 3. Количественно-параметрические Функция трудоемкости зависит как от количества данных на входе, так и от значений входных
- 30. Асимптотический анализ алгоритмов Часто работать непосредственно с функцией трудоемкости сложно, т. к. они обладают такими свойствами:
- 31. Основные оценки сложности Оценка Θ(g(n)) (тетта) - функции, растущие с той же скоростью, что и g.
- 32. 2. Оценка О(g(n)) (О большое) - функции, растущие медленнее чем g. В отличие от оценки Θ,
- 33. Отыскивая асимптотическую оценку для суммы, можно отбрасывать члены меньшего порядка, которые при больших n становятся малыми
- 34. 3. Оценка Ω (Омега) - функции, растущие быстрее чем g. В отличие от оценки О, оценка
- 35. Свойства асимптотических оценок
- 36. Сравнение скорости роста. Сравнение скорости роста Чем меньше степень роста функции трудоемкости, тем больше размер задачи,
- 37. Классы сложности.
- 40. Задачи со сложностью O(1): - вставка и удаление элемента в односвязном и двусвязном списке; - добавление
- 41. Класс NP Задачи, которые нельзя отнести ни к классу P, ни к классу E. Задачи, которые
- 42. Пример. Дано n чисел a1,…an и число V. Задача: Найти вектор (массив) X=(x1,…,xn), xi∈{0,1}, такой, что
- 43. Проблема равенства классов P и NP. Поскольку детерминированная машина Тьюринга может рассматриваться как специальный случай недетерминированной
- 44. На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит
- 45. Для класса NPC доказана следующая теорема: если существует задача, принадлежащая классу NPC, для которой существует полиномиальный
- 46. Примеры NP – полных задач
- 47. Пути решения NP-полных задач. 1. Поиск приближенного решения (например, использование жадных алгоритмов для решения задач о
- 48. Когда временными оценками можно пренебречь. Если создаваемая программа будет использована только несколько раз, тогда стоимость написания
- 49. Вычисление времени выполнения не рекурсивных алгритмов I. Нахождение функции трудоемкости по фактическому количеству элементарных операций. В
- 50. Анализ трудоемкости основных алгоритмических конструкций
- 52. Примеры анализа простых алгоритмов Пример 1. Задача суммирования элементов квадратной матрицы Алгоритм выполняет одинаковое количество операций
- 53. Пример 2. Задача поиска максимума в массиве Данный алгоритм является количественно-параметрическим, поэтому для фиксированной размерности исходных
- 54. Худший случай Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы
- 55. Средний случай Элементарное усреднение Tcр(n) =(Ta∨(n) + TA^(n))/2= 6n-3= Θ(n). Вероятностный подход Переприсваивание максимума при просмотре
- 56. Некоторые математические формулы, необходимые для анализа алгоритмов. Логарифмы Формулы суммирования
- 58. Математическое ожидание дискретной случайной величины. Если известен закон распределения случайной величины x, то есть известно, что
- 59. II. Нахождение вида функции трудоемкости без подсчета фактической стоимости команд.
- 60. Анализ наилучшего случая. На вход подается уже отсортированный массив. При этом все внутренние циклы состоят всего
- 61. Анализ наихудшего случая. Входной массив, отсортирован в обратном порядке. При этом каждый a[i] элемент сравнивается со
- 62. Анализ среднего случая. Характер поведения "усредненного" времени работы часто ничем не лучше поведения времени работы для
- 64. III. Оценивание порядков роста времени работы. Следствие. Из правила сумм также следует, что если f(n)
- 68. Скачать презентацию