Pull to refresh
192
13
Александр @jasiejames

Инженер (210406)

Send message

Как шутят математики. Шифры Фейнмана

Reading time 8 min
Views 12K

Ранее я писал о взломе первого и второго шифра, придуманных математиком Полом Оламом ради розыгрыша своего друга Ричарда Фейнмана. Если описать контекст в нескольких словах, то эти шифры были одной из математических шуток, которые были в широком ходу у коллектива учёных, работавших на «продуктовой» базе в Лос‑Аламосе над созданием той самой «ядрёной» бомбы. Также я упоминал о трёх других шифрах, авторство которых до сих пор достоверно неизвестно и вряд ли выяснится. Их называют шифрами Фейнмана, и до середины прошлого года два из них оставались нераскрытыми, о чём я также писал ранее. Так вот, в мае прошлого года это всё‑таки свершилось и они были вскрыты. В этой статье я расскажу как.

Само собой разумеется, что работал с этими шифрами не я, но и мне здорово пришлось поломать голову, как это всё рассказать. Пришлось пройти весь путь и кое‑что допилить, чтобы результат стал доступен как можно большему количеству людей на той части земной поверхности, которую со времён господина Стрельбицкого было принято называть «одной шестой». Автор взлома — Дэйв Вьера (David Vierra).

Читать далее
Total votes 16: ↑16 and ↓0 +16
Comments 11

Как шутят математики. Решение второго шифра Олама

Level of difficulty Medium
Reading time 9 min
Views 4.6K

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

Оба шифра оставались неразгаданными 75 лет. Скорее всего, виной тому оказался тот факт, что они находились в архивных хранилищах Калифорнийского технологического института, а не из-за их чрезвычайной сложности. Однако не стоит забывать, что в момент своего появления они не были вскрыты Ричардом Фейнманом, а после и его аспирантом Крисом Коулом. Разумеется, с тех пор криптоанализ существенно продвинулся и обзавёлся новыми возможностями автоматизации и вычислительными мощностями.

Читать далее
Total votes 22: ↑22 and ↓0 +22
Comments 1

Как шутят математики. Решение первого шифра Олама

Level of difficulty Medium
Reading time 12 min
Views 14K

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

Итак, Лос-Аламос объединил одной целью многих видных учёных того времени. Одним из них был замечательный учёный Ричард Фейнман. Разумеется, основным предметом его интереса всегда была физика, но помимо потрясающих познаний в ней, профессор Фейнман отличался и другими талантами. Из его автобиографии (всем, кто ещё не читал, настоятельно рекомендую) известен факт, что профессор особенно гордился своими реактивными скилами решения головоломок и математических задач.

Читать далее
Total votes 26: ↑26 and ↓0 +26
Comments 16

Треугольник Паскаля и скрытые в нём «паск(х)алки» (часть 1)

Level of difficulty Medium
Reading time 10 min
Views 4.4K

Известный американский популяризатор науки Мартин Гарднер в своей книге «Математические новеллы» посвятил целую главу «одной из самых изящных и известных схем в истории математики», которую чаще всего принято называть треугольником Паскаля. Эта математическая конструкция, конечно, была известна и до того, как «французский Архимед» написал свой «Трактат об арифметическом треугольнике». Однако на момент издания труда Блеза Паскаля именно в нём содержалась наиболее полная информация об этом математическом явлении. Правда, итальянцы предпочитают называть этот фундаментальный артефакт треугольником Тартальи, описавшем таблицу за сто лет до Паскаля, а в Германии его называют треугольником Штифеля. В Иране и, пожалуй, в большинстве арабских стран его принято называть треугольником Хайяма, а китайцы отстаивают приоритет своего соотечественника и называют его треугольником Ян Хуэя.

Читать далее
Total votes 17: ↑15 and ↓2 +13
Comments 8

Горные лыжи, нобелевский лауреат по литературе и прослушка

Level of difficulty Easy
Reading time 10 min
Views 2.4K

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

