Теормин (1125514)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Введение в теорию сложностиИндивидуальная и массовая задачи, кодировка задачи,алгоритм решения массовой задачи, временная сложностьалгоритма.Методичка, стр. 4-8Массовая задача Π:▪▪список свободных параметров;формулировка свойств, которым должно удовлетворять решение задачи.Π есть множество индивидуальных задач. Индивидуальная задачаполучается, если всем параметрам присвоить конкретные значения.Пусть Σ — конечный алфавит, а Σ * — множество слов в этом алфавите.

Отображениеe:называется кодировкой задачи Π.Алгоритм A решает массовую задачу Π, если для любой индивидуальной задачи :▪▪A применим к I, то есть останавливается за конечное число шаговA дает решение IКодировка задачи P — такое отображениеследующими свойствами:, обладающее▪Возможность однозначно декодировать, то есть у двух различных ИЗ не можетбыть одинаковых кодировок.▪▪e,e − 1 — полиномиально вычислимыКодировка не избыточна, то есть для любой другой кодировки e1,удовлетворяющей 1 и 2 условиям справедливо:Язык массовой задачи — это множество правильных слов, то есть слов,соответствующих ИЗ, имеющим положительный ответ(подразумевается задачараспознавания):Язык алгоритма — множество слов, принимаемых A, то есть таких, на которыхалгоритм останавливается в состоянии qY, что соответсвует "да":Алгоритм A решает массовую задачу Π, с кодировкой e, если L(e,Π) = L(A) иА останавливаетсяЧисло шагов алгоритма A для входа— это tA(s).Временная сложность.Задачи распознавания свойств.

Классы P и NP.Методичка, стр. 8-11Задача распознавания свойств -- массовая задача, предполагающая ответ "да" или"нет", в качестве своего решения.▪▪D(Π) -- множество всех возможных значений параметров массовой задачи.Y(Π) -- множество всех индивидуальных задач, ответом на которые является"да".Класс полиномиально разрешимых задач (P) -- это такие задачи, временнаясложность алгоритма решения которых ограниченна полиномом:▪такой, что A решает массовую задачу Π с кодировкой e▪-- полином такой, чтоПримеры неполиномиальных задач:▪алгоритмически неразрешимые задачи:▪применим к I, например,▪ 10-я проблема Гильберта: по данному многочлену g с целымикоэффициентами выяснить, имеет ли уравнение g = 0 целочисленноерешениезадачи, для которых длина записи выхода превышает любой наперед заданныйполином от длины входа▪ найти все маршруты в задаче коммивояжёра∀А, решающего П с кодировкой e, ∀p(·) ∃I ∈ П: tA(e(I)) > p( | e(I) | )▪такая, что A неКласс недетерминированно полиномиальных задач (NP) -- это такие задачи, длякоторых существует алгоритм решения на недерменированной машине Тьюринга:▪▪для НДМТ такой, чторешает массовую задачу Π с кодировкой e-- полином такой, чтоТеорема об экспоненциальной временной оценке для задачиз класса NP.Методичка, стр.

11Для любойсуществует ДМТ A, решающая ее с не более чемэкспоненциальной временной сложностью:.Класс co-NP. Пример задачи, допускающей хорошуюхарактеризацию. Доказательство утверждения овзаимоотношении классов NPC и co-NP.Методичка, стр. 12-14Дополнительная задачак массовой задаче Π -- задача, получаемая из Π путемвведения альтернативного вопроса.

То есть если в Π спрашиваем "верно ли x", то вспрашиваем "верно ли, что"▪▪Класс co-P -▪co-P = P.Класс co-NP -▪.co-NP = NP пока не удалось ни доказать, ни опровергнуть, но это вряд ли верно.▪Массовая задача Π допускает хорошую характеризацию, если▪пример такой задачи -- это задача определения простоты числа.▪Массовая задача Π' с кодировкой e' полиномиально сводится к задаче Π скодировкой e, если любая индивидуальная задачаможет быть сведена заполиномиальное от её длины время к некоторой задачеответа.с сохранениемМассовая задача Π называется NP-полной (универсальной), если▪принадлежит классу NP:▪ любая задача из NP полиномиально сводится к Π:Класс NPC (NP-complete) -- множество всех NP-полных задач.Критерий NP-полноты. Д-во NP-полноты задачи ЦЛНМетодичка, стр. 15Критерий NP-полноты.

