Как стать автором
Обновить
240.99

Математика *

Царица всех наук

Сначала показывать
Порог рейтинга
Уровень сложности

Общество полной справедливости и неравенства

Уровень сложности Простой
Время на прочтение 4 мин
Количество просмотров 5.9K
Математика *

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

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

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

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

Читать далее
Всего голосов 25: ↑24 и ↓1 +23
Комментарии 57

Новости

Акселерометр = полунавигатор

Уровень сложности Средний
Время на прочтение 3 мин
Количество просмотров 2.9K
Математика *Программирование микроконтроллеров *Производство и разработка электроники *Физика DIY или Сделай сам
Мнение

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

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

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

Читать далее
Всего голосов 11: ↑7 и ↓4 +3
Комментарии 30

Вычислительная сложность некоторых игр и головоломок (часть 2)

Уровень сложности Простой
Время на прочтение 14 мин
Количество просмотров 1.7K
Блог компании FirstVDS Алгоритмы *Математика *Логические игры

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

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

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

Читать далее
Всего голосов 13: ↑13 и ↓0 +13
Комментарии 4

Каково расстояние между «Будапештом» и «Бухарестом» или об отождествлении слов с помощью расстояния Левенштейна

Уровень сложности Средний
Время на прочтение 6 мин
Количество просмотров 1.2K
Блог компании Smart Engines Алгоритмы *Обработка изображений *Математика *

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

Читать далее
Всего голосов 5: ↑4 и ↓1 +3
Комментарии 6

Истории

Движок для игры от первого лица в 265 строках Javascript

Уровень сложности Сложный
Время на прочтение 6 мин
Количество просмотров 14K
Блог компании Timeweb Cloud JavaScript *Разработка игр *Математика *Игры и игровые консоли
Туториал
Перевод
image

Сегодня окунёмся в мир, который можно потрогать. В этой статье мы исследуем, как с нуля, быстро и без особо сложной математики написать движок для игры от первого лица. Для этого мы воспользуемся приёмом под названием «бросание лучей» (raycasting). Возможно, вы видели примеры такой техники в играх Daggerfall и Duke Nukem 3D, а из более свежего – в статьях из «ludum dare» от Нотча Перссона. Что ж, для Нотча это неплохо, но не для меня! Вот демка (управление стрелками и тачпадом) [источник].
Читать дальше →
Всего голосов 72: ↑72 и ↓0 +72
Комментарии 29

Удивительное изобретение русского инженера, которое не спасло его от нищеты. Прямило Липкина

Уровень сложности Простой
Время на прочтение 3 мин
Количество просмотров 37K
Блог компании ГК ITGLOBAL.COM Математика *Научно-популярное Биографии гиков

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

Читать далее
Всего голосов 92: ↑76 и ↓16 +60
Комментарии 119

Собеседования по алгоритмам: максимальная конкатенация

Уровень сложности Средний
Время на прочтение 1 мин
Количество просмотров 5.6K
Спортивное программирование *Занимательные задачки Алгоритмы *Математика *
Кейс

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

Читать далее
Всего голосов 14: ↑11 и ↓3 +8
Комментарии 138

Кодирование и декодирование данных

Уровень сложности Средний
Время на прочтение 7 мин
Количество просмотров 1.9K
Блог компании OTUS Математика *Сжатие данных *Читальный зал
Обзор


Автор статьи: Артем Михайлов

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

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

Важным примером применения кодирования и декодирования данных является цифровое телевидение и интернет-трансляции. Например, H.264 — это технология кодирования видео, которая позволяет получить максимально высокое качество с минимальным объемом данных. При этом, при передаче через Интернет, данные сжимаются, и после достижения адресата автоматически декодируются.
Читать дальше →
Всего голосов 10: ↑8 и ↓2 +6
Комментарии 1

Можно ли в деловом документе найти созвездие Большой Медведицы?

Уровень сложности Средний
Время на прочтение 10 мин
Количество просмотров 1.4K
Блог компании Smart Engines Алгоритмы *Математика *Искусственный интеллект

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

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

Читать далее
Всего голосов 4: ↑4 и ↓0 +4
Комментарии 2

Параметрический анализ данных

Уровень сложности Средний
Время на прочтение 8 мин
Количество просмотров 1.7K
Блог компании OTUS Математика *Визуализация данных *
Обзор


