Фразы о компьютерах многолетней давности

[Amicus Plato]

Давно собиралась позаимствовать у коллег.
В сообществе физиков-романтиков есть чудесная запись.

Пишет  Серебряный:

Фразы о компьютерах многолетней давности.

- В будущем компьютеры будут весить не более чем 1.5 тонны (Popular Mechanics, 1949 г.).

- Думаю, что на мировом рынке мы найдем спрос для пяти компьютеров. (Thomas Watson - директор компании IBM, 1943 г.)

- Я изъездил эту страну вдоль и поперек, общался с умнейшими людьми, и я могу вам ручаться в том, что обработка данных является лишь причудой, мода на которую продержится не больше года. (Редактор издательства Prentice Hall, 1957 г.)

Продолжение

- Но, что... может быть полезного в этой штуке? (Вопрос на обсуждении создания микрочипа в Advanced Computing Systems Division of IBM, 1968 г.)

- Ни у кого не может возникнуть необходимость иметь компьютер в доме. (Ken Olson - основатель и президент компании Digital Equipment Corp., 1977 г.)

- Такое устройство, как телефон, имеет слишком много недостатков, чтобы рассматривать его как средство связи. Поэтому считаю, что данное изобретение не имеет никакой ценности. (гИз обсуждений в компании Western Union в 1876 г.)

- Концепция интересна и хорошо оформлена. Но для того чтобы идея начала работать, она должна содержать здравый смысл. (Профессура Yale University в ответ на предложение Фреда Смита об организации сервиса доставки на дом; Fred Smith станет основателем службы доставки Federal Express Corp.)

- Да кого, к чертям, интересуют разговоры актеров? (Реакция H.M.Warner - Warner Brothers на использование звука в кинематографе. 1927 г.)

- Нам не нравится их звук, и вообще, гитара - это вчерашний день. (Decca Recording Cо, отклонившая запись альбома группы The Beatles в 1962 г.)

- Летающие машины весом тяжелее воздуха невозможны! (Lord Kelvin - президент Королевского Общества - Royal Society - 1895 г.)

- Бурение земли в поисках нефти? Вы имеете в виду, что надо сверлить землю для того, чтобы найти нефть? Вы сошли с ума. (Ответ на проект Edvin L. Drike в 1859 г.)

- Самолеты - интересные игрушки, но никакой военной ценности они не представляют. (Marechal Ferdinand Foch, профессор).

- Теория Луи Пастера о микробах - смешная фантазия. (Pierre Pachet- профессор психологии университета Тулузы, 1872 г.)

- 640 КБ должно быть достаточно для каждого. (Bill Gates, 1981г.)

- 100 миллионов долларов - слишком большая цена за Microsoft. (IBM, 1982г.)

---

Лев и человек

[Amicus Plato]

Задача взята из "Математической смеси" Литлвуда.
Привожу ее не столько из-за нее самой, сколько из-за сопутствующих соображений. Во-первых, очень порадовало "лирической отступление" Литлвуда про задачу с монетами.
А во-вторых, та самая апория про Ахиллеса и черепаху этой задаче и в подметки не годится!

Значится...

Лев и человек

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

Говорят, что задача о "взвешивании монет" стоила 10 000 человеко-часов непродуктивно потраченного времени математиков, занятых оборонной работой во время войны. Было даже сделано предложение сбросить эту задачу над Германией.

Задача о льве, хотя и имеет уже 25-летнюю давность, недавно вновь пронеслась по стране; но большинство удовлетворилось ответом "L (лев) все время должен находиться на радиусе ОМ (М — человек)".
Если L сходит с ОМ, то асимметрия идет в пользу М.
...

Дальше я цитировать не буду, но вывод, как вы уже догадались, такой, что лев так никогда и не пообедает.
Не верите? Проверьте!

(*) "Кривая погони" (L всегда бежит прямо на М) требует бесконечного времени, так что формулировка задачи не лишена смысла.

@темы: Бесконечность, ))), Головоломки и занимательные задачи, Amicus Plato, Публикации

---

[Amicus Plato]

А вот давненько не было тут вопросов на засыпку.
Читаю книгу Дэннета и Хофштадтера "Глаз разума". И вот, что вычитала:

«В курсах математики и физики есть знаменитый "вопрос на засыпку": "почему зеркало меняет местами правое и левое, но не верх и низ?" Этот вопрос заставляет многих задуматься, и если вы не хотите, чтобы вам сказали ответ, пропустите следующие два абзаца».

Надо сказать, что "следующие два абзаца" мало меня удовлетворили. Разве что одним предложением в самом конце. Но это был не ответ на поставленный вопрос! Отнюдь!
Есть ли у кого соображения по этому поводу?

@темы: ))), Головоломки и занимательные задачи, Amicus Plato, Вопросы

---

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

[Amicus Plato]

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

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

Проблема Кука (P=?NP) ждет своего разрешения уже 37 лет. Интуитивно, вроде бы ясно, что эти классы ну никак не могут быть равны. И сейчас (поскольку никто не может доказать их равенство) все ведут себя так, как будто они и неравны.
Из определения классов Р и NP (напомню, класс Р состоит из задач, разрешимых за полиномиальное время; класс NP состоит из задач, которые разрешимы с подсказкой за это же полиномиальное время) следует, что P ⊂ NP.

Т.е. если мы представим это в виде картинки, получим следующее:

P ⊂ NP

Однако до сих пор никто не может ни доказать, ни опровергнуть строгость этого включения, иными словами, найти такой алгоритм, который лежит в классе NP, но не принадлежит в P (т.е. находится в желтой части картинки).

Давайте посмотрим на NP-полные задачи.
Из определений классов следует, что класс Р — класс самых легких задач из NP. Класс NP-полных задач — самый сложный. NP-полные задачи решаются за экспоненциальное время, а это может быть очень, очень долго!


NPC ⊂ NP (где NPC — NP-Complete — NP-полные задачи)
На картинке классы Р и NPC не пересекаются:
NPC ∩ P = ∅

А что бы было, если бы они пересеклись? По определению NP-полной задачи к ней можно свести любую задачу из класса NP. Поэтому если хотя бы для одной из них удастся найти алгоритм решения за полиномиальное время — это будет означать: УРА! Проблема решена!

"Ура", да не очень "ура"!
Потому что если человечество научится быстро (за полиномиальное время) решать NP-полные задачи, последствия будут очень и очень печальными.
Практическая криптография (по большей части) окажется бесполезной. Вся защищенная информация окажется полностью "беззащитной". Заходи, кто хочешь, бери, что хочешь!
Кроме этого, теория алгоритмической сложности испытает очень существенные потрясения. Потому что есть еще много-много разных классов, о которых я здесь просто не упоминала, но часть из них образует (бесконечную) иерархию внутри NP. Если же равенство P=NP будет доказано, вся эта иерархия свернется в один единственный класс Р.

