Pull to refresh

Доказательство np-полноты задач

Lumber room
Необходимо решить четыре задачи на данную тематику, перечитал кучу книжек по теме, в том числе и Гери и Джонсона. Честно говоря, в голову ничего не приходит.
Я уверен, что на хабре много умных и добрых людей. Помогите, пожалуйста, с решением начинающему хабрачеловеку.

Собственно сами задачи:
1)Доказать, что данная задача np-полная, путем сводимости ее к задаче 3-ВЫП. Задача: разбиение на гамильтоновы подграфы. Условие: задан ориентированный граф G = (V,A). Вопрос: можно ли разбить вершины графа G на непересекающиеся подмножества V1, V2, ..., Vk такие, что каждое Vi содержит по крайней мере 3 вершины, а все индуцируемые ими подграфы графа G содержали бы гамильтонов циклы?

2)Доказать, что данная задача np-полная, путем сводимости ее к задаче ТП-3. Задача: Разложение подстановки. Условие: задана подстановка b множества {1,2,...,N} и последовательность S1, S2,...,Sm подмножеств множества {1,2,...,N}. Вопрос: можно ли представить подстановку b в виде композиции подстановок b = b1,b2,...,bm, где для каждого i, 1 <= i <= m, подстановка bi оставляет неподвижными элементы множества {1,2,...,N}\Si?

3)Доказать, что данная задача np-полная, путем сводимости ее к задаче ТП-3. Задача: оптимальный коммуникационный остов. (условие приводить не буду, проще всего его посмотреть в Гэри и Джонсоне)

4)Доказать, что данная задача np-полная, путем сводимости ее к задаче ВП. Задача: кратчайшая общая надпоследовательность. Условие: заданы конечный алфавит E, конечное множество R слов в алфавите E* и положительное целое число k. Вопрос: существует ли такое слово w из E*, что |w| <= k и каждое слово x из R есть подпоследовательность w, т.е. w = w0x1w1x2w2...xkwk, где wi из E*, а x = x1,x2,..,xk?
Total votes 6: ↑1 and ↓5 -4
Views 2K
Comments 0

P=NP? Важнейшая нерешенная задача теоретической информатики

Entertaining tasks
Эта задача была сформулирована в 1971 году и до сих пор остается нерешенной. За доказательство утверждения P=NP или за доказательство его опровержения Математическим институтом Клэя назначена премия в 1 миллион долларов США. Если все-таки окажется, что P=NP, то это даст возможность быстро и эффективно решать множество трудноразрешимых на данный момент задач.

Так в чем же все-таки суть проблемы?

Читать дальше →
Total votes 96: ↑84 and ↓12 +72
Views 16K
Comments 376

Оценка сложности алгоритмов

Algorithms *
Sandbox

Введение


Для любого программиста важно знать основы теории алгоритмов, так как именно эта наука изучает общие характеристики алгоритмов и формальные модели их представления. Ещё с уроков информатики нас учат составлять блок-схемы, что, в последствии, помогает при написании более сложных задач, чем в школе. Также не секрет, что практически всегда существует несколько способов решения той или иной задачи: одни предполагают затратить много времени, другие ресурсов, а третьи помогают лишь приближённо найти решение.

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

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

Подробности
Total votes 43: ↑30 and ↓13 +17
Views 54K
Comments 10

Теорема Клини о неподвижной точке: квайны

Programming *Algorithms *
Здравствуйте, хабралюди. В последнее время было много разговоров о квайнах, и даже некоторый теоретический спин-офф.
Повторю за автором только что упомянутого топика: если вы знакомы с CS, то далее читать нет смысла — все это
вы и так хорошо знаете. А статья будет ответом на вопрос — всегда ли можно написать квайн? Точнее, на любом ли языке?
Физики скажут, что на всех: раз можно написать и на компилируемом C, и на брейнфаке, а кто-то и на SQL пишет — опыт говорит, что ответ на вопрос да. Математика тоже говорит, что да.

Теорема 2
На любом алгоритмически полном языке программирования можно написать программу, печатающую свой код.
Читать дальше →
Total votes 59: ↑55 and ↓4 +51
Views 22K
Comments 22

Мысль — материальна: Алан Тьюринг как «универсальный вычислитель»

Cryptography *Programming *Algorithms *Mathematics *
image
Источник: geektimes.ru

В первой половине XX века, когда были изобретены первые вычислительные машины. Однако наряду с физически осязаемыми машинами появлялись и машины-концепции. Одной из них была «машина Тьюринга» — абстрактное вычислительное устройство, придуманное в 1936 году Аланом Тьюрингом — учёным, которого считают одним из основоположников информатики.

Его кругозор распространялся от квантовой теории и принципа относительности до психологии и неврологии. А в качестве способа познания и передачи своих знаний Тьюринг использовал аппарат математики и логики. Он находил решения, казалось бы, нерешаемых задач, но был сильнее всего увлечен идеей «Универсальной машины», способной вычислить всё, что в принципе вычислимо.
Читать дальше →
Total votes 33: ↑33 and ↓0 +33
Views 43K
Comments 11

Неожиданная полнота по Тьюрингу повсюду

Information Security *Computer hardware Artificial Intelligence Desktop PC's CPU
Translation
Каталог программных конструкций, языков и API, которые неожиданно являются полными по Тьюрингу; последствия этого для безопасности и надёжности. Приложение: сколько компьютеров в вашем компьютере?

Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp. — Десятое правило Гринспена

Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.

Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин»1). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.
Читать дальше →
Total votes 54: ↑53 and ↓1 +52
Views 46K
Comments 15

Кто же ты такой, алгоритм?

ITSOFT corporate blog Algorithms *Mathematics *Popular science

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

Читать далее
Total votes 12: ↑11 and ↓1 +10
Views 7.6K
Comments 13

История проблемы равенства классов P и NP

Timeweb Cloud corporate blog Mathematics *Popular science

В 2000 году Математический институт Клэя определил 7 математических задач, решение которых не могли найти в течение многих лет. За решение каждой из них была назначена награда в размере 1 миллиона долларов. Эти 7 задач известны как «задачи тысячелетия», и на сегодняшний день только одна из них была решена — гипотеза Пуанкаре. В этой статье пойдет речь о вопросе равенства классов P и NP, ответ на который может сильно повлиять на всю IT-сферу.

Читать далее
Total votes 25: ↑24 and ↓1 +23
Views 9.8K
Comments 8