courses:algorithms_building_and_analysis:materials:np_full_tasks_notes
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2020/07/05 18:05] aoblizanov [Что такое полиномиальное время?] |
courses:algorithms_building_and_analysis:materials:np_full_tasks_notes [2022/12/10 09:08] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== [В работе] NP класс и NP-полные задачи ====== | + | ====== NP класс и NP-полные задачи ====== |
| - | ===== Вопросы и ответы про NP, P и т.д. ===== | + | ===== Вопросы и ответы про $NP, P$ и т.д. ===== |
| ==== Что такое класс $P$? ==== | ==== Что такое класс $P$? ==== | ||
| - | $P$ -- класс задач, решаемых за **полиномиальное** (от размера входа) время. Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д. | + | $P$ -- класс задач, //решаемых// за **полиномиальное** (от размера входа) время. Примеры таких задач: задача о существовании пути в графе, задача о взаимно простых числах и т.д. |
| ==== Что такое полиномиальное время? ==== | ==== Что такое полиномиальное время? ==== | ||
| - | Говорят, что алгоритм работает за полиномиальное время, если время работы ограничено сверху многочленом от размера входа алгоритма, то есть $T(n)=O(n^k)$ для некоторой константы $k$. | + | Говорят, что алгоритм работает за полиномиальное время, если время работы //ограничено сверху// многочленом от размера входа алгоритма, то есть $T(n)=O(n^k)$ для некоторой константы $k$. |
| (Примерами задач являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из $n$ чисел, нахождение эйлерова цикла на графе из $m$ рёбер, обнаружение в тексте длиной $n$ некоторого слова, построение покрывающего дерева минимальной стоимости) | (Примерами задач являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из $n$ чисел, нахождение эйлерова цикла на графе из $m$ рёбер, обнаружение в тексте длиной $n$ некоторого слова, построение покрывающего дерева минимальной стоимости) | ||
| ==== Что такое класс $NP$? ==== | ==== Что такое класс $NP$? ==== | ||
| - | $NP$ -- класс задач, верифицируемых (проверяемых) за **полиномиальное** время. Альтернативное определение: класс задач, решаемых за полиномиальное время на недетерминированной машине Тьюринга. Примеры таких задач: задача о выполнимости булевой формулы, задача о вершинном покрытии, задача о клике и т.д. | + | $NP$ -- класс задач, //верифицируемых// (проверяемых) за **полиномиальное** время. Альтернативное определение: класс задач, решаемых за полиномиальное время на //недетерминированной машине Тьюринга//. Примеры таких задач: задача о выполнимости булевой формулы, задача о вершинном покрытии, задача о клике и т.д. |
| ==== Как доказать, что задача принадлежит классу $NP$? ==== | ==== Как доказать, что задача принадлежит классу $NP$? ==== | ||
| Существует два варианта: | Существует два варианта: | ||
| Line 19: | Line 19: | ||
| **Сертификат** -- дополнительная информация, позволяющая быстро решить задачу. Важно помнить, что размер сертификата должен быть полиномиален относительно размера самой задачи. | **Сертификат** -- дополнительная информация, позволяющая быстро решить задачу. Важно помнить, что размер сертификата должен быть полиномиален относительно размера самой задачи. | ||
| - | **Алгоритм верификации** -- принимает на вход экземпляр задачи и сертификат к нему, а возвращает ответ к задаче, 0 или 1. | + | **Алгоритм верификации** -- принимает на вход //экземпляр// задачи и сертификат к нему, а возвращает ответ к задаче, 0 или 1. |
| - | + | ||
| - | **Пример:** задача о клике. Сертификат -- множество вершин, образующих клику. Алгоритм верификации: проверить, что все вершины, приведенные в сертификате, связаны между собой (сложность - $O(n^2)$ | + | |
| <note>Грубо говоря, к классу $NP$ относятся те задачи, правильность решения которых можно проверить быстро (за полиномиальное время). К классу $P$ относятся задачи, которые можно быстро решить. Далее рассмотрим подробнее задачи, связанные с классом $NP$.</note> | <note>Грубо говоря, к классу $NP$ относятся те задачи, правильность решения которых можно проверить быстро (за полиномиальное время). К классу $P$ относятся задачи, которые можно быстро решить. Далее рассмотрим подробнее задачи, связанные с классом $NP$.</note> | ||
| + | |||
| + | <note tip>В тексте есть слова, выделенные //курсивом//. Убедитесь, что хорошо понимаете их значение, порой оно связано со смежными науками.</note> | ||
| + | |||
| ---- | ---- | ||
| ==== Какие задачи называются $NP$-трудными? ==== | ==== Какие задачи называются $NP$-трудными? ==== | ||
| - | Это задачи, к которым сводимы все задачи из класса $NP$ за полиномиальное время. При этом не требуется, чтобы сама задача принадлежала классу $NP$, она может быть более сложной. | + | Это задачи, к которым //сводимы// все задачи из класса $NP$ за полиномиальное время. При этом не требуется, чтобы сама задача принадлежала классу $NP$, она может быть более сложной. |
| ==== Что значит, что одна задача водима к другой за полиноминальное время? ==== | ==== Что значит, что одна задача водима к другой за полиноминальное время? ==== | ||
| - | Это значит, что существует полиномиальная функция, которая отображает экземпляр первой задачи в экземпляр второй задачи. Если входная задача соответствует положительному решению, то и выходная задача соответствует положительному решению. Если входная задача соответствует отрицательному решению, то и решение выходной задачи отрицательно. | + | Это значит, что существует полиномиальная функция, которая //отображает// экземпляр первой задачи в экземпляр второй задачи. Если входная задача соответствует положительному решению, то и выходная задача соответствует положительному решению. Если входная задача соответствует отрицательному решению, то и решение выходной задачи отрицательно. |
| ==== Какие подходы к решению $NP$-трудных задач? ==== | ==== Какие подходы к решению $NP$-трудных задач? ==== | ||
| * Полный перебор (Brute force) | * Полный перебор (Brute force) | ||
courses/algorithms_building_and_analysis/materials/np_full_tasks_notes.1593972317.txt.gz · Last modified: 2022/12/10 09:08 (external edit)
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
