Синхронизируемые автоматы. Лекция 2
Алгоритмы и сложность
Обзор основных алгоритмических вопросов, связанных с синхронизируемыми автоматами. Полиномиальный алгоритм для распознавания синхронизируемости. NP-полнота задачи о существовании синхронизирующего слова данной длины. Жадный алгоритм построения синхронизирующего слова. Верхняя оценка для длины слова, возвращаемого жадным алгоритмом.
Страница лекции на сайте Computer Science клуба
АвторМихаил Волков
ОрганизаторComputer Science клуб при ПОМИ РАН
Лекции курса
9- Синхронизируемые автоматы. Лекция 1
- Синхронизируемые автоматы. Лекция 2▶ Вы тут
- Синхронизируемые автоматы. Лекция 3
- Синхронизируемые автоматы. Лекция 4
- Синхронизируемые автоматы. Лекция 5
- Синхронизируемые автоматы. Лекция 6
- Синхронизируемые автоматы. Лекция 7
- Синхронизируемые автоматы. Лекция 8
- Синхронизируемые автоматы. Лекция 9
Онлайн-курсы по программированию
3
Машинное обучение для анализа текстов
От бизнес-идеи к ее реализации: учимся инновационному предпринимательству с нуля.
С платными опциями
Разработка игры-платформера на Defold: базовый уровень
Создайте свой первый платформер с нуля! За 7 недель вы не просто освоите движок Defold, а пройдете весь путь геймдев-разработчика: от кода и анимаций до дизайна и сюжета.
Бесплатный
Python для начинающих
Курс посвящен основам программирования на языке Python — одном из самых популярных и понятных языков, идеально подходящих для первого знакомства с IT.
Бесплатный