Каждый, кто хоть раз бывал на горе, помнит, как легко спуститься и насколько трудно подняться. А если нужно повторить это несколько раз? Обычно в более или менее цивилизованных местах мы обращаемся с такой целью к подъёмнику. Где-то бугельный, где-то кресельный, но это по ситуации. Любой подъёмник — сложное техническое сооружение, требующее для своего создания и обслуживания людей с совершенно разной специализацией и квалификацией. А как же было раньше?

Как это было..
Total votes 11: ↑9 and ↓2 +7
Comments 21

От аль-Кинди до Керкгоффса

Level of difficulty Easy
Reading time 7 min
Views 1K

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

С одной стороны, эта задача может показаться тривиальной, поскольку в криптологии за сотни лет накопилось множество самых разнообразных шифров, но такое впечатление обманчиво. Хотя книг и статей по истории криптографии очень много, большая их часть так или иначе описывает одни и те же шифры, и это печально. Десятки похожих описаний шифров Цезаря, Виженера, Плейфера (на самом деле Уитстона), Отендорфа и других постепенно переходят к диску Альберти и цилиндру Джефферсона, от которых уже рукой подать до Энигмы и её потомков. В любом случае чем тривиальней кажется материал, тем интересней сделать из него то, что не потеряется в ленте и вызовет какой-то положительный фидбэк. Ну что же, трудности созданы, осталось их героически преодолеть.

Читать далее
Total votes 13: ↑13 and ↓0 +13
Comments 0

Приключения Люцифера во «Дворце головоломок»

Level of difficulty Easy
Reading time 12 min
Views 1.6K

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

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

До 1970-х,по меткому выражению Дэвида Кана, криптография практически полностью находилась на службе бога войны Марса. Гражданское применение криптографии являлось уделом редких энтузиастов. Появление общих вычислений в начале 1970-х годов ясно показало, что гражданским правительственным учреждениям, банкам и другим организациям тоже необходимо защищать свои данные, однако большая часть полезной информации о шифровании находилась под колпаком силовых структур. В США на рынке существовало некоторое количество проприетарных систем, однако за пределами АНБ вряд ли кто-то знал, что такое надёжный алгоритм шифрования. При этом в других странах ситуация была ещё хуже.

ЧБД
Total votes 7: ↑7 and ↓0 +7
Comments 0

Старые песни о главном и pig butchering

Level of difficulty Easy
Reading time 9 min
Views 1.1K

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

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

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

Через несколько лет после прочтения «героев компьютерной революции» мне попалось «искусство обмана» Митника и Саймона тоже в достаточно отвратном переводе. Это потом, уже где-то в 2005, был издан более или менее приличный русскоязычный вариант. Сейчас не буду приводить каких-то цитат из прочитанного, но помню, что необычно было читать про поиск в мусоре каких-то «бумажек» с записанными паролями к учёткам или про наивные телефонные разводы. И всё это так и осталось бы забавными историями давно минувших дней, если бы идентичные методы не работали и сегодня. Опять же, в который раз история учит только тому, что ничему не учит, и всё свежепридуманное — это хорошо забытое «старое».

Читать далее
Total votes 9: ↑8 and ↓1 +7
Comments 0

Теннис родом из Лос-Аламоса

Reading time 8 min
Views 2.1K

История парадоксальна и её выверты порой удивительны. Что общего у Манхэттенского проекта и компьютерных игр? 65 лет назад была продемонстрирована первая многопользовательская видеоигра с графическим интерфейсом — Tennis for Two. Это была достаточно простая для современного избалованного пользователя игра в теннис, похожая на классическую аркаду 1970-х годов, только появилась на десяток лет раньше и являлась побочным продуктом национальной лаборатории Брукхейвена. Автором игры был физик Уильям Хигинботэм.

Много лет спустя в интервью Фрэнку Ловесу он вспоминал, что в то время, работая над экспозицией, он осознал, насколько статичными было большинство научных экспонатов. Будучи главой контрольно-измерительного отдела лаборатории, он намеревался изменить это недоразумение.

