Структуры данных. В рамках классической теории осуществляется классификация задач по классам сложности (P-сложные, NP-сложные

Классы сложности

В рамках классической теории осуществляется классификация задач по классам сложности (P-сложные, NP-сложные, экспоненциально сложные и др.). К классу P относятся задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга), а к классу NP — задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решённой, если хотя бы одна ветвь процесса пришла к ответу. Другое определение класса NP: к классу NP относятся задачи, решение которых с помощью дополнительной информации полиномиальной длины, данной нам свыше, мы можем проверить за полиномиальное время. В частности, к классу NP относятся все задачи, решение которых можно проверить за полиномиальное время. Класс P содержится в классе NP. Классическим примером NP-задачи является задача о коммивояжёре.

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

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

Дополнительная литература

1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296.

2. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720.

3. Марков А. А., Нагорный Н. М. Теория алгоритмов, изд. 2. — М.: ФАЗИС, 1996.

• http://th-algoritmov.narod.ru/
• А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления
• http://www.williamspublishing.com/Books/5-8459-0857-4.html
• Миниэнциклопедия по теории сложности и комбинаторным алгоритмам
• Лекции по теории сложности и комбинаторным алгоритмам
• Принципы развития теории алгоритмов (DOC)

Получено с http://wiki.traditio.ru/index.php/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2

Введение

Конспект лекций

Лекция 17

Рекурсия в структурах и алгоритмах

Научный редактор доц., д-р техн. наук Л.Г. Доросинский

Екатеринбург

Содержание

1. Понятие рекурсии. 3

1.1 Рекурсивная триада. 3

1.2 Рекурсивные объекты.. 4

2. Некоторые задачи, где можно применить рекурсию.. 7

3. Использование рекурсии в графике. 11

3.1. Кривые Гильберта. 12

3.2. Кривые Серпинского. 16

Дата добавления: 2014-01-07