CRDT

Mar. 13th, 2017 09:30 pm
ermouth: (ang)

Аббревиатура от Сonflict-free Replicated Data Types, https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type. Коротко, CRDT – это специальным образом задизайненные типы данных, которые позволяют гарантровать strong eventual consistency в распределённых системах. С математической точки зрения это такой дизайн данных, что:

If the system is monotonically increasing in state, clients never observe state rolling back. The set of system states is partially ordered, and the merge operation being commutative, associative and idempotent, the set of all system states is a semilattice, and the merge operation is the semilattice join.

Вполне достижимо не слишком большими усилиями, если речь не идёт о больших массивах бинарных данных, типа видео или картинок.

ermouth: (ang)
Я просто до тошноты обчитался всяким сабжевым (в смысле, про топологию), пытаясь разобраться с Нобелевкой по физике 2016, и мне теперь топологические псевдотеории прямо таки везде мерещатся.

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

Хотя мне почему-то кажется, что эмдрайв – это про ошибки измерения история.
ermouth: (Default)

Утверждение (b) на сфере, оказывается, неверно. То-есть, существует класс конструкций, в которых расстановка возможна.

frogs-23

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

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

6-я невалидна, блин.

И да, следующий пост точно будет не про лягушек )

ermouth: (Default)

Просто картинка к задаче про лягушек, но на сфере, собрал из нескольких рисунков.

frogs-12

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

ermouth: (Default)

Как водится в таких задачках, она решается в одно соображение. Решение в конце под катом, а для начала я опишу, как я это решение придумывал.

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

Сначала я пошёл сложным путём и попытался задачу генерализовать топологически, рассматривая примерно вот такие конструкции:

frogs-3

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

frogs-15

Игры с такого рода конструкциями увели меня ещё дальше в сторону примерно на неделю, плюс я тому моменту как раз недавно перечитал Пенроуза с его графическим формализмом и увидел явные аналогии – у него там расшивка скрещивания тоже меняет знак итога. Тем не менее неожиданно рассмотрение задачи на сфере дало мне решение на плоскости.

Я рассматривал случаи, когда все концы лежат в одной полусфере и обратил внимание, что для длинных дуг решение в некотором смысле берётся с обратным знаком в том случае, если заменить дуги на короткие и продолжить короткие дуги так, чтобы условия оставались в силе. Замена дуг на короткие привела меня к мысли, что удобнее рассматривать граничный случай, когда концы дуг лежат на одной геодезической (условном “экваторе”). На плоскость этот случай отображается элементарным образом:

Read more... )
ermouth: (ang)
Хорошая задачка вот с международной математической олимпиады 2016 (все задачки за все года вот тут).

Задача 6. На плоскости расположено n ⩾ 2 отрезков так, что любые два из них пересекаются по внутренней точке, а никакие три из них не имеют общей точки. Иван выбирает один из концов каждого отрезка и сажает в него лягушку лицом к другому концу этого отрезка. Затем он n − 1 раз хлопает в ладоши.

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

(a) Докажите, что Иван всегда может добиться желаемого, если n нечётно.
(b) Докажите, что Иван никогда не сможет достичь желаемого, если n чётно.

----

Есчо, справедливо и для построения на 2-сфере (типа Иван – Маленький принц и живёт на маленькой планетке с жабами ггг). Соответственно вместо отрезков – ортодромы дуги геодезических линий (не обязательно кратчайшие).
ermouth: (Default)

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

http://www.wou.edu/~girodm/library/benny.pdf

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

Китайская комната, во всей красе.

Бенни описывает свои ощущения от тестов как wild goose chase, на русский я бы это перевёл как “бесполезная движуха”. То-есть это такая игра, в которой основной результат вовсе не понимание, а проходной балл. Иными словами, основной стимул – как можно быстрее дать правильный ответ.

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

Набрёл я на этот пример с правилами Бенни в рамках диалога и размышлений о подходах работы абстрактного генератора программ по нечёткому заданию.

Затрудняюсь точно описать выводы. Как минимум, теперь я уверен, что подход, связанный с “охотой” на решение, выражаемое в рамках замкнутой символической системы, не очень то уместен как генерализованный для нейросетей.

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

Понятно, что способ начинает давать ложные результаты при расширении выборки – но мы склонны патчить имеющиеся правила (как Бенни), а не искать более общую закономерность.

Ну и related video вот, Алан Кей рассказывает про важность простоты. Там в начале хороший пример в тему – про Птолемееву систему мироустройства.

ermouth: (Default)

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

Это я контексте обдумывания IDE в VR наткнулся. Размышлял, как именно (в какой последовательности) дети лепят фигурки из пластилина и в каком порядке взрослые рисуют более-менее геометрически связанные фрагменты пространства.

Brief Overview

Снимок экрана 2016-08-02 в 2.55.11

Why TDA beats dimension reduction

Снимок экрана 2016-08-02 в 3.07.24