Однако же, я думаю, выгоды тоже будут колоссальными! Мы научимся считать быстро! Всё!

А вот повторю то, о чем писала в прошлый раз:
Проблема равенства классов P и NP является одной из семи проблем, за решение которых Математический институт Клэя назначил премию в 1 млн. долларов США.

Кстати, на сайте этого института дано уморительное описание этой проблемы!
www.claymath.org/millennium/P_vs_NP/
Не поленюсь даже и переведу. (Хотя за точность перевода ручаться не буду)
***
Предположим, вы организуете расселение четырехсот студентов университета. Однако (как всегда) общежитие не может вместить всех, и места в этом общежитии получат только сто из них. Чтобы усложнить вашу задачу, декан выдал вам список пар "несовместимых студентов" и потребовал, чтобы ни одна пара из этого списка не оказалась вместе!
Это пример того, что ученые называют NP-задачей, т.к. легко проверить, является ли определенный выбор ста студентов подходящим (т.е. ни одна пара из результирующего списка не оказалась в списке, выданном деканом), однако задача формирования такого списка с нуля кажется настолько трудной, что выполнить ее практически невозможно.
В самом деле, общее число путей выбора ста студентов из четырехсот кандидатов больше чем число атомов в нашей Вселенной! (прим. АР: неужели правда? С₄₀₀¹⁰⁰ — больше, чем число атомов Вселенной? Хотя что это я... Если всего-то до миллиарда можно считать больше 30 лет...)
Таким образом никакая цивилизация будущего не может даже надеяться на создание суперкомпьютера, способного решить эту задачу с помощью "грубой силы" )))), т.е. проверяя каждую возможную комбинацию 100 студентов из 400. Однако эта очевидная трудность может всего лишь отражать недостаток изобретательности вашего программиста ))))
Фактически, это одна из выдающихся проблем информатики — доказать существование или несуществование такого вопроса, ответ на который можно легко проверить, но который требует невероятно долгого времени для своего решения любым прямым методом.
Задачи, аналогичные той, которую мы рассмотрели, точно кажутся именно такими! Но однако до сих пор никто не смог доказать, что хотя бы одна из них, на самом деле настолько сложна, как кажется! Т.е. что на самом деле нет ни одного возможного способа получить ответ с помощью компьютера. Стивен Кук и Леонид Левин сформулировали проблему Р (т.е. легко найти) vs NP (т.е. легко проверить) независимо друг от друга в 1971 г.
(Конец цитаты)

Так что если кто-то таки найдет доказательство равенства этих классов, смело сможет расселять студентов по общежитиям)))
А на самом деле, всё-таки, надо полагать, кроме огромного минуса в виде полного кризиса в области защиты данных, человечество получит и грандиозный плюс! Решать быстро задачи такого класса сложности — оооо, этим надо гордиться! Только вот что-то расправляться с этой проблемой никто не торопится...

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

---

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

[Amicus Plato]

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

Задача выполнимости булевых формул (еще она называется SAT (satisfiability) (по-русски: ВЫП — выполнимость)) так и формулируется: можно ли присвоить всем переменным, встречающимся в формуле, значения ЛОЖЬ и ИСТИНА так, чтобы формула стала истинной.

И здесь огромную лепту внес Стивен Кук.
Согласно теореме Кука, доказанной им в 1971-м году, задача SAT NP-полна.
Вообще, в этом знаменательном 1971-м году Стивен Кук написал статью, в которой-то и был впервые введен термин «NP-полная задача», и задача SAT была первой задачей, для которой доказывалось свойство NP-полноты.

В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT.
Впоследствии NP-полнота была доказана и для множества других задач.
Но для доказательства NP-полноты нужны ведь какие-то методы! Как вообще взять задачу, и доказать, что к ней сводится любая другая задача из класса NP? На первый взгляд кажется, что это вещь невыполнимая, по крайней мере, чрезвычайно трудоемкая.
Но на самом деле тут тяжелее всего пришлось Куку! Потому что он доказал NP-полноту впервые! Как раз ему-то и пришлось перебирать все задачи класса NP по одной.
Всем последователям было уже гораздо проще!
Ведь для доказательства NP-полноты некоторой задачи достаточно показать, что к ней за полиномиальное время сводится сама задача SAT! Ха! А если она свелась (а она ведь NP-полна), то, стало быть, наша задача тоже NP-полна! Всё просто! (Хотя, конечно, и в таком виде это ой как непросто!)

Но теперь зато понятно, почему задача SAT стоит особняком.

Вообще же к NP-полным задачам относятся:

Задача о наименьшем числе перестановок в пятнашках
Задача коммивояжёра
Задача раскраски графа
Задача о вершинном покрытии
Задача о покрытии множества
Задача о клике

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

Попробую еще раз ее "сформулировать неформально" (простите за оксюморон):

Вернемся к решению задач с подсказками. "Подсказкой" у нас может быть оракул или свидетель. О свидетелях мы уже говорили много. Но приведу еще самый простой пример. Предположим, вы оказались в большом скоплении людей. Скажем, в театре. И вы договорились встретиться "где-то здесь" с другом. Людей много. Вам нужно "оглядеть" каждого, чтобы найти своего друга. Однако же, если кто-то покажет вам пальцем, и скажет: "да вот же он!", — вы узнаете его мгновенно!
Если обобщить такие примеры и сформулировать "общий принцип", мы получим, что решение какой-либо задачи всегда(?) часто занимает больше времени, чем проверка правильности решения.
Стивен Кук сформулировал проблему следующим образом: "может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки?".
Эта проблема является одной из нерешенных проблем логики и информатики.
Ее решение в корне бы изменило основы криптографии (в том случае, если бы равенство классов Р и NP удалось доказать) — вся безопасность информации полетела бы в тартарары. Но об этом в следующий раз.
(При подготовке использовался материал вот отсюда: rc.nsu.ru/text/news/Physics/093.html
Кто хочет получить миллион, посмотрите! Там для вас есть кое-то еще)))

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

---

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

Ответ:

Ответ:
0. — нет.
1. — да. Истинное.
2. — да. Ложное.
3. — да. Ложное.
4. — нет.
5. — нет. (почему?)
6. — да. Истинное.

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

С высказываниями разобрались. Их может быть бесконечно много, но их логические значения могут быть равны всего двум константам: "истина" или "ложь". Поэтому сами высказывания нас больше интересовать не будут — нам всё равно, что в них утверждается. Для нас важно только принимаемое ими значение. Истину мы будем записывать как "1", ложь — как "0".
Сами высказывания мы будем обозначать большими буквами: А, В, С, и т.д.
Кроме таких вот "всказывательных переменных" в булевой формуле используются логические связки.
Я расскажу только о трех из них, потому что без этих трех нам никак не обойтись (на самом деле, можно обойтись и двумя, но это уже получится извращение).

