Всем добрый день! Этот короткий пост посвящен рассмотрению моделей процессов разработки Waterfall и Agile (на примере Scrum и/или Kanban). И вот в чем дело: с точки зрения заказчика, процесс не столь важен, сколько срок и бюджет удовлетворительного с точки зрения функционала результата. И если известно, что (изменения не учитываются) затраты Waterfall-процесса идут по S-кривой, а затраты Agile-процесса накапливаются линейно (так как ресурсы используются одновременно все), то как они должны различаться по эффективности. Чтобы исследовать этот вопрос, необходимо построить модели и сравнить их, и для этого будет использована несложная математика.

Перевод поста Джона Маклуна (Jon Mcloone, директор департамента международного бизнеса и стратегического развития Wolfram Research). Оригинал поста: How to Win at Rock-Paper-Scissors
Скачать пост в виде документа Mathematica

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

Комбинаторика в старших классах школы, как правило, ограничивается текстовыми задачами, в которых нужно применить одну из трёх известных формул — для числа сочетаний, перестановок или размещений. В институтских курсах по дискретной математике рассказывают и о более сложных комбинаторных объектах — скобочных последовательностях, деревьях, графах… При этом, как правило, ставят задачу вычислить количество объектов данного типа для некоторого параметра n, например количество деревьев на n вершинах. Узнав количество объектов для фиксированного n, можно задаться и более сложным вопросом: как все эти объекты за разумное время предъявить? Алгоритмы, решающие подобного рода задачи, называются алгоритмами комбинаторной генерации. Таким алгоритмам, например, посвящена первая глава четвёртого тома «Искусства программирования» Дональда Кнута. Кнут очень подробно рассматривает алгоритмы генерации всех кортежей, разбиений числа, деревьев и других структур. Придумать какой-нибудь алгоритм, работающий умеренно быстро, для каждой из этих задач несложно, но с дальнейшей оптимизацией могут возникнуть серьёзные проблемы.

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



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

Иногда чисто теоретические, математические абстракции находят удивительное соответствие в живой природе. Пожалуй, самые известные среди них — фракталы. Но вот группе математиков, физиков и химиков из США, Южной Кореи и Японии удалось найти ещё один замечательный пример. Они доказали, что известная теорема о четырёх красках в точности описывает структуру некоторых кристаллов.

Уже не раз всплывала тема про поддержку ввода формул на хабре, был даже отдельный вопрос на Тостере.

Пару дней назад я напрямую спросил об этом службу поддержки Хабрахабра и получил ответ:

Здравствуйте. Пока поддержка LaTeX не планируется.

Но что думает по этому поводу хабрасообщество? Голосовалка под катом.

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

Введение

Знаменитая задача трисекции произвольного угла циркулем и линейкой без делений является одной из древнейших задач, привлекавших многих математиков в течение нескольких тысячелетий. Неразрешимость задачи, т.е. невозможность такого построения, была окончательно доказана в 19 веке, однако некоторые люди до сих пор предлагают свои решения. Например, решение одного академика РАН было опубликовано в журнале «Наука и жизнь». Хотя, может быть, это такой тонкий троллинг…

Наука и жизнь, №3, 1998

Правда, по словам одного профессора математики, поток писем с решениями трисекции угла и простыми доказательствами великой теоремы Ферма в последнее время заметно снизился. Сейчас ему присылают, как правило, доказательства гипотезы Римана.

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

В соседнем посте была приведена интересная задача, условие которой звучит следующим образом:

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

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

Хотите узнать правильное решение этой задачи? Добро пожаловать под кат!

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

