• ↓
  • ↑
  • ⇑
 
Записи пользователя: 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, Искусственный интеллект, Поп-математика, Алгоритмы

22:32 

Amicus Plato
Простыми словами
Вчера на федеральном тестировании по информатике среди прочего попались интересные задачи. До сегодняшнего дня я считала их задачами "на сообразительность". Очень удивлялась, тому, что они оказались в тестах по информатике. Там вроде и сообразительности особой не требовалось....
Сегодня знающие люди просветили меня, что это задачи из теории массового обслуживания.
Как оказалось, я ее должна была преподать в рамках информатики )))
Решала я их (и прорешала штук двадцать похожих) именно как решала бы задачи для младшей школы "на смекалку" — графическим способом.
И теперь вот думаю: наверное, для решения таких задач существуют специальные методы?

А задачи таковы (делятся они на две группы: в одной надо найти время, в другой количество людей; выпишу по одной из каждой группы):

1. Врач принимает каждого пациента 15 минут. К нему пришли 4 пациента с интервалом в 5 минут. Какое максимальное время сидения пациентов в очереди?

2. Врач принимает каждого пациента 15 минут. На прием пришли 5 пациентов с интервалом в 5 минут. Какое максимальное количество человек окажется в очереди?

(Сами числа беру с потолка, поэтому ответов не знаю сама)))
Решая, получила море удовольствия (хоть и очень краткосрочного)))!
Чего и вам желаю )))

22:37 

Amicus Plato
Простыми словами
Наверное, всем известно, что на моем аватаре картина Мориса Эшера "Куб с магическими лентами".
Я о ней как-то никогда особо не задумывалась, и считала, что кроме парадоксального переплетения лент с диагоналями граней куба и между собой, ничего сверхъестественного в нем нет.
Однако недавно прочла в книге, что вот эти самые пУпочки на лентах одни люди видят выпуклыми, а другие — вогнутыми. И, в принципе, каждому под силу увидеть их и такими и такими, но только в разные моменты времени.
Какими их вижу я, — не скажу. Однако же вижу только в одном состоянии, и сколь ни стараюсь, в другом увидеть не могу....
Скажите, что видите вы?

@темы: Amicus Plato, Вопросы, Невозможные фигуры

21:51 

Amicus Plato
Простыми словами
Задачка (легкая, но забавная)))

После семи стирок длина, ширина и высота куска мыла уменьшились вдвое.
На сколько стирок хватит оставшегося куска?

11:47 

Amicus Plato
Простыми словами
Когда я только начинала заниматься искусственным интеллектом, многое для меня, человека с классическим математическим образованием, было совершенно непонятно.
Некоторые термины теории алгоритмов вызывали едва не священный трепет.
Когда кто-то рядом произносил "NP-полнота", я даже приблизительно не могла представить, о чем идет речь.
Вообще, классы сложности алгоритмов — удивительно интересная вещь.
Вот, дам ссылку на статью.
www2.computerra.ru/xterra/253871/
Статья написана очень хорошо, но лично мне понятны там не все логические переходы.
Постараюсь рассказать об этом попроще, а кроме того, надеюсь, расскажу и о других классах сложности алгоритмов.

@темы: Интересные ссылки

22:12 

Счетные палочки Джона Непера

Amicus Plato
Простыми словами
Не знаю, всем ли известно имя одного из выдающихся математиков, барона Джона Непера (1550-1617) — шотландца по происхождению.
Вот он собственной персоной (с) Википедия:


Знаменит о в первую и в самую основную очередь тем, что изобрел логарифмы!
Можно себе представить, как мучились люди в те времена, производя умножение и деление многозначных чисел. Непер же придумал специальные таблицы, в которых было произведено взаимно однозначное соответствие геометрической прогрессии и арифметической. Причем, естественно, геометрическая прогрессия была исходной. Таким образом, умножению Непер сопоставил гораздо более легкое сложение, а делению, соответственно, — вычитание.
За что всё прогрессивное человечество благодарно ему по сей день.

Но я сейчас буду рассказывать не об этом.
В 1617 году Непер предложил другой, не логарифмический, способ умножения чисел, для которого придумал специальное устройство, получившее название «палочки Непера».
Рассказываю я о нем в связи с записями о фигурных числах. Это еще один способ визуализации арифметики. (Хотя, на самом деле, больше ничего общего с фигурными числами тут нет).

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

Этот «вычислительный инструмент» состоял из брусков с нанесенными на них цифрами от 0 до 9 и кратными им числами. Для умножения какого-либо числа бруски располагали рядом так, чтобы цифры на торцах составляли это число. Ответ можно было увидеть на боковых сторонах брусков.

Вот смотрите: (это самая лучшая из найденных мной картинок):

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

