Вход через социальные сети

  • 06.12.2012, 12:29
    0 up down
    Сообщение
    Уточняю один из вариантов определения терминов:

    класс NP - решаемые недетерминированной машиной тьюринга за полиномиальное время
    класс P - решаемые детерминированной машиной тьюринга за полиномиальное время
    среди задач класса NP выделяются также задачи
    NP - трудные - те к которым можно свести за полиномиальное время любую задачу из класса NP (hint: например реализовав недетерминированную машину Тьюринга)
    NP - полные задачи - такие NP трудные задачи и сама лежит в классе NP ( по простому сначала к ней можно любую свести а потом еще и решить)

    Недетерминированный алгоритм (машина) - который встречая развилку (ветвление, if) просто создает копию себя и они уже вдвоем продолжают решать задачу - кто превый решит тот и молодец. Тогда как тот кто пошел по ложной ветке просто исчезает. Понятно что таким образом найти решение например путь в лабиринте гораздо проще - у вас нет обходов вы просто идете во ВСЕ закоулки одновременно и время работы недетерминированного алгоритма в данном случае - время прохода по настоящему маршруту - то есть недетерминированный алгоритм решает задачу прохода по лабиринту за линейное время.

    Кстати не помню что то доказательства что между NP и E ничего нет...

    Кстати в голливуде был фильм в котором Николас Кейдж работал по недетерменированному алгоритму - очень наглядно. Запамятовал название.

    По поводу пользы полиномиальных алгоритмов все не так просто.
    Случай 1: Симплекс метод. Сложность экспоненциальная. На практике полиномиальная - прост понятен - используется чаще чем доказанно полиномиальные алгоритмы.
    Cлучай 2: Сложность N^3 - метод гаусса. На практике практически не используется - во первых накапливает ошибки численные, во вторых куб это слишком много. Чаще используются итерационные методы в которых основная операция это умножение матриц а не обращение - то есть N^2 (и меньше нельзя так как элементов в матрице N^2 - если не брать разреженные матрицы и специализированные алгоритмы). (Замечу что есть прямые методы которые дают близкую к N^2 оценку - народ здорово продвинулся по теории, но все равно не слышал о практическом применении этих методов)
    Случай 3: Сложность N^2 - казалось бы супер, но в области проектирования электроники характерный размер задачи 10^6-10^8 ну кое где 10^5, как результат N^2 лежит за пределами возможностей по вычислению.

    Вообще в области САПР для электроники используются как правило эвристические или приближенные алгоритмы - но зато либо линейные либо чуть хуже - максимум N^log(N) - это например означает что структуры данных должны быть четко оптимизированы под работу алгоритма - нельзя себе позволить даже сортировку лишнюю. Да и вопросы отладки сталкиваются с приколами - например приходит баг и тесткейс к нему с комментарием - исправить надо за неделю, тесткейс грузится 18 часов, ошибка возникает на 72 часу работы программы. Таковы примерно реалии больших задач.
  • 06.12.2012, 15:57
    0 up down
    Сообщение
    N T в 6.12.2012, 15:34 написал(а): link

    Был бы очень признателен, если бы определили этот термин - "полиномиальное время"

    Полиномиальное время - это значит что задача размерности N будет решена на алгоритме переведенном в машину Тьюринга не более чем за P(N) шагов. Где P(N) это некий конкретный для данного алгоритма полином. NP это соответственно то же самое на недетерминированной машине Тьюринга. Не разрешимость за полиномиальное время означает что для любого P(N) найдется задача (и соответственно N) которая решится за больше чем P(N) шагов. В строгом смысле машина Тьюринга должна напечатать ответ и остановиться.
  • 06.12.2012, 16:14
    0 up down
    Сообщение
    Стянул определение машины Тьюринга - пусть повисит пока лучшего не найдем

    произвольное конечное множество A (алфавит); его элементы называются символами;
    некоторый выделенный символ a0 ∈ A (пробел, или пустой символ);
    конечное множество S, называемое множеством состояний;
    некоторое выделенное состояние s0 ∈ S, называемое начальным;
    таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа (см. ниже);
    некоторое подмножество F⊂ S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).


    Таблица переходов устроена следующим образом: для каждой пары <Текущее состояние, текущий символ> указана тройка <новое состояние, новый символ, сдвиг ленты> . Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A → S x A x {-1,0,1}, определенная на тех парах, в которых состояние не является заключительным.

    Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z → A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом, если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).
  • 06.12.2012, 16:18
    0 up down
    Сообщение
    А вот метод тупого перебора, т.е. например цифровой замок из 4-х цифр -- тупо подбираю комбинацию 0000, 0001, ... 9999.
    Как такой метод называется?
  • 06.12.2012, 16:57
    0 up down
    Сообщение
    N T в 6.12.2012, 18:18 написал(а): link

    А вот метод тупого перебора, т.е. например цифровой замок из 4-х цифр -- тупо подбираю комбинацию 0000, 0001, ... 9999.
    Как такой метод называется?

    полный перебор, или метод грубой силы, brute force

    подсчитаем вычислительную сложность этого алгоритма
    Количество цифр фиксировано, их 10 (0..9)
    Размер исходных данных, который может меняться - длина входного слова (замка) - n цифр.
    Количество возможных вариантов первой цифры - 10, второй цифры - 10 и.т.д
    Получаем 10*10*...*10 = 10^n возможных вариантов замка
    Для их генерации потребуется O(a^n) шагов - алгоритм экспоненциальный
  • 06.12.2012, 17:31
    0 up down
    Сообщение
    Рекомендую почитать Кормена, глава 34. Достаточно доходчиво об P, NP, NPC. Третье издание пока только в английском, но изменений в этой конкретной главе практически нет..

    В той же книге - как определяется время работы алгоритма и т.п. вещи. Считаю, что (из того, с чем сам работал, конечно) по тематике именно алгоритмов - это наилучшая книга.

    N T в 6.12.2012, 14:18 написал(а): link

    А вот метод тупого перебора, т.е. например цифровой замок из 4-х цифр -- тупо подбираю комбинацию 0000, 0001, ... 9999.
    Как такой метод называется?


    Exhaustive search, вообще-то Smile

    Зависит от того, что считать размером входных данных (сейчас не шучу).
  • 06.12.2012, 17:31
    0 up down
    Сообщение
    Svetlana Fainshtein в 6.12.2012, 16:11 написал(а): link
    как ни кодируй, что не подавай на вход - в любой модели эта задача решается за экспоненциальное число шагов
    Ок. Понятно.
    А вот если немного смодификовать задачу с цифровым замком 10^4:
    Дополнительно известно, что сумма всех цифр больше 5 и меньше 20.
    В общем можно и дальше использовать "brute force", но вроде можно и иначе. Как тогда называется такой метод?

  • 06.12.2012, 17:50
    0 up down
    Сообщение
    для программирования полного перебора используют рекурсивный алгоритм с возвратом (перебор с возвратом, backtracking)
    дополнительные ограничения вставляются туда в виде условий (отсечений), что ускоряет работу алгоритма на реальных данных, но его теоретическая выч. сложность остаётся всё равно экспоненциальная, в худшем случае

    Kiv, неча на Кормена пенять, пишите прям сюда, в дополнение и разъяснение
  • 06.12.2012, 20:10
    0 up down
    Сообщение
    Детерминированные машины Тьюринга (ДМТ). Класс P полиномиальных алгоритмов.

    Детерминированная машина Тьюринга - математическая модель алгоритма. Вообще, по математической модели алгоритма все языки программирования можно разделить на три группы: алгоритмические (ДМТ), функциональные (вычислимая функция), логические (исчисление предикатов).

  • 06.12.2012, 20:43
    0 up down
    Сообщение
    Svetlana Fainshtein в 6.12.2012, 19:10 написал(а): link
    Вообще, по математической модели алгоритма все языки программирования можно разделить на три группы...

    По математической модели - может так и деляться.
    Вот C/ANSI куда отнести: алгоритмические, функциональные (вычислимая функция), логические (исчисление предикатов)?

    A еще обычно языки программирования делять:
    -- по способу компиляции,
    -- уровню, как бы сказать, приближенным к нормальному языку или к языку машины,
    -- структуруальные, обьекто-ориентированные ...