Адрес e-mail:
Прошедшие события
Онлайн-презентация кафедры космической физики ЛФИ
Сессия вопросов-ответов с биоинформатиком Антоном Буздиным
Презентация магистерской программы «Физика сверхпроводимости и квантовых материалов»
Презентация магистерской программы «Двумерные материалы: физика и технология наноструктур»
Презентация магистерской программы «Цифровые технологии в бизнесе»
Денис Дмитриев: «Особенности поступления и ответы на вопросы. Приемная кампания — 2020»
Всероссийский онлайн-выпускной
Онлайн-презентация кафедры интегрированных киберсистем ФРТК
Сессия вопросов-ответов с Михаилом Щелкановым
Круглый стол: «Тенденции рынка труда во время всеобщей самоизоляции»
Онлайн-марафон #надоразобраться
Максим Поташев: «Бридж – самый популярный в мире интеллектуальный вид спорта»
Сергей Иванов: «Человек в центре бизнеса: конкурентное преимущество или корпоративные сказки?»
Семинар: «Выбор обратной связи в системах управления как задача оптимизации»
Константин Виноградов: «Как работают венчурные фонды и почему стоит строить глобальный бизнес с первого дня»
Интеллектуальная игра Genium Challenge с Максимом Поташёвым
Цифровая ярмарка вакансий МФТИ
Михаил Бурцев: «Разговорный искусственный интеллект»
Всероссийская конференция «Преподавание ИТ в России»: обучение студентов в «новой реальности»
Презентация магистерской программы МФТИ и МБИ имени Анатолия Собчака «Технологическое лидерство»

Демонстрация программного обеспечения TRAG для проверки свойств графов

Демонстрация программного обеспечения TRAG для проверки свойств графов

9 июня в 18:15 в 107 БК состоится демонстрация программного обеспечения для проверки свойств графов «TRAG. Monadic second-order model checking with fly-automata».

Докладчик: Бруно Курсель (Bruno Courcelle), французский математик, известный своими исследованиями в теории графов, работает в лаборатории информатики (LABRI) Университета Бордо I во Франции.

Abstract:

An algorithmic meta-theorem states that every graph property expressible by a monadic second-order (MSO) sentence can be checked in linear time for graphs of bounded tree-width, or even, of bounded clique-width, given by appropriate algebraic terms. The standard proofs construct from MSO sentences and bounds on tree-width or clique-width  finite but huge automata intended to run on input terms encoding the input graphs.

By using fly-automata that do not store states and transitions but compute them whenever needed, we could implement  this result. And check in particular colorability and other NP-complete properties. In order to verify a graph property, we must input a clique-width term (corresponding to a decomposition of the graph witnessing an upper bound to its clique-width), together with a relevant fly-automaton. The property is verified if and only if the term is recognized by the automaton. This technique has been implemented in the system TRAG written in Common LISP by I. Durand.

The demonstration will show how to input a graph, to decompose it in several ways, to check coloring properties and Hamiltonicity. The system can build an automaton from a given MSO sentence.

Программное обеспечение TRAG можно найти на сайте. Документация доступна по ссылке.

На демонстрацию приглашаются студенты и специалисты, интересующиеся математикой и программированием. Вход свободный.

Мероприятие проходит в рамках конференции «Russian workshop on complexity and model theory», проходящей в МФТИ с 9 по 11 июня.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2020 Московский физико-технический институт (национальный исследовательский университет)

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

Техподдержка сайта | API

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

МФТИ в социальных сетях