Аппаратный подход «hardware»

NP-тяжёлые задачи

В тео?рии алгори?тмов — науке, изучающей закономерности алгоритмов и общие свойства и разнообразные формальные модели их представления, классом NP (от англ. non-deterministic polynomial) именуют множество задач распознавания, ответ которых при наличии некоторых дополнительных сведений возможно «скоро», другими словами за время, не превосходящее полинома от размера разрешённых проверить на машине Тьюринга.

Хорошая теория методов изучает неприятности формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности (P, NP и др.).

По задачам распознавания образов на факультете ВМК МГУ читается важный курс http://www.ccas.ru/frc/papers/mestetskii04course.pdf . Постановка задачи тут такая. Будем вычислять, что все объекты либо явления разбиты на конечное число классов. Для каждого класса известно и изучено конечное число объектов – прецедентов. Задача распознавания образов пребывает в том, дабы отнести новый распознаваемый объект к какому-либо классу.

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

1. Машинное зрение. Это совокупности, назначение которых пребывает в получении изображения через составление и камеру его описания в символьном виде (какие конкретно объекты присутствуют, в каком обоюдном отношении находятся и т.д.).

2. Символьное распознавание – это распознавание букв либо цифр.

a. Optical Character Recognition (OCR);

b. хранение и Ввод документов;

c. Pen Computer;

d. Обработка чеков в банках;

e. Обработка почты.

3. Диагностика в медицине.

a. Маммография, рентгенография;

b. Постановка диагноза по истории заболевания;

c. Электрокардиограмма.

4. Геология.

5. Распознавание речи.

6. Распознавание в дактилоскопии (отпечатки пальцев), распознавание лица, подписи, жестов.

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

Эквивалентно класс NP возможно выяснить как класс, содержащий задачи, каковые возможно «скоро» решить на недетерминированной машине Тьюринга. Сейчас давайте разберемся, что свидетельствует «скоро» и из-за чего так много внимания этим вопросам?

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

Для определенности скажем, что вычисления выполняются на машине Тьюринга, не смотря на то, что возможно перенести логику рассуждения на любую мнимую (Поста, Успенского, Маркова) либо настоящую машину. Зависимость времени работы от длины входа (кроме этого для определенности её измеряют длиной входа в битах) возможно задана функцией f(x). Она возможно полиномом N-ной степени, экспонентой ex, факториалом х! и т.п. При громадных х факториал будет расти стремительнее экспоненты, экспонента стремительнее любого полинома, полином бОльшей степени — стремительнее полинома меньшей. При малых х это, по большому счету говоря, не выполняется, но важность воображает как раз поведение при громадных х.

Классом P (от англ. polynomial) именуют множество задач, для которых существуют «стремительные» методы ответа (время работы которых полиномиально зависит от размера входных данных для детерминированной МТ). Полиномиальные методы – это методы, время работы которых оценивается как функция O(n), O(n log n), O(n2), O(n3), O(n1000), где n – это «размер входа».

Примерами задач из класса P являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, задачи сортировки данных, выяснение связности графов и другие. Итак, к классу P относятся задачи, ответ которых возможно скоро (за полиномиальное время) отыскано.

К классу NP принадлежат задачи, решаемые за полиномиальное время посредством недетерминированной МТ. За «полиномиальное время» свидетельствует, что в случае если входные эти, записанные на ленту МТ, занимают N ячеек, то машине чтобы получить ответ нужно совершить не более T(N) переходов, где T(N) –многочлен (какой-то степени).

В случае если задача экспоненциальна, то ее ответ вероятно лишь для малых значений входа. Исходя из этого громадный интерес воображает нахождение полиномиальных методов ее решения либо подтверждение того, что для данной задачи таких нет в принципе. В попытках отыскать ответ некоторых задач, было найдено, что, в определенном смысле, они все эквивалентны. В случае если существует полиномиальный метод, решающий одну из них, то существует таковой метод для любой из них. Наряду с этим преобразование любой задачи из этого класса в решаемую требует полиномиального времени. В отличие от задач класса P, для которых найдется полиномиальный метод (степень полинома произвольна — задача со сложностью N1000000 полиномиальна!), и задач класса Е, каковые не решаемы менее чем за экспоненциальное время, задачи данного класса решаются недетерминированными автомобилями Тьюринга за полиномиальное время — неясно, действительно, где НДМТ производятся! НДМТ не более чем полиномиальное число раз в ходе ответа сталкиваются с необходимостью выбора — и решают его превращением одной автомобили в пара, любая из которых идёт по собственному пути (говорят, в свое время так в Соединенных Штатах решали вопрос выбора метода получения урана для ядерной бомбы — выстроили по заводу для каждого метода!). Ясно, что попытка это реализовать фактически приведет к появление экспоненциального — но уже числа автомобилей. Пара более утешительна другая интерпретация — в момент выбора появляется оракул, что растолковывает нам, что путь верный. Утешительна она вследствие того что в случае если нам удастся придумать и алгоритмизовать метод выбора верного пути, то мы возьмём полиномиальный метод. Так, удайся нам ответ хоть одной NP-задачи, мы можем сохранять надежду на решение их всех.

