Теормин (Esyr) (1125519)

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

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

Введение в теорию сложности1) Индивидуальная и массовая задачи, кодировка задачи, алгоритм решения массовой задачи, временная сложность алгоритма.Методичка, стр. 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).Временная сложность.2) Задачи распознавания свойств.

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

11Для любойсуществует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью:.4) Класс 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-полных задач.5) Критерий NP-полноты.

Д-во NP-полноты задачи ЦЛНМетодичка, стр. 15Критерий NP-полноты. Массовая задача Π NP-полна тогда и только тогда, когда она принадлежит классу NP и к ней полиномиально сводится какая-либо NP-полная задача.6) Д-во NP-полноты задачи 3-выполнимость.

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

Рабочая гипотеза, что.Если для некоторой NP-полной задачи Π дополнительная к ней задача, то NP = co-NPКласс PSPACE массовых задач -- класс алгоритмов, требующих не более, чем полиномиальной памяти.Гипотеза.(то есть, не факт, что вложение строгое, но скорее всего так). При этом NP-полные, NP-трудные, NP-эквивалентные задачи8) Псевдополиномиальные алгоритмы. Пример для задачи о рюкзакеПсевдополиномиальный алгоритм - полиномиальный алгоритм, проявляющий экспоненциальный характер только при очень больших значениях числовых параметров.Пусть M(I) -- некоторая функция, задающая значение числового параметра индивидуальной задачи I.

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

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

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

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

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

В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его ребрам от вершины к вершине в сторону увеличения значения функционала.

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

Тип файла PDF

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

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

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