1. Логическое сложение, или дизъюнкция. Обозначается: ∨. Соответствует союзу "или".
Если:
F = А ∨ В, то F истинно, когда истинна хотя бы одна из двух переменных: А или В. F — ложно, тогда и только тогда, когда А и В ложны одновременно.
Переберем все возможные варианты значений переменных А и В:
А=1 В=1 ⇒ 1 ∨ 1 = 1
А=1 В=0 ⇒ 1 ∨ 0 = 1
А=0 В=1 ⇒ 0 ∨ 1 = 1
А=0 В=0 ⇒ 0 ∨ 0 = 0
Видно, что очень похоже на обычное сложение (просто как бы больше единицы у нас нет числа, поэтому 1+1=1)))

2. Логическое умножение или конъюнкция. Обозначается: ∧. Соответствует союзу "и".
Если:
F = А ∧ В, то F истинно, тогда и только тогда, когда истинны обе переменные: А и В. F — ложно, когда хотя бы одна из двух переменных А или В ложна.
Для конъюнкции выполняется:
А=1 В=1 ⇒ 1 ∧ 1 = 1
А=1 В=0 ⇒ 1 ∧ 0 = 0
А=0 В=1 ⇒ 0 ∧ 1 = 0
А=0 В=0 ⇒ 0 ∧ 0 = 0
А вот это самое что ни на есть умножение! Без всяких оговорок.

3. Логическое отрицание. Если операции дизъюнкции и конъюнкции бинарны (т.е. для них требуется две переменных), то для операции отрицания нужна всего одна — она унарна.
Не-А пишется как А с чертой вверху или еще как ¬ А.
Для отрицания выполняются следующие соотношения:
А=1 ⇒ ¬ А=0
А=0 ⇒ ¬ А=1

Кроме этих трех есть еще разные логические связки. Самая распространенная: импликация: "→".
Формула "А → В" читается (не совсем точно, но всё же): "если А, то В".
Еще есть эквиваленция, исключающее или, штрих Шеффера, стрелка Пирса, но на них мы сейчас останавливаться не будем.

Так вот, высказывательные переменные, соединенные логическими связками, и образуют формулы.
В свою очередь, сами формулы можно тоже объединять с помощью связок в более сложные формулы. Чтобы правильно определить порядок действий, конечно, нам еще понадобятся скобки.
Всё это вкупе мы и назовем булевой формулой.
Почему же именно выполнимость булевых формул так важна для нас, я уже напишу в следующий раз. Так что финальная запись про Р=(?)NP опять откладывается.

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

---

Класс NP

[Amicus Plato]

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

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

2. Задача, известная под названием Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) данного размера.
Кликой (clique) в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики — число вершин, содержащихся в ней.
На рисунке красным выделена клика размера четыре.


Есть разные варианты формулировки задачи о клике.
Первый, "облегченный" вариант ее таков: существует ли в заданном графе G клика размера k?
"Настоящая" же задача о клике формулируется следующим образом: в заданном графе G найти клику максимального размера.
Свидетелем здесь являются номера вершин, образующих клику.
На рисунке это номера 2, 3, 6, 7. (Клика размера 4 и будет здесь максимальной)
А вот, например, вершины 2, 3, 6 или 3, 6, 7 — тоже образуют клики размера 3, но они уже не удовлетворяют критерию максимальности.


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

вершины 8, 4, 5, 6, 9 образуют Гамильтонов цикл. И он здесь далеко не один.
Свидетель — последовательность вершин, образующих гамильтонов цикл.

4. Задача о коммивояжёре — о, это очень распространенная задача оптимизации! До сих пор на эту тему пишутся и защищаются диссертации. Потому что каждый раз бедному коммивояжеру нужно находить всё новые и новые пути: критериев оптимальности очень много.
Звучит эта задача следующим образом: у нас есть коммивояжер, то есть мы сами и есть тот коммивояжер, которому надо посетить указанный список городов. Нам нужно отыскать самый выгодный маршрут, проходящий через указанные города хотя бы по одному разу. (А если мы нечисты на руку, и не хотим потом встречаться со своими покупателями, то ровно по одному разу — улавливаете требование гамильтонова цикла?)
В условие задачи входят различные критерии выгодности маршрута: как короче, как дешевле, как быстрее по времени, и т.д. и т.п.
Свидетель здесь — просто решение задачи.

5. Существование целочисленного решения системы линейных неравенств.
Свидетель — тоже решение.

Почему я так подробно всё это описываю?
Определение класса NP было бы неполным, если бы я не упомянула вот о каком аспекте. Логически он вытекает из того, что уже было сказано, но всё-таки лучше рассказать о нём в явном виде.
Пусть у нас есть задача из класса NP. Возьмем любую из перечисленных. Например, задачу о гамильтоновом цикле. Если у нас есть свидетель, то остается только проверить, действительно ли указанные вершины можно обойти по разу и вернуться в начальную. Это задача, которую можно решить быстро, то есть задача класса Р. Если проверка дала положительный результат, то есть мы не обманули нашу машину Тьюринга, дав ей "хорошего" свидетеля, она должна выдать ответ "ДА". Если же мы дали неверный совет, неверно нашли свидетеля, машина должна сказать нам "НЕТ". Давайте посмотрим на картинку с гамильтоновым циклом еще раз.

Предположим, я говорю машине: "Свидетель — вершины: 1, 0, 4, 5". Машина отвечает: "НЕТ". Вроде бы, здесь всё понятно, непонятно только, зачем я так подробно об этом пишу. А вот зачем!
Гамильтонов цикл-то на самом деле здесь ЕСТЬ! И даже не один! Так что машина, отвечая "НЕТ" на самом деле отвечает не на вопрос о существовании или несуществовании гамильтонова цикла, а об истинности или ложности нашей подсказки. (Но сама-то машина об этом не знает)
То есть, с точки зрения вопроса о существовании цикла машина ошиблась.
Так вот, такие "ошибки" допустимы.
Зато ошибки в другую сторону недопустимы ни при каких обстоятельствах. Если мы дали машине правильного свидетеля, она ни при каких обстоятельствах не может сказать, что он не подходит!

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

Итак, подытожить это можно следующим образом.
Задача входит в класс NP, если существует машина Тьюринга, которая по представленному нами свидетелю сможет за полиномиальное время либо дать положительный ответ и не ошибиться, либо дать отрицательный ответ с возможной ошибкой; причем, каждый данный нами "правильный" свидетель должен "соответствовать" этой машине Тьюринга, то есть она должна его "понимать".

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

---

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

[Amicus Plato]

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

