Geum.ru

Основная образовательная программа высшего профессионального образования Направление подготовки 010100 Математика

Вид материалаОсновная образовательная программа

Содержание


Синтез и сложность дискретных управляющих систем
Элементы теории дискретных структур
Коды и схемы
Графы и алгоритмы
Совершенные структуры
Подобный материал:
1   2   3   4   5   6   7
Глава 4. Задача сортировки реверсалами
    1. Перестановки и помеченные перестановки как модель представления

генных последовательностей
    1. Сортировка реверсалами на перестановках
      1. NP-трудная задача
      2. Приближенные алгоритмы сортировки
    2. Сортировка реверсалами на помеченных перестановках
      1. Полиномиальные алгоритмы сортировки
    3. Другие задачи сортировки, возникающие в молекулярной биологии

Глава 5. Задача восстановления вершин графа
    1. Постановка задачи в теории кодирования
    2. Решение задачи для графов Хэмминга и Джонсона
    3. Решение задачи для графов Кэли на симметрической и гипероктаэдральной

группах
    1. Прикладные аспекты задачи в молекулярной биологии



^ СИНТЕЗ И СЛОЖНОСТЬ ДИСКРЕТНЫХ УПРАВЛЯЮЩИХ СИСТЕМ


Введение. Понятие управляющей системы (УС), примеры: дизъюнктивные нормальные формы, формулы, контактные схемы, схемы из функциональных элементов, ветвящиеся программы.

Проблемы оценок сложности управляющих систем. Связь с проблемой P  NP

Дизъюнктивные нормальные формы. Совершенные, минимальные, кратчайшие, сокращенные, тупиковые ДНФ. Соотношение между различными типами ДНФ

Контактные схемы. Простейшие методы синтеза контактных схем. Метод Шеннона синтеза контактных схем. Метода Лупанова синтеза контактных схем

Схемы из функциональных элементов. Метод Лупанова синтеза схем из функциональных элементов. Функция Шеннона сложности вычисления булевых функций схемами из функциональных элементов

Теорема Яблонского о невозможности элиминации перебора при построении последовательности самых сложных функций

Эффективные нижние оценки сложности. Сложность линейной функции в классе контактных схем.

Метод Нечипорука получения нижних оценок сложности контактных схем, формул, ветвящихся программ

Метод Субботовской. Пример Андреева

Метод Храпченко получения нижних оценок сложности параллельно-последовательных контактных схем для линейной функции. Нижние оценки сложности вычисления булевых функций ветвящимися программами


^ ЭЛЕМЕНТЫ ТЕОРИИ ДИСКРЕТНЫХ СТРУКТУР


Формулы обращения.

Формула включений и исключений.

Частично упорядоченные множества, их функции Мебиуса и теорема об обращении Мебиуса.

Производящие функции. Возвратные последовательности и рекуррентные соотношения.

Решение линейных рекуррентных соотношений.

Теорема Рамсея и ее частный случай для графов. Одно приложение теремы Рамсея.

Теорема Ван-дер-Вардена.

Конечные геометрии. Структура конечной плоскости.

Конечные плоскости и их связь с другими комбинаторными конфигурациями: латинские квадраты.

Блок-схемы и их связь с конечными плоскостями.

Булевы функции, формулы. Реализации булевых функций. Дискретные устройства без памяти – схемы из функциональных элементов.

Дискретные устройства с конечной памятью – конечные автоматы. Представление событий в автоматах. Существование событий, не представимых в конечных автоматах.

Регулярные события. Источники. Детерминированные источники. Теоремы синтеза и анализа автоматов.

Схемы отношений и дистанционно регулярные графы. Алгебра Боуза-Меснера.

Дуальность в схемах отношений.

Подмножества в схемах отношений.

Схемы Хэмминга и Джонсона. Метрические и P(Q)-полиномиальные схемы.


^ КОДЫ И СХЕМЫ


Предметы теории кодирования, теории блок-схем (designs). Модель канала связи с шумами, определение кода (теоретические и геометрическое). Задание кода. Пример кода Хэмминга длины 7.

Кодовое расстояние, линейные коды. Теорема о связи проверочной и порождающей матриц. Граница Хэмминга, код Хэмминга, его кодирование и декодирование. Границы Синглтона, Варшамова-Гилберта. Методы построения кодов, теорема Плоткина.

