Сложность вычислений (алгоритмов)

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Московский государственный открытый университет

Кафедра

Информационные системы и измерительные технологии

КУРСОВОЙ ПРОЕКТ

Дисциплина:

Теория вычислительных процессов

Тема:

Сложность вычислений (алгоритмов)

Студент: Блыщак С.Б.

Группа: ПОВТ/с

Москва, 2012 гСодержание

Введение

1. Алгоритмы и их сложность

1.1 Классы сложности задач

1.1.1 Класс P

1.1.2 Класс NP

1.2 Проблема P = NP

1.3 Класс NPC (NP - полные задачи)

2. Основы теории сложности вычислений

2.1 Машина Тьюринга

2.2 Нормальные алгорифмы Маркова

Литература

Введение

С понятием алгоритма были знакомы еще ученые древних цивилизаций. Алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел был описан в книге VII «Начал» Евклида, датирующейся 330-320 гг. до н.э. Прообраз метода исключения Гаусса был описан в китайском источнике «Девять книг по арифметике» (202 г. до н.э. -- 9 г.н.э.). Эратосфен (приблиз. 276-194 гг. до н.э.) предложил алгоритм проверки простоты числа, получивший впоследствии название решета Эратосфена.

Тем не менее, различные формализации понятия алгоритма были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться современная теория алгоритмов. Ее возникновение связано с точным математическим определением такого, казалось бы, интуитивно ясного понятия как алгоритм. Потребность в этом определении была вызвана внутренними тенденциями развития математики, поскольку некоторые открытые проблемы заключались в выяснении существования (или несуществования) алгоритма для решения конкретных задач. Например, знаменитая 10-я проблема Гильберта заключалась в вопросе о существовании процедуры нахождения целочисленных корней произвольного многочлена от нескольких переменных с целыми коэффициентами.

Именно потенциальная возможность несуществования алгоритмов решения некоторых проблем потребовала формального определения алгоритма. Почти одновременно в 30-х годах XX века независимо (и в разных формах) рядом крупных математиков того времени -- А. Тьюрингом, А. Черчем, Э. Постом, К. Геделем, С. Клини и др. -- было формализовано понятие вычислимости.

Э. Пост и А. Тьюринг определили алгоритм как вычисление на абстрактных машинах. При этом вычислимость функции понималась как вычислимость на машинах Тьюринга. К. Гедель, А. Черч и С. Клини определили понятие вычислимости по-другому, на языке введенных ими арифметических функций, которые теперь называются частично рекурсивными функциями. Позднее А.А. Марков ввел понятие нормального алгорифма. Однако выяснилось, что все эти определения, совершенно различные по форме, описывают некое единое математическое понятие -- понятие алгоритма.

Доказательство алгоритмической неразрешимости многих известных задач и получение ряда других отрицательных результатов послужило хорошим стимулом развития классической теории алгоритмов.

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

С практической же точки зрения часто нет никакой разницы между неразрешимой задачей и задачей, решаемой за экспоненциальное от длины входа время.

В связи с актуальными потребностями в анализе алгоритмов и задач с точки зрения вычислительной сложности с 50-х годов XX века -- с момента создания вычислительной техники -- начала активно развиваться теория сложности вычислений.

1. Сложность алгоритмов

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

Основные свойства, присущие любому алгоритму:

1. массовость -- алгоритм предназначен для решения задачи с некоторым множеством допустимых входных данных;

2. конечность -- алгоритм должен завершаться за конечное число шагов (но это количество шагов может быть разным для разных входных данных).

Задачи могут быть сформулированы по-разному (дифференциальные уравнения, задачи на графах, задачи оптимизации и т.п.). Для того чтобы можно было строить единую теорию алгоритмов, необходимо свести разные формулировки задач к какому-то «единому знаменателю». Например, можно считать, что задача сводится к вычислению некоторой функции F:X>Y. Ясно, что в таком виде можно сформулировать любую задачу. Но для некоторых задач функция F может быть выражена неявно. Например, для задачи поиска минимума функции ? на отрезке [0,1] имеем: X = множество

функций, Y = [0,1], F(?) = x*: ?(x*) = min{?(x): x ? [0,1]}.

Не для любой задачи можно построить алгоритм. Существуют алгоритмически неразрешимые задачи.

Проблема алгоритмической разрешимости задачи тесно связана с требованием массовости алгоритма. Алгоритмическая неразрешимость задачи означает, что для любого алгоритма A, решающего данную задачу, существует набор входных данных x, на котором алгоритм работает неверно (либо возвращает неправильный результат, либо не останавливается).

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

