Википедия говорит :
Полные решетки появляются во многих приложениях в математике и информатике
Это просто ссылка на тот факт, что стандартная булева алгебра, используемая в вычислениях, является полной решеткой? Есть ли что-то, что мы приобретаем, работая на абстрактном уровне решеток, а не конкретно с булевой логикой?
Поиск по Google не находит много по теме, но я, вероятно, использую неправильные ключевые слова.
lattices
order-theory
Xodarap
источник
источник
Ответы:
Смотрите, например, эту книгу: Теория решеток с приложениями, Виджей К. Гарг , которая начинается следующим образом:
В книге не упоминается теория рекурсии (теория вычислимых множеств), но из статьи Википедии по теории вычислимости мы видим:
Дальнейшее чтение смотрите в блоге « Теория решеток» для программистов и не-компьютерщиков .
источник
Ссылки, данные Полем Г.Д., действительно очень уместны. Итак, давайте сосредоточимся на второстепенной проблеме в этом ответе. Некоторое время назад я немного читал о решетках и начал задумываться о том, не было бы понятие полурешетки более подходящим для приложений. Вы могли бы возразить, что полная полурешетка автоматически также является решеткой, но гомоморфизмы и подструктуры (то есть подрешетки и субрешетки) различны.
Я впервые столкнулся с (полу) решетками при изучении полугрупп, как коммутативные идемпотентные полугруппы. Затем я подумал о связи между иерархическими структурами и решетками и заметил, что дерево, естественно, также является полурешеткой. Затем я нашел решетки в контексте безопасности и в программном анализе, и мне всегда казалось, что структура полурешетки была действительно важной частью, и решетка была просто взята, потому что ее можно было получить «бесплатно». Даже для алгебры Гейтинга существует асимметрия между конъюнкцией и дизъюнкцией, что наводит меня на мысль о том, что модель асимметричной полурешетки может дать больше понимания, чем модель симметричной решетки.
источник
очень важный, но не очень известный случай - он хорошо известен среди теоретиков, но не так хорошо известен в смысле обучения студентов - использование решетки для доказательства суперполиномиальных нижних оценок размера монотонных цепей Вычислительная клика, за которую Разборов получил Неванлиннскую премию . однако оригинальная конструкция очень техническая, и более поздние конструкции, например, Берг / Ульфберг, упрощают каркас без ссылки на решетки.
так что в этом случае теория решетки использовалась в качестве основы для открытия оригинального доказательства, но более поздние формулировки имели тенденцию не относиться к нему напрямую как к концептуальному упрощению.
так что да, решетки могут рассматриваться как более экзотический математический объект [Разборов говорил в другом месте о своем стиле применения продвинутой математики к CS], который может соответствовать некоторому другому более «конкретному» объекту в CS, в данном случае это «врата приближения» т. е. логические элементы в схемах, которые дают «приблизительно правильные» ответы и решетка которых является своего рода «индукционной структурой» для преобразования точной схемы в неточную, приблизительную схему.
источник
С тех пор я нашел бесплатные бумажные заказанные наборы и полные решетки: учебник для информатики для других заинтересованных читателей.
источник
Регулярные метки ребер и связанные с ними структуры образуют распределительную решетку (см., Например, здесь ). Это может быть использовано для эффективного поиска в пространстве всех регулярных меток ребер для данного графа (см. Здесь ). В качестве приложения вы можете определить, можно ли нарисовать карту в виде картограммы с определенным назначением области для граней.
источник
Также удивительно (для меня, по крайней мере) криптография . Проверьте это, это позволяет новые атаки известных криптосистем и дает надежду на постквантово-вычислительную криптографию.
источник