Немногим ранее
Total votes 9: ↑9 and ↓0 +9
Comments 10

Mafiaboy – история одного DDoSa

Level of difficulty Easy
Reading time 9 min
Views 1.4K

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

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

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

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

Читать далее
Total votes 3: ↑3 and ↓0 +3
Comments 0

Morte Alla Francia, Italia Anela…

Level of difficulty Medium
Reading time 12 min
Views 1.1K

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

В сегодняшней статье речь пойдёт об игре, о которой я, к своему стыду, узнал всего лет пятнадцать назад, хотя она появилась ещё в 1986 году и стала достаточно популярной уже в середине 90-х. Сегодня найти человека, который ничего не знал бы об этой игре, практически невозможно. Я говорю о «Мафии».

«Мафия» — клубная командная психологическая пошаговая ролевая игра, созданная в 1986 году студентом МГУ Дмитрием Давыдовым, базируется на культурно-исторической теории советского психолога Л. С. Выготского. В Википедии достаточно подробно описана сама игра и её варианты, но существуют и классические правила.

В общем, различные варианты игры похожи, и все участники разделены на две конкурирующие фракции: красная команда — «мирные жители», чёрная команда — «мафия». Цель игры состоит в том, чтобы уничтожить группу противника. Игра состоит из двух последовательных фаз (дневной и ночной) и определённого набора действий. Члены мафии обладают определёнными фичами (знают друг друга, убивают ночью), тогда как «мирных жителей» больше. Оказывается, что относительно небольшое количество членов «мафии», т. е. пропорциональное квадратному корню из общего числа игроков, даёт равные шансы на выигрыш для обеих групп. Кроме того, игра сильно зависит от чётности общего числа игроков.

Итак, давайте уже перейдём к конкретике.
Total votes 8: ↑8 and ↓0 +8
Comments 2

IoT и его криптонит

Level of difficulty Easy
Reading time 11 min
Views 1.9K

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

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

Многие устройства IoT также являются частью концепции домашней автоматизации и, соответственно, в той или иной мере обладают схожими преимуществами и недостатками. Пожалуй, главной «ахиллесовой пятой» обеих концепций являются вопросы обеспечения безопасности, и если ранее до массового распространения этих технологий на безопасность как большинству пользователей, так и производителей было плевать с высокой колокольни, то сегодня эта проблема носит достаточно острый характер. В 2021 году количество устройств IoT превысило 13,8 миллиарда, и ожидается, что к 2025 году их число как минимум удвоится. Такое количество разнородных подключённых устройств и объём данных, которыми они обмениваются, заставляют нервничать многих специалистов по безопасности. Этот вопрос становится ещё более существенным, когда понимаешь, что более 90% всего трафика между устройствами IoT не зашифровано.

В результате хорошо известные угрозы и атаки, такие как распределённый отказ в обслуживании (DDoS) и «человек посередине» (Man-in-the-Middle, MitM), достаточно легко и непринуждённо применяются для компрометации систем IoT. Хотя DDoS является самой популярной атакой на системы вообще, в сфере IoT MitM может её затмить. Если первая метафорически сравнима с ударом дубиной по голове, то вторая — это укол шпагой. Атаки MitM обычно более сложны, чем другие, и их трудно идентифицировать. Обычно они включают в себя широкий спектр мероприятий, в которых злоумышленник располагается в центре коммуникации, перехватывая контроль над каналами связи.

Дальше-больше..
Total votes 5: ↑5 and ↓0 +5
Comments 3

Головоломка ассасина

Level of difficulty Easy
Reading time 9 min
Views 15K

В 2014 году профессор математики Стэнфордского университета Марьям Мирзахани в одной из своих лекций упомянула интересную математическую головоломку, но не стала давать её решение. Спустя годы появились различные вариации задачи. Однако сначала речь пойдёт о первоисточнике.

