Две леммы о разрастании — утверждения, использующиеся для доказательства ограниченности важных классов формальных языков: регулярных и контекстно-свободных. Важность этих классов для программистов понять легко: регулярные выражения (один из видов описания регулярных языков) в работе используются достаточно часто, а уж языки программирования, синтаксис которых описывается контекстно-свободными грамматиками, и подавно.

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

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

КДПВ иллюстрирует процесс разрастания для КС-грамматик

TLDR: кому перестановки делают больнее — меряем свёрткой графов.
Код: RolX и ванильная трёхслойная GCN на мотифах.

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

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

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

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


Рисунок 1. Первые 100, 200, 500, 1000, 2000 и 5000 точек выборки из предлагаемого прогрессивного нестохастического ряда точек (уравнение 11), демонстрирующие почти изотропные характеристики синего шума с быстрой сходимостью QMC и сниженным количеством артефактов. Ряд основан на новой простой псевдослучайной последовательности с низким расхождением $$.

Введение

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


Рисунок 2. Сравнение регулярной решётки (слева) с тремя разными псевдослучайными функциями (посередине) и простым случайным распределением (справа). Заметьте, что псевдослучайные распределения выглядят менее регулярными, чем решётка, но имеют не так много скоплений и разрежений точек, как случайное распределение.

Поискал я статьи на данном ресурсе на тему ПИД-регуляторов. Много статей. И с объяснением принципов работы таких регуляторов. И с алгоритмами подбора параметров. И с реализацией на конкретных железках и программах. Не увидел одного — симуляции ПИД-регуляторов на моделях, с тем, чтобы пользователь без использования без всякого железа мог «пощупать» работу ПИД-регулятора.

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

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

Когда в начале 1990-х Эндрю Джон Уайлс доказал Великую теорему Ферма, это стало монументальным шагом не только для математиков, но и для всего человечества. Формулировка теоремы очень проста – она утверждает, что у уравнения xⁿ + yⁿ = zⁿ нет целых положительных решений при n > 2. Однако это простое заявление привлекало огромное количество желающих доказать его более 350 лет, с тех пор, как французский математик Пьер де Ферма небрежно набросал формулировку теоремы в 1637 году на полях «Арифметики» Диофанта. Знаменита и формулировка Ферма: он «нашёл этому поистине чудесное доказательство, но поля книги слишком узки для него». Столетиями профессиональные математики и энтузиасты-любители искали доказательство Ферма – или какое угодно ещё.

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

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

Приведу несколько задач, в основном из физики. Мне они нравятся. Надеюсь они понравятся и Вам.

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

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

Большинство задач, так или иначе, обсуждалось в Internete. Но время идет и приходят новые поколения и, может быть, для них задачи будут в новинку.

Каждый год я участвую примерно в сотне собеседований в образовательных проектах JetBrains: собеседую абитуриентов в Computer Science Center и корпоративную магистратуру ИТМО (кстати, набор на программу идёт прямо сейчас). Все собеседования устроены по одному шаблону: мы просим на месте порешать задачи и задаём базовые вопросы по дисциплинам, которые студенты изучали в университетах. Большинство вопросов, которые мы задаём, довольно простые — нужно дать определение некоторого понятия, сформулировать свойство или теорему. К сожалению, у значительной доли студентов все эти определения выветриваются сразу после экзаменов в университетах. Казалось бы, что тут удивительного? В современном мире любое определение можно за пару секунд нагуглить, если это нужно. Но невозможность восстановить базовое определение свидетельствует о непонимании сути предмета.

Если непонимание алгебры или математического анализа может мало влиять на вашу жизнь, то непонимание теории вероятностей делает из вас лёгкую мишень для обмана и манипулирования. Суждения о вероятностях различных событий настолько глубоко вошли в нашу повседневную жизнь, что умение правильно рассуждать и отличать правду от невежества или манипуляции является необходимым. В этом небольшом обзоре мы поговорим о базовых понятиях теории вероятностей, научимся правильно формулировать утверждения про простые случайные процессы и разберём несколько парадоксов. Часть материала позаимствована из брошюры А. Шеня «Вероятность: примеры и задачи», которую я очень рекомендую для самостоятельного изучения.

После появления DeBroglie и Tessera меня много раз просили объяснить, как они работают. Генерирование может выглядеть как волшебство, но лежащие в его основе правила на самом деле просты.

Привет, Хабр!

Продолжаем публиковать рецензии на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество! Первая часть мартовской сборки обзоров опубликована ранее.

Статьи на сегодня:

1. NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis (UC Berkeley, Google Research, UC San Diego, 2020)
2. Scene Text Recognition via Transformer (China, 2020)
3. PEGASUS: Pre-training with Extracted Gap-sentences for Abstractive Summarization (Imperial College London, Google Research, 2019)
4. Lagrangian Neural Networks (Princeton, Oregon, Google, Flatiron, 2020)
5. Deformable Style Transfer (Chicago, USA, 2020)
6. Rethinking Few-Shot Image Classification: a Good Embedding Is All You Need? (MIT, Google, 2020)
7. Attentive CutMix: An Enhanced Data Augmentation Approach for Deep Learning Based Image Classification (Carnegie Mellon University, USA, 2020)