Практика довольно часто ограничивается нахождением приближенного ответа за разумное время.

В чем неприятность?

«Hardware» vs. «Brainware»

Базисный метод: время работы O(2n), на практике трудится для n

Аппаратный подход «hardware»

По закону Мура[1] каждые полтора года компьютеры удваивают производительность. Каким станет n0? Оказывается n0 — n0 + 1.

Мозговой подход

Удалось придумать метод, трудящийся за 1.41n и n0 — 2n0.

Примеры NP-полных задач (не попадающих в класс P):

  • Задача о выполнимости булевых формул. Экземпляром задачи есть булева формула, которая состоит лишь из имен переменных, операций и скобок (И), (Либо) и (HE). Задача содержится в следующем: возможно ли назначить всем переменным, видящимся в формуле, значения истина и ложь так, дабы формула стала подлинной.
  • Задача коммивояжёра. Одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого удачного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (малейший, самый недорогой, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. В большинстве случаев, указывается, что маршрут обязан проходить через любой город лишь один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
  • Задача о портфеле. Преступник пробрался в помещение, где лежит N предметов. Для каждого предмета известна его стоимость и масса. Требуется заполнить портфель, максимизируя суммарную цена предметов, при условии, что неспециализированная масса отобранных предметов не имеет возможности быть больше заданного P.
  • Неприятность Штейнера пребывает в поиске минимального дерева Штейнера — малейшей сети, соединяющей заданный конечный комплект точек плоскости. Собственный наименование взяла в честь Якоба Штейнера (1796—1863). В первой половине 40-ых годов двадцатого века вышла монография Р. Куранта и Г. Роббинса «Что такое математика?», в которой авторы написали следующее:

«Весьма несложная и вместе с тем поучительная неприятность была изучена в начале прошлого столетия известным берлинским геометром Якобом Штейнером. Требуется соединить три деревни , , совокупностью дорог так, дабы их общая длина была минимальной.

Чтобы получить вправду хорошее внимания обобщение неприятности Штейнера, … поставим задачей выстроить «уличную сеть» либо «сеть дорог между данными сёлами», владеющую минимальной неспециализированной длиной».

  • Неприятность раскраски графа. Выяснить предельное количество цветов (хроматическое число графа G — обозначается ?(G).), в каковые возможно раскрасить вершины графа G так, дабы финиши любого ребра имели различные цвета.
  • Задача о вершинном покрытии. Вершинное покрытие для неориентированного графа G = (V, E) это множество его вершин S, такое что, у каждого ребра графа хотя бы один из финишей входит в S. Задача о вершинном покрытии требует указать минимально вероятный размер вершинного покрытия для заданного графа.

Пример: Граф, изображённый справа, имеет вершинное покрытие размера 4. Но оно не есть мельчайшим вершинным покрытием, потому, что существуют вершинные покрытия меньшего размера {2, 4, 5} и {1, 2, 4}. Размером (size) вершинного покрытия именуется число входящих в него вершин.

  • Задача о клике. Кликой в неориентированном графе именуется подмножество вершин, каждые две из которых соединены ребром графа. И ными словами, это полный подграф начального графа. Размер клики определяется как число вершин в ней. Задача о клике существует в двух вариантах: в задаче распознавания требуется выяснить, существует ли в заданном графе G клика размера k, в то время как в вычислительном варианте требуется отыскать в заданном графе G клику большого размера. На рисунке приведен граф с кликой размера 3.

Неформально: к классу NP относят задачи, каковые смогут быть решены перебором 2роly(n) вариантов.

Принадлежность классу NP — это хорошая черта!

Пример: факторизация, либо разложение числа на простые множители. Всякое составное число возможно единственным образом представлено в виде произведения несложных множителей. К примеру, 48 = 2 · 2 · 2 · 2 · 3, 225 = 3 · 3 · 5 · 5, 1050 = 2 · 3 · 5 · 5 · 7 .

В отличие от задачи распознавания простоты числа, факторизация предположительно есть вычислительно непростой задачей.


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


Вторая несколько — субэкспоненциальные методы. Советую Д. Кнут Раздел 4.5.4. Разложение на простые множители // Мастерство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные методы. — С. 425—468. — 832 с. — ISBN 0-201-89684-2

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

NP-полные задачи. Неформально, это самые трудные задачи в класса NP. Примеры были приведены.

NP-тяжёлые задачи. Неформально, задача C именуется NP-тяжёлой, в случае если для неё существует такая NP-полная задача, которая сводится к C за полиномиальное время (алгоритмическая сводимость по Куку). К примеру, неприятность остановки есть NP-тяжёлой, т.к. её нереально решить на МТ. С не обязательно в собственности классу NP!

Неприятность остановки

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

Подтверждение неразрешимости неприятности останова кратко и остроумно. Вот оно.

Предположим, что МТ, решающая задачу останова, существует. Обозначим ее H(m, s). Эта машина разбирает закодированную машину m с содержимым ее ленты s. В случае если машина m заканчивает работу на ленте s[2], машина H переходит в состояние qyes; в другом случае будет произведен переход в состояние qno (обратите внимание, что машина H постоянно заканчивает работу!) Сейчас сконструируем другую машину T с состоянием ленты str. Метод работы автомобили T таковой:

Имитировать работу автомобили H(str, str);

if (машина H перешла в состояние qno ) перейти в состояние qyes;

else делать нескончаемый цикл;

Так, машина T заканчивает работу, в случае если переданная ей в виде строчка машина str «зависает». В другом случае T переходит в нескончаемый цикл сама.

«Зависает» ли машина T(t) (где t — закодированное представление автомобили Т)?

Предположим, что да. Это указывает, что исполнение метода пошло по ветви В противном случае, что, со своей стороны, быть может, в случае если H(t, t) заканчивает работу в состоянии qyes. По определению автомобили Н это переводится как «машина t с лентой t не зависает». Получается, что машина Т не зависает! Мы пришли к несоответствию.

Разглядим сейчас вторую альтернативу: машина T(t) заканчивает работу. Это указывает, что машина H(t, t) переходит в состояние qno, другими словами «машина t с лентой t не заканчивает работу (зависает)». Несоответствие!

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

Способы для ответа NP-полных задач

• Рекурсия

• Умный перебор

Локальный поиск

• Случайный порядок действий

• Вероятностное сведение к несложной задаче

• Случайное блуждание

• Разделяй и властвуй

Верификация программ

Формальная верификация — формальное подтверждение соответствия либо несоответствия формального предмета верификации его формальному описанию. Предметом выступают методы, другие доказательства и программы.

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

Курс на ВМК МГУ http://www.youtube.com/watch?v=6cT4GkQCzc4

Тестирование ПО не имеет возможности доказать, что совокупность, метод либо программа не содержит никаких дефектов и ошибок и удовлетворяет определённому свойству. Это может сделать формальная верификация.

Формальные способы

«Применение математического аппарата, реализованного в языках, методах и верификации программ и средствах спецификации»

• Способы формальной спецификации

• Способы формальной верификации:

° Подтверждение теорем

° Верификация на моделях

° И второе

Методы для поисковых совокупностей, квантовые вычисления – к семинару

[1] Гордон Мур (Gordon Moore). Сутки рождения: 03.01.1929 года. Место рождения: Калифорния, Сан-Франциско, США. Гражданство: США

предприниматель и Известный миллиардер. Популярным Гордон Мур стал еще в апреле 1965-го года, в то время, когда вышла в свет его печатная работа – «Закон Мура», затрагивающий область полупроводников. Гордон Мур, один из основателей компании Intel, на протяжении наблюдений распознал закономерность, в соответствии с которой количество транзисторов, размещаемых на кристалле интегральной схемы, удваивается примерно каждые два года. Как следствие, мощность вычислительных устройств возрастает экспоненциально. Правило, в соответствии с которому полупроводниковая индустрия начинается уже практически 50 лет, стало называться закона Мура.

В 1975 году он поменял временную составляющую закона и заявил об удвоении количества транзисторов каждые два года. В 2007 году Мур объявил, что закон, разумеется, не так долго осталось ждать прекратит функционировать из-за ограничения скорости и атомарной природы вещества света

[2] Очевидно, задача останова решается для некоей МТ и тех либо иных данных ее ленты. Одинаковая МТ может завершать работу либо переходить в нескончаемый цикл в зависимости от входных данных.

Как попадает косметика в ноготь и кожу? В. Соломонов


Также читать:

Понравилась статья? Поделиться с друзьями: