Задачи по Python с решениями

    На этом шаге мы рассмотрим классы сложности NPC и NPI.     Напомним утверждение IF NP ≠ P then NP:= P∪NPC∪NPI. В соответствии с ним класс NP не исчерпывается (при условии NP≠Р) простыми полиномиальными задачами и сложными NP-полными задачами. В него входят еще и задачи промежуточной сложности, класс которых обозначен здесь как NPI. Утверждение это […]

    На этом шаге мы рассмотрим теорему о полиномиальной сводимости задачи ВЫПОЛНИМОСТЬ к задаче 3-ВЫПОЛНИМОСТЬ. Теорема. Задача ВЫПОЛНИМОСТЬ полиномиально сводима к задаче 3-ВЫПОЛНИМОСТЬ. Доказательство. Пусть имеется КНФ общего вида (без априорного ограничения на длину дизъюнктов). Для доказательства теоремы нам требуется построить КНФ3, в которой длины дизъюнктов ограничены величиной три, такую, что КНФ выполнима тогда и […]

    На этом шаге мы рассмотрим задачу о k-выполнимости.     Задача о k-выполнимости - это задача о выполнимости для выражений, в которых длины дизъюнктов не превосходят величины k (рисунок 1). Рис.1. Задачи k-выполнимости попадают в разные классы     Разумеется задача о k-выполнимости проще задачи о (k+1)-выполнимости, и проще общей задачи о выполнимости для любого конечного […]

    На этом шаге мы рассмотрим классы сложности P, NP, NPI, NPC. IF NP ≠ P then NP:= P∪NPC∪NPI     Введем еще один класс задач - NP-полные (NPC) задачи (проблемы). Проблема Т называется NP-полной, если она удовлетворяет двум условиям: Т ∈ NP, Если R ∈ NP, то R сводится к T за полиномиальное время.     […]

    На этом шаге мы рассмотрим связь между классами P и NP.     Задача о переносе "Ханойской башни" по самой постановке не может быть распараллелена, так как в один момент времени только один диск переносится с иглы на иглу. Поэтому, даже при появлении такой мощной техники как недетерминированные машины эта задача остается в классе ЕХР. […]

    На этом шаге мы рассмотрим теорему о принадлежности задачи ВЫПОЛНИМОСТЬ к классу сложности NP. Теорема. Задача ВЫПОЛНИМОСТЬ принадлежит классу NP. Доказательство. Оно проводится конструктивно, путем построения алгоритма для недетерминированной машины: for i:= 1 to n do x:= выбор({0, 1}); if Φ(x1, x2, ..., xn) then успех else неудача     Этот алгоритм работает следующим образом. […]

    На этом шаге мы рассмотрим класс сложности задач NP.     Изобразим условно взаимоотношение классов задач полиномиальной и экспоненциальной сложностей (рисунок 1). Рис.1. Сложность некоторых задач     Здесь каждая точка области, ограниченной прямоугольником, представляет некоторую задачу. Две точки - это примеры задач из разных классов. Выше было выяснено, что для переноса "Ханойской башни" требуется O(2n) […]

    На этом шаге мы рассмотрим понятие полиномиальной сводимости.     Будем говорить, что задача Q сводится к задаче P за полиномиальное время, если существует детерминированный полиномиальный алгоритм, преобразующий произвольный частный случай задачи Q (частную задачу, полученную подстановкой значений вместо параметров общей задачи Q) в некоторый частный случай задачи P, и второй детерминированный полиномиальный алгоритм, преобразующий […]

    На этом шаге мы рассмотрим понятие задачи распознавания.     Задачи обычно формулируются так: дан набор исходных данных X; требуется найти результат Y, удовлетворяющий условиям задачи. Для некоторых задач в качестве результата удобно рассматривать только значения "да" и "нет". Такие задачи формулируются как вопрос. Например, задача синтаксического анализа текста программы X: "Соответствует ли программа X […]

    На этом шаге мы рассмотрим понятие переборной задачи (задачи решаемой с помощью полного перебора).     Положим, у нас имеется множество S из n элементов. Нам требуется отыскать какое-либо его подмножество, обладающее определенным свойством. Это можно сформулировать так: дан предикат (утверждение) P(A), определенный на множестве 2S всех подмножеств множества S, т. е. A∈2S, истинный на […]