Совершенные коды. Конструкция Васильева. Построение кодов общей проверкой на четность. Нижняя оценка числа совершенных кодов. Совершенные и совершенные расширенные коды длины 15 и 16, их классификация.

Системы троек Штейнера порядка n (STS(n)), определение, спектр существования. Теорема о необходимом и достаточном условии существования STS(n), примеры STS(n) для малых n, эквивалентные STS(n). Конструкция произведения.

Конструкция Ассмуса и Маттсона, ее связь с конструкцией Васильева. Теорема о совокупности кодовых слов веса 3 в совершенном коде (веса 4 в совершенном расширенном коде).

Определение блок-схемы, теорема о параметрах блок-схемы. Неравенство Фишера.

Свитчинги в блок-схемах и кодах. Свитчинговость конструкций Васильева, Ассмуса-Маттсона. Представление кода Хэмминга через объединение линейных компонент, -компоненты.

Системы четверок Штейнера порядка n (SQS(n)), определение, спектр существования, примеры. Конструкции Ханани и Алиева. Cвитчинговая конструкция SQS(n).

Полиномы Кравчука.

Введение в полностью регулярные коды. Теорема Ллойда. Теорема Зиновьева, Леонтьева и Тиетвайнена.


^ ГРАФЫ И АЛГОРИТМЫ

  1. Основные определения и обозначения, связанные с графами, мультиграфами и орграфами. Способы задания графов. Лемма о рукопожатиях.
  2. Способы задания графов и орграфов. Теорема о числе маршрутов, соединяющих две вершины графа (орграфа).
  3. Двудольные графы. Критерий двудольности графа.
  4. Леса и деревья. Теорема об эквивалентных определениях дерева. Корневые деревья.
  5. Вершинно и реберно k-связные графы. Числа вершинной и реберной связности, неравенство между ними.
  6. Вершинно и реберно-двусвязные графы Точки сочленения и мосты в графе. Теорема об эквивалентных определениях вершинно-двусвязного графа.
  7. Простейшие операции, сохраняющие вершинную двусвязность графа. Точки сочленения, мосты и блоки. Взаимное расположение двух блоков в графе. Граф блоков и точек сочленения, теорема о его строении.
  8. Поиск по графу в глубину и в ширину. Дерево поиска. Связь поиска в ширину с нахождением кратчайших цепей в графе.
  9. Алгоритм нахождения блоков в связном графе.
  10. Теорема о существовании остовного дерева (остова) в связном графе. Поиск минимального остова во взвешенном графе. Алгоритм Краскала.
  11. Поиск минимального остова во взвешенном графе. Алгоритм Примы.
  12. Кратчайшие пути во взвешенных орграфах. Алгоритм Дейкстры.
  13. Кратчайшие пути во взвешенных орграфах. Алгоритм Флойда-Уоршелла.
  14. Определения сети и потока. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Лемма о величине потока через разрез.
  15. Сети и потоки в сетях. Задача о максимальном потоке. Теорема Форда-Фалкерсона.
  16. Обобщенный алгоритм Форда-Фалкерсона. Анализ работы алгоритма в случае целых и рациональных пропускных способностей.
  17. Метод кратчайших путей в задаче о максимальном потоке.
  18. Реберная теорема Менгера для орграфов (о наименьшем числе дуг, разделяющих два подмножества вершин орграфа).
  19. Вершинная теорема Менгера для орграфов (о наименьшем числе вершин, разделяющих два подмножества вершин орграфа).
  20. Теоремы Менгера для неориентированных графов (вершинный и реберный варианты).
  21. Критерии вершинной и реберной k-связности графа (теоремы Уитни).
  22. Гамильтоновы циклы и цепи, необходимые условия их существования. Достаточные условия гамильтоновости графа (теоремы Дирака и Оре).
  23. Понятия эйлерова цикла и цепи. Эйлеровы графы. Критерий эйлеровости графа и алгоритм Флери.
  24. Независимые множества вершин и ребер графа. Вершинные и реберные покрытия, факторы и паросочетания. Числовые характеристики, связанные с независимостью и покрытиями, их простейшие свойства.
  25. Лемма о строении минимального реберного покрытия графа. Теорема Галлаи.
  26. Характеризация наибольших паросочетаний графа в терминах чередующих-ся дополняющих цепей.
  27. Алгоритм поиска наибольшего паросочетания и наименьшего вершинного покрытия в двудольном графе. Задача о назначениях.
  28. Паросочетание, покрывающее долю двудольного графа. Теорема Холла и ее следствия. Связь с системами различных представителей.
  29. Теоремы Кенига о числе реберной независимости двудольного графа и о (0,1)-матрицах.
  30. Совершенные паросочетания и r-факторы. Критерий Татта существования 1-фактора (доказательство необходимости).
  31. Теоремы Петерсена о 2-факторах в кубических графах и о 2-факторизуемости регулярных графов четной степени.
  32. Раскраски вершин графов, k-раскрашиваемые и k-хроматические графы. Нижние оценки хроматического числа. Верхняя оценка хроматического числа k-вырожденного графа. Теорема Брукса. Верхние оценки хроматического числа планарных графов (без доказательства).
  33. Раскраски ребер графов и мультиграфов. Хроматический класс. Нижние оценки хроматического класса. Верхние оценки Визинга и Шэннона для графов и мультиграфов. Неулучшаемость оценок. Хроматический класс двудольного (мульти)графа.
  34. Плоские и планарные графы. Понятие грани, ранга грани, формула для суммы рангов всех граней плоского графа. Планарность графов выпуклых многогранников. Формула Эйлера, ее различные представления.
  35. Верхняя оценка для числа ребер планарного графа. Максимальные планарные и плоские графы, триангуляции, 5-вырожденность планарных графов.
  36. Верхняя оценка для числа ребер планарного графа без 3-циклов, 3-вырожденность таких графов; связь с четыреангуляциями.
  37. Подразбиения графов и их гомеоморфизм. Критерий планарности Понтрягина-Куратовского.