ОПРЕДЕЛЕНИЕ Количественная характеристика потребляемых ресурсов, необходимых программе или алгоритму для работы (успешного решения задачи) -- это и есть сложность алгоритма.

Основные ресурсы: время (временнбя сложность) и объем памяти (ёмкостная сложность). Наиболее важной (критической) характеристикой является время.

Очевидно, что для разных экземпляров задачи (для разных входных данных) алгоритму может требоваться разное количество ресурсов.

С каждым экземпляром x задачи Z связывается определенное число (реже -- набор чисел) |x|, называемое длиной или размером входных данных (размером задачи). Размер задачи -- это объем входных данных, необходимых для задания всех параметров задачи.

Однако для многих задач количество времени, необходимое для решения задачи, зависит не только от размера входных данных, но и от самих данных. То есть для решения задачи для двух входных данных x и y одинакового размера (|x|=|y|) алгоритм может тратить разное время. Поэтому для получения оценок временной сложности в зависимости от размера задачи определяют ее как максимальное время, затрачиваемое алгоритмом для входных данных длины n: T(n)=max{T(x): |x|=n}.

Эта функция называется сложностью алгоритма в худшем случае.

Во многих случаях более важной для практики характеристикой алгоритма является его сложность в среднем.

Формально сложность в среднем определяется так:

Tср(n)=У T(x)p(x)

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

Более того, обычно оценивают не точное значение функции сложности T(n), а порядок роста этой функции, т.е. находят такую функцию f(n), что T(n) = O(n) при n>?.

1.1 Классы сложности задач

В предыдущем параграфе мы ввели понятие «сложность алгоритма». Хотелось бы аналогичным образом определить и сложность задачи -- например, как сложность самого эффективного (по времени или ёмкости) алгоритма, решающего эту задачу (для данных размера n). К сожалению, это невозможно. Доказано, что есть задачи, для которых не существует самого быстрого алгоритма, потому что любой алгоритм для такой задачи можно «ускорить», построив более быстрый алгоритм, решающий эту задачу. Это утверждение называют теоремой Блюма об ускорении. Если отвлечься от технических деталей, то упрощенный вариант теоремы

Блюма можно сформулировать следующим образом:

Теорема Блюма об ускорении:

Существует такая алгоритмически разрешимая задача Z, что любой алгоритм A, решающий задачу Z, можно ускорить следующим образом: существует другой алгоритм A?, также решающий Z и такой, что TA'(n) ? log TA(n) для почти всех n.

ЗАМЕЧАНИЕ Теорема Блюма не утверждает, что ускорение возможно для любой задачи. Более того, для задач, интересных с практической точки зрения, ускорение невозможно; для таких задач существует оптимальный (самый быстрый) алгоритм. Тем не менее, утверждение теоремы Блюма о существовании «неудобных» задач не позволяет определить универсальное (применимое ко всем задачам) понятие «оптимального алгоритма».

Поэтому в теории сложности использован другой подход -- через классы сложности.

Классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Существуют классы сложности языков и функциональные классы сложности. Класс сложности языков -- это множество предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Понятие функционального класса сложности аналогично, за исключением того, что это не множество предикатов, а множество функций. В теории сложности, по умолчанию, класс сложности -- это класс сложности языков. Типичное определение класса сложности выглядит так:

Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O(f(n)) ресурса, где n -- длина слова x.

В качестве ресурсов обычно берутся время вычисления (количество рабочих тактов машины Тьюринга) или рабочая зона (количество использованных ячеек на ленте во время работы). Языки, распознаваемые предикатами из некоторого класса (то есть множества слов, на которых предикат возвращает 1), также называются принадлежащими тому же классу.

Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами для данного класса.

1.1.1 Класс P (задачи с полиномиальной сложностью)

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

Иными словами, задача относится к классу P, если существует константа k и алгоритм, решающий задачу с:

F_a(n)=O(n^k),

где n - длина входа алгоритма в битах n = |D| [6].

Отметим следующие преимущества алгоритмов из этого класса:

· для большинства задач из класса P константа k меньше 6;

· класс P инвариантен по модели вычислений (для широкого класса моделей);

· класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).

Таким образом, задачи класса P есть уточнение определения «практически разрешимой» задачи.

1.1.2 Класс NP (полиномиально проверяемые задачи)

Представим себе, что некоторый алгоритм получает решение некоторой задачи - соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность?

Рассмотрим, например задачу о сумме: Дано N чисел - А = (a₁,…a_n) и число V. Задача: Найти вектор (массив) X=(x₁,…,x_n), x_i{0,1}, такой, что a_ix_i = V.

