Главная » Просмотр файлов » С.А. Абрамов - Вычислительная сложность алгоритмов (лекции)

С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 11

Файл №1121252 С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (С.А. Абрамов - Вычислительная сложность алгоритмов (лекции)) 11 страницаС.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252) страница 112019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Деление в этом случае будет неточным, поэтому надо выполнитьbbделение с запасом ( 3m ), после чего умножить. При этом младшие разряды могутоказаться неверными. Дотошные люди посчитали, что их количество не превосходит 3,и «шевелением» этих разрядов можно получить точный ответ. Осталось показать, чтоR ≤ D , но это очевидно.Определение. Пусть существуют 2 задачи P и Q и 2 алгоритма U и V такие, что алгоритм Uпо входу задачи P строит один или несколько входов для задачи Q:Uy1 , ...

, yk — входы Qx — вход P ⎯⎯→Задача Q переводит y1 , ... , yk в z1 , ... , zk : Q( y1 , ... , yk ) → z1 , ... , zk , а алгоритм V по z1 , ... , zkстроит решение задачи Q. Тогда пару (U , V ) будем называть сведением.Отвлечёмся на минуту от сведений и докажем общее утверждение.Утверждение. Если P и Q таковы, что P ≤ Q , P и Q — классы алгоритмов, решающихзадачи P и Q соответственно, и пусть f (n) — асимптотическая нижняя граница сложностидля класса P. Тогда f (n) будет являться асимптотической нижней границей сложности длякласса Q.(Доказательство: P ≤ Q ⇔ TAP (n) = O TAQ (n))()⇔ TAQ (n) = Ω TAP (n) . С другой стороны,f (n) является асимптотической нижней границей для P ⇒ ∀A ∈ P (в частности, дляA = AP ) будет верна оценка: TA (n) = Ω( f (n) ) ⇒ TAP (n) = Ω( f (n) ) ⇒ TAQ (n) = Ω( f (n) ) , чтодоказывает утверждение.Пример.

Вернёмся к задаче построения выпуклой оболочки. Покажем, что если за размеравхода взять n — количество данных точек на плоскости, то Ω(n log n) будет нижнейасимптотической оценкой. Отметим, что «продвинутые» алгоритмы построениявыпуклой оболочки имеют оценку сложности O(n log n) , тем самым являютсяоптимальными по порядку сложности. Как показать Ω(n log n) ? Для этого сведёмалгоритм сортировки к задаче о построении выпуклой оболочки. Пусть на входеалгоритма сортировки имеется набор чисел x1 , x2 , ... , xn . Построим по ним набор точек()()()на плоскости следующим образом: x1 , x12 , x2 , x22 , ...

, xn , xn2 .xi2xiОчевидно, что все точки будут принадлежать выпуклой оболочке. Теперь, если мызахотим её выдать в виде упорядоченного массива вершин с обходом, например, по50часовой стрелке, то нам непременно потребуется отсортировать начальные значенияx1 , x2 , ... , xn . Мы уже знаем, что Ω(n log n) является асимптотической оценкой снизудля алгоритмов сортировки, поэтому для алгоритмов построения выпуклой оболочкибудет верна оценка Ω(n log n) . Таким образом, если известно, что одна задача решаетсямедленно, то, сведя другую задачу к первой, можно показать, что она тоже решаетсямедленно.Рассмотрим две задачи: умножение булевых матриц и транзитивно-рефлексивное замыканиеграфа.

Можно показать, что эти задачи являются эквивалентными. Таким образом, если мынаучимся находить транзитивное замыкание за O(n 2 ) , то и булевые матрицы мы сможемумножать за O(n 2 ) .Действительно, если A — матрица смежности исходного графа (A порядка n), тогда матрицасмежности транзитивно-рефлексивного замыкания графа будет равнаA* = I ∨ A ∨ A2 ∨ ... ∨ An = (I ∨ A) (максимальная длина пути — n)nПусть у нас есть две матрицы: A и B. Построим по ним ещё одну матрицу по следующемуправилу:⎡0⎢0⎢⎢⎣0A000⎤B ⎥⎥0 ⎥⎦и рассмотрим граф, для которого эта матрица будет являться матрицей смежности. Теперьпосмотрим, что будет транзитивно-рефлексивным замыканием этого графа.

Замыканиембудет граф со следующей матрицей смежности:⎡I⎢0⎢⎢⎣0A AB ⎤IB ⎥⎥0 I ⎥⎦Тем самым, для получения произведения AB достаточно прочитать верхний правый уголполучившейся матрицы.Обычно для построения транзитивно-рефлексивного замыкания используют алгоритмУоршела со сложностью O (n3 ) , где за O скрывается совсем не большая константа (порядка3), и ещё одним преимуществом алгоритма является небольшой расход памяти.Далее нашей целью будет рассмотрение некоторых вопросов алгоритмов полиномиальнойсложности.

Для таких алгоритмов сложность не обязательно является полиномом, но тем неменее она должна допускать оценку O(n c ) , где c — некоторая константа. Вообще говоря,оценка с O предполагает выполнение соответствующего неравенства начиная с некоторого n,но мы будем считать, что для всех n выполняется T (n) ≤ p(n) , где p(n) — полином.Полиномиальной сложности алгоритмы — это искусство. Вопрос существованияполиномиального алгоритма, решающего ту или иную задачу, отнюдь не праздный. Отэкспоненциальной сложности стараются перейти к полиномиальной.

