avatar

Можем ли мы доверять решению компьютера, если не можем его проверить?

Опубликовал в блог Новости IT технологий
0
Если помните, Рей Курцвейл обещал приход сингулярности уже в 30 годах этого века. Похоже, что первые предвестники уже появляются: два бывших наших соотечественника, Алексей Лисица и Борис Конев, работающие в Ливерпульском университете, запустили на расчет задачу несоответствия Эрдеша. Задача считается неразрешенной, и программа, запущенная исследователями с задачей справилась. Но! Проблема в том, что доказательства решения сами по себе занимают 13 Гб (еще раз, текстовый лог-файл, по сути и являющийся доказательством, занимает 13 Гб) и с трудом поддается верификации. Отсюда напрашивается простой вопрос – можем ли мы доверять решению компьютера, если не в состоянии проверить его выкладки?


Читать дальше →
avatar

О решении неполного кубического уравнения

Опубликовал в блог Новости IT технологий
0
image

Intro
Я публикую этот топик как tutorial. Собственно говоря, существенной новизны в материале нет, тема заезжена. Думаю, что интересным будет подход к решению задачи.

Помню, на первом курсе на занятиях по математическому анализу пришел в голову один интеграл. Преподаватель вызвал к доске, но прозвенел звонок. По дороге домой в автобусе сложился «скелет» решения кубического уравнения. Общая схема, конечно, не самая рациональная. Есть более эффективная — тригонометрическая формула Виета. Там сразу выписывается корень по виду уравнения, а, вообще, по объему вычислений все-таки лучше использовать численный метод Ньютона, поскольку степенные ряды для обратных тригонометрических функций сходятся медленно (а по ним в основном и строятся вычисления таких функций в калькуляторах и некоторых библиотеках). Вот что получилось.
Читать дальше →
avatar

О гипотезе Пуанкаре. Лекция в Яндексе

Опубликовал в блог Новости IT технологий
0
Еще в XIX веке было известно, что если любую замкнутую петлю, лежащую на двумерной поверхности, можно стянуть в одну точку, то такую поверхность легко превратить в сферу. Так, поверхность воздушного шарика удастся трансформировать в сферу, а поверхность бублика – нет (легко вообразить себе петлю, которая в случае с бубликом не стянется в одну точку). Гипотеза, высказанная французским математиком Анри Пуанкаре в 1904 году, гласит, что аналогичное утверждение верно и для трехмерных многообразий.

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



Читают лекцию доценты механико-математического факультета МГУ к. ф-м. н. Александр Жеглов и к. ф.-м. н. Федор Попеленский.
Конспект лекции
avatar

Отыскание периодических решений одного класса неавтономных систем дифференциальных уравнений

Опубликовал в блог Новости IT технологий
0
В прикладной математике иногда возникает задача построения периодических решений нормальной системы обыкновенных дифференциальных уравнений вида

image

где функция imageпредставляет собой сумму

image

многомерного многочлена imageи тригонометрического полинома image, являющегося image-периодической векторной функцией.

Многие из теорем существования периодических решений системы (1) используют тот фундаментальный факт, что такие решения полностью определяются неподвижными точками оператора сдвига по траекториям системы. Однако использование данных теорем для непосредственного нахождения нужного периодического решения, скорее всего, не представляется возможным.
Читать дальше →
avatar

[Из песочницы] Анализ источников трафика для повышения конверсии

Опубликовал в блог Новости IT технологий
0
Google Analytics - мощный инструмент для анализа трафикаВ этой статье речь пойдет о том, как правильно анализировать источники трафика, например, с помощью инструментов Google Analytics или Yandex Metrica. Отключив источники с низкой либо нулевой конверсией, можно существенно поднять общую конверсию, снизить стоимость заказа и улучшить рентабельность интернет-рекламы.

Цель этой статьи — получить отзывы и замечания по описанным ниже методам, описать способы принятия обоснованных решений по блокировке некачественных источников трафика.
Читать дальше →
avatar

Коллективный разум в теории чисел

Опубликовал в блог Новости IT технологий
0
В мае на Хабре была опубликована статья, которая повествует о работе Yitang Zhang в области теории простых чисел, вызвавшей большой резонанс в научном сообществе. В этой заметке даётся краткая сводка результатов, которых удалось достичь научному сообществу спустя девять месяцев с момента публикации этой работы.

Подробности
avatar

[Из песочницы] Как я изобретал метод имитации отжига

Опубликовал в блог Новости IT технологий
0

Доброго времени, Хабр!

Сподвигло меня на написание этой работы прочтение «Введение в оптимизацию. Имитация отжига». Так уж сложилось, что как раз недавно я столкнулся с задачей коммивояжера и для ее решения придумал алгоритм, суть которого, как оказалось, очень близка к идее алгоритма имитации отжига, описываемого в указанной статье. Более того, там даже есть «отсылка» к моей идее, а еще похожие обсуждения велись в комментариях, потому я решил, что сообществу будет интересно посмотреть на реализацию.
Читать дальше →
avatar

Вероятность в алгоритмах. Лекция Яндекса

Опубликовал в блог Новости IT технологий
0
Многие являются детерминированными – то есть последовательность их действий зависит лишь от входных данных и программы. Но что будет, если разрешить алгоритму по ходу работы использовать случайные числа?

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


Конспект лекции
avatar

Метод погруженной границы для чайников

Опубликовал в блог Новости IT технологий
0
Отношение между «чистыми» и «прикладными математиками» основаны на доверии и понимании. «Чистые математики» не доверяют «прикладным математикам», а «прикладные математики» не понимают чистых математиков.

Некоторое время назад я столкнулся с тем, что не смог найти доступных материалов, в которых на великом и могучем описывался бы метод погруженной границы. Если в кратце, то это метод вычислительной гидродинамики, который позволяет расчитывать обтекание достаточно сложных по форме и динамике объектов. Так вот русскоязычных публикаций на эту тему было крайне недостаточно. «Не беда, будем читать работы зарубежных коллег» — подумалось мне. Но и тут ждал небольшой подвох — все имеющиеся материалы и публикации по этому методу были очень теоретичны, а мне (не уверен, возможно это не только моя особенность) обычно сложно сделать переход от теоретических выкладок к более-менее рабочему воплощению в коде. Поэтому для таких же несчастных, что и я (и с некоторой долей надежды на советы от умудренных опытом личностей) я решил сделать краткое описание этого метода и предложить самый простой способ его реализации.
Читать дальше →
avatar

Амортизационный анализ

Опубликовал в блог Новости IT технологий
0
Привет, Хабр!

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

Читать дальше...