Похожие видео
Текстовая версия
Привет сегодня я вам расскажу немножечко про моноида про монолит и помогает! И промо на веточке моей на разумеется не все несколько отдельных.
Фактик of в том числе начинает сведение что это такое вот потом рассмотрим простейшие примеры потом пример чеки чуть поинтереснее ну и в конце.
Немножко прикладывать и традиционно и так моноиды что ж это такое некоторые считают. Что моноид эта категория с единственным объектом.
Это те же самые люди которые считают что монады это моноид. В категории in da funk трав другие считают!
Что моноиды это полу группа с единицей это те же самые люди которые считают что группа это моноид с обратным элементом. Как ни странно все эти люди правы но мы рассмотрим.
Моноиды с простейших позиций как алгебраические структуры через операции на множествах и так моноид называется.
Бинарная операция который поддерживает свойство ассоциативности что такое?
Ассоциативность написано вот здесь в первой строчке это значит.
Что нам все равно как раскрывать скобки вычисляя вот такое выражение соединяющие три элемента множества через две бинарные. Мы на и данной операции либо сначала применить бинарную операцию а sb результат применить операцию с либо наоборот.
Математика
Сначала применить операцию bsc а потом а применить операцию к результатов операции бойцы также для моноиды необходимо. Существование нейтрального элемента множестве это значит что бинарная операция для любого элемента из множества.
С нейтральным элементом возвращает этот элемент здесь очень. Важно что у нас это нейтральность элементы должна быть как слева так и справа поскольку мы нигде не требуем коммутативности этой бинарной.
Операции то есть совершенно не требуется чтобы операция к применены к аргументам а и b давала. Тот же результат что операция применены к аргументам b и а есть коммутативной моноиды есть не коммутативное. Ну и сразу же несколько простейших примеров но например операция сложения!
На действительных числах является моноидам отца ассоциативность очевидно нейтральный элемент это 0 операций умножения тоже является моноидам нейтральный элемент единица ассоциативность тоже очевидно рассмотрим. Пример чуть поинтереснее не на числах например склейка.
Скраб строк конкатенация строк нейтральный элемент у нас будет пустая строка вот ассоциативность тоже очевидно! Мы получаем строку склеиваем склеивает 3 нам все равно в каком порядке склеивать первые со второй результат 3 либо 2 из 3 и первые приклеивать к нему начали.
Вот первые два примера является абай коммутативной моноида. Третий пример не коммутативное ума но это не так же можно придумать очень много примеров где эти моноида всплывают. В повседневной жизни скажем так далее ума но и дав есть один очень интересный момент которым.
Часто пользуется это свёртка структур по моноидам. Я не буду употреблять страшные слова типа к там орфизм и и всякие прочие сложные вещи из теории категорий не абстрактные.
Алгебра я буду рассматривать простейший структур ки упорядоченный список конечного набора элементов если у нас есть у порядочный списочек элементов из нашего. Множество x1 x2 и так далее да и ценного мы можем свернуть этот список по маны и дальной операции очевидно свою. Силу ассоциативности нам все равно в каком порядке применять эти операции нам все равно как расставлять скобки!
Это знать что мы можем записать то есть просто раскидав значки мы на реальных операций между этими подряд. Идущими элементики вот порядок их имеет значение если монолит не коммутативной вот и в этом случае очевидно что свёртка по моноида пустого. Списка в котором нет элементов результатом его является нейтральный элемент нашего моноида потому что очевидно что мы можем в любой список с любым количеством элементов докинуть:
Савватеев
Любое количество нейтральных элементов потому что наличие нейтральных элементов не изменит результат и соответственно свёртка пустого списка мы можем во-первых постулировать. Что она является нейтральным элементом во вторых это полностью согласуется с тем что докинув список сколь угодно нейтральных элементов. Применив принимайте бинарные операции моно и дальние мы получим.
Нейтральные элементы на выходе свёртка послал спец как нейтральный элемент итак перейдем к следующим пример. Щекам чуть поинтересней операция минимум бинарная заданное на некотором множестве она очевидно ассоциативно то есть если у нас есть 3 элемента.
Нам все равно в каком порядке из них считать.
Минимальный элемент вот поэтому операциями ним является ассоциативной но является ли она моноидам для этого мы рассмотрим что и выполняется! Ли условие что для любого элемента наше множество для любого а у нас будет существовать один! И тот же элемент е такой что операция минимум as е будет давать нам нашу hq если.
Наше множество имеет максимальный элемент разумеется в качестве? Нейтрального элемента можно взять этот максимальный лимит наше множество но например если мы рассмотрим операцию минимум на множество всех действительных. Чисел будет ли она является моноидам и можно ли что-то сделать.
Чтобы операция минимум на множестве действительных чисел являлась моноидам сейчас желающие могут поставить видео на паузу и немножко? Подумать но для остальных продолжаем мы расширим наше множество добавив.
В него специальный элемент я вот здесь обозначил под плюс бесконечности это неважно как обозначать этот элемент.
Мы могли бы назвать и в любой буквы любым символом то есть мы расширяем что наше множество теперь не только. Состоит из всех действительных чисел а все действительные числа плюс некий дополнительный элемент и нам придется:
Постулировать поведение нашей бинарные операции минимума на элементах нашего на у множества и мы говорим что на числах он будет действовать как обычные минимум на числах. На вот этом нейтральным элементе который мы добавили плюс бесконечности бинарная.
Популяризация
Операция будет давать самого самой сам же этот нейтральный. Элемент и также мы постулируем что это бинарная операция. На любом числе и этом нашем добавленным элементе:
Будет давать наше число соответственно все условия все свойства моноида выполняются и таким образом на таком расширенном множестве операция минимум будет являться моноидам но это. Как следствие свёртка поэтому она виды пустого списка будет равна плюс бесконечности то есть такой некий казус ный факт что операция не минимум.
Свёртка по минимуму пустого списка будет давать плюс бесконечности теперь следующий примерчик! Еще поинтересней операция меньше как видите это вообще не является операцией замкнутые. На множестве то есть это бинарный предикат у нас могут быть элементы этой операции значением либо множество который позволяет сравнение на больше меньше.
Но результат это операции это более в значении этот роль фолз можем ли мы операция меньше считать. Моноидам или что-либо сделать чтобы в каком-то смысле операция меньше являлась моноидам здесь опять желающие могут подумать. А для остальных продолжаем мы расширим наше исходное множество даже не расширим мы сделаем отображение нашего исходного множества на новое!
Множество следующим образом это наши много и множество будет содержать своем составе следующие элементы все упорядоченные пары из элементов нашего. Исходного множества и два дополнительных элементов назовем их empty и файл условно первое что нам нужно сделать это нам нужно определить.
Правила отображения нашего исходного множества на новое множество для любого а из нашего исходного множества. Которые мы можем проверять на бинарные операции больше или меньше мы сделаем следующее? Отображение что любое а переходит в упорядоченную пару а.а. отлично в качестве нейтрального элемента мы выберем наш добавленный элемент.
М ти нового получившегося множество соответственно со всеми свойств и нейтрального элемента что на но множество для любого для любых других элементов либо. У порядочный par a и b либо файл она и данная:
Операция с empty будет давать свой второй. Аргумент также мы постулируем аксиоматической зададим поведение элементы множества нашего файл на любых других элементах? Нашего множество скажем так что для любого а принадлежащего м это либо пара либо mt либо файл как мы видим я мано и данной операции?
С файл слева или справа будет давать файл и здесь я подписал. Чтобы обратили внимание что при таком задании множество м!
Наука
У нас дома дополнительно элементы empty и файл не конфликтуют действительно давайте посмотрим. Если мы в качестве а возьмем empty маны и данная операция любого. Значения из файла будет давать файл а поскольку m kit является нейтральным элементом нашего моноида по определению значит маной данной операции?
Нейтрального элемента стоил он также будет давать файл то есть все соответствует. Пока никаких противоречий нет теперь результат мы на и дальние операции на нашем множестве если мы будем это примерять ему дают! Мы не данную операцию к порядочным планом ну возьмем например пары abcd и мы постреляем следующее что мы медаль на операции обобщенные меньше на двух парах abcd у нас равна.
Новой паре а.д. то есть первые элементы с первой парой 2 элементы 2. Пары если б меньше c либо файл если.
Иначе таким образом получается что мы определили во-первых отображения. Нашего исходного множества в новое множество на котором мы уже задаем об обобщенная? Операции меньше как именно бинарные операции замкнутые на нашем новом множестве м что результаты этой наши обобщенные операции.
Меньше бинарные на на во множестве будут также принадлежать этому множество соответственно легко показать что это операций обобщенной при таком расширение нашего!
Множество при таком отображение нашего множество и при таких правилах она будет являться мана войдом у нее есть нейтральный: Элемент и она также ассоциативно и она удовлетворяет всем аксиомам моноида центры в а теперь чтобы получить как бы обратное преобразование.
Из нашего отображено во множество в более узкое значение мы поступим простейшим образом что если результат. В нашем множестве м является значением файл то переводится это в близкое значение фолз ложь иначе все остальное переводится в близкое значение. True истина получается что сворачивая таким образом любое количество ну по списку как мы придем.
Предварительно говорили до любое количество порядочного на набора элементе cove мы получаем.
Либо фоллз либо true а смысл за этим стоит следующий что такое свёртка. По моноида меньше упорядоченного набора чисел это проверка. Является ли они расположены строго по возрастанию например здесь.
Покажу да вот расположен или элементики x1 x2 и так далее цен строго по возрастанию как мы это проверяем май производим отображение этих элементов на наши новые.
Множество м виде палочек x 1 x 1 x 2 x 2 и так далее. И сворачиваем их по наши вообще на операции меньше получаем результат!
На множестве м и переводим его обратно вульва ну а теперь обещанная. Прикладу х как бы зачем нужны эти казалось бы далекие?
От практической деятельности конструкции алгебраической структур ки моноиды и так далее очень много! Обоснований для того зачем они нужны но одно из них могу привести вот прямо.
Сразу очевидно что вот эта свёртка по мы на и дальние операции любого конечного набора элементов она тривиальным.
Образом параллели ца что я имею ввиду мы можем разбить вот этот наш наборщик элементов. X 1 x dx м на сколь угодно групп на несколько. Групп и сворачивать эти группу моно и далее каждую по отдельности получать свои результаты а потом в том.
Же порядке в котором мы разбивали тина группы мы не дали свернуть результаты и получившийся результат будет точно такой же как если. Мог бы сворачивали их подряд как сами элементики из этого следует очень важное практическое применение.
Данных алгоритмов последнее десятилетие компьютер развивались так сильно что фактически скорость обработки информации удваивалось каждые определенное количество времени но с недавних пор мой первый с потолок. В этом плане и бесконечно наращивать мощности и производительности скорости железо компьютерного уже нельзя мы достигли уже пределов физических ограничений. Поэтому важное значение появляется появляется у тех алгоритмов которые позволяют!
Распараллеливания как говорил мёллер что если собрать вместе 9 беременных женщин ребенок все равно не родится через месяц в компьютерных вычислений! Такой не всегда верно часть алгоритмах позволяют раз про распараллелить.
Их на 9 машин и получить результат в 9 раз быстрее потому что каждый. Из машин будет делать свою работу и свёртка по mma на и данным операциям именно является. Как раз ярким примером таких вещей что мы можем разбить.
Наш исходный длинный-длинный списочек на 9 кусков отдать каждый кусок своей машине получить 9 результатов свернуть их также по маны и данной операции получить результат в 9 раз быстрее? Ну и опускаясь к приземленным примером например. Всем понятно что если нужно посчитать сумму элементов массива мы разумеется можем разбить этот массив на 9 кусочков отдать и 9 компьютером.
Каждый компьютер посчитает свою часть сумма потом мы сложим эти девять результатов а вот например средства. Стоят задача проверить является ли этот массив все его элементы каждое! Следующее строго больше предыдущего то есть расположены по строгому возрастанию тут нужно было немножко подумать.
О да пролили цели эта задача как разбивать массе с перекрытием не с перекрытием но вот таким хитрым путем. Приведя эту операцию к моноидам мы автоматически обеспечили распараллеливание света. В алгоритма так что моноиды нужны важны и широко применимы всем спасибо?