Сторонники получениякакого-нибудь алгоритма не стремятся получить алгоритм с полиномиальной сложностью.Основной своей задачей они считают получение алгоритма, а снижение показателясложности — это вопрос времени.Рассмотрим следующий пример. В линейном программировании существует симплексметод, позволяющий решать задачи, сложность которого не является полиномиальной.Несколько лет назад был найден алгоритм решения задач линейного программирования с51полиномиальной сложностью, но коэффициенты полинома были настолько велики, чтоникакого продвижения не было. Симплекс-метод обладает субэкспоненциальнойсложностью: растёт медленнее, чем d n , но быстрее, чем любой полином.

Например,субэкспоненциальной будет сложность, имеющая вид n log n . Тем не менее, дело-то в том, чтосложно, глядя на задачу, определить, имеется ли полиномиальный алгоритм её решения илинет.Сосредоточимся на задачах распознавания, т.е. задачах, ответом на которые является «да»или «нет».

Более конкретно рассмотрим задачу распознавания языков, которая ставитсяследующим образом: есть некоторый алгоритм A, множество слов в алфавите A обозначимчерез A* и выбирается их подмножество L ⊂ A* — язык в алфавите A. Оговорим ещё однодопущение: что брать за размер входа? Для массивов мы брали число элементов, дляквадратных матриц — порядок (что не то же самое, что число элементов). Здесь входомбудут слова x, а за размер входа возьмём его длину x — число букв в этом слове(неотрицательное целое).

Определимся с операциями. Т.к. любой конечный алфавит можносвести к A = {0, 1} (все слова в алфавите A можно кодировать последовательностями изнулей и единиц). Тогда в качестве операций можно рассматривать битовые операции ибитовую сложность. Не обязательно рассматривать двухсимвольный конечный алфавит,можно и более богатый, только операции в этом случае будут задаваться соответствующимитаблицами. Примечательно, что таким способом суженная задача вызывает проблемы болееосязаемые и более привычные.Пусть алгоритмы распознавания языков, имеющие полиномиальную сложность, образуюткласс P.

В некоторых изданиях к P относят все алгоритмы с полиномиальной сложностью,что было бы не совсем правильным. Класс полиномиальных алгоритмов правильнее было быобозначить через Poly. Вернёмся к нашему определению класса P, как классу алгоритмовраспознавания имеющих полиномиальную сложность. Задача определения принадлежностиалгоритма к классу P является достаточно сложной.Нас будут интересовать предикаты, определённые на словах.

Можно говорить не о «задачах»из класса P, а о предикатах.Рассмотрим наряду с P другой класс алгоритмов — NP.Определение. Будем говорить, что предикат (задача) u ( x) ∈ NP , если существуют такиеполиномы p и q и такой предикат R ( x, y ) , что u ( x) = ∃ y∈A* , y ≤ p ( x )R( x, y ) и предикат R ( x, y )имеет полиномиальную временную сложность, ограниченную q ( x + y ) .Соотношение для u (x) можно записать и в другой форме: ∃ y∈A* ( y ≤ p( x ) ∧ R( x, y ) ) .Обозначение NP происходит от non deterministic polynomer. Слово y в этом случаеназывается сертификатом x (в некоторой литературе — «подсказкой»).Класс NP замечателен тем, что легко проверить принадлежность к нему.

Рассмотрим это напримерах. Но для начала мы должны определится с тем, как будем записывать слова внашем алфавите. Эти способы, вообще говоря, могут быть весьма разнообразными. Дляпримера рассмотрим ситуацию, когда алфавитом являются целые положительные числа. Вэтом случае для их записи мы можем использовать палочную систему (рисовать столькопалочек, какое число мы хотим изобразить) или позиционную систему счисления.Сложность в разных случаях будет различной.Рассмотрим задачу определения, является ли заданный граф гамильтоновым.Гамильтоновым называю граф, если в нём существует путь, проходящий через все вершиныровно по одному разу.

Когда мы рассматриваем произвольный граф и хотим определить,является ли он гамильтоновым, мы можем записать граф матрицей смежности (при52необходимости разделяя строчки некоторым разделителем). Не трудно видеть, чтосформулированная задача распознавания гамильтонового графа принадлежит классу NP.Чтобы доказать это достаточно указать сертификат, в качестве которого в данном случаеможно взять сам гамильтонов путь. Уж как-нибудь за не очень большое (полиномиальное)время проверить, является ли он путём и является ли он гамильтоновым, мы вполне сможем.Задача определения составного числа так же принадлежит классу NP.

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

Будем говорить, что задача (предикат) u1 полиномиально сводится к задачеu2 , если существует функция f : A* → A* , применимая к любому слову из A* , времявычисления которой ограничено p0 ( x ) , и такая, что истинность u1 ( x) эквивалентнаистинности u2 ( f ( x) ) .Обозначение: u1 ≤ P u2Необходимо отметить важный момент: если u1 полиномиально сводится к задаче u2 иu2 ∈ P , тогда u1 ∈ P .

Характеристики

Список файлов лекций

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6510
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее