[Кафедра МаТИС]

Тесты
Короткие тесты
Разделяющие поверхности
Теорема Новикова
Комбинаторно-логический подход к распознаванию образов
Иерархическая распознающая система

Модели вычислений, используемые для оценки сложности алгоритмов и вычислений
Меры сложности алгоритмов
Труднорешаемость задач
Классы P и NP и их свойства
NP-полные задачи
Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний
Полиномиальная сводимость задач
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения
Оптимизация алгоритмов перебора
Политика жадности
Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии
Матроиды
Характеризация случаев оптимальности жадных алгоритмов
Теорема Радо- Эдмонса.

Свободные группы
Группы Бернсайда
Матрицы

Лабиринты: прямоугольные, мозаичные, шахматные.
Перемещение независимых систем автоматов в лабиринтах.
Возможность обхода конечных мозаичных лабиринтов конечными автоматами.
Теорема Будаха-Подколзина (невозможность обхода конечным автоматом всех мозаичных лабиринтов).
Обход автоматом конечных односвязных шахматных лабиринтов.
Обход конечным автоматом конечных лабиринтов с ограниченными внутренними дырами.
Перемещение в лабиринтах коллективов автоматов.
Периодичность поведения системы автоматов в конечных лабиринтах.
Пример непериодического поведения коллектива автоматов.
Автоматы со счётчиками.
Обход произвольных конечных шахматных лабиринтов автоматом со счётчиком.
Обход произвольных конечных шахматных лабиринтов коллективом автоматов.
Обход коллективом автоматов лабиринтов с одной дырой.
Постановка задачи преследования в шахматных лабиринтах.
Поведение конечного автомата в L0.
Задача преследования независимой системой хищников независимой системы жертв в L0.
Поведение конечного автомата в L1.
Задача преследования независимой системой хищников независимой системы жертв в L1.
Поведение конечного автомата в L2(l).
Задача преследования независимой системой хищников независимой системы жертв в L2(l).
Поведение конечного автомата в L3(l) и L4.
Задача преследования независимой системой хищников независимой системы жертв в L3(l) и L4.
Поимка данной жертвы в L0 коллективом хищников.
Существование универсального коллектива хищников в L0.
Существование универсального коллектива хищников в L1, L2(l), L3(l) и L4.
Задача преследования коллективом хищников независимой системы жертв в L5(l).
Нерешённые лабиринтные задачи.

Линейный автомат как преобразователь степенных рядов.
Операторы замыкания в классе линейных автоматов. Проблема полноты.
Аппроксимационно предполные классы. Решение задачи об аппроксимационной полноте в классе линейных автоматов над простым полем.
Решение задачи об аппроксимационной полноте в классе линейных автоматов над конечным полем.
Предполные классы по операциям композиции. Решение задачи о полноте в классе линейных автоматов над простым полем.
Решение задачи о полноте в классе линейных автоматов над конечным полем.

Основы технологии синтеза БИС.
Логический синтез. Конечный автомат как модель БИС.
Задача трассировки. Минимальные прямоугольные деревья Штейнера: теорема существования, алгоритмы построения, алгоритм для приближенного решения.
Задача укладки. Минимальные разрезы в графе: алгоритмы точного и приближенного решения. Задача разбиения: эвристические алгоритмы.
Специализированные схемы (сортировки, сложения, умножения).
Плоские клеточные схемы. Оценки сложности специализированных плоских клеточных схем.
Эвристические алгоритмы укладки. Gordian алгоритм.