Главная | Обратная связь

P, NP и NP полные проблемы.

Неформально класс NP можно определить с помощью понятия, которое мы будем называть недетерминированным алгоритмом. Такой алгоритм состоит из двух различных стадий – стадии угадывания и стадии проверки.

Класс NP, определяемый неформально, - это класс всех задач распознавания П, которые при разумном кодировании могут быть решены недетерминированными (N- nondeterministic) алгоритмами за полиномиальное (P- polynomial) время принадлежность задачи П классу Pвлечет принадлежность дополнительной задачи классу P, но не известно, имеет ли место аналогичное утверждение для класса NP.

Любой детерминированный алгоритм может быть использован в качестве стадии проверки недетерминированного алгоритма.

Способность недетерминированного алгоритма проверить за полиномиальное время экспоненциальное число возможностей может навести на мысль, полиномиальные недетерминированные алгоритмы являются более мощным средством, чем полиномиальные детерминированные алгоритмы.

Фундамент теории NP-полных задач был заложен в работе С. Кука, опубликованной в 1971 г. под названием "Сложность процедур вывода теорем". В этой короткой, но элегантной работе Кук получил несколько важных результатов. Во-первых, он подчеркнул важность понятия "сводимость за полиномиальное время", т. е. сводимость, которая выполняется с помощью алгоритма с полиномиальной временной сложностью. Если одна задача сводится за полиномиальное время к другой, то любой полиномиальный алгоритм решения второй задачи может быть превращен в полиномиальный алгоритм решения первой. Во-вторых, он обратил внимание на класс задач распознавания свойств (класс NP), которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве. (Задачей распознавания свойств называется задача, решениями которой могут быть либо "да", либо "нет".) Большинство не поддающихся решению задач, которые встречаются на практике, после переформулировки их в виде задач распознавания попадают в этот класс. В-третьих, С. Кук доказал, что одна конкретная задача из NP, называемая задачей о выполнимости, обладает тем свойством, что всякая другая задача из класса NP может быть сведена к ней за полиномиальное время'). Таким образом, если задача о выполнимости может быть решена за полиномиальное время, то и любая задача из класса NP полиномиально разрешима, а если какая-то задача из NP труднорешаема, то и задача о выполнимости также должна быть труднорешаемой Таким образом, в некотором смысле задача о выполнимости - "самая трудная" в классе NP. Вопрос о том, действительно ли NP-полные задачи труднорешаемы, в настоящее время считается одним из основных открытых вопросов.

17. Односторонние функции. Асимметричные криптосистемы. Структура алгоритма RSA. Электронная подпись.

17.

Односторонняя функция эффективно вычисляется за полиномиальное время на детерминированной машине Тьюринга, но не существует полиномиальной вероятностной машины Тьюринга, которая обращает нашу функцию с более чем экспоненциально малой вероятностью.

Существование таких функций не доказано. Современная асимметричная криптография основывается на предположении, что они все-таки существуют

Криптографическая система с открытым ключом (или Асимметричное шифрование, Асимметричный шифр) — система шифрования и/или электронной цифровой подписи (ЭЦП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу, и используется для проверки ЭЦП и для шифрования сообщения. Для генерации ЭЦП и для расшифрования сообщения используется секретный ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL.

 

Схема, разработанная Райвестом, Шамиром и Адлеманом, основана на выражениях со степенями. Открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа n. Это значит, что длина блока должна быть меньше или равна log2(n). На практике длина блока выбирается равной 2^k битам, где 2^k < n < 2^k+1. Шифрование и дешифрование для блока открытого текста M и блока шифрованного текста C можно представить в виде следующих формул:

C =M^e mod n,

M =Cd mod n = (M^e)^dd mod n = M^ed mod n.

 

Электронная цифровая подпись(ЭЦП)- это полученный в результате криптографического (шифровального) преобразования информации с использованием закрытого ключа подписи реквизит электронного документа, предназначенный для защиты этого документа от подделки, а также от внесения несанкционированных изменений.

18. Искусственный интеллект (ИИ). Тест Тьюринга. Основные подходы к моделированию ИИ. Подходы к реализации ИИ. Области применения ИИ.

Термин интеллект - означает ум, рассудок, разум; мыслительные способности человека. Соответственно искусственный интеллект- ИИ (AI) обычно толкуется как свойство автоматических систем брать на себя отдельные функции интеллекта человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий.

Задачи, связанные с отысканием алгоритма решения класса задач определенного типа, будем называть интеллектуальными. Мы можем перефразировать определение интеллекта как универсальный сверхалгоритм, который способен создавать алгоритмы решения конкретных задач.

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

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

Второй подход в качестве объекта исследования рассматривает ИИ. Здесь речь идет о моделировании интеллектуальной деятельности с помощью вычислительных машин. Целью работ в этом направлении является создание алгоритмического и программного обеспечения вычислительных машин, позволяющего решать интеллектуальные задачи не хуже человека.

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

Для начала кратко рассмотрим логический подход. Почему он возник? Ведь человек занимается отнюдь не только логическими измышлениями. Это высказывание конечно верно, но именно способность к логическому мышлению очень сильно отличает человека от животных.

Основой для данного логического подхода служит Булева алгебра. Практически каждая система ИИ, построенная на логическом принципе, представляет собой машину доказательства теорем. При этом исходные данные хранятся в базе данных в виде аксиом, правила логического вывода как отношения между ними. Кроме того, каждая такая машина имеет блок генерации цели, и система вывода пытается доказать данную цель как теорему. Если цель доказана, то трассировка примененных правил позволяет получить цепочку действий, необходимых для реализации поставленной цели. Мощность такой системы определяется возможностями генератора целей и машиной доказательства теорем.

Под структурным подходом мы подразумеваем здесь попытки построения ИИ путем моделирования структуры человеческого мозга. Одной из первых таких попыток был перцептрон Френка Розенблатта. Основной моделируемой структурной единицей в перцептронах (как и в большинстве других вариантов моделирования мозга) является нейрон.

Довольно большое распространение получил и эволюционный подход. При построении систем ИИ по данному подходу основное внимание уделяется построению начальной модели, и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, это может быть и НС и набор логических правил и любая другая модель. После этого мы включаем компьютер и он, на основании проверки моделей отбирает самые лучшие из них, на основании которых по самым различным правилам генерируются новые модели, из которых опять выбираются самые лучшие и т. д.

Еще один широко используемый подход к построению систем ИИ — имитационный. Данный подход является классическим для кибернетики с одним из ее базовых понятий — "черным ящиком" Таким образом здесь моделируется другое свойство человека — способность копировать то, что делают другие, не вдаваясь в подробности, зачем это нужно. Зачастую эта способность экономит ему массу времени, особенно в начале его жизни.