Давайте посмотрим.
Думаю, в детстве многие сталкивались с таким примером (на самом деле когда-то поразившим мое воображение!). Когда объясняют, что же такое большие числа, часто, чтобы помочь оценить масштаб, делают это таким способом.
Представьте что вы начинаете вслух считать до миллиарда. Миллиард — это всего лишь единичка и девять нулей. Число не такое уж и большое. 1 000 000 000.
И вот, представьте, что считаете вы размеренным голосом, и каждую секунду произносите очередное число. (Пока числа маленькие, вы можете не спешить: ...двадцать один, двадцать два, двадцать три.... вполне можно успеть. Дальше, однако, будет сложнее. Чтобы произнести число четыреста восемьдесят девять миллионов восемьсот пятьдесят четыре тысячи триста девяносто один, секунды уже маловато, но мы всё равно попробуем!)
Так вот, элементарные подсчеты показывают, что если мы будем считать без сна и отдыха, без перерыва на еду, и даже не позволим себе глотка воды, у нас на это уйдет 31,7097919837645865043125317097921 год.
То есть где-то 31 год и восемь с половиной месяцев, если я нигде не ошиблась.
Некоторые из нас еще даже не дожили до этого возраста)))
То есть, начни они считать во младенчестве, сейчас бы еще находились в пути... )))

Но машины, конечно же, считают быстрее!
Вот, возьмем не очень быстрый процессор с тактовой частотой 1 ГГц. Гигагерц — это как раз 10⁹ герц, или тактов в секунду. Значит, наш компьютер может просчитать "в уме" до миллиарда за секунду (если мы будем считать, что один такт соответствует "произнесению" одного числа). Да, так гораздо быстрее, чем если бы мы делали это сами!
Но вот вернемся к задаче, которую я приводила раньше:
Дано число: 15256677987889881453. Проверить, является оно простым или составным.
Число для удобства напишу так:
15 256 677 987 889 881 453
Оно содержит 20 знаков. (И это на самом деле не очень большое число!)
Корень из этого числа будет состоять из десяти знаков (то есть как раз соответствовать нескольким миллиардам).
Чтобы проверить, делится ли наше число нацело, нужно эти самые несколько миллиардов раз проделать ряд однотипных действий. Хорошо, если наше число не настолько велико, что умещается в одной переменной.
Тогда достаточно такого алгоритма:

1. N=3905979774 (это приблизительное значение квадратного корня)
2. для i=1 до N (начинаем цикл)
3. остаток=остаток_от_деления(15 256 677 987 889 881 453 на i) (функция "остаток_от_деления" выдает остаток от деления проверяемого числа на каждое очередное значение счетчика i)
4. если остаток=0 то (если остаток = 0, то число поделилось нацело, и мы сразу получили ответ)
5. печать: i (печатаем делитель)
6. выход (выходим из программы)
7. всё если
8. конец цикла (здесь происходит увеличение счетчика на единицу и возврат на начало)

Итого в худшем случае (если мы не найдем делителя раньше), нам нужно повторить 4 действия — строчки с номерами 2, 3, 4, 8 (и даже чуть больше, потому что надо еще анализировать, где нам встретится строчка конца условия 7: "всё если"). То есть, давайте считать это за 5 действий. Итак 5 действий надо выполнить без малого четыре миллиарда раз. Итого 20 миллиардов. По одному миллиарду в секунду.
20 секунд для такой простенькой задачи — это очень немало!

Вот, к примеру, каковы реалии. И, думаю, это на сегодняшний день уже устаревшие данные.
В статье "Простота и совершенство" я уже об этом упоминала.
Наибольшим известным простым числом по состоянию на сентябрь 2006 года является 2^32582657 − 1. Оно содержит 9 808 358 десятичных цифр!

Не десять цифр, как то число, которое мы рассматривали сейчас, а без малого десять миллионов цифр! Представляете сколько считал бы наш алгоритм?
В миллион раз дольше!
20*1 000 000 =20 000 000 секунд = 5555, (5) часов = 231,(481) суток!!!
Теперь понятно, почему хочется сделать это чуть быстрее)))

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

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

---

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

[Amicus Plato]

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

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

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

О! Вот тут вопрос для самопроверки))))

Вопрос. Определить класс сложности этого алгоритма (алгоритма "перебора делителей") в терминах О-нотации, или вообще в каких бы то ни было терминах.

Вообще на самом деле, поскольку большие простые числа очень активно используются в криптографии, то важно иметь быстрые алгоритмы, которые помогают определить, простое число перед нами, или составное. Такие алгоритмы называются тестами простоты.
Те, кто ответит на вопрос для самопроверки, убедятся, что сложность самого простого и естественного, с первого взгляда, алгоритма значительно превосходит полиномиальную. Однако, человеческая мысль не стоит на месте. Разработано достаточно много полиномиальных тестов простоты. Однако сами эти алгоритмы (простите за каламбур) не так уж просты!
Причем, то, что задача проверки на простоту полиномиально разрешима в общем виде, было доказано только в 2002 году! Однако предложенный детерминированный алгоритм оказался достаточно сложным, и это, конечно, сильно затрудняет его применение!

И вообще, здесь, конечно, палка о двух концах: чем больше мы пытаемся упростить алгоритм в терминах алгоритмической сложности, тем больше мы запутываем сам алгоритм, и, как следствие, код программы, пока он не станет совершенно нечитабельным!
***
Я читала где-то (очень давно, правда, в те времена, когда машины были не столь быстры, и время работы даже маленькой программы существенно зависело от ее структуры), что для ускорения хода работы программы желательно все циклы насколько это возможно писать линейно!
О чем я? Вот, представьте, у нас есть массив, состоящий из десяти элементов. Нам нужно каждому элементу присвоить его порядковый номер, умноженный на два.
Массив — это такая структура данных: как длинный ящик с перегородками, делящими его на ячейки. Название у него одно, но в каждой ячейке лежит своё значение.
Вот, например, пустой массив с именем А:

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

Обычно это делается в цикле, который на псевдоязыке выглядит следующим образом:

для i от 1 до 10 с шагом 1
А_i = i*2
конец цикла

i — это вспомогательная переменная, называемая счетчиком цикла. Она пробегает все значения от 1 до 10 с шагом 1 (то есть цикл обернется вокруг себя 10 раз), и в каждый элемент массива положится его значение.

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

Вот такой алгоритм считал бы (почти) вдвое быстрее:

для i от 1 до 9 с шагом 2
А_i = i*2
А_i+1 = (i+1)*2
конец цикла

Что мы здесь сделали?
Мы за каждый проход цикла стали вычислять не одно значение массива, а сразу два. Тем самым цикл укоротился вдвое (хотя тело его удлинилось, но это как раз менее существенно).

А вот такой алгоритм будет работать еще быстрее:

для i от 1 до 6 с шагом 5
А_i = i*2
А_i+1 = (i+1)*2
А_i+2 = (i+2)*2
А_i+3 = (i+3)*2
А_i+4 = (i+4)*2
конец цикла

Здесь у нас получится всего два прохода цикла вместо 10. (Нетрудно проверить, что результат у всех трех алгоритмов будет один и тот же!)
И наконец, самым быстрым будет вот такой вот линейный алгоритм:
А₁ = 2
А₂ = 4
А₃ = 6
А₄ = 8
А₅ = 10
А₆ = 12
А₇ = 14
А₈ = 16
А₉ = 18
А₁₀ = 20

