Сложность задач

Сентябрь 3, 2022

Главная
Алгебра
Сложность задач

Содержание

2. Чем определяется сложность задачи? Предметом вычислительной техники являются задачи, которые умеют решать машины. Решения этих задач
3. Измерение сложности задачи
4. Способы определения сложности задачи Пусть временная сложность задачи равна Θ(f(n)), где f(n) — это некоторая математическая
5. Алгоритма сортировки слиянием и его сложность Этот алгоритм решает задачу сортировки списка длиной n так, что
6. Сложность алгоритма сортировки слиянием Общее количество сравнений, которые выполняет алгоритм сортировки слиянием при сортировке списка длиной
7. Полиномиальные и не полиномиальные задачи Задача называется полиномиальной (polynomial problem), если она принадлежит О(f(n)), где f(n)
8. NP-задачи Если набор команд не является алгоритмом в техническом смысле, то такие инструкции называются недетерминироваными, а
9. Задача, которая может быть решена за полиномиальное время при помощи недетерминированного алгоритма, называется недетерминированной полиномиальной задачей
10. Заключение Таким образом, задачи могут быть разрешимыми (имеющими алгоритмическое решение) и неразрешимыми (для которых нет алгоритмического
12. Скачать презентацию

Слайд 2

Чем определяется сложность задачи?
Предметом вычислительной техники являются задачи, которые умеют решать

машины. Решения этих задач формулируются в виде алгоритмов. Таким образом, сложность задачи определяется свойствами алгоритмов, решающих ее. Точнее, сложность простейшего алгоритма для решения задачи считается сложностью этой задачи.

Слайд 3

Измерение сложности задачи

Слайд 4

Способы определения сложности задачи
Пусть временная сложность задачи равна Θ(f(n)), где f(n)

— это некоторая математическая функция от n. То есть временная сложность задачи определяется как временная сложность ее наилучшего решения. В ситуациях, когда невозможно определить лучшее решение, для обозначения того, что нам известно о сложности задачи, применяется О-представление. Говоря, что задача принадлежит О(f(n)), мы имеем в виду, что для нее есть решение со сложностью Θ(f(n)), но, возможно, существуют и более хорошие решения.

Слайд 5

Алгоритма сортировки слиянием и его сложность
Этот алгоритм решает задачу сортировки списка

длиной n так, что исходная задача сортировки разделяется на две меньших, когда сортируются списки длиной приблизительно n/4. Эти две задачи, в свою очередь, делятся еще раз, и мы получаем четыре задачи сортировки . Этот процесс деления можно представить при помощи дерева на рисунке 1.
Рисунок 1- Дерево деления списка

Слайд 6

Сложность алгоритма сортировки слиянием
Общее количество сравнений, которые выполняет алгоритм сортировки слиянием

при сортировке списка длиной n, получается умножением количества сравнений на каждом уровне на количество уровней, на которых требуются сравнения. Мы делаем вывод, что оно не превышает n [lg n]. Т.е. алгоритм сортировки слиянием принадлежит О(n lg n). Учитывая тот факт, что сложность задачи сортировки равна Θ(n lg n), можно утверждать, что алгоритм сортировки слиянием является оптимальным решением задачи сортировки в отличии, например, от алгоритма сортировки вставкой, который принадлежит О(n2).

Слайд 7

Полиномиальные и не полиномиальные задачи
Задача называется полиномиальной (polynomial problem), если она

принадлежит О(f(n)), где f(n) - это полином (многочлен), или это выражение ограничено полиномом. Набор всех полиномиальных задач обозначается Р.
Поиск задач, принадлежащих Р, является одной из главных проблем вычислительной техники, так как он тесно связан с вопросами о том, существует ли для задач практическое решение. То, что теоретически разрешаемые проблемы, не принадлежащие Р, имеют огромную временную сложность, заставляет признать, что их невозможно решить с практической точки зрения. Ученые, занимающиеся вычислительной техникой, называют такие задачи трудно разрешимыми. В свою очередь, задачи, для которых существуют практические решения, содержатся в Р. Поэтому понимание границ класса Р стало важной областью исследований вычислительной техники.

Слайд 8

NP-задачи
Если набор команд не является алгоритмом в техническом смысле, то такие

инструкции называются недетерминироваными, а сам алгоритм называют недетерминированным.
Во многих случаях лишь тонкая грань отделяет детерминированные алгоритмы от недетерминированных. Но различие между ними достаточно очевидно и существенно. Детерминированный алгоритм не надеется на творческие способности механизма, выполняющего алгоритм, тогда как для недетерминированного «алгоритма» они могут быть достаточно важны.

Слайд 9

Задача, которая может быть решена за полиномиальное время при помощи недетерминированного

алгоритма, называется недетерминированной полиномиальной задачей (nondeterministic polynomial problem), или NP-задачей. Класс NP-задач обозначается NP. Обратите внимание, что все задачи из Р также принадлежат NP, так как к любому (детерминированному) алгоритму можно добавить недетерминированную команду, не влияющую на работу алгоритма.

Слайд 10

Заключение
Таким образом, задачи могут быть разрешимыми (имеющими алгоритмическое решение) и неразрешимыми

(для которых нет алгоритмического решения). Более того, в классе разрешимых задач есть два подкласса. Первый - это набор полиномиальных задач, то есть задач, имеющих практическое решение. Второй представляет собой не полиномиальные задачи, практическое решение для которых может быть найдено только для относительно небольших и тщательно отобранных входов. И в заключение, существуют загадочные NP-задачи, не поддающиеся точной классификации.

Сложность задач

Содержание

Чем определяется сложность задачи?Предметом вычислительной техники являются задачи, которые умеют решать

Измерение сложности задачи

Способы определения сложности задачиПусть временная сложность задачи равна Θ(f(n)), где f(n)

Алгоритма сортировки слиянием и его сложностьЭтот алгоритм решает задачу сортировки списка

Сложность алгоритма сортировки слияниемОбщее количество сравнений, которые выполняет алгоритм сортировки слиянием

Полиномиальные и не полиномиальные задачи Задача называется полиномиальной (polynomial problem), если она

NP-задачиЕсли набор команд не является алгоритмом в техническом смысле, то такие