В США названы лучшие восстановители измельчённых документов

Команда-победитель обошла почти 9000 соперничающих групп. Перед вами один из восстановленных документов. Несмотря на неполную реконструкцию, «детективы» сумели понять, о чём идёт речь в этой бумаге (иллюстрация Shredder Challenge/DARPA).

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

Стартовавший в конце октября конкурс по воссозданию измельчённых документов Shredder Challenge завершён.

Первое место и призовые $50 тысяч завоевала команда программистов из Сан-Франциско под названием «Все ваши обрезки принадлежат США» (All Your Shreds Are Belong To U.S.). Она быстрее и точнее соперников собрала все пять пазлов, то есть документов, разрезанных в общей сумме на 10 тысяч тонких полосок. И ещё она первой ответила на связанные с загадками вопросы относительно городов и людей, упоминаемых в текстах.

Исходный и реконструированный победителем текст номер 1. Он был разбит всего на 224 кусочка (дальше степень измельчения пазлов шла по нарастающей), потому данную бумагу команда собрала уже 6 ноября (иллюстрация Shredder Challenge/DARPA).

Ключом к успешному решению задания оказалось сочетание чисто машинного подхода (сортировка и сравнение фрагментов) с творческой работой людей-сборщиков, сообщает устроившее конкурс агентство DARPA. Программа-победитель подбирала отсканированные кусочки бумаг друг к другу лишь вчерне и предъявляла пары для проверки членам команды.

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

К примеру, в первом тексте упоминается название фильма, который снял режиссёр Анатоль Литвак в 1937 году. В энциклопедии можно узнать, что в данном году Литвак выпустил две ленты – «Товарищ» и «Женщина, которую я люблю». Товарищ по-английски – comrade, и это как раз то слово, с которого начинается первый документ.

Загадка номер пять была самой сложной во всей серии. Здесь было разрезано и перемешано сразу три листка бумаги (на фото показан только третий — до измельчения и после восстановления).

Один из трёх листов был исполосован в направлении, перпендикулярном двум другим, а общее число кусочков составило более шести тысяч! Вдобавок небольшая часть текста представляла собой морзянку в виде нагромождения повторяющихся слов dit и dah. Над этой головоломкой команда победителей колдовала до 29 ноября (иллюстрация Shredder Challenge/DARPA).

Собрав третий документ (на фото под заголовком), участники должны были назвать судьям задуманный в загадке город — Сьенфуэгос.

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

Исходный документ номер 3 и скрытые в нём подсказки. Данная бумага была разрезана на 1115 кусочков (иллюстрация Shredder Challenge/DARPA).

При выборе победителя учитывалось не только первенство в сборке пазлов. За те или иные правильные ответы на вопросы по содержанию документов судьи начисляли дополнительные баллы. Группа All Your Shreds Are Belong To U.S. оказалась лучшей не только в деле программирования, но и просто эрудиции, сообразительности.

Задача номер два. Умеренное число обрывков – всего 373 — позволило победителям восстановить этот документ быстро и практически на 100% (иллюстрация Shredder Challenge/DARPA).

Своё последнее решение из серии заданий команда из Сан-Франциско прислала всего через 33 дня после анонса конкурса. На составление алгоритма машинного зрения и сортировки обрывков, а также собственно на сборку бумаг умельцы потратили 600 человеко-часов.

Между тем перед стартом соревнования некоторые эксперты DARPA считали предложенные загадки практически нерешаемыми, во всяком случае в столь сжатые сроки.

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

Четвёртый пазл (порезанный на 2340 кусочков) поддался победителям лишь частично. Но и восстановленных фрагментов хватило для того, чтобы узнать «имена учёных», работавщих над «секретным проектом» (иллюстрация Shredder Challenge/DARPA).



Новое приложение для телефона предупреждает пешехода о машинах

28 ноября 2011

Учёные получили энергию от тел жуков-киборгов

25 ноября 2011

Американцы удачно испытали управляемое гиперзвуковое оружие

21 ноября 2011