Поделюсь с вами одной историей. Около двадцати лет назад я получил степень по физике, но занимался реверс-инжинирингом и криптоанализом. Наша компания AccessData работала в конце 90-х и начале 2000-х. Тогда правительство США постепенно снимало ограничения на экспорт криптографии, однако парольная защита в большинстве программ по-прежнему оставалась довольно бесполезной. Мы брали офисные программы, я проводил реверс-инжиниринг и выяснял алгоритм шифрования, а потом ломал криптозащиту.

Это был нескончаемый поток интересных, но не особенно сложных математических головоломок. За всё время я написал около сорока взломщиков паролей. Мы продавали их домашним пользователям, системным администраторам, местным и федеральным правоохранительным органам. Мне пришлось несколько раз съездить в федеральный центр подготовки сотрудников правоохранительных органов в Глинко, чтобы объяснить ребятам из Секретной службы, ФБР и АТФ основы криптографии и как использовать наши продукты.

Особенно ярко мне запомнились два проекта. Первым был Microsoft Word 97. До его появления файлы шифровались с помощью XOR байтов открытого текста и 16-байтовой строки, которая выводилась из пароля. Самыми распространёнными байтами в файле Word обычно были 0x00, 0xFF или 0x20 (пробел), поэтому мы просто выбирали самый распространённый символ в каждом столбце и проверяли 3¹⁶ вариантов. Восстановление ключа обычно происходило мгновенно, но чтобы людям не казалось, что они зря потратили деньги, мы вставили небольшую анимацию, похожую на голливудскую хакерскую сцену с множеством случайных символов, из которых постепенно проявляется правильный пароль.

Как я и говорил, я потихоньку строю очень простой, но функциональный и при этом бескомпромиссно троичный вычислитель, основанный на сбалансированной троичной системе счисления. В этой статье я описываю эмулятор моего вычислителя, который мне поможет в отладке железа. Если вам интересно, не стесняйтесь писать под него программы, я их обязательно запущу на настоящем железе как только оно будет готово! Это очень просто, Триадор понимает обычный очень примитивный императивный язык, схожий с ассемблером или brainfuck :)

— Жуткий кошмар! Нули и единицы повсюду. И кажется, я видел двойку.
— Это просто сон, Бендер. Двоек не бывает.

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

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

Меж тем, именно левый график получен при помощи «честного» генератора случайных чисел. Правый график тоже содержит сплошь случайные точки; но эти точки сгенерированы так, чтобы все маленькие квадраты содержали равное количество точек.

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

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

Привет, Хабр! Продолжаем публиковать рецензии на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество!

Статьи на сегодня:

1. Fast Differentiable Sorting and Ranking (Google Brain, 2020)
2. MaxUp: A Simple Way to Improve Generalization of Neural Network Training (UT Austin, 2020)
3. Deep Nearest Neighbor Anomaly Detection (Jerusalem, Israel, 2020)
4. AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (Google, 2020)
5. SpERT: Span-based Joint Entity and Relation Extraction with Transformer Pre-training (RheinMain University, Germany, 2019)
6. High-Resolution Daytime Translation Without Domain Labels (Samsung AI Center, Moscow, 2020)
7. Incremental Few-Shot Object Detection (UK, 2020)

Привет, Хабр! Сегодняшний пост про фракталы попался в рамках проработки темы Python, в частности, Matplotlib. Последуем примеру автора и предупредим, что в посте много тяжелой анимации, которая может даже не работать на мобильном устройстве. Зато как красиво.



Всем приятного чтения

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

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

Вся моя жизнь неразрывно связана с математикой. В голове постоянно рождаются мысли: «Почему именно так и какое этому объяснение?». Мне нравится находить разные способы решения интересных задач.

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

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

И ответы действительно есть. Проблема в том, что в них царит раздрай. К примеру, центры по контролю и профилактике заболеваний США используют модели, судя по предсказаниям которых в лучшем случае от вируса погибнет 200 000 американцев. Тем временем отчёт Имперского колледжа Лондона попал в заголовки газет со своим ужасным сценарием, по которому погибнет 2,2 млн американцев, если никто не будет менять своего повседневного поведения.

(кадр из телешоу Монти-Холла: гость не сумел правильно подсчитать вероятности, поэтому вместо автомобиля выиграл удивленную ламу)

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

Хилель Фарстенберг, 84 лет, и Григорий Маргулис, 74 лет, профессора на пенсии, разделили математический эквивалент нобелевской премии

Хилель Фарстенберг

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

Её получили Хилель Фарстенберг, 84 лет, из Еврейского университета в Иерусалиме, и Григорий Маргулис, 74 лет, советский и американский математик из Йельского университета. Оба – профессора на пенсии.

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