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

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

В статье о треугольнике Паскаля я уже упоминал о связи фундаментальных основ современной академической теории вероятностей с азартными играми. И это действительно так, поскольку первые массовые коммерческие азартные игры появились, случайно или нет, практически одновременно с началом формализации основ теории вероятности. И она в некотором роде берёт свои корни из изучения игровых механик. Те же Блез Паскаль и Пьер Ферма заинтересовались проблемами теории вероятностей с подачи своего знакомого Антуана Гомбо, математика-любителя и по совместительству весьма увлечённого игрока.

В одной из предыдущих статей я уже упоминал нобелевского лауреата по физике 2024 года Джеффри Хинтона (праправнук Джорджа Буля). Вторым лауреатом стал Джон Хопфилд. Сеть Хопфилда — это одна из форм полносвязных рекуррентных нейронных сетей. Одной из ключевых особенностей сетей Хопфилда является их способность восстанавливать полные шаблоны из частичных или зашумленных входных данных, что делает их устойчивыми к неполным или поврежденным данным.

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

Кунихико Фукусима, работавший в Научно-исследовательском институте технологий радиовещания NHK, и Шуничи Амари, почётный профессор Токийского университета, ранее добились новаторских результатов, которые привели к исследованию Хинтона и Хопфилда, отмеченному Нобелевским комитетом.

Так кто же эти самураи исследований в области искусственного интеллекта?

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

В отличие от предыдущих методов этот модуль ассоциативной памяти объединяет представления отдельных токенов в непараметрическую модель распределения. Эта модель управляется динамически путём надлежащего балансирования новизны и свежести входящих данных. Извлекая информацию из консолидированной ассоциативной памяти, базовый LLM на стандартных тестах достигает лучших результатов. Эта архитектура называется CAMELoT (Consolidated Associationive Memory Enhanced Long Transformer). Она демонстрирует превосходную производительность даже при крошечном контекстном окне в 128 токенов, а также обеспечивает улучшенное контекстное обучение с гораздо большим набором демонстраций.

В основе этой статьи лежит материал статьи математика Джима Проппа.

Если бы новые виды чисел были как новые потребительские товары, математики имели бы полное право уволить маркетолога, который придумал названия для «комплексных» и «мнимых» чисел. Как бы звучал слоган для этих брендов? «Хотите купить число? Без проблем, хотя оно действительно трудно для понимания, и, что самое лучшее, его даже не существует!»

Математикам некого винить, кроме самих себя, поскольку один из них (Рене Декарт) наделил такие числа, как sqrt(−1), термином «мнимые», а другой (Карл-Фридрих Гаусс) — окрестил числа вроде 2+sqrt(−1), «комплексными». Сейчас эти названия кажутся немного не соответствующими смыслу понятий, скрывающихся за ними, но уже несколько столетий поздно просить всех использовать другие слова, хотя эти столетия дали нам более чёткое понимание того, для чего нужны эти относительно новые виды чисел.

В принципе, понятно, почему sqrt(−1) назвали «мнимым». Корень из -1 обозначает число x со свойством x² = −1, но ни одно приличное число так себя не ведёт. Число может быть положительным, отрицательным или нулевым. Если x положительно, x² тоже будет положительным. Если x отрицательно, x² всё равно будет положительным, поскольку отрицательное число, умноженное на отрицательное число, является положительным числом. А если x равен нулю, x² также будет равен нулю. Ни в одном из трёх допустимых случаев x² не является отрицательным, поэтому x² не может быть равным −1. Это в некотором роде невыполнимое уравнение. И можно было бы подумать, что это положит конец вопросу…

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

В прошлой статье мы остановились на том, что необходимо сформулировать алгоритм выбора сравнений в каждой точке дерева решений для любого N ≥ 3. В статье будет много формул, за что я искренне извиняюсь, но кто сказал, что математика может обходиться без них?

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

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

Для начала проведём анализ проблемы.

В предыдущей части материала я достаточно подробно рассказал об уравнении 1 + 1 = 1 в булевой арифметике с точки зрения Джорджа Буля и дальнейших усовершенствованиях его идей. В том числе о вкладе Уильяма Джевонса (именно он ввёл термин булева функция).

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

2 ноября исполняется 209 лет со дня рождения Джорджа Буля, одного из основателей математической логики, и этот материал — часть большой работы, посвящённой ему и его наследию.

Сегодня я расскажу, какой смысл имеет уравнение 1 + 1 = 1 в булевой арифметике, и как оно стало инструментом для проектирования сложных цифровых схем. Наибольший вклад в это положение дел внесли два человека: Джордж Буль и Клод Шеннон.

Итак, начнём в хронологическом порядке с Джорджа Буля.

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

Алгоритм футбольной оптимизации (Football Optimization Algorithm, FOA)

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

Совсем недавно закончился Евро-2024 и, если честно, оставил после себя смешанные чувства. Я, конечно, больше по хоккею, однако такое событие, как чемпионат Европы по футболу, не могло остаться совсем за бортом.

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

Почти год назад я написал статью о постквантовой криптографии и в этом материале решил продолжить эту тему, поскольку с каждым годом приближается момент, когда криптография, какой мы её знаем сегодня, накроется медным тазом. С появлением квантовых вычислений значительно возрос интерес к асимметричным технологиям шифрования. В частности сегодня пытаются найти подходящую замену RSA и алгоритмам на основе дискретных логарифмов, которые тривиально легко будут взломаны с помощью алгоритма Шора. Хотя симметричное шифрование более устойчиво к квантовым вычислениям, с их широким распространением оно будет существенно скомпрометировано реализациями алгоритма Гровера, поскольку он может выполнять неструктурированный поиск за O(sqrtN). Таким образом размер симметричного ключа уменьшится в два раза, то есть эффективность ключа AES-256 будет уменьшена до 128 бит. Тогда автоматически возникает вопрос, будет ли AES-256 оставаться безопасным? Давайте разбираться.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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