• ↓
  • ↑
  • ⇑
 
Записи с темой: алгоритмы (список заголовков)
18:02 

Amicus Plato
Простыми словами
Как вам вот это, товарищи?

beta.novoteka.ru/?s=science#nnn15049216

Про P?=NP в сообществе написано много.
Но вот решить проблему мы не пробовали. А она, как оказалось, решилась. И всего на ста страницах.
Вот еще ссылка:
lenta.ru/articles/2010/08/12/np/

UPD: А вот и само доказательство:
www.hpl.hp.com/personal/Vinay_Deolalikar/Papers...

@темы: Интересные ссылки, Вопросы, Алгоритмы

19:14 

Наконец-то! P?=NP и институт Клэя

Amicus Plato
Простыми словами
В конце прошлой записи мы вплотную подошли к проблеме равенства классов сложности P и NP. Сформулировать ее можно следующим образом:

Если правильность ответа на какой-либо вопрос можно проверить за полиномиальное время, то верно ли, что этот ответ возможно так же быстро найти (т.е. за полиномиальное время и используя полиномиальную память)?

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

16:20 

Еще одна запись об NP-полноте (не обещаю, что последняя)

Amicus Plato
Простыми словами
Тема алгоритмической сложности, даже если пробегать по самым ее верхам (как я и планировала), оказывается такой же неисчерпаемой, как и атом.
Попытаюсь всё-таки продвинуться к логическому завершению.
Почему же столь важны оказались именно булевы формулы?
Напомню, булева формула называется выполнимой, если существует такой набор значений входящих в нее переменных, для которого она принимает значение ИСТИНА.

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

16:48 

NP-полнота, NP-полные задачи и булевы формулы

Amicus Plato
Простыми словами
Что же такое NP-полные задачи?
О задачах из класса NP мы уже поговорили, но оказывается, среди них есть особенные. И таких особенных тоже не так уж мало.
NP-полные задачи — это класс задач, лежащих в классе NP, к которым сводятся все задачи класса NP за полиномиальное время. То есть, если найдется быстрый алгоритм (полиномиальный) для решения любой из NP-полных задач, то и любая задача из класса NP тоже может быть решена быстро!

Вот сейчас я прочитала в одном месте удивительную мысль. Не могу не процитировать:
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи удается доказать ее NP-полноту, есть основания считать ее практически неразрешимой. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать искать быстрый алгоритм, решающий ее точно.
(с)
"В принципе", всё так и есть. Но проблема P=(?)NP так и висит в воздухе. И доказать неравенство тоже ведь никто не может, не только равенство.

О проблеме равенства классов P и NP, надеюсь, я напишу в следующей записи (и тем самым завершу этот цикл), а сейчас перечислю NP-полные задачи (не все, конечно) — для иллюстрации того, что их ведь достаточно много! А стоит решить "быстро" одну, и к ее решению можно будет свести все остальные! Вот где простор для деятельности!

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

Небольшой экскурс в теорию и историю
История
Что же такое булева формула?
Булева формула — это формула логики высказываний. Логика высказываний — самая простая из всех логик. Говорят еще, что это классическая логика нулевого порядка.
Про нее я даже могу рассказать, не прибегая ни к каким ухищрениям.
Остановимся на основном определении. "Высказывание". Что это такое?
Под высказыванием понимают любое повествовательное предложение, о котором можно сказать, истинно оно или ложно.
Например (с этого я каждый раз начинаю первое занятие по матлогике) какие из перечисленных предложений являются высказываниями?

0. Который час?
1. 2*2=4
2. 2*2=5
3. Лондон — столица Парижа.
4. Включите свет.
5. 2*х=8
6. a*b = b*a для любых a и b

Ответ:

Продолжение теории

@темы: Поп-математика, Искусственный интеллект, Алгоритмы, Amicus Plato

16:13 

Класс NP

Amicus Plato
Простыми словами
Самые известные задачи, входящие в класс NP, следующие:

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

12:23 

Время работы алгоритмов

Amicus Plato
Простыми словами
Напишу про то, зачем же нам всё-таки нужно понижать алгоритмическую сложность. Казалось бы, машины быстрые, процессоров у них тоже может быть много. Неужели действительно так остро стоит проблема времени?

Давайте посмотрим.
читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

18:34 

Алгоритмическая сложность. Лирическое отступление.

Amicus Plato
Простыми словами
Хочу подробнее остановиться на том примере, который привела в прошлой записи.

Задача формулируется очень просто: определить, является заданное число простым или составным.

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

23:49 

Продолжение рассказа про алгоритмическую сложность, классы P, NP и про NP-полноту III

Amicus Plato
Простыми словами
Недетерминированная Машина Тьюринга
Рассматривая детерминированную машину Тьюринга, мы коснулись и недетерминированной тоже.
Еще раз приведу определение:

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

С тем, что означает "существует не более одного правила", мы разобрались в прошлый раз. А что же значит "в противном случае"?

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

22:59 

Продолжение рассказа про алгоритмическую сложность, классы P, NP, и про NP-полноту II

Amicus Plato
Простыми словами
Продолжаю рассказ про алгоритмическую сложность.
С О-нотацией мы разобрались, осталось разобраться еще с некоторыми вещами.
Итак, про то, что такое класс Р, нам уже известно.
Напомню: классом P (polynomial) называется множество алгоритмов, время работы которых не превосходит многочлена от размера данных. То есть сложность таких алгоритмов в терминах О-больших будет О(NC), где N — размер входных данных.
Алгоритмы, принадлежащие классу P, считаются быстрыми. Оттого-то мы и испытываем к ним повышенный интерес.
К классу Р относятся алгоритмы сортировки, поиска в множестве, перемножения матриц, выяснения связности графов и некоторые другие.

читать дальше

@темы: Amicus Plato, Алгоритмы, Искусственный интеллект, Поп-математика

22:51 

Продолжение рассказа про алгоритмическую сложность, классы P и NP и про NP-полноту I

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

@темы: Поп-математика, Искусственный интеллект, Алгоритмы, Amicus Plato

23:48 

Рассказ про алгоритмическую сложность, классы P и NP, и про NP-полноту

Amicus Plato
Простыми словами
(Всё, что я здесь напишу, будет изложено неформально. Постараюсь избежать каких бы то ни было определений, и, тем более, сложных выводов... Хотя это будет совсем не просто)))

Что же такое сложность алгоритма? На самом деле, понять это интуитивно довольно легко.
Алгоритмическая сложность — это зависимость времени исполнения алгоритма от длины входных данных.
То есть, конечно же очевидно, что если нам нужно что-то найти во входных данных или что-то переставить местами, то чем больше количество информации на входе, тем больше времени понадобится, чтобы получить результат.
"Время" здесь величина довольно абстрактная. Естественно, она (эта величина) должна быть универсальной, и не зависеть от типа и производительности компьютера или иного устройства, а также от других частностей. Измеряется она числом элементарных шагов. Сейчас поясню, что это такое.

читать дальше

UPD: В комментариях важное дополнение сделал  Хранитель печати. Он привел основные классы сложности с их описанием.

@темы: Amicus Plato, Искусственный интеллект, Поп-математика, Алгоритмы

Поп-математика для взрослых детей

главная