Не шучу!
Это хорошо, когда известно заранее, сколько нам надо сделать шагов! Если же нет (мы не знаем длины массива до определенного времени), то без цикла всё же не обойтись, но предлагается делать его "большими шагами", как показано для случаев с шагом 2 и 5.

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

Кроме того, возвращаясь к проверке больших чисел на простоту. Тут нас поджидает еще одна, на этот раз техническая проблема. В компьютере могут храниться разные типы данных. Каждый числовой тип, даже самый "вместительный" может хранить числа до какого-то максимального значения. А дальше — стоп! Переполнение! Numeric Overflow! И поэтому помимо всех вышеизложенных проблем, стоит еще проблема представления больших чисел и их обработки!
Можете себе представить? Мы вынуждены хранить число не целиком, а кусочками, и тем не менее нам нужно узнать, поделится оно на что-нибудь или нет! О-о-о! Здесь всё совсем непросто!

Однако, люди всё-таки имеют большой опыт каким-то образом выходить из трудных ситуаций.
Так, например, для некоторых классов чисел придумали специализированные эффективные тесты простоты.
Хотя, конечно, далеко не для всех...

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

---

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

[Amicus Plato]

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

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

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

Напомню принцип действия машины Тьюринга.
Вдоль бесконечной ленты движется каретка, которая называется устройством управления (УУ). Каретка умеет читать символы на ленте и записывать туда другие символы алфавита. УУ может находиться в одном из нескольких состояний, которые описаны заранее. Его (УУ) действие для каждой конкретной ячейки определяются двумя факторами: 1) символом, записанным в эту ячейку, и 2) текущим состоянием.
Так вот, если это самое действие определено однозначно, то такая машина будет детерминированной.
А если нет? Тогда, предположим, что УУ в некотором состоянии перешло в ячейку, в которой оказался некоторый символ. УУ сверяется со своими правилами перехода и видит, что когда оно в данном состоянии встретило данный символ, оно может совершить не четко определенную одну вещь, а сразу несколько разных. И ничто не возбраняет ему (УУ) совершить любую из этих вещей.
Проще говоря, машина оказывается на развилке нескольких дорог, и никто кроме нее не может решить, куда же ей податься. И никто не знает заранее, что же она выберет. Именно поэтому она и называется недетерминированной. Ее поведение становится неопределенным.

И здесь есть несколько интересных моментов, на которые я хотела бы обратить внимание.

1. Как такая машина Тьюринга выбирает, куда ей двинуться на каждой развилке? Ответ на этот вопрос: да никак! Случайным образом. Самое печальное, когда путей у нас много, а правильный из них только один. Но и это печальное не так печально. Сейчас мы с этим разберемся.

2. Про "много путей, из которых правильный только один", я сказала не зря! Для классов задач, решаемых такими машинами (а чуть позже окажется, что недетерминированная машина Тьюринга в частности как раз и решает класс NP) из всех путей по всем развилкам результативным часто оказывается только один.
Если представить это наглядно, то можно вообразить себе детерминированную машину Тьюринга (ДМТ) в виде единственной дорожки, представляющей собой «путь вычислений». Недетерминированная машина Тьюринга (НМТ) в таком случае представляет собой сад расходящихся тропок. Говорят, что она имеет «дерево вычислений». В общем случае у этой машины число путей, по которым может развиваться вычисление, растет экспоненциально.
Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает.
То есть другими словами, если хотя бы один из всех возможных путей приведет к решению задачи, то такая машина пригодна для ее решения. Если же ни один из путей нас не устраивает, то, соответственно, и вся машина нам не подходит.
Говорят еще, что "ДА" и "НЕТ" здесь несимметричны. Думаю, теперь понятно, почему: для "ДА" нам достаточно одного подходящего пути из любого (пусть и очень большого) числа неподходящих; для "НЕТ" нужно, чтобы все пути не подходили одновременно.

3. На вид недетерминированная машина Тьюринга (НМТ) гораздо мощнее, чем детерминированная (ДМТ). И гораздо сложнее. Однако, оказывается, что они эквивалентны! Любую НМТ можно представить в виде ДМТ! Легче лёгкого! Доходя до каждой развилки мы начинаем клонировать машины. То есть недетерминированная машина делится на копии, каждая из которых развивает свою веточку дерева. И так на каждой новой развилке.
Википедия сравнивает этот процесс в многозадачной операционной системой. И в чем-то она права. Разве что вряд ли в операционной системе количество задач растет по экспоненте.

Конечно же, представление НМТ с помощью ДМТ требует значительно больше времени. Насколько больше — неизвестно. И если бы было известно, то задача, которую я и взялась рассматривать: «P = (?) NP» была бы решена!

Класс NP
Вот определение из Википедии:
Класс алгоритмов, выполняемых за полиномиальное время на недетерминированных машинах Тьюринга, называется классом NP.
Но определение это неполно! Всё так, да не совсем так.
Формальное определение дам в следующий раз. А сейчас просто расскажу, что это такое за класс.

Представьте, что у нас есть недетерминированная машина Тьюринга. Все веточки дерева дают нам 0, то есть не ведут никуда, и только одна дает нам 1, то есть, правильный ответ, — за полиномиальное время. "Полиномиальное время", как мы помним, — это количество шагов, не большее Const*N^C, где N — длина входных данных.
Если мы начнем перебирать все цепочки подряд и ходить по всем веточкам, вытягивая их в один линейный и очень длинный путь, мы увязнем, и всё это будет очень долго.
Но представьте, что у нас есть подсказка! На развилке она нам говорит, куда пойти, чтобы сразу добраться до результата!
Мы идем на полиномиальную веточку, которая ведет к ответу, и решаем задачу быстро!
Иногда эту подсказку, как правило, в виде готового решения, которое нужно только проверить, называют свидетелем. Иногда же рассматривают машину Тьюринга с оракулом. То есть, достигая развилки, машина Тьюринга обращается к оракулу — внешнему устройству, выдающему правильные ответы на некоторый круг вопросов.
На практике, однако, поиск свидетелей и построение оракулов — задача не из легких.

Вот, очень простой пример, который можно встретить в литературе в той или иной интерпретации.
Задача. Дано число: 15256677987889881453. Проверить, является оно простым или составным. (Честно скажу, я не проверяла, делится ли сумма цифр на три, не проверяла и другие, менее очевидные признаки делимости, но будем считать, что они не выполняются).
Если мы начнем действовать перебором и подбирать на роль кандидатов в делители все простые числа до квадратного корня из этого числа, мы потратим уйму времени!
Если же мы возьмем себе в помощь "свидетеля": число 123567898761 (которое я специально умножила на другое число, чтобы получить данное), то достаточно просто разделить одно на другое и убедиться, что мы поделили нацело. То есть, со свидетелем эта задача из разряда "нечего делать"; без свидетеля она становится весьма сложной.

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

