Коллектив Авторов - Цифровой журнал «Компьютерра» № 214

Ещё в тридцатых годах прошлого века венгерский математик Пал Эрдёш предположил, что для любого натурального числа C в бесконечной последовательности (x_n), состоящей только из чисел «1» и «-1», существует субпоследовательность x_d, x_{2d}, ... , x_{kd} с некоторыми положительными целыми числами k и d. Такими, что |x_d + x_{2d} + ... + x_{kd}|> C.

Гипотеза получила известность под названием задачи несоответствия Эрдёша. Её доказательство стало одной из основных проблем в комбинаторной теории чисел. 

Она связана с поиском закономерностей в бесконечной последовательности. На практике сложности возникают из-за объёма проверочных вычислений при использовании наборов конечной длины. 

Алексей Лисица и Борис Конев использовали Plingeling — модификацию программы Lingeling, допускающую распределённые вычисления. Её авторы получили награды в семи номинациях на конкурсе SAT 2013. Он проводился среди разработчиков программ класса SAT-solvers, проверяющих условие выполнимости булевых формул по заданным параметрам и применяющихся для проверки математических гипотез.

В своей работе Лисица и Конев применяли обычный настольный компьютер с процессором Core i5-2500K (работающим на частоте 3,3 ГГц) и 16 ГБ ОЗУ. Итерационно увеличивая длину набора чисел, они установили, что для расхождения 2 можно получить последовательность длиной 1 160. При С=2 не существует последовательности длиной 1 161, удовлетворяющей условиям задачи. Иными словами, было получено частичное решение задачи несоответствия Эрдёша.

Объём сгенерированного программой файла, содержащего доказательство, составил примерно 13 ГБ. Именно это и стало поводом для сенсации. Читая о подобных достижениях, люди часто видят дилемму — принимать такие доказательства на веру или отказаться от них в силу невозможности проверить вручную.   Это проблема не науки, а нашего восприятия. Тринадцать гигабайт — действительно много для частичного доказательства, однако не удивительно само по себе. SAT-solvers и эвристические алгоритмы способны быстро выдавать решение из множества допустимых, но редко оно оказывается самым оптимальным.

Логи размером в пару гигабайт тоже никто не проверяет вручную. Для проверки утверждения, что ни одна последовательность чисел «1» и «-1» длиной 1 161 не имеет расхождения 2, использовалась программа Glucose. Она применяет совершенно другой алгоритм, работа которого требует в 27 раз больше времени при тех же машинных ресурсах.

В целом алгоритмы интеллектуального анализа и поиска закономерностей усложняются с каждым годом. Задача их дальнейшего развития уже породила отдельное направление — технологии «больших данных». Именно они позволяют сегодня выполнять сложнейшее моделирование в режиме реального времени, прогнозировать различные ситуации, предсказывать выход оборудования из строя, создавать персонализированные сервисы и оптимизировать бизнес-процессы. 

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

К примеру, в проектах распределённых вычислений системы BOINC пакет заданий считается выполненным только в том случае, когда решение получено минимум от трёх разных компьютеров — и хотя бы два результата полностью совпадают.

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

Согласно работам Вернадского, Неймана и Винджа, само появление программ класса SAT-solvers можно рассматривать как малый предвестник технологической сингулярности — момента истории, в который технический прогресс из-за своей скорости становится недоступным пониманию человека. 

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

К оглавлению

Опубликовано 25 февраля 2014

В эти выходные в пляжном мексиканском городишке Мазатлан был арестован Хоакин Лэора Гусман, более известный миру под криминальной кличкой Коротышка (El Chapo). Наркобарон и один из самых богатых людей на планете, Гусман любил приватность, нуждался в ней и отстаивал её всеми способами, включая убийства. Но даже он не сумел защитить себя от электронного наблюдения — и теперь его история может служить уроком для всех, кто задумывается о возможности уйти из под надзора Большого Брата.

Получивший своё прозвище за небольшой рост ещё в юности, Коротышка хоть и не затмил Пабло Эскобара, но в общем шёл той же дорожкой и добился многого. Он родился в 1957 году в бедной многодетной семье в каком-то захолустье, и, говоря по правде, нам неизвестна даже точная дата его рождения (кто-то называет 1954-й). С учёбой не сложилось. Школу (если она там вообще была: скорее говоря, приезжающий в деревню учитель) наш герой бросил в первые же годы. Папаша выращивал мак, так что профессиональная стезя у пацана рисовалась обычная: сначала помогал отцу, потом обзавёлся собственной плантацией, а совершеннолетним подался в город и быстро пошёл вверх по «служебной» лестнице: возил наркотики сам, затем контролировал поставки из Колумбии, проявил себя серьёзным, дотошным, скорым на расправу менеджером среднего звена.

Короче говоря, к 90-м у него и друзей уже был свой наркокартель «Синалоа» (по названию родного штата) и образ этакого Робин Гуда в глазах сограждан. Подкуп чиновников, убийства неугодных и нарковойны с десятками тысяч смертей — всё это обычное дело для современной Мексики. Но до Коротышки страна была лишь второстепенным игроком, обочиной для наркотрафика, а благодаря ему превратилась в международного лидера. Инновационные методы транспортировки (кокаин в банановой кожуре, кофейных банках, тоннели под государственной границей и пр.), перенаправление наркопотоков из Колумбии в Штаты через Мексику, богатое местное производство (от кокаина и героина до синтетических препаратов) с прицелом опять таки на США — всё это ставят в «заслугу» Эль Чапо. И не удивительно, что северный сосед Мексики мечтал поймать его едва ли не больше её самой: никто другой не ввёз в Штаты такого количества «дури»!

Пик карьеры Коротышки пришёлся на последние годы. Его картель стал самым сильным в Мексике, его личное состояние оценивается в миллиард долларов, власть распространяется не только на мексиканские, но и на некоторые американские банды, а Соединённые Штаты официально нарекли его самым разыскиваемым наркоторговцем мира и даже (Чикаго) «врагом общества номер один», чего, говорят, не случалось со времён Аль Капоне.

С правосудием ему довелось познакомиться в 1993-м: арест, обвинения в убийстве и перевозке наркотиков, 20 лет тюрьмы. Но и в самой строгой мексиканской тюрьме он жил на широкую ногу: держал бизнес контрабанды, крутил роман с сидевшей здесь же бывшей высокопоставленной сотрудницей полиции, а в 2001-м спланировал и реализовал побег в своём фирменном стиле. Он подкупил всех, кого мог, вплоть до начальника заведения, «заказал» несогласных и выехал на свободу в тележке с грязным бельём. И с этого момента стал человеком-легендой: он везде и нигде конкретно, всё знает, всех держит в кулаке.

Однако в последние пару лет полиция стала подбираться к нему всё ближе, схватила нескольких крупных фигур, а в середине февраля он и сам избежал ареста только благодаря крепкой двери на одном из своих поместий в Кулиакане (столица Синалоа) и системе секретных тоннелей, соединённых с канализационным лабиринтом под городом. И всё таки 22-го числа его взяли тёпленьким, в постели с подругой. Даже без стрельбы. Так... дали пару раз прикладом, чтобы не хватался за «калаш».

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