Математика *

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

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

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

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

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

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

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

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

Большинство нижних оценок имеют вид , где традиционно длина входа. Увы, наука чаще всего умеет доказывать только простые вещи в духе «для решения задачи необходимо считать весь вход». Даже для сортировок не ограниченных только доступом к сравнениям нижняя оценка остаётся открытым вопросом (при дополнительных ограничениях на вход за линейное время работает, например, Counting Sort). Чаще всего во вводных курсах по алгоритмам и книжках можно встретить нижние оценки для задач на взвешивание: поиск максимума за сравнение, одновременный поиск максимума и минимума за сравнений, и ещё несколько подобных задач. За исключением нескольких простых хорошо известных примеров, задачи на нижние оценки часто оказываются либо сложными, либо требуют знакомство со специальной (математической) техникой, нужной для их решения. Какого же было моё удивление, когда я встретил среди задач, используемых на вступительных испытаниях в Школу анализа данных Яндекса задачу на нижние оценки, которую можно решить достаточно простым способом!

Ссылка на первую часть.

Мастер‑теорема

На примере из прошлой части, попробуем сформулировать и обобщить принцип «Разделяй и властвуй». Мы беремся за проблему, размера n, делим эту проблему на подзадачи размером n/b. Количество таких подзадач обозначим числом a. И еще имеется задача скомпоновать результаты выполнения этих a задач размером n/b в итоговый результат для задачи размера n, который будем считать задачей полиномиальной сложности степени c, O(n^c) . Если задача компоновки будет не полиномиальной, то все изложение резко усложнится. Поэтому, давайте позволим задаче компоновки быть полиномиальной, тем более в это попадает очень большое количество алгоритмов.

Поговорим о датчиках угла.

Есть один остроумный и умозрительный способ измерять углы: при помощи поляризаторов.

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

Насколько реально сделать датчик угла на основе закона Малюса?

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

Но, что если нам надо перемножить два числа любой длины? Не LONG, не байт, не число от 1 до 10, а любые два числа, которое, имеют в общем случае длину n бит, а результат умножения может иметь длину 2n бит.

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

Давайте применим его к нашей задаче.

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

Здравствуй, Хабр! На связи отдел компьютерной томографии Smart Engines. 

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

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

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

Модель вещества (атома) в настоящее время разработана в деталях и понятна настолько, что колоссальную энергию, заключенную в нем, научились извлекать и поставили на службу человеку (в первую вчередь это АЭС). Тем не менее хотелось бы убедиться в правильности наших представлений об атоме, увидеть изображение реального атома, «пощупать» руками, прогнозировать дальнейший прогресс исследований вещества.

Для проведения исследований структуры вещества в динамике необходим источник синхротронного излучения высокой энергии. В РФ под Новосибирском в наукограде Кольцово Институт ядерной физики (ИЯФ) СО РАН им. Г.И. Будкера ведет строительство такого источника поколения 4+СКИФ (электроны будут разгоняться до энергии 3ГэВ). Ожидается, что ввод в строй СКИФа позволит осуществить серьезный прорыв в материаловедении и многих других научных направлениях

Ученые США (Ун-т Огайо) впервые сделали рентгеновский снимок отдельного атома. Атомы стало возможно извлекать поштучно, перемещать и синтезировать из них конструкции, визуализировать с помощью сканирующих зондовых микроскопов. Но без рентгеновских лучей невозможно определить из чего они состоят. Впервые атом «просветили» лучами. Стало возможно назвать не только тип элемента, но и его химическое состояние. В публикации Science Daily приводятся примеры атомов железа (26) и тербия (65). Сейчас стало возможно определить тип конкретного атома по числу протонов. Благодаря прорыву можно будет назвать не только тип элемента, но и его химическое состояние. Это позволит лучше манипулировать частицами внутри различных материалов для удовлетворения потребностей различных отраслей науки и практики.

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

Математик, окончивший Гарвард, а затем террорист, на протяжении 17 лет державший в страхе население США. Теодор Качинский (Унабомбер) умер в федеральном тюремном медицинском центре в Батнере утром 10 июня.

История неуловимого террориста и неплохого математика...

Посмотрите на серию фигур из точек:

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

Вопрос: сколько всего точек на первых n гексах?

Сосчитаем ответ при малых : на первых двух гексах точек, на третьем -, поэтому на первых трёх - . Заметим, что и . Хм... Просто совпадение? Посмотрим, сколько точек на 4-м гексе. На его внешнем слое будет точек. Плюс внутри него расположен третий гекс из 19 точек. Итого, точек. Значит, всего на первых четырёх гексах точки. А - закономерность подтверждается. Правда ли, что на первых гексах всегда точек? Выведем это несколькими методами.

Здравствуйте,

Меня зовут Роман и я разрабатываю технологию извлечения смысла из математических формул. 

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

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

Сначала я хотел просто рассказать об этом продукте. Но это получалось скучно. Интересно только для тех, кто занимается сходной тематикой.

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

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

Привет, Хабр 🙋‍♂️

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

Привет, Хабр! В этой статье разберём, что такое метрики отношения. Узнаем, почему критерий Стьюдента не работает. Попробуем применить бутстреп к зависимым данным. Изучим дельта-метод — способ оценки А/Б тестов с метрикой отношения.