На словах это выглядит не слишком убедительно, но давайте посмотрим на картинки.
Вот недетерминированная машина Тьюринга, вернее, конечно, не она сама — она выглядит совсем не так. Это дерево возможных решений. (Конечно, вовсе не обязательно, чтобы из каждого набора символ+состояние выходило три альтернативы. Ветвиться дерево может как угодно. Это просто для "быстроты рисования": исходя из удобства Ctrl+С Ctrl+V))). Я нарисовала только первые семь ходов, да и то опустила около половины веток. Представляете, что мы получим для реальной задачи?

Зато если у нас есть путеводная звезда в виде свидетеля или путеводная нить в виде оракула, то пройти по этому лабиринту нам не составит труда. Например, вот так:


Если красная веточка заканчивается за полиномиальное время, а все другие — не обязательно (они могут даже вообще никогда не заканчиваться), то перед нами графическая иллюстрация НМТ для задачи класса NP.

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

---

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

[Amicus Plato]

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

(Я вот всё думала, почему вроде бы такие простые вещи как переход от Р к NP и NP-полноте всегда так запутанно написаны.... А теперь столкнулась с этим сама. Нужно предварительно рассказать о нескольких вещах, а одно знание цепляется за другое, и очень сложно выбрать то, с чего надо начинать. Я попробую начать с детерминированной машины Тьюринга).

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

Что же такое Детерминированная Машина Тьюринга?
Определение я дам очень неформальное.
Представьте себе, что у нас есть бесконечная в обе стороны лента, разделенная на ячейки, в которых записаны какие-то символы — буквы из какого-то алфавита. Под алфавитом мы просто понимаем некоторый базисный набор знаков. Помимо символов алфавита, обязательно есть еще особый пустой символ, который заполняет все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Вдоль ленты движется каретка, которая называется управляющим устройством. Каретка может читать символы на ленте и записывать туда другие символы алфавита.
Каретка (управляющее устройство (УУ)) может находиться в одном из нескольких состояний, которые описаны заранее. Ее действие для каждой конкретной ячейки определяются символом, записанным в эту ячейку, и текущим состоянием.
Управляющее устройство работает согласно правилам перехода.
За каждый такт оно считывает текущий символ с ленты и в зависимости от своего состояния и значения прочитанного символа выполняет определенное правило перехода: 1) записывает в эту клетку новый символ, 2) переходит в новое состояние и 3) перемещается на одну клетку влево или вправо.
Не обязательно выполнение всех трех пунктов сразу. Содержимое ячейки или состояние УУ вполне могут остаться без изменения.
Описанный "аппарат" и есть Машина Тьюринга.
Машина Тьюринга обязательно должна иметь состояние, переход в которое будет означать конец работы, остановку алгоритма. Таких состояний может быть несколько. (*)

Есть такой знаменитый тезис Чёрча-Тьюринга, который говорит о том, что любой мыслимый алгоритм можно реализовать на машине Тьюринга.
На самом деле это очень важный результат. Представьте себе, что какой бы сложный алгоритм мы ни придумали, для абсолютно любого мы можем построить Машину Тьюринга.
"Мы можем" — это конечно для красного словца ))) На самом деле это не слишком просто. Но Чёрч и Тьюринг говорят, что теоретически это возможно.

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

Что это значит?
Детерминированность — одно из основных свойств алгоритмов. Говоря просто, это значит, что при выполнении каждого очередного шага, мы точно будем знать, какой шаг мы сделаем следующим. У нас нет распутья. Нам не надо кидать монетку, чтобы узнать, куда нужно пойти. Всё однозначно.
С недетерминированнной Машиной Тьюринга дело обстоит иначе. И она нам понадобится в очень скором времени.

Но сейчас речь идет только о детерминированной. И с ее помощью мы дадим еще одно определение класса Р.

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

Если машина Тьюринга M, реализует некоторый алгоритм, и ее максимальное время работы не превосходит N^C для некоторого числа C и достаточно больших N, то говорят, что она принадлежит классу P, или полиномиальна по времени.

(*) Кстати, насчет терминальных символов, которые отвечают за остановку Машины Тьюринга. Еще одним свойством алгоритмов является результативность. Результативность как раз и означает, что любой алгоритм рано или поздно должен остановиться (и выдать результат, но это уже побочный продукт факта остановки). Если машина Тьюринга для какой-то задачи остановиться не может, значит, эта проблема алгоритмически неразрешима! И такие проблемы существуют!
(Но о них нужно писать отдельно, если у кого-то возникнет желание про них почитать))) На самом деле, это очень интересно!)

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

---

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

[Amicus Plato]

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

Если, конечно, щелкнут на кат

В общем случае можно считать, что для двух функций f(x) и g(x) выполняется соотношение:
g(x)=O(f(x)) (читается "жэ от икс есть О-большое от эф от икс") в некоторой точке х₀, если существует такая положительная константа С, что для любых значений х из окрестности этой точки
|g(x)| ≤ С•|f(x)|
иными словами, отношение |g(x)|/|f(x)| ограничено сверху некоторой константой.
Или, что еще проще, хотя и несколько фривольно, это величины одного порядка.

Для о-малого (хоть мы его больше касаться и не будем) соотношение иное:
g(x)=о(f(x)) в некоторой точке х₀, если отношение абсолютных величин этих функций стремится к нулю в окрестности этой точки.
|g(x)|/|f(x)| → 0
Например, в окрестности нуля верно, что х²=o(x), и вообще хⁿ=o(x^n-1)
Здесь на самом деле нас может ждать множество подвохов, потому что о-малое при таком определении вещь очень неоднозначная.
Например, в окрестности нуля будет выполняться много много равенств:
х²=o(x)
х³=o(x)
х⁴=o(x)
...
и т.д.
Поэтому мы и не будем трогать о-малые.
Нам и О-больших хватит за глаза.

Что же такое О-нотация применительно к сложности алгоритмов?

Если говорят, например, что сложность данного класса алгоритмов O(N), это означает, что существует некоторая константа C, единая для всех алгоритмов этого класса, такая, что количество элементарных шагов, сделанных алгоритмом, не будет превосходить C•N операций, где N - объем начальных данных задачи.

Для алгоритмов класса O(N) для каждого входного элемента выполняется только одно действие. (На самом деле, может быть, конечно, не одно, а два, три, и т.д., но главное не больше С•N, где С — константа).
Для программистов (для меня по крайней мере) неформально это легко представить следующим образом: у нас может быть сколько угодно (но конечное число) одномерных циклов, пробегающих весь набор входных данных, идущих друг за другом (идущих циклов, а не данных), но вложенных циклов быть не может.
Плюс, естественно, может быть некоторый набор шагов до, после и между циклами.
Для алгоритмов класса O(N²) каждый входной элемент обрабатывается (или проходится) С•N² раз. Это означает (для наглядности, только как одну из возможностей) наличие вложенных (двойных) циклов.
Для алгоритмов класса O(N³) — С•N³. Здесь уже цикл-в-цикле-в-цикле.
И т.д.
Все эти классы являются подклассами общего класса: O(N^x), где х - любое (целое) число.
Это класс алгоритмов, работающих с полиномиальной скоростью.
Он и называется Р-классом.

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

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