Ну и слайдшер с некоторыми подробностями (т.е. ключевыми словами для дальнейшего чтения)

Снимок экрана 2016-08-02 в 3.12.04

Почему-то вспомнилась классификация животных из Борхеса Ж)

Шашки

Feb. 8th, 2016 01:36 am
ermouth: (Default)

Шашки, оказывается, решены полностью в слабом смысле – то-есть посчитаны все оптимальные деревья и известно, как играть, чтобы была ничья.

“Известно, как играть, чтобы была ничья” не означает, кстати, умение выигрывать, и вот почему. Наиболее рациональной стратегией программы, “понявшей”, что ничья гарантированно достижима, вообще говоря не является скорейшее сведение партии к ничьей.

Рациональной стратегией будет поддержание потенциально ничейной позиции максимально долго, ожидая, что оппонент ошибётся.

Это прекрасное соображение, и ещё целую пачку похожих, я обнаружил как раз в публикации “Solving the Game of Checkers” по мотивам алгоритма программы Chinook.

Я пытался прикинуть схему оценки количества “мусорных” ветвей деревьев событий, совершенно, правда, в другой области – и наткнулся на эту работу, где такие соображения есть.

Картиночка вот оттуда.

Снимок экрана 2016-02-08 в 1.23.52

15 страниц PDF, хорошо вдумчиво читается за часик. Много оценок, подходов и вообще соображений общего плана – и никакой зауми.

Советую http://library.msri.org/books/Book29/files/schaeffer.pdf

ermouth: (ang)
Пришло в голову, что запрещённые властями (или правообладателями) к распространению тексты, картинки, видеоролики и тп – это произведения не только с точки зрения группового названия, но и с точки зрения арифметики.

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

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

Немного пошерстил и нашёл прекрасный термин для этого – illegal prime. Вау.
ermouth: (ang)
Очень клёвая презенташка. В середине, естественно, появляется LISP – куда ж без него )



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

GC, правда, родом из 1970 (оригинал публикации CJ Cheney) и его по нынешним временам никак эффективным не назовёшь – зато он очень простой. 
ermouth: (ang)
Прекрасное просто https://www.quantamagazine.org/20150519-will-computers-redefine-the-roots-of-math/

Про множества, теорию типов, гомотопии, эквивалентность и изоморфизм – и мой любимый HoTT, на идеях которого и построен jQuery.my.

Материал написан очень простым и доступным английским языком. Очень рекомендую.

После прочтения материала станет понятно, почему я хотел объяснять $.my через гомотопию – потому что манифест $.my устанавливает гомотопию между интерфейсом (то, что я назвал абстрактным связным пространством вот тут) и данными под ним. Таким образом, манифест $.my определяет тип, который суть эквивалентность между пространством данных и пространством интерфейса.
ermouth: (ang)

Благодаря https://nplus1.ru/news/2015/05/25/nash мне попался на глаза оригинал доказательства существования точки равновесия в играх с ненулевой суммой.

Оно выглядит так (клик – PDF с работой):

Снимок экрана 2015-05-27 в 23.00.46

Соотнесение некоторых терминов типа “product space” с, например, теорией множеств можно посмотреть в моём старом посте про HoTT, там табличка есть. Это, возможно, несколько облегчит понимание.

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

Теорему Какутани о неподвижной точке можно посмотреть в Вики, она достаточно понятна. Упрощённый механистический смысл этой теоремы – если какая-то сущность выпукла, у неё есть точка равновесия, лежащий внутри этой сущности.

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

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

Это можно объяснить даже школьникам. Очень красивое и простое доказательство, жаль, что я никогда не доходил до него раньше.

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

RIP, Джон Нэш.

J operator

May. 21st, 2015 11:51 pm
ermouth: (Default)

J – это от JUMP, “безусловный переход”, GOTO. Совершенно нехарактерная для современных высокоуровневых языков конструкция, а для функциональных – и вовсе практически табуированная.

Тем не менее, оказывается для безусловного перехода в функциональном мире есть хорошая абстракция, она называется J operator. Интересно, что ни про эту конструкцию, ни про её изобретателя – Питера Лэндина – в русской вики статей нет.

Про J operator у Лэндина есть оригинальная работа 1965 года, клик по картинке – академический PDF.

Снимок экрана 2015-05-21 в 22.56.00

Абстракция эта – довольно любопытный зверёк. Это конструкт, который превращает блок кода по метке в лямбду сохраняя её собственный scope в месте объявления, плюс перекрывая этот scope локальным к месту вызова. После этого лямбда исполняется, но вместо return-а она делает jump обратно (или куда-то ещё).

И получается, что блок кода по метке как бы исполняется по месту вызова.

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

Любопытно, что приблизительно таких свойств конструкт я выдумывал, когда делал CoverCouch. Та-же песня – совмещение scope’ов, но не в общем, а в конкретном случае (что гораздо проще), исполнение и возврат результата по месту вызова мутированием аккумулятора в scope вызова.

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

