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

NP-трудные задачки

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

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

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

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

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

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

a. Optical Character Recognition (OCR);

b Аппаратный подход «hardware». Ввод и хранение документов;

c. Pen Computer;

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

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

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

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

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

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

4. Геология.

5. Определение речи.

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

Понятно, что такие задачки хотелось бы Аппаратный подход «hardware» решать стремительно, а в ряде всевозможных случаев их нужно решать стремительно.

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

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

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

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

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

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

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

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

В чем неувязка?

«Hardware» vs. «Brainware»

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

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

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

Мозговой Аппаратный подход «hardware» подход

Удалось придумать метод, работающий за 1.41n и n0 -> 2n0.

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

· Неувязка Штейнера состоит в поиске малого дерева Штейнера — кратчайшей сети, соединяющей данный конечный набор точек плоскости. Свое заглавие получила в честь Якоба Штейнера Аппаратный подход «hardware» (1796—1863). В 1941 году вышла монография Р. Куранта и Г. Роббинса «Что такое математика?», в какой создатели написали последующее:

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

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

· Неувязка раскраски графа. Найти малое число цветов (хроматическое число графа G — обозначается χ(G).), в которые можно раскрасить верхушки графа G так, чтоб концы хоть какого ребра имели Аппаратный подход «hardware» различные цвета.

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

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

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

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

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

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


Зависимо от трудности методы факторизации можно разбить на две группы. 1-ая группа — экспоненциальные методы, сложность которых экспоненциально находится в зависимости от длины входящих характеристик (другими словами от длины самого числа Аппаратный подход «hardware» в бинарном представлении).


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

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

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

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

Неувязка остановки

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

Подтверждение неразрешимости препядствия останова лаконически и остроумно. Вот Аппаратный подход «hardware» оно.

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

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

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

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

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

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

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

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

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

Способы для решения NP-полных задач

• Рекурсия

• Хитрецкий перебор

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

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

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

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

• Дели и Аппаратный подход «hardware» владычествуй

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

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

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

Курс на ВМК МГУ http://www Аппаратный подход «hardware».youtube.com/watch?v=6cT4GkQCzc4

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

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

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

• Способы формальной Аппаратный подход «hardware» спецификации

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

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

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

° И другое

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


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

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

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

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


aprel-podgotovitelnaya-gruppa.html
aprelevskij-veterinarnij-centr.html
aprelya-2013-goda-gorod-moskva.html