Математика *

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

При устройстве в иностранный хедж-фонд XQuant на среднюю позицию у вас будет два тестирования по математике и программированию, одно hr собеседование, шесть технических собеседований, три интервью с биг боссами, одно интервью на сошиал фит, часть интервью на английском языке. При устройстве аналитиком в российские IT-компании (Яндекс, Авито, Тинькофф, ...) количество технических собеседований может варьироваться (по нашим оценкам от 2 до 7), но минимум два по алгоритмам и математике пройти придётся.

Для оценки IQ кандидата (2) или того, насколько быстро, оригинально и глубоко он может мыслить, ему предлагают решить задачи по математике, алгоритмам, а также брейнтизеры — головоломки на общую сообразительность. Некоторые задачи стандартные, из школьных и вузов- ских учебников, но часто на собеседованиях предлагают нестандартные задачи. Такие, которые не встречались ни в школе, ни в вузе (и даже ни в баре и ни на дискотеке). Например, такого характера (3):

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

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

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

Пожалуй большинство программистов так или иначе сталкивались с с++. Как и я большинство таких людей начинали познавать с++ через его великого основателя Бьярне Страуструпа. Одна из его энциклопедий по с++ начиналась с калькулятора. С подобной задачей написания калькулятора для расчета выражений нам довелось столкнуться в рамках одного из спринтов только уже на c#. (AngouriMath, DynamicExpresso, MathExpressionEval)

В цикле статей под общим названием «Связь решения СЛАУ и минимума квадратичного функционала» постараюсь осветить различные методы решения СЛАУ, которые редко можно встретить в учебниках по линейной алгебре. Основная цель – написать понятный, но в то же время наполненный полезной информацией материал. К каждой последующей статье будет прилагаться соответствующая реализация на языке программирования C++.

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

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

В-третьих, основной рецепт во введении, на первой же странице.

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

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

Давайте ненадолго перенесёмся в школьные годы и вспомним уроки математики и физики. Помните, чему равно число π? Естественно, помните, мы же на Хабре! А чему равно π в квадрате? Это тоже странный вопрос. Конечно, 9,87. А чему равно ускорение свободного падения g помните? Ещё бы, это число так тщательно вдолбили в нашу память, что захочешь — не забудешь: 9,81 м/c². Конечно, оно может варьироваться, но для решения базовых школьных задачек мы обычно использовали именно это значение.

А теперь, внимание, следующий вопрос: а с какого это перепугу π² примерно равно g?

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

История эта началась лет 10 назад, когда моя дочь София Валерьевна принесла задачку (автор ее - Дмитрий Юрьевич Кузнецов аka ДЮК)  с олимпиады для 7-го класса.

«Незнайка записывает 9 разрядов 10-значного десятичного числа и пропускает один по своему выбору. Пропущенный разряд он предлагает записать Винтику, а затем показывает полученное 10‑значное число Шпунтику. Как могут Винтик и Шпунтик договориться, чтобы Шпунтик угадал, какой именно разряд записал Винтик? »

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

TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

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

Я люблю проводить численные эксперименты. Процессор должен думать, а не простаивать. Напомню, что нетривиальные нули Зета функции Римана, расположенные симметрично относительно оси X, имеют вещественную часть равную -1/2 (что не доказано, может быть, у вас получится?), а мнимая часть у первых нулей равна (+/-, так как они расположены симметрично): 14.13, 21.02, 25.01, 30.42, 32.93...

Поиграем с этим.

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

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

Всем привет! На связи команда ad-hoc аналитики X5 Tech. В этой статье мы – Лев Баскин, Андрей Полушкин и Александр Сахнов – расскажем, как без регистрации и смс спланировать смены для сотрудников офлайн-магазинов. Казалось бы, задача достаточно тривиальная: берём симплекс метод или другой метод условной оптимизации и на основе ожидаемой загрузки получаем расписание сотрудников. Однако, не всё так просто. 

Первое препятствие на пути – масштабы. У Х5 порядка 25 000 магазинов от Калининграда до Владивостока и более 378 000 работников, обеспечивающих непрерывное функционирование бизнеса. У каждого магазина своя специфика и различающиеся бизнес-процессы. Во-вторых, даже зная, сколько часов занимает тот или иной процесс и как он локализован во времени, из-за внешних факторов нельзя так просто взять и поместить его в расписание. Например, обстановка на дорогах может повлиять на время поставки и, как следствие, сдвинуть ряд процессов в магазине. Достаточно предисловия, перейдём к сути!

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

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

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

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

О явлениях хаоса и самоорганизации я рекомендую прочитать книгу Джеймса Глейка «Хаос. Создание новой науки» (1987). Если же у вас нет ни времени, ни желания изучать всю историю науки о хаосе, вы узнаете всё самое важное из данной статьи. Здесь я разъясняю множество специфических терминов, которые приведут в ужас даже хорошо образованного человека: эмерджентность, синергия, флуктуации, диссипативные структуры, динамический хаос, точка бифуркации, аттракторы, фракталы и т.д. Также мы выясним, не противоречит ли самоорганизация второму началу термодинамики и действительно ли случайность, необратимость и неустойчивость являются источниками всякого развития.

Одна из самых забавных историй во всей научной фантастике — книжка «Автостопом по Галактике» Дугласа Адамса, в одном из эпизодов которой суперкомпьютеру поручили найти «ответ». Созданный якобы для того, чтобы дать ответ на «главный вопрос о жизни, Вселенной и всём остальном», компьютер тратит 7,5 миллиона лет на вычисление ответа и наконец выдаёт его: 42. Только вот когда ответ, наконец, раскрывается, никто не может вспомнить, в чём же, собственно, заключался «главный вопрос». Это ещё один пример того, что не стоит быть настолько одержимым идеей добраться до цели, чтобы изначально потерять из виду весь смысл путешествия – тогда её достижение уже не будет иметь значения,

К счастью для нас, существует ряд возможных вопросов-кандидатов, которые мы можем использовать задним числом, поскольку они действительно могут быть тем самым окончательным вопросом – ведь нам известно, что ответ на эти вопросы действительно «42». Мог ли хоть один из этих вариантов быть тем, о чём спрашивали суперкомпьютер, когда речь шла о раскрытии ответа на «главный вопрос о жизни, Вселенной и всём остальном»? Хотя никто не может быть уверен, даже в вымышленном мире Дугласа Адамса, вот пять возможных вопросов, которые относятся к числу самых увлекательных. Ответом на каждый из них действительно будет «42», и, возможно, один из них покажется вам по-настоящему захватывающим.

С.Б. Пшеничников

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

Использование IT в обработке естественного языка (Natural Language Processing, NLP)  требует стандартизации текстов, например, токенизации или лемматизации. После этого можно пробовать применять математику, поскольку она является высшей формой стандартизации и превращает исследуемые объекты в идеальные, например, таблицы данных в матрицы элементов. Только на языке матриц можно искать общие закономерности данных (чисел и текстов).

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

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

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

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