#трэш #математично #лекториум #математика #боян
https://youtu.be/mqAf5lOJZew

Новая заявка на решение задачи P vs. NP

На днях Норберт Блюм опубликовал на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия, за которую кроме почестей полагается 1 миллион долларов.


Проблему равенства классов P и NP можно неформально определить следующим образом:

Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти? Задачи первого типа относятся к классу P, второго — к классу NP. Проблема равенства этих классов является одной из важнейших проблем теории алгоритмов. (Wikipedia)

#теория_сложности #p_v_ np #математика #логика #алгоритмы
https://telegra.ph/Novaya-zayavka-na-reshenie-zadachi-P-vs-NP-08-18

Табличку, известную под номером Plimpton 322, обнаружили в начале ХХ века на территории современного Ирака. Более ста лет ее назначение оставалось загадкой. Ученые из Университета Нового Южного Уэльса заявили, что им удалось идентифицировать знаки на табличке. По словам ученых, она описывает соотношения сторон прямоугольных треугольников.

Табличка датирована периодом от 1822 до 1762 года до н.э. Более ранние исследования показали, что на ней изображены числа в четыре столбца. Было принято считать, что табличка служила либо «тетрадью» ученику, либо «шпаргалкой» учителю, проверявшему решения уравнений.

В записях использована шестидесятеричная система счисления, которую Вавилон унаследовал от шумеров

Авторы новой работы пришли к выводу, что табличка содержит список пифагоровых троек — наборов из трех натуральных чисел, удовлетворяющих уравнению a2 + b2 = c2. В самую известную из таких троек входят числа 3, 4 и 5. Это соотношение еще до Пифагора использовалось для построения прямых углов.

Левый край таблички не сохранился. Ученые предполагают, что изначально она состояла из шести столбцов чисел и 38 строк. Таблица содержит относительно большие числа: например, первую сохранившуюся тройку образуют числа 119, 120 и 169.

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

#археология #шумеры #математика #история
https://naked-science.ru/article/sci/vavilonskaya-glinyanaya-tablichka

Численное моделирование помогло найти такую форму двумерной лужайки, с которой кузнечику с наибольшей вероятностью не удастся выпрыгнуть за один прыжок. Решение задачи поможет при решении фундаментальных проблем квантовой физики, связанных с нарушением неравенств Белла, пишут авторы статьи в Proceedings of the Royal Society A.

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

#физика #моделирование #математика #монте_карло
https://nplus1.ru/news/2017/11/23/grasshopper-problem

@alexanderdyakonov очень понятно и со вкусом объясняет что такое логистическая фукция ошибки, как её готовить и зачем она нужна
Вообще его блог можно уже издавать отдельной книгой как методичку по #ML, всем категорически рекомендую

#моделирование #математика #машинное_обучение
https://alexanderdyakonov.wordpress.com/2018/03/12/логистическая-функция-ошибки/

Физики из Канады нашли способ искать плотные подграфы с помощью бозонных, точнее, фотонных семплеров. Звучит как абзац из романа Питера Уоттса? Сейчас попробуем расшифровать.

Читая текст ниже, держите в голове, что любое упрощение — это только часть правды )

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

Одним из решений проблемы (кроме, очевидно, залить недостатки деньгами) стало построение специализированных вычислительных узлов, которые умеют что-то одно, но хорошо, быстрее классических компьютеров. Так вот, фотонные семплеры – это и есть одно из семейств таких узлов.

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

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

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

#физика #кванты #симуляция #квантовый_компьютер #квантовые_вычисления #вычисления #математика #графы

#физика #кванты #симуляция #квантовый_компьютер #квантовые_вычисления #вычисления #математика #графы
https://nplus1.ru/news/2018/07/23/boson-DkS

О шлягерах и попсе среди певчих птиц.

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

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

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

Для того, чтобы выяснить это, биологи построили несколько симуляций эволюции птичьих песен, а потом сравнили результаты с экспериментальными замерами, в том числе и с записями 1976-1978 годов, и оказалось, что за 40 лет из 19 слогов изменилось всего пара. По оценкам учёных, возраст многих слогов превышает 500 лет, а значит Эрик Рыжий вполне имел все шансы слышать те же трели, что исполняют зонотрихии сегодня.

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

#биология #птицы #эволюция #теория_вероятностей #вычисления #математика
https://telegra.ph/Konformizm-na-strazhe-tradicii-pesni-bolotnoj-zonotrihii-mogut-ne-menyatsya-stoletiyami-07-29

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

Почитайте комментарии, они тоже интересные :3

Примерно 15 минут

#математика #теория_вероятностей #статистика #байесианство #образование #MLE #MAP
https://alexanderdyakonov.wordpress.com/2018/07/30/байесовский-подход/

Наконец-то математики всерьёз взялись за машинное обучение.

Представьте, что у вас есть сайт, который посещает большая популяция людей X. Вы хотите разместить на сайте рекламный баннер из множества A. Каждый баннер из этого множества соответствует какому-то подмножеству посетителей FA ⊆ X. Каждый посетитель может принадлежать нескольким подмножествам: например, он может быть программистом, любителем котиков и читателем фантастики. У вас есть набор тренировочных данных, на которых вы обучаете своей ML-оракул. Ваша задача найти такой баннер, который удовлетворяет вкусам большинства пользователей.

Так вот, группа математиков, опираясь на теорему Гёделя о неполноте, доказали, что эту невозможно доказать или опровергнуть саму возможность решения этой задачи. Это фундаментальное ограничение, которое нельзя обойти, используя общепринятые базовые аксиомы математики.

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

#математика #ML #интеллект #доказательство #IT
https://nplus1.ru/news/2019/01/21/machine-not-always-learning

В 1950-х годах советский математик Андрей Колмогоров выдвинул гипотезу о том, что сложность перемножения чисел всегда пропорциональна N². О том, как преодолевали этот порог сложности, и почему это важно для обычных людей рассказывает переводная статья от Дмитрия Иванова

#математика #алгоритмы
https://nplus1.ru/blog/2019/04/15/how-to-multiply-big-numbers