Этот пост про относительно новый метод обработки сигналов, описанный в статье Adaptive data analysis via sparse time-frequency representation, а также про крохотную, но сбившую лично меня с толку, ошибку. Сию статью опубликовали в 2011 году профессора прикладной математики Калифорнийского Технологического института Томас И. Хоу и Ши Цзоцян, и, вероятно, к моменту, как вы это читаете, они уже её поправили.
На эту статью я наткнулся в поиске различных методов частотно-временного анализа нелинейных и нестационарных сигналов — в моем случае ультразвуковых сигналов от передвигающихся форменных элементов крови в сосудах человека. Суть такого анализа состоит в отслеживании изменений характеристик сигнала, иначе говоря, мы хотим знать зависимость составляющих сигнал частот от времени. За исключением широко распространенных методов — спектрального и вейвлет-анализа, были найдены такие методы как EMD (разложение на эмпирические моды) и синусоидальное моделирование, о котором далее пойдет здесь речь.
Метод эмпирических мод довольно прост в применении, однако не особо развит с точки зрения обоснованности полученных результатов. Томас Хоу и Ши Цзоцян пошли дальше в развитии математического аппарата и предложили свой метод синусоидального моделирования сигнала. Его идея заключается в разреженной декомпозиции сигнала на гармоники с гладкими амплитудами. Какой результат мы ожидаем получить — на картинке выше. В данном случае раскладывался сигнал, полученный функцией f(t) = 6t + cos(8πt) + 0.5 cos(40πt). Разложение сигнала, естественно, не уникально, поэтому был введен критерий минимума составляющих гармоник, и задача сформировалась следующим образом:

За применение в бизнесе мнимых величин уже дали премию. Теперь интересно что-нибудь поиметь с дуальных.
Дуальное число — это расширение поля действительных чисел (или любого другого, например комплексных) вида a + εb, где a и b — числа из исходного поля. При этом полагается, что ε ε = 0.
Оказывается, у таких странных чисел есть практическое приложение.

Основным полезным свойством дуальных чисел является
f(a + εb) = f(a) + εf'(a)b.
Когда у нас есть формула для f(x), получить производную f'(x) труда не составит. Но часто f(x) доступно только в виде алгоритма — например как решение специальным образом составленной системы линейных уравнений. Запустив алгоритм с исходными данными, в которые добавлена ε мы получим результат и значение производной по одному из параметров.

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

Ниже приведен алгоритм точного решения целочисленной задачи о рюкзаке. Предлагаемый алгоритм требует меньше вычислительных ресурсов и возможно несколько проще алгоритма динамического программирования (ДП).

Причина побудившая автора к публикации

Первая версия описания алгоритма было послана мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:

Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.

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

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

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

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

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

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



А вот как сам Роман Михайлов описывает свой курс:

«Планируется разбор и обсуждение некоторых открытых проблем теории групп и маломерной теории гомотопий: проблемы асферичности Уайтхеда, D(2)-гипотезы Уолла, проблемы дыр соотношений, проблемы делителей нуля в групповых кольцах. Скорее это не курс, а беседы о теории групп и теории гомотопий, с описанием различных примеров, трюков и методов.»

Ну а потом родилась идея сделать конкурс таких роликов.

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

Кстати, если у вас есть знакомые или их дети, которым рано идти в ШАД, но которые подают надежды, расскажите им о факультете Computer Science, который открывается в этом году в Высшей школе экономики при участии Яндекса. Во многом он будет расти из Школы анализа данных, но в неё мы принимаем студентов и выпускников. Поэтому если вы абитуриент, то приходите 27 апреля на презентацию этого факультета, где ректор НИУ ВШЭ Ярослав Кузьминов и сооснователь Яндекса Аркадий Волож расскажут о нём все подробности. Мы всех приглашаем.

Истории: одна о гуглере и одна — о сотруднике Яндекса

С момента создания ШАД её закончили 260 специалистов в области computer science. Мы попросили двух выпускников Школы рассказать о том, что им дало обучение в ней, и дать несколько советов тем, кто решил поступать.

Андрей Петров, разработчик в мюнхенском офисе Google.

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

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

Краткое содержание курса можно найти в статьях «Математическая модель двигателя Lego NXT» и «Математическая модель Lego Segway».
Курс ознакомит вас с основами механики Лагранжа, матричного представления систем, основными приемами теории автоматического управления. Я постарался не обращаться к сложным математическим приемам, поэтому для прохождения курса должно хватить школьных знаний.