Содержательно: может ли быть представлено число V в виде суммы каких либо элементов массива А. Если какой-то алгоритм выдает результат - массив X, то проверка правильности этого результата может быть выполнена с полиномиальной сложностью: проверка a_ix_i = V требует не более (N) операций.

Формально: DD_A, |D|=n поставим в соответствие сертификат SS_A, такой что |S|=O (n^l) и алгоритм A_s = A_s (D,S), такой, что он выдает «1», если решение правильно, и «0», если решение неверно. Тогда задача принадлежит классу NP, если F (A_s)=O (n^m) [6].

Задача относится к классу NP, если ее решение некоторым алгоритмом может быть быстро (полиномиально) проверено.

1.2 Проблема P = NP

После введения в теорию алгоритмов понятий сложностных классов Эдмондсом (Edmonds, 1965) была поставлена основная проблема теории сложности:

P = NP?

Словесная формулировка проблемы имеет вид: можно ли все задачи, решение которых проверяется с полиномиальной сложностью, решить за полиномиальное время? [6]

Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть полиномиально проверена - задача проверки решения может состоять просто в повторном решении задачи.

На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пусто - рис 6.1

Размещено на http://www.allbest.ru/

Рисунок 6.1 Соотношение классов P и NP

1.3 Класс NPC (NP - полные задачи)

Понятие NP - полноты было введено независимо Куком (Stephen Cook, 1971) и Левиным (журнал «Проблемы передачи информации», 1973,т.9, вып. 3) и основывается на понятии сводимости одной задачи к другой [6].

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

Таким образом, если задача 1 задана множеством конкретных проблем D_A1, а задача 2 - множеством, и существует функция f_s (алгоритм), сводящая конкретную постановку задачи 2 (d_А2) к конкретной постановке задачи 1(d_А1): f_s(d₍₂₎D_A2) = d₍₁₎D_A1, то задача 2 сводима к задаче 1.

Если при этом F_A (f_s) = O(n^k), т.е. алгоритм сведения принадлежит классу P, то говорят, что задача 1 полиномиально сводится к задаче 2 [6].

Принято говорить, что задача задается некоторым языком, тогда если задача 1 задана языком L1, а задача 2 - языком L2, то полиномиальная сводимость обозначается следующим образом: L2 _p L1.

Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: во-первых, задача должна принадлежать классу NP (L NP), и, во-вторых, к ней полиномиально должны сводиться все задачи из класса NP (L_{x P} L, для каждого L_x NP), что схематично представлено на рис 6.2.

Размещено на http://www.allbest.ru/

Рисунок 6.2 Сводимость и класс и NPC

Для класса NPC доказана следующая теорема: Если существует задача, принадлежащая классу NPC, для которой существует полиномиальный алгоритм решения (F = O(n^k)), то класс P совпадает с классом NP, т.е. P=NP [6].

Схема доказательства состоит в сведении любой задачи из NP к данной задаче из класса NPC с полиномиальной трудоемкостью и решении этой задачи за полиномиальное время (по условию теоремы).

В настоящее время доказано существование сотен NP- полных задач [6,7], но ни для одной из них пока не удалось найти полиномиального алгоритма решения. В настоящее время исследователи предполагают следующее соотношение классов: P NP, то есть NP \ P , и задачи из класса NPC не могут быть решены (сегодня) с полиномиальной трудоемкостью.

2. Основы теории сложности вычислений

Теория сложности вычислений -- бурно развивающаяся область теоретической информатики (theoretical computer science) и охватывает как чисто теоретические вопросы, так и вопросы, непосредственно связанные с практикой. Среди наиболее важных приложений этой теории можно назвать способы построения и анализа эффективных алгоритмов, а также современные криптографические методы.

2.1 Машина Тьюринга

Машимна Тьюмринга (МТ) -- абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

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

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

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

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

Пример машины Тьюринга

Проверка на чётность числа символов (единичек), записанных на ленте

§ q₁ 1 -> q₂ R *

§ q₂ 1 -> q₁ R *

§ q₁ * -> q₀ E чётное

§ q₂ * -> q₀ E нечётное

Пример многоленточной машины Тьюринга

Проверка делимости натурального числа на меньшее: делимое будет записано на верхней ленте, а делитель - на нижней:

§ q₁(1,1) -> q₁(R,R)(1,1)

§ q₁(1,*) -> q₂(E,L)(1,*)

§ q₂(1,1) -> q₂(E,L)(1,1)

§ q₂(1,*) -> q₁(E,R)(1,*)

§ q₁(*,*) -> q₀(E,E)(делится,*)

