ДИСКРЕТНЫЙ АНАЛИЗ И КОМБИНАТОРИКА
28.03.2018 Кафедра теоретической кибернетики НГУ
профессор
1. Методы кодирования для подсчёта или оценивания числа объектов. Основные классы отображений конечных множеств, их кодирование и подсчет числа. Числа Стирлинга. Числа Каталана. Кодирование деревьев и их число. Кодирование и нумерация подмножеств конечного множества. Алгоритмы построения нумерующих отображений. Коды Грея в булевых гиперкубах. Подсчёт с помощью рекуррентных уравнений и производящих функций (на примерах конкретных задач).
2. Комбинаторика слов и символьных последовательностей. Классические символьные последовательности, способы задания. Комбинаторная сложность. Графы де-Брёйна. Число последовательностей де-Брёйна. Универсальные слова. Восстановление слов по фрагментам. Псевдослучайные последовательности. Задачи сборки слов с помощью операций. Асимптотически оптимальный алгоритм сборки. Аддитивная сложность слов. Суффиксные деревья. Префиксные коды. Запрещённые подслова. Теоремы о полноте систем запретов.
3. Дискретные метрические пространства и кодирующие отображения ограниченного искажения. Аксиоматика понятия близости, расстояния, метрики. Метрические пространства на множествах подмножеств, словах, символьных последовательностях. Метрики Хаусдорфа, Хемминга, Ли, решётки. Структуры гиперкубов и n-мерных торов. Вложения графов в гиперкубы. Локально изометрическое кодирование целочисленной решётки.
4. Булевы, к-значные и словарные функции. Способы задания булевых функций. Формулы, конъюнктивная и дизъюнктивная (ДНФ) нормальные формы, бинарные диаграммы решений (BDD), представления логическими полиномами. Существенные переменные. Минимизация булевых функций, сокращённая и тупиковые ДНФ. Геометрическая теория минимизации. Замкнутые классы булевых функций. Теорема Поста о полноте, следствия. Алгоритм распознавания полноты. Вычисление булевых функций схемами из функциональных элементов. Решения систем булевых уравнений. SAT технологии. Логические производящие функции и их применение.
5. Дискретные модели генных сетей. Автоматная модель функционирования сети с булевыми функциями в вершинах. Структура и сложность функциональных графов динамики состояний сети (на примере регуляторного контура генной сети). Анализ динамики сетей нерегулярной структуры методами символьных вычислений.
28.03.2018 / /
