Страсть к машинам

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

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

Привет! Меня зовут Азат, я создаю курсы по подготовке к экзамену в ШАД. Недавно мы запустили курс по дискретной математике, поэтому наша команда активно прорешивает задачки по соответствующей теме. После разбора экзамена в ШАД 2019 года мы увидели большой интерес пользователей Хабра к занимательным задачкам из экзамена. Поэтому выкладываем здесь 4 избранных по дискретной математике. Наслаждайтесь!

Сегодня у меня необычный текст, совершенно не связанный с машинным обучением (для новых читателей: этот текст – часть блога компании Surfingbird, в котором я в течение последнего года рассказывал о разных аппаратах машинного обучения в приложении к рекомендательным системам). В этом посте математической части практически не будет, а будет описание очень простой программки, которую я написал для своих студентов. Вряд ли кто-то узнает для себя из этого поста много содержательно нового, но мне кажется, что некоторую ценность представляет сама идея – многие люди просто не задумываются о том, что «и так можно». Итак…

Короткая предыстория

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

Заноза в голове

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

Оказывается улучшить можно.
Попробуем нарисовать новый вид цифры 0.
Если интересно, зачем и почему — прошу под кат.

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

Чтобы стало понятно о чем идет речь, представим, что нам необходимо протестировать какую-либо программу или сайт. Очень хорош пример с тестированием веб-формы, скажем, для регистрации или для поиска. Возникает вопрос, с какими ошибками в ней скорее всего встретится пользователь? Пускай у нас в форме имеется 6 вопросов, для каждого из которых возможны 10 вариантов ответа. Допустим, на страницу зашел целый миллион пользователей, и каждый из них ответил уникально. Теперь представим, что в форме для заполнения ответами скрывается ошибка. Если ошибка обнаруживается только при определенной комбинации ответов на все 6 вопросов, то на неё наткнется лишь один человек. Если же ошибка вылетает при наборе определенных ответов на какие-то 3 вопроса, то количество людей, обнаруживших ошибку возрастет до тысячи. Очевидно, что чем меньше элементов в комбинации, требуемой для ошибки, тем больше людей с ней встретится. Соответственно, перед нами теперь стоит задача: если мы не можем обнаружить все ошибки, то давайте хотя бы найдем самые критичные, то есть те, на которые наткнется больше всего пользователей.
Таким образом, мы должны сформировать тест-кейсы (и чем меньше, тем лучше), при переборе которых мы наткнемся на самые легкодоступные ошибки. Допустим, у нас имеется множество вопросов A, которое мы задаем количеством вариантов ответа на каждый из них: А = {2, 3, 5, 2, ...}. Пусть n — количество вопросов, а 1≤m≤n — степень критичности ошибок, она же степень покрытия или глубина покрывающего набора. Чем меньше значение m, тем критичнее ошибка. Задавая степень покрытия мы строим тестовый набор, который позволит обнаружить все ошибки, степень критичности которых меньше данного m. Если m = n, то поиск ошибок сводится к перебору всех вариантов. Чем меньше задаем степень, тем меньше тест-кейсов будет сформировано и тем меньше ошибок мы найдем.

Деревья. Кратко напомним

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

Полное название статьи должно было звучать как «Устойчивая „топологическая“ сортировка графа с циклами за O(|V| + |e| log |e|) по времени и O(|V|) по памяти без рекурсии», но мне сказали, что это перебор.

Все мы изучали в курсе математики численные методы. Это такие методы, как интегрирование, интерполяция, ряды и так далее. Существует два вида числовых методов: детерминированные и рандомизированные.

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

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

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

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

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

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

 

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

Синхронизация является основным методом борьбы с состязаниями сигналов в цифровых схемах.

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

Часто на собеседованиях в магистратуру СПбАУ или CS центр ребята затрудняются ответить на вопросы об элементарных понятиях как из классической, так и из дискретной математики. А эти знания требуются для освоения курсов алгоритмов, машинного обучения и прочих Computer Science дисциплин. Чтобы облегчить подготовку, Академический университет совместно с Computer Science Center этой весной запускают два онлайн-курса:

1. Ликбез по дискретной математике. Преподаватель — А.В. Омельченко (СПбАУ РАН).
2. Введение в математический анализ. Преподаватель — А.И. Храбров (СПбГУ, СПбАУ РАН, CS центр).

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

Курсы размещены на дружественной платформе Stepic.

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

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

Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?