Полоски с нанесенными на них числами, были еще разделены диагоналями так, что слева (выше) диагонали располагаются десятки, а справа — единицы.
Для получения произведений осуществляется суммирование «вдоль диагоналей».


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

Помимо умножения, палочки Непера позволяли выполнять деление и извлекать квадратный корень.

Под кат спрячу цитату с одного сайта, постичь которую я не в состоянии)))
Тем не менее, там всё объясняется))
Упражнение для пытливых умов:
читать дальше

@темы: Amicus Plato, Люди

22:27 

Из дружественного сообщества))

Amicus Plato
Простыми словами
Пишет  Серебряный:
31.05.2008 в 01:07


ЛОГИЧЕСКИЕ ОПЕРАТОРЫ
! нет
&! и нет!
!,!&! нет, нет и нет!
. точка.
!&. нет и точка!
= равно
* все
~* не все
*= все равно
~*=? не все ли равно?
*>&> все больше и больше
# точно
!# приблизительно
!#* почти все
$? Деньги есть?
>! Больше нет.
#!? Точно нет?
!4u Не для тебя
&? И чо?
&!? И ничо!

URL записи

@темы: Публикации, )))

14:41 

Фигурные числа III

Amicus Plato
Простыми словами
Пятиугольные числа
Пятиугольные числа — числа, которые составляют пятиугольники.
По-моему, это образование уже менее естественное, чем все предыдущие, но если вспомнить, какое внимание пифагорейцы уделяли пятиконечной звезде, вписанной в правильный пятиугольник, то удивляться тут нечему.
Вот как они выглядят:
(Знаю, что они даже кривее, чем треугольники... Но что поделать...)


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

@темы: Натуральные числа, Люди, Amicus Plato, античность

23:25 

Фигурные числа II

Amicus Plato
Простыми словами
Квадратные и прямоугольные числа

Как нетрудно догадаться, квадратные числа — это такие количества камушков, из которых можно выложить квадраты.
То есть, числа, которые можно представить в виде: n*n.


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

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

@темы: Amicus Plato, Люди, Натуральные числа, античность

21:19 

Фигурные числа I

Amicus Plato
Простыми словами
Пифагор.
Про Пифагора я уже писала: вот здесь.
Речь шла о несоизмеримости гипотенузы и катетов прямоугольного равнобедренного треугольника.
Но это была только самая малость из того, что я хочу рассказать об этом поистине великом человеке.


А сейчас рассказ пойдет о фигурных числах.

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

Главной особенностью античной математики был полу-арифметический - полу-геометрический подход к числам.
Пифагорейцы различали треугольные, квадратные, прямоугольные, пятиугольные числа (это, так сказать, двумерные числа, — числа на плоскости). Как производные от них получались кубические и пирамидальные числа.
Не уверена, что перечислила все, но давайте разберемся сначала с этими.

Треугольные числа
Треугольные числа — это такие числа, из которых (имея столько камушков) можно выложить правильные треугольники.
Вот первые четыре числа:

Их значения равны:
Т1=1, Т2=3, Т3=6 и Т4=10.

Нетрудно продолжить ряд и получить значения следующих треугольных чисел:
Еще парочка...
Т5=15, Т6=21, Т7=27, Т8=36...

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

Тn = 1 + 2 + 3 + 4 +...+ n

С давних времен известно (еще даже до того как девятилетний Карл Фридрих Гаусс открыл сумму первых n членов арифметической прогрессии))), что сумма первых n чисел может быть посчитана следующим образом:

1 + 2 + 3 + 4 +...+ n = 1/2 • n(n+1)

Таким образом, треугольное число с номером n вычисляется по этой формуле:
Тn = 1/2 • n(n+1)

Треугольные числа кроме всего прочего являются биномиальными коэффициентами при второй степени икса (в разложении (1 + x)n по степеням x).

"Число зверя" 666 также является треугольным.

Сумма двух последовательных треугольных чисел даст нам число квадратное.
Формула такова:
Tn + Tn − 1 = n2.
Но об этом — продолжение следует.

@темы: Amicus Plato, Люди, Натуральные числа, античность

22:46 

Очередная просьба о помощи ))

