This media is not supported in your browser
VIEW IN TELEGRAM
🔥19❤9🐳3👍2👀2
О том как перемножать матрицы n×n
(I. или как метрополисом оптимально по графу на 2⁶⁴ вершин шагал)
На компьютере хорошо складывать числа, а не умножать, поэтому если бы умножать матрицы 2х2 можно было бы не за 8 умножений, а за 7, то всё стало бы немного быстрее. И в 1968 году Штрассен выяснил, что да, можно!)
Операция умножения матриц Cᵢⱼ = Aᵢₖ Bₖⱼ является билинейной и может быть переписана в виде Cᵢ = Tᵢⱼₖ Aⱼ Bₖ (сплющили матрицы в 4d векторы). Тензор Tᵢⱼₖ определяется только размерами матриц и универсален для всех (C, A, B). Осталось сделать декомпозицию тензора Tᵢⱼₖ = Σ uᵢ vⱼ wₖ по минимальному набору триад (u, v, w), а это уже NP-complete задача. Если воспринимать добавление триады как шаг на графе, а тензоры Tᵢⱼₖ как вершины, то формально мы ищем кратчайший путь в графе на 2^(n⁶) вершин степени 2^(3n²). Даже для n=2 у нас уже 2⁶⁴ вершин.
Зато можем попробовать отжиг (как тут или тут). И это работает, на графике d представлен мой процесс отжига для n=2, который по итогу 8 минут работы находит таки оптимальную декомпозицию на 7 умножений (даже 14 разных её реализаций, среди которых и аналогичная Штрассену). А на графиках a, b, c иллюстрация декомпозиции из AlphaTensor (которые своим RL понаходили такие разложения вплоть до n=5).
P.S. В комментариях можно найти минимальную реализацию отжига в пределах 100 строк)
(I. или как метрополисом оптимально по графу на 2⁶⁴ вершин шагал)
На компьютере хорошо складывать числа, а не умножать, поэтому если бы умножать матрицы 2х2 можно было бы не за 8 умножений, а за 7, то всё стало бы немного быстрее. И в 1968 году Штрассен выяснил, что да, можно!)
Операция умножения матриц Cᵢⱼ = Aᵢₖ Bₖⱼ является билинейной и может быть переписана в виде Cᵢ = Tᵢⱼₖ Aⱼ Bₖ (сплющили матрицы в 4d векторы). Тензор Tᵢⱼₖ определяется только размерами матриц и универсален для всех (C, A, B). Осталось сделать декомпозицию тензора Tᵢⱼₖ = Σ uᵢ vⱼ wₖ по минимальному набору триад (u, v, w), а это уже NP-complete задача. Если воспринимать добавление триады как шаг на графе, а тензоры Tᵢⱼₖ как вершины, то формально мы ищем кратчайший путь в графе на 2^(n⁶) вершин степени 2^(3n²). Даже для n=2 у нас уже 2⁶⁴ вершин.
Зато можем попробовать отжиг (как тут или тут). И это работает, на графике d представлен мой процесс отжига для n=2, который по итогу 8 минут работы находит таки оптимальную декомпозицию на 7 умножений (даже 14 разных её реализаций, среди которых и аналогичная Штрассену). А на графиках a, b, c иллюстрация декомпозиции из AlphaTensor (которые своим RL понаходили такие разложения вплоть до n=5).
P.S. В комментариях можно найти минимальную реализацию отжига в пределах 100 строк)
❤26🔥11
О том как перемножать матрицы n×n
(II. или о случайных блужданиях на flip-graph)
Продолжаем решать задачу о поиске оптимального алгоритм для умножения матриц (начало в посте выше). Хотим найти за наименьшее число троек (триад) n²-мерных векторов (u, v, w) разложение Tᵢⱼₖ = Σ uᵢ vⱼ wₖ . Число троек называют рангом r. Дальше правильное разложение буду обозначать за UVW(r).
Рассмотрим некоторое разложение UVW(r=n²), такое всегда существует. Если у двух триад совпадает один из векторов, то можем сделать flip и перейти к новому UVW(r). Продолжаем делать случайные флипы, пока у двух триад не совпадёт два вектора, тогда можем сделать reduction и попасть в UVW(r-1). Если к операциям добавить ещё путь к UVW(r+1), то получим образующие для flip-graph, но нам часто достаточно ходить горизонтально и вниз.
Просто случайными блужданиями по flip-графу здесь (и тут с учётом симметрий) и нашли рекордные на сегодня схемы: r=93 для n=5 и r=153 для n=6 (было 98 и 160). Интересно, можно ли как-то сделать блуждания направленными.
Мою PyTorch реализацию (ну приятно же на gpu случайно блуждать) можно потыкать на
github.com/k1242/flip-graph
(или поддержать звёздочками). Для n=3 находит оптимальные алгоритмы за 10с, а это, между прочим, поиск кратчайшего пути на графе в 2⁷²⁹ ~ 10²¹⁹ вершин :)
(II. или о случайных блужданиях на flip-graph)
Продолжаем решать задачу о поиске оптимального алгоритм для умножения матриц (начало в посте выше). Хотим найти за наименьшее число троек (триад) n²-мерных векторов (u, v, w) разложение Tᵢⱼₖ = Σ uᵢ vⱼ wₖ . Число троек называют рангом r. Дальше правильное разложение буду обозначать за UVW(r).
Рассмотрим некоторое разложение UVW(r=n²), такое всегда существует. Если у двух триад совпадает один из векторов, то можем сделать flip и перейти к новому UVW(r). Продолжаем делать случайные флипы, пока у двух триад не совпадёт два вектора, тогда можем сделать reduction и попасть в UVW(r-1). Если к операциям добавить ещё путь к UVW(r+1), то получим образующие для flip-graph, но нам часто достаточно ходить горизонтально и вниз.
Просто случайными блужданиями по flip-графу здесь (и тут с учётом симметрий) и нашли рекордные на сегодня схемы: r=93 для n=5 и r=153 для n=6 (было 98 и 160). Интересно, можно ли как-то сделать блуждания направленными.
Мою PyTorch реализацию (ну приятно же на gpu случайно блуждать) можно потыкать на
github.com/k1242/flip-graph
(или поддержать звёздочками). Для n=3 находит оптимальные алгоритмы за 10с, а это, между прочим, поиск кратчайшего пути на графе в 2⁷²⁹ ~ 10²¹⁹ вершин :)
❤16🔥8
О том как одиночные атомы фотографирую
#coldatoms #masterthesis@qdiag
Допустим вы хотите сфотографировать атом, один. Естественным было бы посветить на него из лазера резонансным светом и собрать флюоресцирующие фотоны. Но каждый раз поглощая фотон, атом получает толчок на h/λ в одну сторону (дрейф). К тому же излучая фотон атом толкается на h/λ в случайную сторону (диффузия). Естественно было бы убрать дрейф, если светить с двух сторон. И это оказывается ужасной идеей!
Атомы сидят в решётке, достаточно близко к друг другу, поэтому хочется и дрейф и диффузию уменьшить. На fig 2b(left) видно как со временем атом сдувает вправо, fig 2b(middle) мы пробуем светить с двух сторон и атом очень быстро убегает от центра (в комментариях объяснение). Решением будет светить с двух сторон по очереди (fig 2a, fig 2b(right)), тогда атом и в среднем с нулевым импульсом и от центра далеко не уходит.
И теперь можно получить замечательные фотографии, как на fig 4b(left). От каждого атома до камеры у нас доходит около 30 фотонов, и этого оказывается достаточно, чтобы их найти в 99% случаев. Немного поработав с фотографией, получается fig 4b(right), где каждый атом это такое синее пятнышко.
P.S. У меня через полтора месяца диплом, так что буду рассказывать вам про графики из диплома)
#coldatoms #masterthesis@qdiag
Допустим вы хотите сфотографировать атом, один. Естественным было бы посветить на него из лазера резонансным светом и собрать флюоресцирующие фотоны. Но каждый раз поглощая фотон, атом получает толчок на h/λ в одну сторону (дрейф). К тому же излучая фотон атом толкается на h/λ в случайную сторону (диффузия). Естественно было бы убрать дрейф, если светить с двух сторон. И это оказывается ужасной идеей!
Атомы сидят в решётке, достаточно близко к друг другу, поэтому хочется и дрейф и диффузию уменьшить. На fig 2b(left) видно как со временем атом сдувает вправо, fig 2b(middle) мы пробуем светить с двух сторон и атом очень быстро убегает от центра (в комментариях объяснение). Решением будет светить с двух сторон по очереди (fig 2a, fig 2b(right)), тогда атом и в среднем с нулевым импульсом и от центра далеко не уходит.
И теперь можно получить замечательные фотографии, как на fig 4b(left). От каждого атома до камеры у нас доходит около 30 фотонов, и этого оказывается достаточно, чтобы их найти в 99% случаев. Немного поработав с фотографией, получается fig 4b(right), где каждый атом это такое синее пятнышко.
P.S. У меня через полтора месяца диплом, так что буду рассказывать вам про графики из диплома)
🔥27❤17
Про что ещё вам интересно было бы узнать?
Anonymous Poll
49%
Как сфотографировать атомы с учётом их спина
40%
Как подготовить заданное число очень холодных атомов
32%
Как раздуть систему реализовав ψ(r) → ψ(r/magnification)
51%
Что с атомами потом делать
55%
Про оборудование, которым это все делается (e.g. акустооптика)
1%
(свой вариант в комментариях)
О том как одиночные атомы фотографирую (spin-resolved)
#coldatoms #masterthesis@qdiag
Всё это происходит в рамках аналогового квантового симулятора, когда систему электронов, моделируем системой атомов. И на самом деле электроны разного спина |↑⟩ и |↓⟩ это скорее просто [1] два различимых типа фермионов. Так что чтобы воспроизвести это на атомах достаточно иметь два различимых типа фермионных атомов, что достигается просто положением электрона у них в двух разных конфигурациях.
На fig 1 видна система уровней ⁶Li и их расщепление во внешнем магнитном поле. Удобно работать с атомами, когда они находятся в |1⟩ и |2⟩ состояниях [2], где мы их и приготавливаем. А потом для фотографирования мы через две антенны (радиоволновую и микроволновую) отправляем их в stretched состояния |3⟩ и |6⟩.
Когда светим на атомы резонансным светом (смесью σ₊ и σ₋ поляризаций), они флуоресцируют, и |3⟩ в σ₋, а |6⟩ в σ₊. Остается поставить λ/4 пластинку и поляризационный кубик, и мы пространственно разделили свет от двух разных спинов. Сфокусировав свет на разных областях камеры получаем fig 5.
P.S. Через [1], [2] отметил места, которые поясню в комментариях.
P.P.S. Если хотите дать обратную связь, то пусть ничего непонятно это 👀, а понятно это 🐳
#coldatoms #masterthesis@qdiag
Всё это происходит в рамках аналогового квантового симулятора, когда систему электронов, моделируем системой атомов. И на самом деле электроны разного спина |↑⟩ и |↓⟩ это скорее просто [1] два различимых типа фермионов. Так что чтобы воспроизвести это на атомах достаточно иметь два различимых типа фермионных атомов, что достигается просто положением электрона у них в двух разных конфигурациях.
На fig 1 видна система уровней ⁶Li и их расщепление во внешнем магнитном поле. Удобно работать с атомами, когда они находятся в |1⟩ и |2⟩ состояниях [2], где мы их и приготавливаем. А потом для фотографирования мы через две антенны (радиоволновую и микроволновую) отправляем их в stretched состояния |3⟩ и |6⟩.
Когда светим на атомы резонансным светом (смесью σ₊ и σ₋ поляризаций), они флуоресцируют, и |3⟩ в σ₋, а |6⟩ в σ₊. Остается поставить λ/4 пластинку и поляризационный кубик, и мы пространственно разделили свет от двух разных спинов. Сфокусировав свет на разных областях камеры получаем fig 5.
P.S. Через [1], [2] отметил места, которые поясню в комментариях.
P.P.S. Если хотите дать обратную связь, то пусть ничего непонятно это 👀, а понятно это 🐳
🔥14❤6👀5🐳4👍2
О том какие на улице бывают лампы
(или о дифракции в домашних условиях)
Ночь, улица, фонарь, дождь, белый и монохроматичный свет.
Сегодня вечером от дождя на очках у меня образовались капельки, которые вполне себе неплохие линзы. И всматриваясь в сторону желтых ламп увидел характерные дифракционные паттерны. Действительно, теплый свет на улице зачастую идет от натриевых ламп высокого давления, спектр которых имеет узкий пик на 589 нм (дублет D-линий натрия).
Сфотографировав уличную лампу через очки с капельками, получаем прекрасную демонстрацию волновой природы света. На графике как раз приведен получившийся на капельке паттерн дифракции на полуплоскости!
P.S. Совсем другая история с белыми лампами, гораздо более широкого спектра. Белый свет составной, у разных длин волн максимумы будут в разных местах, из-за чего дифракционная картинки размывается и становится околонулевой контрастности. Вы можете разглядеть первый максимум, а вот потом всё. Для натриевой лампы, для сравнения, было видно около 7 осцилляций.
(или о дифракции в домашних условиях)
Ночь, улица, фонарь, дождь, белый и монохроматичный свет.
Сегодня вечером от дождя на очках у меня образовались капельки, которые вполне себе неплохие линзы. И всматриваясь в сторону желтых ламп увидел характерные дифракционные паттерны. Действительно, теплый свет на улице зачастую идет от натриевых ламп высокого давления, спектр которых имеет узкий пик на 589 нм (дублет D-линий натрия).
Сфотографировав уличную лампу через очки с капельками, получаем прекрасную демонстрацию волновой природы света. На графике как раз приведен получившийся на капельке паттерн дифракции на полуплоскости!
P.S. Совсем другая история с белыми лампами, гораздо более широкого спектра. Белый свет составной, у разных длин волн максимумы будут в разных местах, из-за чего дифракционная картинки размывается и становится околонулевой контрастности. Вы можете разглядеть первый максимум, а вот потом всё. Для натриевой лампы, для сравнения, было видно около 7 осцилляций.
❤36🔥13
Как вы думаете, чему равна лучшая известная вычислительная сложность умножения двух n-bitных чисел?
Anonymous Quiz
9%
O(n²)
34%
O(n^1.58)
34%
O(n × log n)
24%
O(n × log n × log log n)
🔥6❤5
Графики каждый день (почти)
Как вы думаете, чему равна лучшая известная вычислительная сложность умножения двух n-bitных чисел?
О том как числа быстро перемножать
(или о Карацубе и FFT)
Наивная реализация столбиком требует O(n²) операций. Но давайте разобьём числа на две части длины m=n/2:
(2ᵐa₀+a₁)(2ᵐb₀+b₁) = 2ⁿ(a₀b₀)+2ᵐ(a₀b₁+a₁b₀)+2⁰(a₁b₁)
Итого вместо одного n-bit умножения, у нас четыре (n/2)-bit умножения, пока чуда не случилось. Но давайте перегруппируем (как тут для матриц)
a₀b₁+a₁b₀=(a₀+a₁)(b₀+b₁) - a₀b₀ - a₁b₁
И у нас получилось уже всего три (n/2)-bit умножения! Повторяя процедуру рекурсивно получим алгоритм Карацубы 1960 года работающий за О(n^log₂3), то есть О(n^1.58).
Мы могли разбить числа не на две части, а например на n/8 частей длины 8 bit. Тогда результат умножения двух чисел это результат умножения двух полиномов с основанием х=2⁸. А это можно сделать эффективно через FFT за O(n log n), что и предложили в 1968 году. Правда, как понял, накладные расходы на Фурье приводили к O(n × log n × log log n), так что формально только в 2019 году была опубликована реализация за O(n × log n), но это представляло больше теоретический интерес, на практике используют версию 1968 года)
P.S. Про FFT и умножение полиномов очень советую этот элегантный рассказ, а потом тут можете найти подробнее про Карацубу)
P.P.S. Алгоритм 1968 года это работа того же Штрассена, что и предложил способ умножать матрицы за O(n^2.8)
(или о Карацубе и FFT)
Наивная реализация столбиком требует O(n²) операций. Но давайте разобьём числа на две части длины m=n/2:
(2ᵐa₀+a₁)(2ᵐb₀+b₁) = 2ⁿ(a₀b₀)+2ᵐ(a₀b₁+a₁b₀)+2⁰(a₁b₁)
Итого вместо одного n-bit умножения, у нас четыре (n/2)-bit умножения, пока чуда не случилось. Но давайте перегруппируем (как тут для матриц)
a₀b₁+a₁b₀=(a₀+a₁)(b₀+b₁) - a₀b₀ - a₁b₁
И у нас получилось уже всего три (n/2)-bit умножения! Повторяя процедуру рекурсивно получим алгоритм Карацубы 1960 года работающий за О(n^log₂3), то есть О(n^1.58).
Мы могли разбить числа не на две части, а например на n/8 частей длины 8 bit. Тогда результат умножения двух чисел это результат умножения двух полиномов с основанием х=2⁸. А это можно сделать эффективно через FFT за O(n log n), что и предложили в 1968 году. Правда, как понял, накладные расходы на Фурье приводили к O(n × log n × log log n), так что формально только в 2019 году была опубликована реализация за O(n × log n), но это представляло больше теоретический интерес, на практике используют версию 1968 года)
P.S. Про FFT и умножение полиномов очень советую этот элегантный рассказ, а потом тут можете найти подробнее про Карацубу)
P.P.S. Алгоритм 1968 года это работа того же Штрассена, что и предложил способ умножать матрицы за O(n^2.8)
❤18🔥6👍3
Я тут сделал небольшую головоломку (и мой первый сайт)!
Но пока не понимаю как оценивать сложность получающихся задач. Можно регулировать размер доски и количество слагаемых, но даже когда они зафиксированы всё равно возникают задачи очень разной сложности.
Если некоторая конфигурация покажется особенно интересной, то можете прислать код задачи (есть в настройках) через feedback. Можете попробовать решить
P.S. Внизу показаны миникарточки слоёв, они выбираются нажатием. Итоговый результат получается через их сумму (по mod 2 или булеву).
Но пока не понимаю как оценивать сложность получающихся задач. Можно регулировать размер доски и количество слагаемых, но даже когда они зафиксированы всё равно возникают задачи очень разной сложности.
Если некоторая конфигурация покажется особенно интересной, то можете прислать код задачи (есть в настройках) через feedback. Можете попробовать решить
841204FBA4F939366B3. Буду рад обратной связи)P.S. Внизу показаны миникарточки слоёв, они выбираются нажатием. Итоговый результат получается через их сумму (по mod 2 или булеву).
🔥18❤7👍1
khoruzhii-thesis.pdf
7.5 MB
Закончил магистрский диплом!
По мотивам некоторых постов выше сложился диплом про кусочки аналогового симулятора для Ферми-Хаббарда. Я, из основного, сделал штуку которая фотографирует отдельные атомы (с учётом их электронной конфигурации), написал для неё ПО, написал ПО для штуки которая управляет двухмерным массивом оптических пинцетов и придумал как в них загружать произвольные конфигурации атомов с учётом их спина, так раньше не умели. А ещё написал под GPU пакет для численного моделирования многочастичной системы.
Я доволен)
P.S. К слову игра BMF как раз возникла в контексте задачи загрузки массива пинцетов.
По мотивам некоторых постов выше сложился диплом про кусочки аналогового симулятора для Ферми-Хаббарда. Я, из основного, сделал штуку которая фотографирует отдельные атомы (с учётом их электронной конфигурации), написал для неё ПО, написал ПО для штуки которая управляет двухмерным массивом оптических пинцетов и придумал как в них загружать произвольные конфигурации атомов с учётом их спина, так раньше не умели. А ещё написал под GPU пакет для численного моделирования многочастичной системы.
Я доволен)
P.S. К слову игра BMF как раз возникла в контексте задачи загрузки массива пинцетов.
❤59🔥28👍4
Возьмем граф с изначально нулевыми весами ребер. Найдем в нем любое минимальное остовное дерево. Увеличим вес каждого ребра в этом дереве на 1. Снова найдем минимальное остовное дерево относительно новых весов, и снова увеличим вес каждого ребра в этом дереве на 1, и так далее.
Пусть для ребра е, x_е — это доля деревьев, содержащих е. Будет ли в таком процессе предел у величин x_e, и если да, то что это за точка?
Оказывается, предел есть. Его можно описать через оптимальные разбиения графа (2007), и он супер важен для алгоритма динамического минимального разреза.
Но этот предел можно описать более геометрично: это проекция нуля на политоп остовных деревьев. То есть, точка в выпуклой оболочке индикаторных векторов всех возможных остовных деревьев, у которой наименьшая норма.
На графиках показано, как убывает погрешность х с количеством деревьев.
Пусть для ребра е, x_е — это доля деревьев, содержащих е. Будет ли в таком процессе предел у величин x_e, и если да, то что это за точка?
Оказывается, предел есть. Его можно описать через оптимальные разбиения графа (2007), и он супер важен для алгоритма динамического минимального разреза.
Но этот предел можно описать более геометрично: это проекция нуля на политоп остовных деревьев. То есть, точка в выпуклой оболочке индикаторных векторов всех возможных остовных деревьев, у которой наименьшая норма.
На графиках показано, как убывает погрешность х с количеством деревьев.
👍12🔥8❤3
О гамильтониане Ферми-Хаббарда
(fermions vs. hard-bosons)
Недавно делал семинар по численным методам, в том числе с ответом на вопрос о разнице между хард-бозонами и фермионами. Мы рассматриваем частицы на решётке. Если взять бозоны и выкрутить энергию на узле в +∞, то эффективно числа заполнения будут {0,1}, как и у фермионов. Будет ли в плане динамики между ними разница?
Разница будет, если у нас случится перепрыгивание одной частицы через другую (второй слайд) — в матричном элементе гамильтониана возникнет знак минус. Действительно, мы можем рассматривать базисные состояния, как вакуум на который подействовали операторами рождения (первый слайд). А если происходит такое туннелирование, то нужно упорядочить состояние, чтобы выразить результат через наш базис. Для бозонов на разных узлах операторы коммутируют и про упорядочивание можно не думать, а вот для фермионов они антикоммутируют
К слову в одномерном случае таких перепрыгиваний не будет, так что гамильтонианы будут идентичными. Это позволяет сводить 1d спиновые цепочки к невзаимодействующим фермионам (Jordan-Wigner transforamation), которые легко решаются)
P.S. Да, фермионы подразумевал спин-поляризованные (неразличимые)
(fermions vs. hard-bosons)
Недавно делал семинар по численным методам, в том числе с ответом на вопрос о разнице между хард-бозонами и фермионами. Мы рассматриваем частицы на решётке. Если взять бозоны и выкрутить энергию на узле в +∞, то эффективно числа заполнения будут {0,1}, как и у фермионов. Будет ли в плане динамики между ними разница?
Разница будет, если у нас случится перепрыгивание одной частицы через другую (второй слайд) — в матричном элементе гамильтониана возникнет знак минус. Действительно, мы можем рассматривать базисные состояния, как вакуум на который подействовали операторами рождения (первый слайд). А если происходит такое туннелирование, то нужно упорядочить состояние, чтобы выразить результат через наш базис. Для бозонов на разных узлах операторы коммутируют и про упорядочивание можно не думать, а вот для фермионов они антикоммутируют
AB=-BA. Так что когда фермион туннелирует, то в матричном элементе возникает множитель (-1)^{# частиц через которые перепрыгнули}.К слову в одномерном случае таких перепрыгиваний не будет, так что гамильтонианы будут идентичными. Это позволяет сводить 1d спиновые цепочки к невзаимодействующим фермионам (Jordan-Wigner transforamation), которые легко решаются)
P.S. Да, фермионы подразумевал спин-поляризованные (неразличимые)
❤13🔥5
Как генерировать (плохие) разрезы графов с помощью случайных деревьев
Возьмем граф - квадратную сетку n на n. Сгенерируем в нем случайное остовное дерево*. На первой картинке цветом показано расстояние от данной вершины до вершины в левом верхнем углу, если двигаться по ребрам дерева.
Для разреза графа определим sparsity как значение (количество разрезанных ребер)/(количество вершин в меньшей части). Нахождение sparsest cut — это известная NP-сложная задача.
На второй картинке показан разрез графа с наибольшей sparsity, который пересекается нашим остовным деревом ровно один раз. Насколько хорошее приближение у нас получилось? Спойлер: совсем не хорошее.
Полученная sparsity убывает как n^-0.75 (третья картинка). Минимальная sparsity равна 2 / n.
Зато можно сказать, что граница разреза имеет размерность Хаусдорфа 1.25 (в пределе мелкой сетки). Интересно, что такая же размерность у loop-erased random walk. Будет интересно, если кто-то докажет равенство этих размерностей.
Возьмем граф - квадратную сетку n на n. Сгенерируем в нем случайное остовное дерево*. На первой картинке цветом показано расстояние от данной вершины до вершины в левом верхнем углу, если двигаться по ребрам дерева.
Для разреза графа определим sparsity как значение (количество разрезанных ребер)/(количество вершин в меньшей части). Нахождение sparsest cut — это известная NP-сложная задача.
На второй картинке показан разрез графа с наибольшей sparsity, который пересекается нашим остовным деревом ровно один раз. Насколько хорошее приближение у нас получилось? Спойлер: совсем не хорошее.
Полученная sparsity убывает как n^-0.75 (третья картинка). Минимальная sparsity равна 2 / n.
Зато можно сказать, что граница разреза имеет размерность Хаусдорфа 1.25 (в пределе мелкой сетки). Интересно, что такая же размерность у loop-erased random walk. Будет интересно, если кто-то докажет равенство этих размерностей.
❤16🔥5
О сложности судоку
(или о хороших головоломках)
Что значит, что задача сложная? Возьмём к примеру судоку. С точки зрения компьютера мы могли бы запустить DFS и дальше размер дерева поиска решения и был бы сложностью. То есть пробуем поставить в пустой квадрат цифру, двигаемся дальше и если приходим к противоречию, то понимаем ошибочность предположения. Guess and try. Но делать так самому не очень интересно.
Вообще хорошее судоку составлено так, что каждый следующий шаг может быть получен из некоторых логических соображений. Например на картинке видно, что в одном из жёлтых квадратов должна стоять 6, поэтому в зелёном её быть не может — там 3. Так что решение сводится к тому что ищется некоторый паттерн, и если нашли то можем уменьшить пространство вариантов (хороший зоопарк паттернов).
Получается сложность сводится к самому сложному паттерну, необходимого для решения. Так и сделал у себя на сайте (картинка с него же). Делаем солвер с техниками (или берём готовый): генерируем возможное заполнение (их всего 5.5B с точностью до симметрий), убираем подсказки до минимального набора (убрать любую следующую приведёт к потере единственности решения) и дальше смотрим каким набором паттернов это решается.
В общем предлагаю вниманию мой минималистичный сайт с 5 уровнями сложности и автоматизированными заметками (включите в настройках prefill, auto clear и нажмите new game):
https://qdiag.xyz/sudoku/
(или о хороших головоломках)
Что значит, что задача сложная? Возьмём к примеру судоку. С точки зрения компьютера мы могли бы запустить DFS и дальше размер дерева поиска решения и был бы сложностью. То есть пробуем поставить в пустой квадрат цифру, двигаемся дальше и если приходим к противоречию, то понимаем ошибочность предположения. Guess and try. Но делать так самому не очень интересно.
Вообще хорошее судоку составлено так, что каждый следующий шаг может быть получен из некоторых логических соображений. Например на картинке видно, что в одном из жёлтых квадратов должна стоять 6, поэтому в зелёном её быть не может — там 3. Так что решение сводится к тому что ищется некоторый паттерн, и если нашли то можем уменьшить пространство вариантов (хороший зоопарк паттернов).
Получается сложность сводится к самому сложному паттерну, необходимого для решения. Так и сделал у себя на сайте (картинка с него же). Делаем солвер с техниками (или берём готовый): генерируем возможное заполнение (их всего 5.5B с точностью до симметрий), убираем подсказки до минимального набора (убрать любую следующую приведёт к потере единственности решения) и дальше смотрим каким набором паттернов это решается.
В общем предлагаю вниманию мой минималистичный сайт с 5 уровнями сложности и автоматизированными заметками (включите в настройках prefill, auto clear и нажмите new game):
https://qdiag.xyz/sudoku/
❤13🔥10
Фракталы Ньютона
(возвращение к старому)
Маленькая, но довольно интересная вещь.
Напоминание:
Метод Ньютона для поиска корней функции f(x) заключается в последовательном применении к некоторому исходному значению x₀ отображения
xₙ₊₁ = xₙ – f(xₙ) / f'(xₙ).
При "хороших" f и x₀ последовательность {xₙ} сходится к одному из корней f.
Если применять метод Ньютона для
f(x) = x² + 1,
начав с некоторого вещественного x₀, то вроде бы ничего особо интересного не получим. Точки будут скакать туда-сюда (рис. 1).
Но метод Ньютона работает много над какими полями, в частности над комплексными числами.
Если начать с
x₀ = 1 + i,
последовательность быстро сойдётся к i (рис. 2), а если, скажем, с
x₀ = 5 – 2i,
то к –i (рис. 3).
Несложно доказать, что области, откуда последовательность будет приходить в соответствующий корень, выглядят очень просто: это верхняя и нижняя полуплоскость.
На рис. 4 каждая точка из решётки, приближающей квадрат со стороной 2 вокруг нуля, окрашена в цвет, отвечающий тому корню, куда придёт последовательность.
Этот результат понятен, и ясно, как обобщить его на произвольный многочлен второй степени.
А что будет, если корней больше?
Получатся (просто по определению) множества Фату для рассматриваемого отображения. Это фрактальные множества, которые можно нарисовать численно, просто беря точки из решётки.
Два примера показаны на рис. 5 и 6.
Можно заметить, что отображения всегда выглядят довольно просто:
xₙ₊₁ = xₙ – ( Σᵢ (xₙ – rᵢ)⁻¹ )⁻¹,
где {rᵢ} — корни f.
Точки, не попавшие ни в одно из этих множеств Фату, образуют множество Жюлиа (рис. 7 и 8). В самом первом примере это множество было просто вещественной осью (это, разумеется, самый лучший одномерный фрактал).
Описанные картины называются (довольно естественно) фракталами Ньютона.
В комментариях .nb, в котором можно построить что-нибудь своё. Правда, вы не найдёте там каких-то продвинутых погромистских методов.
(возвращение к старому)
Маленькая, но довольно интересная вещь.
Напоминание:
Метод Ньютона для поиска корней функции f(x) заключается в последовательном применении к некоторому исходному значению x₀ отображения
xₙ₊₁ = xₙ – f(xₙ) / f'(xₙ).
При "хороших" f и x₀ последовательность {xₙ} сходится к одному из корней f.
Если применять метод Ньютона для
f(x) = x² + 1,
начав с некоторого вещественного x₀, то вроде бы ничего особо интересного не получим. Точки будут скакать туда-сюда (рис. 1).
Но метод Ньютона работает много над какими полями, в частности над комплексными числами.
Если начать с
x₀ = 1 + i,
последовательность быстро сойдётся к i (рис. 2), а если, скажем, с
x₀ = 5 – 2i,
то к –i (рис. 3).
Несложно доказать, что области, откуда последовательность будет приходить в соответствующий корень, выглядят очень просто: это верхняя и нижняя полуплоскость.
На рис. 4 каждая точка из решётки, приближающей квадрат со стороной 2 вокруг нуля, окрашена в цвет, отвечающий тому корню, куда придёт последовательность.
Этот результат понятен, и ясно, как обобщить его на произвольный многочлен второй степени.
А что будет, если корней больше?
Получатся (просто по определению) множества Фату для рассматриваемого отображения. Это фрактальные множества, которые можно нарисовать численно, просто беря точки из решётки.
Два примера показаны на рис. 5 и 6.
Можно заметить, что отображения всегда выглядят довольно просто:
xₙ₊₁ = xₙ – ( Σᵢ (xₙ – rᵢ)⁻¹ )⁻¹,
где {rᵢ} — корни f.
Точки, не попавшие ни в одно из этих множеств Фату, образуют множество Жюлиа (рис. 7 и 8). В самом первом примере это множество было просто вещественной осью (это, разумеется, самый лучший одномерный фрактал).
Описанные картины называются (довольно естественно) фракталами Ньютона.
В комментариях .nb, в котором можно построить что-нибудь своё. Правда, вы не найдёте там каких-то продвинутых погромистских методов.
👍13🔥4❤1