Головоломка относится к классу так называемых «бильярдных задач», изучаемых в области динамических систем. Решение текущей задачи принадлежит профессору математики университета Джонса Хопкинса Эмили Рил.

Рассмотрим квадратную комнату в плоскости XY, и пусть A («ассасин») и T («цель») — две произвольные, но фиксированные точки внутри комнаты. Предположим, что комната схожа по физическим характеристикам с бильярдным столом, так что любой «выстрел» А рикошетит от стен, причём угол падения равен углу отражения. Можно ли заблокировать любой возможный «выстрел» А в Т, разместив конечное количество аналогичных по свойствам точек («телохранителей») в комнате?

Читать далее
Total votes 32: ↑32 and ↓0 +32
Comments 27

Вычислительные модели на языке родных осин

Level of difficulty Easy
Reading time 14 min
Views 1.5K

В последнее время я часто писал о вычислительной сложности, алгоритмах и моделях (например 1, 2, 3). Вычислительные модели лежат в основе вычислительной науки и не только её, и всё же немногие обладают чётким представлением о том, что такое вычислительная модель на самом деле. Это программное обеспечение? Или алгоритм? Как это связано с математическими моделями? Какие языки или обозначения подходят для описания вычислительной модели? Сделает ли ИИ вычислительные модели устаревшими? В процессе обсуждения с некоторыми товарищами сформулировалось достаточно подробное и, надеюсь, понятное описание, которое я и хотел бы представить в этой статье.

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

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

Читать далее
Total votes 9: ↑8 and ↓1 +7
Comments 0

Протокол обмена ключами Диффи-Хеллмана для «самых маленьких»

Level of difficulty Medium
Reading time 10 min
Views 4K

За последние десять лет масса технологий, имеющих хоть какое-либо отношение к информационным, претерпела массу изменений. Более того, многие сферы жизни, изначально не имеющие к IT никакого отношения, также преобразились до неузнаваемости и приобрели некий IT-шный бэкграунд. Немаловажную роль в этих процессах информатизации сыграла концепция Интернета вещей (IoT). С самого появления этой концепции было понятно, что она серьёзно повлияет на все сферы деятельности человека, экономические и социальные процессы, а спустя несколько лет после её появления технология оказалась на карандаше Национального разведывательного совета США и была занесена в список «подрывных инноваций».

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

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

Читать далее
Total votes 9: ↑8 and ↓1 +7
Comments 10

Возвращение блудного молотка

Level of difficulty Easy
Reading time 12 min
Views 1.6K

Почти десять лет назад были описаны атаки, эксплуатирующие непреднамеренный и нежелательный побочный эффект динамической памяти с произвольным доступом (DRAM), так называемый rowhammer. За это время неоднократно появлялись новые эксплойты для повышения привилегий, так или иначе использующие этот эффект. Его особенность заключается в том, что ячейки памяти электрически взаимодействуют между собой и непроизвольно могут изменять состояние своих соседей. Проблема заключается в высокой плотности современных интегральных схем. В дальнейшем были разработаны различные аппаратные методы защиты (например, target row refresh, TRR), однако по мере того как производители внедряли средства защиты, менялись и атакующие паттерны для их обхода.

Основной «ударной» силой этих атак стал двойной шаблон double-sided hammering, использующий целенаправленную активацию двух соседствующих с «жертвой» строк DRAM. Эволюция этой идеи привела к созданию фаззера Blacksmith, рвущего все существующие средства защиты практически на всех устройствах DDR4 как тузик грелку. Хотя касательно TRR вообще всё достаточно мутно, поскольку гарантии безопасности механизмов, встроенных в эту защиту, не получилось изучить в полном объёме из-за их проприетарного характера. Существует много исследований, подвергающих сомнению заверения производителей о надёжности данной защиты.

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

Недавно у rowhammer был обнаружен ещё один вектор применения. Он также напрямую касается информационной безопасности, только вот совсем с другой её стороны, и речь пойдёт о конфиденциальности.