В продажу поступил пуленепробиваемый планшет

8 ноября 2011

Обнародована новая модель военного андроида

1 ноября 2011
  • Михаил Шевцов  5 декабря, 13:46
    Браво!
    ОтветитьНравится
  • Ольга Добрая  5 декабря, 13:58
    нда...шредеры в топку. Надо заводить буржуйку в каждом офисе.
    ОтветитьНравится
  • Александр Иерархов  5 декабря, 17:19
    Ну тык не помогут буржуйки.... Информация она и в Чёрной Дыре не исчезает. И вааще «Рукописи не горят»....
    ОтветитьНравится
  • Дмитрий Степанов  5 декабря, 13:59
    а где наши? они принимали участие?
    ОтветитьНравится
  • Андрей Данилейко  5 декабря, 14:08
    Конкурс был только для граждан США
    ОтветитьНравится
  • Александр Привалов  7 декабря, 06:12
    Андрей Данилейко: Конкурс был только для граждан США

    Не совсем — представлять команду в США должен был американец или постоянный резидент, но на состав команды никаких ограничений не было. Я чего-то сомневаюсь, что команда shurikcom (занявшая 59-ое место), состояла из англоговорящих товарищей.

    ОтветитьНравится
  • Владимир Романович  5 декабря, 14:03
    Следующий этап — наноботы, собирающие страницу из пепла.
    ОтветитьНравится
  • Владимир Романович  5 декабря, 14:05
    Пора переходить на безбумажные технологии, хранение с хорошим шифрованием, и уничтожением ключей вместо уничтожения самой информации.
    ОтветитьНравится
  • Игорь Черток  5 декабря, 14:05
    Муфельная печка и шаровая мельница — и пусть восстанавливают хоть до посинения.
    ОтветитьНравится
  • Дмитрий Журавлёв  5 декабря, 14:37
    А ещё эти остатки можно замешать в бетон и сбросить чушку в Марианскую впадину, только у DARPA изначально стояла другая задача.
    ОтветитьНравится
  • Арсений Щедрин  5 декабря, 15:43
    Гг))) «Аll your brains belong to us» — Plants Vs Zombies
    ОтветитьНравится
  • Алексей Назьмов  5 декабря, 16:18
    ))
    ОтветитьНравится
  • Александр Амелькин  6 декабря, 01:35
    Вообще-то это был намёк (как и приведенная цитата из PvZ) на классическую цитату из игры Zero Wing для Sega Mega Drive от 1991 года: «All your base are belong to us»

    Подробнее тут:
    en.wikipedia.org/wiki/All_your_base_are_belong_to_us

    ОтветитьНравится
  • Сергей Асташкин  5 декабря, 16:54
    -- А если там посадить сотню китайцев — то все секреты США станут прозрачными как одежды Евы ..
    ОтветитьНравится
  •   5 декабря, 17:06
    Эх, тоже хотел тогда поучавствовать, тем более, что есть опыт работы с картинками. Но потом увидел, что подать может только житель США, да и заметил объявление, когда уже с десяток человек подали. Уплыли $50,000 :(
    ОтветитьНравится
  • Shamil Dzhanbolatov  5 декабря, 17:34
    Если так переживаете, может вам переселиться в США? Если женитесь на американке автоматом получите гражданство и 600$ в неделю по безработице, если не найдете работу.
    ОтветитьНравится
  •   5 декабря, 19:11
    В Англии, где я живу, тоже большое пособие, семье с двумя детьми бесплатно дом дают, но я на пособие никогда не жил и не собираюсь.

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

    ОтветитьНравится
  • Shamil Dzhanbolatov  5 декабря, 17:32
    Знаете ли вы что: Информация не материальна
    ОтветитьНравится
  •   5 декабря, 19:15
    Это как посмотреть. Вот иные люди считают, что даже бог не материален. Они ошибаются. Иисус Христос, например, существует в нейронах миллиардов людей. Если бы его не было, нейронные сети в мозгах этих миллиардов имели бы иную структуру, а она материальна — следовательно, Иисус материален и еще как.

    (надеюсь, никто не сочтет мои речи богохульством, наоборот это хвала богу).

    ОтветитьНравится
  • Игорь Черток  5 декабря, 19:34
    Если бы его не было, нейронные сети в мозгах этих миллиардов имели бы иную структуру

    «Если бы он был, нейронные сети в мозгах этих миллиардов имели бы иную структуру».

    Пофиксил.

    ОтветитьНравится
  • Shamil Dzhanbolatov  5 декабря, 20:42
    Хорошо, тогда чем отличается пустой жесткий магнитный диски компьютера винчестер, от заполненного информацией в материальном плане?
    ОтветитьНравится
  • Алексей Худяков  5 декабря, 21:04
    Степенью энтропии. Магнитное состояние поверхности винчестера без информации имеет более высокое значение порядка системы.
    ОтветитьНравится
  •   5 декабря, 21:35
    Как чем?
    Намагниченностью дорожек, а если это лазерный компакт диск, то расположением микроскопических дырочек.
    ОтветитьНравится
  • Shamil Dzhanbolatov  5 декабря, 21:36
    Энтропия не материя, а информация
    ОтветитьНравится
  • Александр Иерархов  5 декабря, 21:41
    Неужели? А не наоборот? А записанная поверхность имеет разную энтропию. Зависит от наблюдателя. Для того наблюдателя которому известен смысл структуры энтропия меньше чистого диска а для того которому не известен — больше....
    ОтветитьНравится
  • Shamil Dzhanbolatov  6 декабря, 02:29
    Вы считаете, что «Зависит от наблюдателя. Для того наблюдателя которому известен смысл структуры энтропия меньше чистого диска а для того которому не известен — больше....» — материя?
    ОтветитьНравится
  • Сергей Шляхтов  5 декабря, 18:16
    И где такую программу можно скачать, чтоб документы восстанавливала? Она идет в комплекте со смекалистыми? Или конкурс был на технологию?
    ОтветитьНравится
  • Илья Цыгвинцев  5 декабря, 19:00
    А кто вам мешает её написать самостоятельно?
    ОтветитьНравится
  • Сергей Шляхтов  7 декабря, 18:43
    Зачем мне это?
    ОтветитьНравится
  • Алексей Мыцик  5 декабря, 19:00
    Интересно, что же (такое разрезанное) хотят восстановить амеры, у кого они этот мешок макулатуры сперли, да небось и у мертвого???
    ОтветитьНравится
  • Алексей Худяков  5 декабря, 21:06
    Это они определяли выкинуть ли госдепу шредеры и не закупить ли буржуйки.
    ОтветитьНравится
  • Алексей Номеров  5 декабря, 21:38
    ответ ниже
    ОтветитьНравится
  • Алексей Номеров  5 декабря, 21:38
    http://www.membrana.ru/particle/11457
    если что, я в курсе что там не амеры
    ОтветитьНравится
  • Алексей Номеров  5 декабря, 21:42
    Офигеть! Сколько же «нереальных» с точки зрения экспертов задач можно решить с помощью энтузиастов и кругленькой суммы...
    ОтветитьНравится
  • Татьяна Селянинова  6 декабря, 14:23
    Вопрос выигрыша в подборе команды. У меня одна знакомая бухгалтерша каждый день (!) начинает с того, что собирает пазл, благо в инете навалом ресурсов с ежедневной выкладкой новых картинок. Так она минут за десять складывает то, что мне за полчаса не собрать. Тренированный у нее глаз.
    Если собрать команду таких фанатов — вполне реально и тысячи кусочков перелопатить. А есть ведь и те, кто миллионные (и метровые) пазлы складывают.
    ОтветитьНравится
  • Александр Привалов  7 декабря, 06:21
    Кстати, я в своей компании долго занимался отбором соискателей и приёмом их на работу. И я скажу, что лучший показатель талантливого программиста — именно успешное участие в подобных командных конкурсах.

    Я имел возможность работать с отобранными мной людьми, и не всегда эта совместная работа была успешной.

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

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

    А вот самый удачный из всех моих «ставленников» — очень талантливый парень — в прошлом был лидером группы студентов, выигравшей университетский конкурс по робототехнике. По образованию он вообще Mechanical Engineer. Чего в программировании он не знал — то выучил. Мгновенно.

    Ему была поставлена задача — через полгода её сделал. Круто сделал. Кое-где немножко видно, что некотоые места он делал именно так не потому, что это оправдано, а просто ему так захотелось. Сверх-автоматизированы некоторые вещи, которые куда проще и быстрее было сделать вручную. Но это терпимо. Код хорошо откомментирован, очень легко читаем. Я не видел такого читаемого кода раньше. Хрен его знает, как он это делает. И всё это было сделано без единого подгоняла или «ценного указания» от начальства.

    Поставленная ему задача была такова, что да её решения многие наши архитекторы однозначно утверждали, что эта задача решения не имеет теоретически. «Вы пытаетесь создать искусственный интеллект» — убедительно предостерегали они. Мне остаётся только резюмировать, что, в таком случае, искусственный интеллект был создан в нашей компании в 2011-ом году. Очень, очень сложные и неочевидные решения должна была принимать эта программа, на основе совершенно непредсказуемых входных данных и без участия человека, вот и прозвали её «искусственный интеллект».

    ОтветитьНравится
  • Алекс Яковенко  7 декабря, 06:58
    и при чем здесь команда??
    ОтветитьНравится
  • Александр Привалов  7 декабря, 09:11
    Чтобы быть полезным, спорт должен быть обязательно командным, и ни в коем случае не индивидуальным.

    Есть, например, такой неисчерпаемый кладезь трудовых ресурсов, как линуксисты. Технических знаний у них — дофигища. Я охотно верю, что среди них можно и нужно находить ценные кадры. Но пока я из их среды ни одного толкового сотрудника не завербовал. Установка Линукса — исключительно индивидуальное занятие. Навыки пребывания в обществе у некоторых линуксистов полностью отсутствуют. Я видел людей, у которых любовь к Юниксу вырождается в достаточно извращённую форму: они делают вывод, что те инструменты, которые применяют они, и есть самые правильные, а все остальные сотрудники должны под них подстраиваться и использовать те же самые тулы. Люди вообще не понимают, как функционирует команда. Напротив — программист обязан быть гибким и применять те инструменты, которые наиболее подходят в данный момент, а не те, которые имеют наиболее отдалённое отношение к Windows.

    Умный математик, ставший весьма посредственным программистом — это просто притча во языцех. Совершенное стандартное явление. Одна из причин этого в том, что математика — индивидуальное занятие.

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

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

    Индивидуального программирования в мире больше не осталось (уже несколько десятитетий назад). Всё современное программирование — это работа в команде.

    IMHO.

    ОтветитьНравится
  • Алекс Яковенко  7 декабря, 22:45
    Возможно в крафтовом програмировании действительно все так плохо. Я просто ученый и в науке индиаидуальность важнее команды в разы. Кроме того Ваш пример из первого письма был явно в пользу индивидульного программера.
    В связи с эти возникает вопрос. Если смешать науку и программинг (скажем ту же разработку ИИ) вероятно получиться комбинация факторов успеха — из науки индивидуальность, из програминга — комманда. Т.е. возможно Ваш опыт несколько ограничен сферой деятельности Вашей компании и не выводы не такие уж глобально-категоричные.
    ОтветитьНравится
  • Алексей Ромчак  7 декабря, 23:10
    Когда мне задают вопрос (из стандартной пиндосской анкеты) «умете ли Вы работать в команде» я просто не понимаю чего от меня хотят – требуют. Я конечно не программист, но это применительно ко многим отраслям. На мой взгляд, единственным человеком в команде обязанным «уметь работать в команде» это координатор проекта, это его прямая обязанность и ликвидная способность.
    ОтветитьНравится
  • Shamil Dzhanbolatov  8 декабря, 00:12
    Я рад за вас Привалов. Но все же это не разум. Если так, пусть здесь прокомментирует, посмотрим
    ОтветитьНравится
  • Shamil Dzhanbolatov  8 декабря, 00:16
    А если сочетать и то и другое? Я не играю в российские игры вообще, потому что все это ужасно. А вы сами?
    ОтветитьНравится
  • Shamil Dzhanbolatov  8 декабря, 00:18
    Уметь работать в команде — умение становиться под углом в 90 градусов.
    ОтветитьНравится
  • Shamil Dzhanbolatov  8 декабря, 00:18
    Вы про мой эффект толпы прочитайте в моей статье про магнитолеты
    ОтветитьНравится
  • Александр Иерархов  8 декабря, 00:20
    Шамиль Джанболатов 8 декабря, 00:18
    Уметь работать в команде — умение становиться под углом в 90 градусов.

    Мдя... Где это научился а...

    ОтветитьНравится
  • Александр Иерархов  8 декабря, 00:22
    Оно конечно бесполезно видимо, но напомню что «в команде» разрабатываются старые, уже известные идеи. Новое, удел одиночек.... Даже если их потом припишут команде... :)))
    ОтветитьНравится
  • Александр Привалов  8 декабря, 09:20
    Алексей Ромчак: Когда мне задают вопрос (из стандартной пиндосской анкеты) «умете ли Вы работать в команде» я просто не понимаю чего от меня хотят

    К сожалению, я уже встречал подобное мнение. Я даже думал нечто похожее в детстве.

    Человек, одолеваемый подобными мыслями, скорее всего просто не понимает сложности поставленной задачи. С точно таким же успехом человек, никогда в жизни не слышавший о скрипке, на вопрос, умеет ли он на ней играть, с возмущением ответит: «я просто не понимаю чего вы от меня хотите — водить длинной деревяшкой по полой деревяшке, как такое можно уметь или не уметь?»

    Ответить на ваш вопрос я бы рад, но вы и сами знаете ответ. Правильный ответ — «да». Вы, вероятно, спрашиваете, чего тут имеется в виду. И вы опять же хорошо это знаете сами. Ну вы же работаете с другими людьми? Так или иначе, на любой должности, это делает каждый. Вот и опишите, как вы с ними работаете, как эффективно вы с ними сотрудничаете, коллаборационируете, так сказать.

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

    Если бы мне на интервью задали подобный вопрос, я ответил бы примерно так:

    Да, последние N лет в этой индустрии научили меня работать в команде. Я предпочитаю работу в дружном коллективе индивидуальной работе. Я читал учебники по этому вопросу, такие как «6 Habits of Highly Effective Teams», «Effective Business Communications», «Dealing with People You Can’t Stand» и так далее.

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

    ОтветитьНравится
  • Алексей Ромчак  8 декабря, 09:40
    «Если бы мне на интервью задали подобный вопрос, я ответил бы примерно так:…»
    — А я обычно ставлю в этой графе прочерк, и меня всё равно берут ;) Может от того, что им нужен работник, а поддержание команды они доверяют умелому администратору.
    ОтветитьНравится
  • Александр Морозов.  8 декабря, 09:45
    >>...можно выразить в три предложения...можно выразить в три предложения

    За пять лет ведения бизнеса я научился этим правилам ;)
    Сейчас передо мной стоит задача расширения штата, и подбор персонала нынче — не простая штука. Неадекватов просто завались, но нет желания их учить (а это все равно придется делать)

    ОтветитьНравится
  • Shamil Dzhanbolatov  8 декабря, 22:16
    Самое лучшее наверно — гибрид, сочетание командной работы, мозгового штурма, с творческими поисками на скорости света.
    ОтветитьНравится
  • Вадим Леонов  7 декабря, 07:27
    Это да, удивительно полезное действо.
    Измельчённые документы по инструкции надо сжигать.
    ОтветитьНравится