Почему такая компания, как Twitter, заинтересована в алгебраических понятиях, таких как группы, моноиды и кольца? Смотрите их репозиторий на github: twitter / algebird .
Все, что я мог найти, это:
Реализации Monoids для интересных алгоритмов аппроксимации, таких как фильтр Блума , HyperLogLog и CountMinSketch . Они позволяют вам думать об этих изощренных операциях, как о числах, которые вы можете, и складывать их в hadoop или онлайн для получения мощной статистики и аналитики.
и в другой части страницы GitHub:
Первоначально он был разработан как часть Scalding's Matrix API, где у Matrices были значения, которые являются элементами Monoids , Groups или Rings . Впоследствии стало ясно, что код имеет более широкое применение в Scalding и других проектах в Twitter.
Чем может быть это более широкое приложение? в твиттере и для общего интереса?
Кажется, что составные агрегаты баз данных имеют моноидную структуру.
Тот же вопрос по Quora: Каков интерес Твиттера к абстрактной алгебре (с algebird)?
У меня математическое образование, но я не ученый. Было бы здорово иметь в реальном мире моноиды и полугруппы. Обычно они считаются бесполезными теоретическими конструкциями и игнорируются во многих курсах по абстрактной алгебре (из-за отсутствия чего-либо интересного сказать).
algebird
библиотеке, в Твиттере: twitter.com/posco/status/300692719561482240Ответы:
Основной ответ заключается в том, что, используя полугрупповую структуру, мы можем создавать системы, которые правильно распараллеливаются, не зная основной операции (пользователь обещает ассоциативность).
Используя моноиды, мы можем воспользоваться разреженностью (мы имеем дело с множеством разреженных матриц, где почти все значения равны нулю в некотором моноиде).
Используя Кольца, мы можем делать умножение матриц на вещи, отличные от чисел (что мы иногда делали).
Сам проект algebird (а также история проблем) довольно четко объясняет, что здесь происходит: мы создаем множество алгоритмов для агрегирования больших наборов данных, а использование структуры операций дает нам выигрыш в системной части. (что обычно является основной проблемой при попытке реализовать алгоритмы на тысячах узлов).
Решите системные проблемы один раз для любой полугруппы / моноида / группы / кольца, и тогда вы сможете подключить любой алгоритм, не думая о Memcache, Hadoop, Storm и т. Д.
источник
Моноиды вездесущи в программировании, просто большинство программистов не знают о них.
Некоторые другие операции образуют не моноиды, а полугруппы. Хорошим примером является поиск минимального элемента последовательности элементов: представляет минимум a и b относительно некоторого заданного порядка.a⋅b a b
Поскольку моноиды являются настолько общими, они позволяют писать очень общие функции. Например, сворачивание структуры данных может быть выражено как отображение каждого ее элемента в моноид и затем использование моноидальной операции для объединения их в один результат.
Другой хороший и очень общий пример - обобщение возведения в степень путем возведения в квадрат моноидов (или полугрупп). Мы можем написать одну функцию, которая вычисляет только в O ( log n ) операциях. Применяя его к разным моноидам, получаем:a⋅…⋅an−times O(logn)
Дополнительные примеры см. В разделе Примеры моноидов / полугрупп в программировании .
источник
Одной из важных проблем в распределенных файловых системах ( DFS ) является создание файлов из распределенных блоков. Область кода Erasure из теории информации и алгебры (группы, кольца, линейная алгебра, ...) широко используется в распределенных отказоустойчивых файловых системах, например в HDFS RAID (файловая система на основе Hadoop). Социальные сети и облачные компании в значительной степени основаны на DFS, поэтому им нужны люди, владеющие Алгеброй и Erasure Code, для разработки более совершенных и высокопроизводительных систем (таких как коды Рида-Соломона и т. Д.).
Это также хороший плакат для их применения (алгебры) в облачном хранилище: новые коды для облачного хранилища
источник
Если ваш вопрос
Хотя это может показаться только теоретическим с алгебраической точки зрения, оно позволяет нам использовать очень сильно оптимизированные библиотеки линейной алгебры для задач с графами. Комбинаторный BLAS является одной из таких библиотек.
источник
В свою очередь, из соображений формальных языков был получен парсер Earley, который можно расширить для анализа полуколец . Это полезно при обработке естественного языка и других областях, использующих стохастические модели для (формальных) языков.
источник
Слишком много интересного сказать. Однако это больше тема дискретной математики и комбинаторики, чем абстрактной алгебры и анализа, по крайней мере, для менее тривиальных тем. Существует также вопрос, как много вы должны знать об определенной теме, прежде чем вы сможете сказать кому-то еще, что это будет интересная математическая тема, связанная с моноидами и полугруппами. Например, мне интересны следующие темы (связанные с полугруппами):
Знаю ли я много о каждой из этих тем? Возможно нет. Есть также много других математических тем, связанных с моноидами и полугруппами, некоторые из них являются более внутренними по отношению к самой теории полугрупп (например, отношения Грина), другие являются более общими и не специфичными для полугрупп (универсальные полугруппы, теоремы о гомоморфизме и изоморфизме, фактор-структуры и конгруэнции), но также важно с математической точки зрения. Темы, которые я упомянул выше, в основном имеют приложения «реального мира», но есть и более связанные темы, которые также имеют приложения «реального мира».
Вышеупомянутое не является ответом на реальный вопрос, но касается только «... обычно считаются бесполезными теоретическими конструкциями ... из-за отсутствия чего-либо интересного сказать ...» замечание. Поэтому я перечислил некоторые «интересные» моменты, заявил, что в большинстве случаев это приложения «реального мира», и теперь Hi-Angel запрашивает немного информации об этих приложениях. Но поскольку «слишком много интересного сказать», не ожидайте слишком многого от этой информации: теорема Крона-Родса является теоремой разложения для конечных полугрупп. Его приложения включают интерпретацию продукта венка как своего рода композиции (преобразователей) в связи с теорией автоматов и регулярных языков, Mark V Lawson: две учебные лекции и справочные материалы. содержали (теперь 404) хороший материал по обратным полугруппам . Основой их приложений является их связь с симметричной обратной полугруппой , т. Е. Множеством всех частичных биекций на множестве. Можно также начать с базовых алгебраических характеристик обратных полугрупп, но такой подход рискует пренебречь связями с частичными порядками, которые важны для многих приложений. Однажды мне придется написать в блоге о конкретном применении обратных полугрупп в качестве «иерархии», используемой для сжатия схем полупроводников. . Применение полуколец уже было описано в других ответах (и тропическая геометрия унесет нас далеко от информатики). Поскольку моноиды и полугруппы также связаны с частичными порядками, такие полезные темы, как функции Мёбиуса, описаны в Combinatorics: The Rota Way. , также связаны. А затем также стали связываться темы из Матриц и Матроидов для системного анализа, такие как разложение Дульмажа-Мендельсона , что стало одной из моих мотивов для изучения теории решеток (и скрытых иерархических структур).
источник