Читать далее
Total votes 9: ↑9 and ↓0 +9
Comments 0

И имя нам легион…

Level of difficulty Easy
Reading time 11 min
Views 3.4K

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

Массивное распараллеливание и разделение общих задач, обеспечиваемое совместной работой простых механизмов, намного эффективнее и экономичнее использования одного более сложного. По этому поводу со времён товарища Форда ни у кого вопросов не возникает. А если посмотреть соревнования F1, то там это кажется настолько органичным, что будто по-другому и нельзя.

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

Читать далее
Total votes 11: ↑11 and ↓0 +11
Comments 14

Минималистичный «алгоритм жука»

Level of difficulty Easy
Reading time 15 min
Views 2.3K

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

Эффективность передвижения достигается за счёт алгоритмов планирования движения на основе сенсорных датчиков. При этом очень многое зависит как от оптимальности алгоритмов, так и от количества сенсорной информации (точной информации о координатах положения, угловых координатах, времени или одометрии). Среди множества алгоритмов выделяется целое семейство так называемых «алгоритмов жука», характеризующихся относительной простотой и эффективностью. В этой статье речь пойдёт именно о таком алгоритме, при котором единственным датчиком, дающим какую-то реальную информацию, является датчик интенсивности опорного сигнала, исходящего от цели.

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

Читать далее
Total votes 6: ↑6 and ↓0 +6
Comments 3

Тот же граф, только в другой руке?

Level of difficulty Easy
Reading time 14 min
Views 4.1K

В 2015 году математик Ласло Бабай представил свой более эффективный алгоритм, решающий задачу изоморфизма графов (Graph Isomorphism, GI) за квазиполиномиальное время. На Хабре даже есть статья, освещающая это событие. Однако в дальнейшем сам учёный признал некоторую ошибочность своего подхода, что всё равно не повлияло на отношение большинства математиков к его открытию, поскольку даже получившийся вариант, решающий задачу за субэкспоненциальное время, оказался эффективнее существующих алгоритмов. Тем не менее учёный не остановился на этом и обнаружил ошибку. Опубликованные исправления алгоритма всё-таки привели к решению задачи изоморфизма за квазиполиномиальное время.

Проблема изоморфизма графов требует алгоритмов, которые могут определить, являются ли два графа структурно идентичными. На протяжении десятилетий эта задача занимала особый статус как одна из немногих естественно возникающих задач, уровень сложности которых трудно определить. Многие годы исследователи пытались выяснить, к чему она относится. Даже сейчас неизвестно, к какому классу относится задача, а абстрактно задачу рассматривают как нечто среднее — сложнее, чем P, но легче NP. Задачу из теории графов можно обобщить до общей проблемы изоморфизма, в смежных областях математики существуют идентичные задачи, например изоморфизм конечных групп.

Читать далее
Total votes 9: ↑9 and ↓0 +9
Comments 2

Не так безопасен OpenPGP как его малюют

Level of difficulty Easy
Reading time 11 min
Views 3.3K

Конфиденциальность и безопасность в сети никогда не были актуальней, чем сегодня. Компании, госслужащие и частные лица сталкиваются со всё более высокими рисками, чем когда-либо прежде. Киберпреступность, злоупотребления со стороны властных структур и банальный шпионаж процветают не только в голливудских фильмах. Финансовая информация, деанонимизация личности, коммерческие патенты или просто конфиденциальные сообщения, — каждому есть что терять, даже если ему нечего скрывать. Одним из самых популярных вариантов решения этого вопроса является использование шифрования. За последние годы PGP, а затем и OpenPGP стали стандартом почти для всех подписанных или зашифрованных электронных писем в мире.

О чём собственно речь?
Total votes 6: ↑6 and ↓0 +6
Comments 0

Information

Rating
414-th
Location
Екатеринбург, Свердловская обл., Россия
Date of birth
Registered
Activity