^ СОВЕРШЕННЫЕ СТРУКТУРЫ

  1. Метрические пространства. Метрика графа.
  2. Декартово произведение метрических пространств.
  3. Гипотеза Улама.
  4. Дистанционно-регулярные графы.
  5. Теорема Шпернера.
  6. Теорема Рамсея.
  7. Гиперкуб. Булевы функции.
  8. Частично упорядоченные множества. Цепи, антицепи. Теорема Дилуорса.
  9. Системы различных представителей. Теорема Холла.
  10. Транзитивные графы. Графы Кели конечных групп.
  11. Совершенные коды. Код Хэмминга.
  12. Теорема Ван дер Вардена о существовании монохроматических арифметических прогрессий.
  13. Числа Рамсея.
  14. Формула для суммы биномиальных коэффициентов, взятых с фиксированным шагом.
  15. Совершенные раскраски. Алгоритм Визинга.
  16. Центрированные функции. Теорема Шапиро и Злотника.
  17. Квазигруппы.
  18. Каскадная конструкция построения Кодов.
  19. Двудольные графы. (0,1)-матрицы. Теорема Кенига.
  20. Поля Галуа.
  21. Совершенные паросочетания. Перманенты.
  22. Кронекерово произведение матриц.
  23. Матрицы Адамара. Проблема существования матриц Адамара заданного порядка.
  24. Методы построения матриц Адамара.
  25. Построение матриц Адамара методом Вильямсона.
  26. Эквидистантные коды.
  27. Блок-схемы.
  28. Теорема Брука--Райзера--Човлы.
  29. Латинские квадраты. Ортогональные латинские квадраты.
  30. Проективная геометрия.
  31. Системы троек Штейнера.
  32. Совершенные упаковки и разбиения.
  33. Апериодические замощения.
  34. Квазикристаллы. Фрактальная сложность.
  35. Дважды стохастические матрицы. Теорема Биркгофа.
  36. Наследственные свойства графов.
  37. Планарные графы. Хроматическое число графа.
  38. Род графа. Род группы.
  39. Собственные пространства оператора Лапласа на графе.
  40. Частичное восстановление совершенных структур.
  41. Сложность сборки слов. Теорема Мерекина.
  42. Компоненты кодов.



ДИСКРЕТНЫЙ АНАЛИЗ

Научно-исследовательский семинар


ТЕОРИЯ ГРАФОВ

Научно-исследовательский семинар


ТЕОРИЯ КОДИРОВАНИЯ

Научно-исследовательский семинар


ФАКТОРНЫЕ ЯЗЫКИ

Научно-исследовательский семинар


КОМБИНАТОРИКА И СИМВОЛЬНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

Научно-исследовательский семинар