§ q₁(*,1) -> q₀(E,E)(не делится,1)

§

2.2 Нормальные алгорифмы Маркова

Нормамльный алгоримтм Мамркова (НАМ)-- один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А. А.Марковым в конце 1940-х годов.

Традиционно, когда говорят об алгоритмах Маркова, используют слово «алгорифм». Так назвал их А.А.Марков, подчеркивая арабо-греческую этимологию слова. К тому же в дореволюционных российских энциклопедиях и учебниках использовалось слово алгорифм. В настоящее время слово алгорифм иногда используют математики так называемой «питерской школы».

Суть алгоритмов Маркова заключается в следующем. Задача для алгоритмов Маркова ставится в виде: найти алгоритм (написать программу) переводящую любую строку S (заданную на некотором алфавите (т.е. наборе символов, которые могут в нее входить)) из некоторого допустимого множества входных строк в строку f(S). Т.е., построить программу - преобразователь строк, выполняющую некое преобразование.Например: перевести все буквы в строке в верхний регистр, инвертировать регистр, перевернуть строку (reverse), и даже такую задачу: из строкового представления десятичного числа получить строковое представление числа на единицу больше (или в 2 раза больше).Программа на языке алгоритмов Маркова - представляет из себя набор правил (Rules). Каждое правило представляет собой замену. Т.е. правило имеет вид:

S1 -> S2

где S1 и S2 некие строки. Правило представляет подстановки, последовательно применяемые ко входной строке и приводящие в итоге ее к требуемой выходной строке. Порядок задания правил важен. Работает алгоритм этот следующим образом. Берется исходная строка и мы начинаем перебирать правила с самого первого, анализируя, может ли оно быть применено (существует ли в строке S подстрока S1). Если не может -> анализируется следующее по порядку правило. Если не одно правило не подошло, алгоритм завершается, текущее состояние строки S является результатом работы алгоритма. Если же правило применимо - совершается замена самого левого вхождения подстроки S1 на строку S2 (или, выражаясь языком питона, S = S.replace(S1, S2, 1)). Причем далее правила начинают перебираться опять с начала.Еще есть так называемые терминальные правила, обозначающиеся точкой в конце:

S1 -> S2.

При срабатывании такого правила алгоритм завершается, и текущее состояние строки S считается результатом работы алгоритма.

Пример алгоритма Маркова №1

Задана строка из 0 и 1. Получить на выходе строку, в которой 1 заменены на 0, а 0 на 1. алгоритм задача сложность вычисление

; "*"-работник движется вдоль строки, и выполняет "работу" меняет 0->1, 1->0*0 > 1**1 > 0*; уничтожение "*"-работника, алгоритм завершается.* > .; ставим в самом начале звездочку-"работника" (замена пустой подстроки на *)> *

Возьмем входную строку "1101". Последовательно применяем подстановки. Первые три не подойдут, поскольку в строке нет "*". Но подойдет самая последняя подстановка, и звездочка будет добавлена. Получим "*1101". Затем, последовательно применяя подстановки номер 1) и 2) будем получать: 0*101, 00*01, 001*1, 0010*. Далее применяем 3) завершающую подстановку. Звездочка в конце удаляется, получаем результат: 0010.

Пример алгоритма Маркова №2

Дано строковое представление числа в десятичной системе счисления, получить десятичное представление числа на 1 больше.

0# > 1.1# > 2.2# > 3.3# > 4.4# > 5.5# > 6.6# > 7.7# > 8.8# > 9.9# > #0*# > 1.*0 > 0**1 > 1**2 > 2**3 > 3**4 > 4**5 > 5**6 > 6**7 > 7**8 > 8**9 > 9* * > # > *

Сперва срабатывает последняя подстановка, добавляющая "*" в начало числа. Применяя подстановки *N > N*, она передвигается к концу числа. Когда звездочка дойдет до конца числа, она будет заменена на "#". Решетка (#) будет выполнять роль 1, которую мы прибавляем к числу. Посмотрим на первые 9 подстановок (N# > {N+1}., N=0..8). Если последняя цифра числа от 0 до 8, то она увеличивается на 1 и алгоритм успешно завершается. Интереснее, когда в конце числа 9-ка, в этом случае срабатывает 9# > #0. Фактически это перенесение 1 в следующий разряд.

Литература

1. Н. Н. Кузюрин С. А. Фомин «Эффективные алгоритмы и сложность вычислений»

2. М.Г. Адигеев «Введение в теорию сложности»

3. Вялый М.Н. «Сложность вычислительных задач»

4. Поздняков С.Н. «Машина Тьюринга»

Размещено на Allbest.ru