1965 год. Не перестаю удивляться.

ermouth: (Default)

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

Снимок экрана 2015-04-29 в 1.02.43

http://infolab.stanford.edu/~ullman/mmds/ch2.pdf – тут только вторая глава, сабж со страницы 14 (32).

Вся книжка – “Mining of Massive Datasets”, Jure Leskovec, Anand Rajaraman, Jeffrey D. Ullman.

ermouth: (Default)

C целью “потрогать” arrow-функции в ES6 написал вот парсер выражений в польской нотации, простенький. Работает в консоли FireFox или в io.js, больше нигде не работает.

var polish = (function () {
  var ops = "+-/*".split("").reduce((a,b)=>(a[b]=Function("x","return x[0]=x.shift()"+b+"x[0],x"),a),{});
  return (s)=>s.split(/\s+/).reduce((a,b)=>(ops[b]?ops[b](a):!isNaN(b)&&b!=''?(a.unshift(+b),a):a),[]);
})();

polish ("10 1 2 3 + + *") напишет [60].

Пожалуй, я уже хочу стрелки в js. До этого как-то они мне не родными для js казались – ну и зря.

ermouth: (Default)

“Может, это и не правда, но хорошо подмечено”. Я эту фразу вчера встретил в прекраснейшей работе Филипа Дэвиса “Are there coincidences in mathematics?”.

Вот, например, прекрасный фрагмент оттуда (не забываем, что работа 1981 года):

Снимок экрана 2015-04-27 в 23.25.23

Он на этом примере развивает мысль, что да, оно близко к целому – но всё же не целое. Однако пристальный интерес к факту, почему же оно настолько близко к целому может сам по себе стать основой открытия.

Ещё оттуда фрагмент, завершающий:

Снимок экрана 2015-04-27 в 23.32.35

Если коротко – обычно сложно найти причину совпадений, которые не выглядят невероятными. Отлично подмечено.

Иногда, правда, случается, что у совпадений причина решительно невероятная.

Например, Шокли – изобретатель планарного транзистора – в войну работал над всякой статистикой в контексте операций ВМФ. И в рамках работ по улучшению точности пеленгации обнаружил, что союзники топят немецкие подлодки гораздо чаще, чем то позволяла методика триангуляции, имевшаяся у военных.

Исследование быстро свернули, а работу засекретили – потому что немецкие подлодки союзники топили вовсе не по данным триангуляции, а по данным расшифровок переговоров (история с Энигмой, то-сё). Так что теории заговоров не наглухо бессмысленны – некоторые странные совпадения гораздо “страньше”, чем кажутся.

ermouth: (Default)

Выложил на гитхаб библиотечку ermouth/calc, которая за последние 10 лет сэкономила мне кучу денег и времени.

Библиотечка восстанавливает билинейную форму по нескольким значениям. В народном хозяйстве применение самое прямое.

Иногда известна дискретная матрица цен, прайс-лист, и нужно быстро посчитать промежуточные значения. Например вот по печати журналов (скриншотик с гитхаба):

Снимок экрана 2015-04-18 в 14.14.10

Фишка в том, что в большинстве отраслей народного хозяйства ценообразование – линейная комбинация нескольких параметров. А коль скоро она линейная комбинация, её можно более-менее точно восстановить, зная всего несколько значений.

Библиотечка позволяет скармливать ей прайсы с несколькими колонками и строками – тогда интерполятор будет… эммм… кусочно-билинейной формой, или как это правильно назвать?

Я с помощь этой библиотеки оперативно подбирал подрядчиков. У меня были наборы опорных точек для разных типографий и выбор между ними делал робот.

Нафига это нужно?

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

Аналогично с доставкой. Аналогично с оптимизацией соотношения риск/маржа. Да сплошь и рядом в самом деле.

С этой библиотечкой достаточно запросить один небольшой расчёт (или посчитать самому опорные точки) – и вся картина ценообразования ясна, больше можно не спрашивать.

Снимок экрана 2015-04-18 в 13.26.17Применимость в UI

Интерполировать можно и по одной оси. Пример такого отображения – ползунок от 1 до 1000 шириной в 100 пикселей.

Хорошо бы, чтобы первые 10 пикселей цифры шли через 1, потом через 2, потом через 5, 10 и 25. То-есть чтобы дискретность повышалась при увеличении числа.

Это получается например так http://s3-eu-west-1.amazonaws.com/cdn.cloudwall.me/demos/calc-slider.html

Ну и онлайн-калькуляторы конечно. Все, что мы сделали, используют эту библиотечку.

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

Ну и тизер в конце. Вообще, билинейная форма – это (0,2)-тензор. Но про тензоры в народном хозяйстве я в другой раз расскажу, да.

Profile

ermouth: (Default)
ermouth

July 2017

S M T W T F S
      1
2345678
9101112131415
16171819202122
23242526 272829
3031     

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 27th, 2017 04:32 am
Powered by Dreamwidth Studios