---

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

[Amicus Plato]

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

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

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

Таким образом, задача поиска фамилии в телефонном справочнике (в самом худшем случае) повторится столько раз, сколько мы можем делить число страниц пополам.
Т.е. если справочник у нас имеет n страниц, то в худшем случае пополам придется делить
2•2•...•2=2^m(>=n) раз, где m — такая степень двойки, что 2^m — минимальное число такого вида, превосходящее n, или равное ему.
Люди, близкие к математике или информатике фыркнут и скажут, что уже давно надо было перейти к логарифмам. Сейчас и перейду.
То самое искомое число m как раз и будет логарифмом по основанию 2 от длины входной информации n.
Т.е. log₂ n = m
Таким образом, чтобы пролистать справочник из тысячи страниц, нам нужно раскрыть его:
log₂ 1000 ≈ 10 раз.
(Потому что 2¹⁰=1024)
Если, предположим, наш справочник вдвое толще, и составляет более 2000 страниц, то нам придется его открыть всего лишь на один раз больше!
Если страниц у нас будет сто тысяч, понадобится всего лишь около 17 открываний!

Аналогично устроены некоторые численные методы! Самый похожий и один из самых распространенных (по крайней мере, в учебных целях): деление отрезка пополам.
Этот алгоритм один в один повторяет наши действия со справочником. Представьте себе, что нам нужно приблизительно найти корень алгебраического уравнения. То есть такое значение х, при котором f(x)=0, где f(x) и есть наше уравнение (какое-нибудь суперсложное, нерешаемое аналитически) Нам достаточно найти два значения х1 и х2, для которых f(x) имеет разные знаки. Предположим, f(x1)>0, а f(x2)<0. Ясно, что между ними лежит по крайней мере одно (хотя может быть и три и пять, и любое нечетное число) искомое нами значение х0, при котором и достигается равенство: f(x0)=0. Правильно? Нельзя же из плюса перескочить в минус, не побывав в нуле, при условии, конечно, что функция, описываемая уравнением, непрерывна на рассматриваемом отрезке!
И вот, это самое х0 мы и будем искать как фамилию в справочнике.
Поделим отрезок пополам и найдем знак нашего уравнения в серединной точке отрезка х3. Если f(x3)>0 (т.е. знак совпал со знаком f(x1)), то на половине отрезка [x1, x3] перехода через ноль не произошло. Таким образом, область поиска сократилась вдвое: остался отрезок [x3, x2], который на следующем шаге тоже поделится пополам. И так далее. Таким образом, за логарифмическое время можно найти корень уравнения с любой наперед заданной точностью.
Есть еще немного отличающийся (или много (или вообще не отличающийся) — пишу по памяти, а она имеет тенденцию привирать) метод пристрелки. Называется он так потому, что имитирует пристрелку орудия к цели. Мы не знаем корня, и в первый раз стреляем очень приблизительно. Но как только мы обстреляли корень с двух сторон: f(x)<0 — недолет, f(x)>0 — перелет, то каждый раз мы вводим в прицел коррективы и стреляем точнее, пока не попадем в сколь угодно малую окрестность корня.

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

Приведу еще один пример из Википедии.
Предположим, нам надо почистить ковер.
Время на его чистку пропорционально площади ковра. Если ковер увеличится вдвое, — время чистки тоже должно возрасти ровно вдвое. Увеличим мы ковер в сто тысяч раз — время чистки возрастет ровно во столько же! В сто тысяч раз.
Тогда как метод половинного деления при увеличении входных данных в сто тысяч раз дает всего лишь семнадцатикратное увеличение времени их обработки.
Таким образом, это задачи из разных классов сложности.
Любой полный перебор (например, нахождение минимального или максимального элемента произвольной последовательности чисел, или вычисление их суммы (произведения)), дает нам сложность ковра)))

(Это было только введение. Продолжение следует)

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

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

---

Сказка о прекрасной РЕЗОЛЬВЕНТЕ, о трёх добрых молодцах и о злом волшебнике Иван –дер

[lyambda]

Как 3 вектора один детерминант в ноль обратили

Как идут две параллели,
да не сходятся,
Как стоят два дуба,
да не наклонятся.

Из старинной песни