Amicus Plato
Простыми словами
Помните вот эту мою "разработку"?
"Ассоциативная модель памяти".
www.diary.ru/~Organon/p40071949.htm
Я ее несколько формализовала, но пока только на описательном уровне.
Теперь мне нужно построить математический аппарат.
Сейчас попытаюсь вкратце изложить суть. Начну с того, что уже описано в той записи, на которую ссылка.
Вот представьте, что у нас есть множества. Предположим, множества эти существуют в виде мешков. На каждом мешке написано имя множества, соответствующее какому-либо свойству объектов предметной области. Например, мешок с названием "зеленый" или мешок с названием "круглый", и т.д. Мешков таких очень-очень много. Что же в них лежит? В них лежат, предположим, чечевичные зерна. Каждое с надписью. Надпись содержит имя объекта, обладающего данным свойством.
Например (пример тоже старый) хотим мы поместить зеленый ромб в модель, описывающую плоские цветные многоугольники. Модель состоит из множества мешков, на которых написано: "Все стороны равны", "Четыре угла", "Углы попарно равны", "Зеленый", "Выпуклый", "Углы прямые".
Мы возьмем и сосчитаем, сколько мешков (свойств) подходит зеленому ромбу. Из перечисленных шести подходят первые пять. Значит, возьмем пять чечевичных зернышек, обзовем их "Зеленый ромб" или как-то так, чтобы мы знали, что это такое (например, это не абстрактный ромб, а, предположим, что-то конкретное, чему у нас есть имя (в голову ничего не приходит)...), ну, вот, возьмем мы эти подписанные зернышки и разложим по нашим мешкам. И так сделаем с каждым объектом предметной области.
И пусть мешки эти очень удобные: сразу видно, что там внутри лежит.
И вот теперь такой вопрос: можно ли создать метрику на таком пространстве? Можно ли задать расстояние между понятиями?
Должно удовлетворяться очень много требований.
Основные таковы:
1. Чем больше общих мешков у двух объектов А и В, тем расстояние меньше.
2. Чем больше разных мешков у А и В, тем расстояние больше.
3. Чем меньше объектов в каждом конкретном общем для А и В мешке, тем расстояние меньше. Поясню. Если у нас объекты связаны ассоциацией, содержащей 1000 понятий, например, ассоциация, заданная цветом ("зеленый"), то эта ассоциация слаба, и расстояние достаточно велико. А если в мешке всего два зернышка, то вытащив одно, мы моментально узнаем второе: такая ассоциация самая сильная. Расстояние должно быть равно нулю.
4. Аналогичное свойство для мешков с разными свойствами. Чем незначительнее различные свойства (предположим, дело всё в том же цвете), тем меньше эта ассоциация должна влиять на близость. Если же свойства, "разнящие" понятия, т.е. мешки, в которые входит А, но не входит В и наоборот, содержат малое количество объектов, то эти свойства значительны, и расстояние должно сильно увеличиться.
У меня есть две формулы-кандидата для вычисления расстояния, но ни для одной из них не выполняется неравенство треугольника. А без него нет речи о метрике! А метрика тут должна быть! Уж очень красиво выходит!
Вдруг у кого какие-нибудь мысли появятся? А?

@темы: Amicus Plato, Вопросы

19:27 

Amicus Plato
Простыми словами
Выкладываю ссылку на интереснейшую статью доктора физико-математических наук Владимира Успенского «Апология математики, или О математике как части духовной культуры».
magazines.russ.ru/novyi_mi/2007/11/us10.html
Если вы читаете сообщество давно, вы найдете поразительное количество практически стопроцентного совпадения текста с записями сообщества! Имею в виду не только и не столько содержание, но к нему еще и форму вплоть до метафор и сравнений!
Всё-таки Платоновское царство идей и Ноосфера, видимо, подспудно сильно влияют на наше мышление.

А вот несколько цитат:

***
Неотъемлемой частью цивилизации является то или иное представление об указанном устройстве — хотя бы признаваемое в наши дни совершенно фантастическим, как, например, такое: “А Земля — это только лишь плесень в перевёрнутой неба корзине; звёзды — это свет другого мира, к нам просвечивающий сквозь дно корзины, сквозь бесчисленные маленькие дыры, не затёртые небесной глиной”.

***
Как говорил один из самых крупных математиков XX века Джон фон Нёйман (1903 — 1957): “В конечном счёте, современная математика находит применение. А ведь заранее не ясно, что так должно быть”.

***
“По-видимому, натуральный ряд чисел не представляет из себя абсолютно объективного образования. По-видимому, он представляет собой функцию головы того математика, который в данном случае говорит о натуральном ряде”.


Одним словом, читайте: не пожалеете!

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

17:09 

Ну, раз уж совсем такая пьянка )))

Amicus Plato
Простыми словами
Задачка бородатая. Может, кто-то и знает...

Задача про леммингов

На доске длиной 50 метров случайно расставили 128 леммингов. Доска достаточно узкая чтобы 2 лемминга не могли разойтись. Каждый лемминг движется со скоростью 50 метров в час (изначально одни идут вправо, другие влево, как расставили). Когда 2 лемминга встречаются они разворачиваются и расходятся в разные стороны. Когда лемминг доходит до края доски он падает и разбивается. Через какое время на доске гаранитрованно не останется ни одного лемминга?

@темы: Головоломки и занимательные задачи

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

главная