Массовая задача Π NP-полна тогда и только тогда, когда онапринадлежит классу NP и к ней полиномиально сводится какая-либо NP-полнаязадача.Д-во NP-полноты задачи 3-выполнимость. NP-трудные задачиМетодичка, стр. 17-18Класс NP-трудных задач содержит:1.задачи распознавания свойств Π, для которых▪2.3.не доказано, что▪задачи оптимизации, для которых соответствующие задачи распознаваниясвойствлюбые задачи, к которым сводятся по Тьюрингу хотя бы одна NP-полнаязадачаВзаимоотношение классов P, NP и NPC, NP и co-NP. КлассPSPACEЛегко показать, что. Рабочая гипотеза, что.Если для некоторой NP-полной задачи Π дополнительная к ней задачаNP = co-NP, тоКласс PSPACE массовых задач -- класс алгоритмов, требующих не более, чемполиномиальной памяти.Гипотеза.(то есть, не факт, что вложение строгое, но скореевсего так).

При этом NP-полные, NP-трудные, NP-эквивалентные задачиПсевдополиномиальные алгоритмы. Пример для задачи орюкзакеПсевдополиномиальный алгоритм - полиномиальный алгоритм, проявляющийэкспоненциальный характер только при очень больших значениях числовыхпараметров.Пусть M(I) -- некоторая функция, задающая значение числового параметраиндивидуальной задачи I. Если таких параметров несколько, в качестве M(I) можновзять или максимальное, или среднее значение, а если задача вовсе не имеетчисловых параметров (например, раскраска графа, шахматы и т.п.), то M(I) = 0.Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкостиTmax(I) = O(p( | I | ,M(I))), где-- некоторый полином от двух переменных.en-wikiСильная NP-полнота.

Теорема о связи сильной NP-полнотызадачи с существованием псевдополиномиального алгоритмаее решенияПолиномиальное сужение массовой задачи Π -- множество таких индивидуальныхзадач I, числовые параметры которых не превосходят полинома от длины входа:Массовая задача Π называется сильно NP-полной, если её полиномиальное сужениеявляется NP-полным. Примеры:▪задача выполнимости, задача 3-выполнимости -- совпадают со своимиполиномиальными сужениями▪ задача булевых линейных неравенств -- ВЫП сводится к её полиномиальноусужению, где числовые параметры (правая часть неравенств) линейны.▪ задача о целочисленном решении системы линейных уравнений -- , т.к.

БЛНсводится к ней▪ задача коммивояжёра (TSL) -- совпадает со своим сужениемЗадача о рюкзаке -- слабо-NPC.Теорема. Если NP не совпадает с P, то ни для какой сильно-NPC задачи не существуетпсевдополиномиального решения.Определение ε-приближенного алгоритма и полностьюполиномиальной приближенной схемы (ПППС). Связь междусуществованием ПППС и псевдополиномиальностьюМетодичка, стр.

22-24Задача дискретной оптимизации -- решение каждой индивидуальной задачиявляется произвольная реализация оптимума, где▪SΠ(I) -- область допустимых значений дискретной переменной z▪fΠ -- целевая функция задачи оптимизации▪ max вообще говоря вполне может быть заменён на minАлгоритм A называется приближённым алгоритмом решения массовой задачи Π,если для любой задачион находит точку, лежащую вобласти допустимых значений, принимаемую за приближённое решение.Утверждение. Если, то ни для какой константы C > 0 не существуетполиномиального приближённого алгоритма решения задачи о рюкзаке с оценкой.Приближённый алгоритм A решения массовой задачи Π называетсяприближённым алгоритмом решения задачи, если-.Теорема об отсутствии ПППС для задач оптимизации,соответствующих сильно NP-полным задачам распознаванияМетодичка, стр.

24Теорема Если для Π оптимизации▪соответствующая ей задача распознавания свойств является сильно NP-полной▪существует полиномто при условии, чтодля Π не существует ПППСОсновы линейного программированияОпределение озЛП. Принцип граничных решений.Алгебраическая и битовая сложность ЛП. Результаты осложности для задач, близких к ЛПЛП (линейное программирование) -- теория, приложения и методы решения системылинейных неравенств с конечным числом неизвестных :, существует лиудовлетворяющий данной системе линейных неравентсв,озЛП (основная задача линейного программирования) : найти такой вектор-- решение задачи линейного программирования,максимизирующее линейную функциюУтверждение (принцип граничных решений). Если озЛП имеет решение, тонайдется такая подматрица AI матрицы A, что любое решение системы уравнений AIx= bI реализует максимум.Алгебраическая сложность -- количество арифметических операций.Битовая сложность -- количество операций с битами.

Битовая сложность задач ЛП,ЛН полиномиальна.Вопрос о существовании алгебраически-полиномиального алгоритма для ЛП остаетсяоткрытым.Геометрическое описание симплекс-метода(Копипаста из [ru.wiki], там-же есть хорошая иллюстрация.)Симплекс-метод -- метод решения озЛП.Каждое из линейных неравенств вограничивает полупространство всоответствующем линейном пространстве.

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

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)