В некотором пространстве, в некотором подпространстве жило-было упорядоченное семейство ортонормированных векторов i1 , i2 , i3 . Не было у них ни собственных чисел, ни собственных значений, жили они в чём мать-матрица родила. Из периода в период от - π до π гнули братья спины на базис богатого комплекса, эксплуататора-тунеядца, прожившего всю свою жизнь по принципу наименьшего действия. Не взлюбил их комплекс и начал вытворять над ними свои комплексные штучки: то одну координату отобьёт, то другую. Собрались братья, стали совет держать: « Не будет нам житья от этого комплекса. Нет от него никаких ограничений». И решили они обойти все пространства и подпространства, все оболочки многообразия и найти правую систему координат.
Вышли они в чисто потенциальное поле и пошли шагом куда глаза глядят.
π идут, 2π идут, 3π идут…Глядь, перед ними голубым разрезом на
ровной комплексной плоскости струйное течение.
- Ане половить ли нам рыбки?, молвил i1.
- Отчего же нет?, сказали братья.
Закинули братья свою видавшую виды ортогональную сеть, и видят: в сети сигма-рыба бьётся, человеческим голосом просит:
- Не губите меня добрые молодцы! Я вам ещё пригожусь!
Послушались её братья, выпустили. А сами дальше пошли. И полпериода не прошли, видят: лежит на траектории малый параметр, худющий-худющий, от голода плачет. Пожалели его братья, накормили ядрами всвёртку. Стал тут параметр расти на глазах. А как достиг экстремальной величины, сказал:
- Я вам ещё пригожусь, добры молодцы!
Да пропал, будто и не было его вовсе.
А братья дальше пошли.
Долго ли шли, коротко ли, больше нуля, меньше бесконечности, смотрят: стоит избушка на курьих ножках.
- Избушка-избушка, стань к нам плюсом, а к лесу минусом!
Попереминалась избушка с ноги на ногу, да и повернулась. Вошли братья и возрадовались: на столе еда стоит. Сытно поели и спрашивают:
- Есть тут кто?
Слышат, из-под печки слабый голос доносится. Видят, лежит не то вектор, не то скаляр, цепными дробями закованный.
- Привет вам, благородные векторы! Я добрый волшебник Ади-Аб-Ата – Коши- Мак- Лорен. Вот уже полжизни сижу здесь. Заковала меня злая набла-яга ∇.
Не успел он договорить, зашумело, засвистело вокруг.
- Бежим!, - вскричал Ади- Аб -Ата.
Расковали его братья и пустились все вместе наутёк. Оглянулись назад: летит по небу прекрасная Δ. Ударилась о плоскость, встала на голову и обратилась в страшную набла-ягу ∇.
- Чую ,векторным духом пахнет!
Ан векторов и след простыл. Вывел их Ади-Аб- Ата на геодезическую линию и сказал на прощание:
- Спасибо, молодцы! Я вам ещё пригожусь.
И пропал-аннулировался.
Пошли братья дальше и увидели Divgrad , то бишь дивный город. И выросли перед ними стены высокие, подобно тому, как растёт tg x при x → π/2.
И расходилось от города сияние лучистое, как расходится гармонический ряд. Но охватывало тот город печаль великая, как охватывает все решения дифференциального уравнения
y'' = - k² y
y = C1 sin kx + C2 cos kx, где C1 и C2 произвольные константы.
Проголодались братья, зашли в харчевню и разговорились они с хозяйкой – дородной Тильдой. И рассказала она им о великом несчастье, постигшем их город и его δ-окрестности.
- Долго мы жили счастливо. Но созвал как-то раз наш король Великий Тензор дважды Ковариантный и четырежды Контравариантный бал по случаю совершеннолетия своей дочери красавицы Резольвенты. Приехал граф Х в самосопряжённой коляске. Приехал князь Синус со своей синусоидой. И другие именитые гости. Дивные звуки n-мерной музыки, исполнявшиеся хором высших гармоник в сопровождении ударных поляр, услаждали слух. Весь зал кружился в танце pa-dt. Вдруг погас свет, замелькали на стенах фигуры Лиссажу… А когда починили пробки, смотрят – нет красавицы Резольвенты… Как показало следствие Центральной Предельной Теоремы, её похитил злой волшебник Иван дер Монд. Он проник во дворец, нарушив условие Даламбера-Эйлера и совершив подстановку в двойной ряд стражи… С тех пор, - вздохнула Тильда, - стала наша область открытой для всех несчастий.
Крепко запала в душу братьев эта страшная история, решили они освободить красавицу Резольвенту. Как услышала об этом добрая Тильда, стало ей жалко молодых неколлинеарных векторов:
- Вы же совсем единичные, - вскричала она, - но братья дружно в один голос ответили:
- Нас мало, но мы образуем базис!
Отправились братья в торговые ряды Тейлора, снарядились, погадали на годографе, и тронулись в путь. Скоро сказка сказывается, но не скоро доказывается.
Тяжёлые граничные условия не позволили векторам проникнуть в соседнюю область, где господствовало классовое неравенство Коши-Буняковского. И тут перед ними, как из-под земли, вырос Ади-Абу-Ата- Коши- Мак- Лорен. И сказал он братьям:
- Я знаю, что вы задумали. Трудное это дело. Смерть Иван Дер Монда в его детерминанте. Детерминант в додекаэдре, додекаэдр в икосаэдре, а икосаэдр привязан тремя узлами к корням полинома Лежандра: один узел простой, другой двойной, а третий логарифмический. Полином тот растёт в изолированной точке за 3х9 земель в пространстве великого хана Банаха. И охраняет его чудовище Декремент с трансцендентным числом ног. Тот детерминант надо достать и приравнять к нулю. Тут и будет конец Иван Дер Монду. Идите по следам матриц и придёте прямо к изолированной точке.
Пошли братья векторы по следам матриц и через три периода оказались перед выпуклым непустым множеством, заполненным несжимаемой вязкой жидкостью. Стоят и гадают, как им быть не знают.
Вдруг вынырнула Σ-рыба, хвостом бьёт, приговаривает:
- Вот я вам и пригодилась.
Перевезла она векторов на другую сторону. Поблагодарили они и пошли дальше. Глядь – перед ними разрыв 2-го рода. А тут откуда ни возьмись – малый параметр! Ударился оземь, разложился по своим степеням, и перешли по нему братья на другую сторону. Дошли братья до точки ветвления. Смотрят, столб стоит, а на том столбе написано:
- Направо пойдёшь – в бесконечность уйдёшь, налево пойдёшь – координат не соберёшь, прямо пойдёшь – транспонируешься!
Подумали братья- подумали, да и пошли в разные стороны.
Рассмотрим вектор i1 . Шёл-шёл i1 , видит: перед ним, как из-под земли вырастают неисчислимые орты хана Банаха, все, кроме, может быть, одного, одеты в Жорданову форму, подстрижены под скобку Пуассона.
- Ах, опечалился вектор, нет со мной моих любимых братьев. Да ничего, i1 в поле воин!
Храбро бросился на врагов. Тут подоспели i2 , i3 . И дрогнули супостаты. Пробили братья себе дорогу. Пошли они дальше.
Вдруг слышат страшный рёв. Заметались в воздухе вихри, зарезонировало и появилось перед ними чудовище Декремент. Не растерялись братья, набросили на него сеть, запутался Декремент своими трансцендентными ногами в узлах и умер в страшных мучениях. Тихо стало в чисто потенциальном поле. Только старый полином Лежандра шумел своими ветвями. Подошли братья к изолированной точке, разрыли корни и достали икосаэдр. Вынули они додекаэдр, извлекли детерминант и приравняли его к нулю. Раздался тут грохот великий, потемнело небо, исчезло солнышко, полетели листья Мёбиуса. Огненные разрывы молний раскололи небесную сферу Римана. Умер Иван Дер Монд. И очутилась перед братьями прекрасная Резольвента, живая и невредимая, что и требовалось доказать.
Замечание 1. Сказка написана для случая n =3. Но, пользуясь методом математической индукции, читатель без труда обобщит её на случай любого n.
Замечание 2. Сказка доступна студентам, аспирантам и преподавателям мехмата. Знание математической логики и алгебраической топологии не обязательно.

@темы: ))), Поп-математика

---

[Amicus Plato]

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

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

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

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

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

---

[Amicus Plato]

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

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

---

[Amicus Plato]

Задачка (легкая, но забавная)))

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

---

Комбинаторно-геометрическая задачка

[Trotil]

Допустим, у нас есть много правильных N-угольников. Вася берет первый из них, раскрашивает. Остальные многоугольники он прикладывает друг другу так, чтобы
1) Они сошлись сторонами
2) Они не пересекались

Задача: минимальным кол-вом многоугольников вымостить путь от первого многоугольника к первому.

На рисунке представлены размещение для N=3,4,5,6,7,8.



Задача: указать формулу для определения этого числа, если формулы не существует - тогда указать асимптотику или эффективный алгоритм перебора )

Решения задачи не знаю (

---

теория всего

[krystofer]

Может кто-нибуть популярно обяснить?

arxiv.org/PS_cache/arxiv/pdf/0711/0711.0770v1.p...

с математической точки зрения, разумеется =)

@темы: теория групп

---

[Amicus Plato]

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

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