Математика *

Американские психологи однажды провели потрясающе простой эксперимент.

Человеку дается сто долларов и говорится, что неплохо было бы поделиться ими еще с одним человеком. Второй участник не присутствует ни до, ни во время, ни после эксперимента, то есть может попросту не существовать. Сто долларов между тем совершенно реальны (святым американцы не шутят). В среднем испытуемый отдает из упавшего с неба стольника 25 долларов. Конечно, встречаются жадины, оставляющие все себе, альтруисты, отдающие все до последнего цента, эгалитаристы, делящие все пополам, но средняя цифра именно такова: три четверти себе, четверть – другому. (Наш фирменный главбух, любезная Анна Анатольевна, ни секунды не думая, сказала, что отдала бы половину. Думаю, в бухгалтерии у нас все в порядке).

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

С этими цифрами удивительно перекликаются другие, из уже личного опыта. У меня есть давний приятель, который сразу после школы подался в таксисты и таксует уже лет 25. Он как-то заехал с проблемой со своим навигатором и рассказал между прочим, как устроена служба такси в наших широтах (дело было как раз перед уберизацией всей страны). Понятно, что никаких таксопарков давно не существует, а все фирмы, предоставляющие такие услуги, – обычные колл-центры, с которыми сотрудничают вольнонаемные водители на своих авто. По словам Андрея, фирмы, которые берут за диспетчерские услуги 25% от цены поездки, жадины и захребетники (там были немного другие слова, я адаптировал), а которые 20% – нормальные ребята и именно с такими он и сотрудничает.

Нам очень повезло, что Земля вращается вокруг своей оси!

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

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

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

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

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

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

В 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 июня.

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