Автор статьи: Артем Михайлов

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

Параметрический анализ широко используется в различных областях, включая экономику, науку и инженерию. Методы параметрического анализа могут быть применены для любого вида данных, включая качественные и количественные.
Читать дальше →
Всего голосов 16: ↑15 и ↓1 +14
Комментарии 1

Матирование изображений, или как получить фотореалистичный передний план

Время на прочтение 7 мин
Количество просмотров 2.2K
Блог компании SberDevices Обработка изображений *Математика *Машинное обучение *Искусственный интеллект

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

Читать далее
Всего голосов 10: ↑9 и ↓1 +8
Комментарии 14

Задача про красные и синие точки

Уровень сложности Средний
Время на прочтение 4 мин
Количество просмотров 10K
Занимательные задачки Алгоритмы *Математика *

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

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

Читать далее
Всего голосов 13: ↑13 и ↓0 +13
Комментарии 48

Задача о нижней оценке на поиск в таблице Юнга

Уровень сложности Средний
Время на прочтение 4 мин
Количество просмотров 1.1K
Алгоритмы *Математика *
Туториал

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

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

Читать далее
Всего голосов 5: ↑5 и ↓0 +5
Комментарии 1

Разделяй и властвуй. Повышение эффективности алгоритмов. Часть 2

Уровень сложности Средний
Время на прочтение 5 мин
Количество просмотров 2.6K
Алгоритмы *Математика *Научно-популярное

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

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

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

Читать далее
Всего голосов 8: ↑8 и ↓0 +8
Комментарии 3

Поляризатор = датчик угла

Уровень сложности Простой
Время на прочтение 7 мин
Количество просмотров 5.6K
Математика *Программирование микроконтроллеров *Производство и разработка электроники *Физика DIY или Сделай сам
Туториал

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

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

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

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

Читать далее
Всего голосов 37: ↑36 и ↓1 +35
Комментарии 78

Разделяй и властвуй. Повышение эффективности алгоритмов. Часть 1

Уровень сложности Средний
Время на прочтение 5 мин
Количество просмотров 6.7K
Алгоритмы *Математика *Научно-популярное
Из песочницы

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

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

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

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

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

Читать далее
Всего голосов 26: ↑25 и ↓1 +24
Комментарии 17

Шум в компьютерной томографии: правда ли он нам мешает?

Уровень сложности Сложный
Время на прочтение 7 мин
Количество просмотров 2.2K
Блог компании Smart Engines Алгоритмы *Обработка изображений *Математика *Научно-популярное

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

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

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

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

Читать далее
Всего голосов 8: ↑8 и ↓0 +8
Комментарии 12

Строение атома и материи

Уровень сложности Сложный
Время на прочтение 18 мин
Количество просмотров 5.6K
Математика *Физика Химия
Recovery mode

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

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

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

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

Читать далее
Всего голосов 27: ↑20 и ↓7 +13
Комментарии 9

В США умер безумный математик-террорист Качинский, который кошмарил страну в течение 17 лет! Его цитировал даже Брейвик

Время на прочтение 10 мин
Количество просмотров 44K
Блог компании ГК ITGLOBAL.COM Математика *Научно-популярное Биографии гиков


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

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

Читать далее
Всего голосов 61: ↑43 и ↓18 +25
Комментарии 263

Новые целочисленные типы для языка C++

Время на прочтение 7 мин
Количество просмотров 9.5K
Блог компании Издательский дом «Питер» Высокая производительность *Программирование *C++ *Математика *
Перевод
(Большинство) реализаций C++ предоставляют по крайней мере 8, 16, 32 и 64-битные знаковые и беззнаковые целочисленные типы. Существуют потенциально неудобные неявные преобразования, споры о неопределенном поведении при переполнении (некоторые считают, что это перебор, другие — что недобор), но по большей части эти языковые конструкции хорошо справляются с поставленными задачами. В новых языках, таких как Rust, этот замысел скопирован, но исправлены проблемы с преобразованиями и поведение при переполнении.

Тем не менее, я считаю, что здесь есть место для инноваций. Позвольте мне рассказать о трех новых семействах целочисленных типов, которые я хотел бы увидеть в C++.
Читать дальше →
Всего голосов 14: ↑11 и ↓3 +8
Комментарии 53

Вклад авторов