Geum.ru

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

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

Содержание


Теория вычислений
2. Регулярные множества и автоматы
3. КС-языки и автоматы с магазинной памятью
4. Машины Тьюринга и проблемы разрешимости
5. Классы P и NP
6. Иерархии языков и задач
7. Сети Петри
Дискретная математика
Теория помехоустойчивого кодирования
Математические методы защиты информации
2. Сжатие информации
Прикладная логика
Денотационная семантика
2. λ-Исчисление как язык программирования.
3. Типизированное λ–исчисление.
4. Семантика Скотта для бестипового λ-исчисления.
Дополнительные главы линейной алгебры
История математики
Теория графов
Дискретный анализ и комбинаторика
...
Полное содержание
Подобный материал:
1   2   3   4   5   6   7

Примечания:

Настоящий примерный учебный план составлен в соответствии с федеральным государственным образовательным стандартом (ФГОС) высшего профессионального образования по направлению подготовки магистров "Математика".

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

В соответствии с Типовым положением о вузе к видам учебной работы отнесены: лекции, консультации, семинары, практические занятия, лабораторные работы, контрольные работы, коллоквиумы, самостоятельные работы, научно-исследовательская работа, практики, курсовое проектирование (курсовая работа).


Приложение 3


^ ТЕОРИЯ ВЫЧИСЛЕНИЙ


1. Введение

Цепочки, языки, графы и деревья. Порождающие грамматики и распознаватели, классификация Хомского, свойства КЗ-грамматик.

^ 2. Регулярные множества и автоматы

Регулярные множества и выражения, приведение КС-грамматики к виду без е-правил. Конечные автоматы, теорема о детерминизации. Регулярные грамматики, лемма о разрастании для регулярных множеств, пример не регулярного множества.

^ 3. КС-языки и автоматы с магазинной памятью

Деревья вывода и эквивалентные преобразования КС-грамматик. Однозначность КС-грамматик и языков, приведение КС-грамматики к нормальной форме Хомского. Лемма о разрастании для КС-языков, пример языка, не являющегося КС-языком. Свойства замкнутости и незамкнутости класса КС-языков. Автоматы с магазинной памятью и их связь с КС-языками. Детерминированные КС-языки и их свойства.

^ 4. Машины Тьюринга и проблемы разрешимости

Машины Тьюринга (ТМ) и их связь с порождающими грамматиками. Линейно-ограниченные автоматы и их связь с КЗ-языками. Алгоритмически неразрешимые проблемы, метод сведения, неразрешимые проблемы КС-грамматик и языков.

^ 5. Классы P и NP

Сложность алгоритмов и задач. Недетерминированные ТМ (NTM), их детерминированное моделирование. Классы P и NP, полиномиальная сводимость, NP-полные и NP-трудные языки и задачи, Теорема Кука. NP-полнота задачи о 3-выполнимости и задачи о клике. NP-полнота задачи о вершинном покрытии и точном покрытии 3-множествами. NP-полнота задачи о трехмерном сочетании. Структура класса NP, список задач из NPC и кандидаты в NPI, класс co-NP.

^ 6. Иерархии языков и задач

Многоленточные ТМ и их моделирование. Класс P-SPACE, примеры языков, полных для P-SPACE, и задач, требующих экспоненциальной памяти. Иерархия по емкостной сложности для DTM. Понятие моделирования, теорема об ускорении. Существование сколь угодно сложных задач, теорема Цейтина. RАМ с равномерным и логарифмическим критерием, ее связь с TM. Техника следов и нижняя оценка сложности распознавания симметрии. Альтернирующие машины Тьюринга (ATM) и их свойства. Полиномиальная иерархия, ее связь с ATM. Модели вычислений PTM, RTM и CTM, класс #P, примеры #P-полных задач. Параллельные RAM, их классификация и свойства. Тезисы инвариантности и параллельного выполнения.

^ 7. Сети Петри

Сети Петри, графы разметок, теорема о дополнительных фишках. Моделирование сетями Петри, представление блок-схем, задачи о взаимном исключении, о производителе/потребителе, об обедающих философах, о читателях/писателях. Основные свойства сетей Петри, проблемы R-включения и R-эквивалентности. Покрывающее дерево, алгоритм проверки ограниченности сети. Полное покрывающее дерево и разрешимость проблемы ограниченности места в сети. Алгоритмы проверки t-тупиковости, безопасности, потенциальной живости, получения местом фишки, неограниченности срабатываний перехода. Проблемы достижимости и живости, их взаимосвязь. Языки сетей Петри, разрешимость проблемы принадлежности.


^ ДИСКРЕТНАЯ МАТЕМАТИКА

Выборки. Перестановки, сочетания, перестановки с повторениями, сочетания с повторениями. Биномиальная  и полиномиальная теоремы. Разбиения. Числа Стирлинга 1-го и 2-го рода; свойства чисел Стирлинга; обращение Стирлинга. Числа Белла и их свойства. Формулы обращения. Дзета-функция и функция Мёбиуса. Метод включений и исключений. Оценки для числа элементов, не обладающих ни одним  из  n свойств. Формула для числа элементов, обладающих в точности m свойствами, 0 ≤ m ≤ n. Формула обращения Мёбиуса. Производящие функции. Примеры применения метода производящих функций для решения комбинаторных задач. Линейные рекуррентные соотношения с постоянными коэффициентами. Теорема о решении линейных рекуррентных соотношений. Числа Фибоначчи. Числа Каталана. Экспоненциальные производящие функции. Трансверсаль. Теорема о числе трансверсалей. Задача о гаремах. Латинские прямоугольники. Теорема Рамсея. Теорема Рамсея для графов.  Верхние и нижние оценки для чисел Рамсея. Теорема Эрдеша – Секереша. Теорема Ван дер Вардена  об арифметических последовательностях.

Булевы функции, их реализация формулами. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Принцип двойственности. Полином Жегалкина. Предполные классы функций. Теорема Поста. Минимальные и кратчайшие ДНФ. Алгоритм Квайна – Мак-Клоски. Карты Карно. Метод Блейка получения сокращенной ДНФ. Таблицы Квайна. Схема из функциональных элементов, ее сложность. Метод Лупанова синтеза схем из функциональных элементов. Мощностной метод получения нижней оценки функции Шеннона для СФЭ. Контактная схема, ее сложность. Функция Шеннона для контактных схем. Метод каскадов для контактных схем. Нижняя оценка функции Шеннона для контактных схем. Схема Кардо. Ограниченно-детерминированные функции. Способы их задания. Конечный детерминированный автомат с выходом. Автоматные функции, связь с ограниченно-детерминированными функциями. Схема из автоматных элементов. Теорема о не существовании конечных полных систем автоматных функций. Схемы из автоматных элементов с использованием операции обратной связи. Реализация произвольной автоматной функции.

Графы. Основные понятия. Способы представления графов. Перечисление графов на нумерованных вершинах. Верхняя оценка для числа неизоморфных графов с  q  ребрами. Деревья и их свойства. Оценка числа неизоморфных корневых  деревьев с  q   ребрами. Теорема Кэли о числе помеченных деревьев. Связность. Свойства двусвязных графов. Теорема Менгера. Эйлеровы циклы. Теорема Эйлера. Теорема Эйлера для ориентированных графов, последовательности де Брейна. Гамильтоновы циклы. Теорема Дирака. Гамильтоновы циклы и степенные последовательности. Теорема Хватала. Гамильтоновы циклы и совершенные паросочетания. Теорема Финка. Укладка графа в пространство. Планарный и плоский графы. Формула Эйлера. Теорема Понтрягина-Куратовского. Алгебраические критерии планарности. Правильная раскраска вершин графа. Оценки хроматического числа. Теорема Брукса. Теорема Зыкова. Раскраски планарных графов. Теорема о четырех красках. Совершенные графы. Теорема Ловаца. Совершенность триангулированных графов. Правильная раскраска ребер графа. Хроматический индекс. Теорема Кёнига о хроматическом индексе двудольных графов. Теорема Визинга.


^ ТЕОРИЯ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ


Модель канала связи с шумами, скорость кода, пропускная способность. Теорема Шеннона для двоичного симметричного канала связи с шумом (с доказательством). Вероятность ошибки декодирования. Стандартное расположение. Синдром.

Поле Галуа, его свойства.

Линейные коды. Кодирование и декодирование. Общие свойства линейных кодов. Теорема о связи проверочной и порождающей матриц. Теорема Глаголева.

Границы объема кода: граница Синглтона, граница Хэмминга, граница Варшамова-Гилберта, граница Плоткина. Оценки мощностей кодов, теоремы Джонсона.

Методы построения новых кодов из заданных. Комбинирование кодов. Теорема Плоткина. Каскадная конструкция.

Совершенные коды. Теорема о существовании совершенных кодов. Коды Хемминга над GF(q), способы задания, кодирование, декодирование, единственность. Группа автоморфизмов кода Хэмминга. Конструкции совершенных кодов: свитчинговые (коды Васильева, Моллара, конструкция -компонент), каскадные (коды Зиновьева, Соловьевой, Фелпса). Оценки числа совершенных кодов. Общие свойства совершенных кодов, теоремы Шапиро и Злотника, группа автоморфизмов совершенных кодов. Связь совершенных кодов с блок схемами, конструкция Ассмуса и Маттсона.

Матрица Адамара. Коды Адамара. Связь кодов Адамара с кодами Хэмминга и блок-схемами.

Коды Рида-Маллера, группа автоморфизмов. Код Голея, его свойства. Код Нордстрома-Робинсона.

Двойственные коды. Весовой энумератор. Дискретное преобразование Фурье. Тождества Мак-Вильямс.

Теория циклических кодов. Кольцо многочленов над полем Галуа. Определение циклического кода. Теорема о необходимом и достаточном условии существования циклического кода с порождающим многочленом g(x). Кодирование и декодирование циклических кодов. Важные классы циклических кодов: коды Хэмминга, коды Боуза-Чоудхури- Хоквингема (БЧХ-коды), коды Рида-Соломона, коды Юстесена, коды Гоппы.


^ МАТЕМАТИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ


1. Введение в криптологию

Введение в криптологию. Секретность и имитостойкость. Основные идеи. Криптография и криптоанализ.

Криптографические системы с секретными ключами. Подстановки.. Перестановки. Полиалфавитные шифры. Шифр с бегущим ключом. Криптографические системы коды. Стандарты шифрования данных DES, AES, GOST. S-блоки, APN-функции, их свойства.

Теорема Шеннона о существовании совершенно секретных шифров.

Криптографические системы с открытыми ключами. Односторонняя функция с лазейкой. “Шарады” Меркля.

Криптосистема Диффи и Хэллмана и проблема вычисления дискретного логарифма.

Криптосистема RSA и проблема разложения числа на простые сомножители.

Криптосистема Меркля-Хэллмана, основанная на задаче об укладке ранца. Криптоанализ системы Меркля-Хэллмана.

Криптосистема Шамира.

Кодирующая система МакЭлиса. Криптосистема МакЭлиса, построенная на коде Рида-Маллера.

Цифровая подпись, применение различных криптосистем для создания цифровой подписи.

Криптосистемы на эллиптических кривых.

Применение теории кодирования в криптографии. Проблема аутентификации. Распределение секретов.

^ 2. Сжатие информации

Разделимые и префиксные коды. Стоимость кодирования. Неравенство Крафта-Макмиллана. Теорема Крафта, теорема Макмиллана.

Оптимальное кодирование. Метод Хаффмена. Метод Фано.

Энтропия, ее свойства. Метод Шеннона для бернуллиевских источников. Теорема Шеннона.

Критерий разделимости побуквенного кодирования. Теоремы Маркова. Алгоритм распознавания разделимости.

Универсальное кодирование, теорема Фитингофа.

Код Левенштейна. Код “стопка книг”.

Адаптивные методы сжатия данных. Методы Лемпела-Зива и их модификации. Адаптивный метод Хаффмена.

Арифметический код.


^ ПРИКЛАДНАЯ ЛОГИКА


Раздел 1. Общие сведения о языках логического программирования. Унификации. Логическая программа. Исчисление предикатов. Хорновские дизъюнкты. Унификации, Алгоритм унификации, Теорема об унификации.

Раздел 2. Резолюции. Резольвента, метод резолюций. SLD-вывод, опровержение. Теорема о корректности метода резолюций.

Раздел 3. Модели Эрбрана. Интерпретация Эрбрана. Модель Эрбрана. Существование модели Эрбрана для выполнимого множества предложений.

Раздел 4. Наименьшая модель Эрбрана. Теорема Тарского. Оператор непосредственного следствия. Теорема о наименьшей модели Эрбрана.

Раздел 5. Полнота метода резолюций. Лемма о mgu. Лемма о подъеме. Решение программы. Теорема о множестве решений программы. Теорема о полноте резолюций.

Раздел 6. Алгоритмические свойства наименьшей модели Эрбрана. Рекурсивная перечислимость наименьшей модели Эрбрана. Теорема о вычислимости ч.р.ф., ее следствие.

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

Раздел 8. Язык и семантика темпоральной логики программ. Язык и семантика пропозициональной темпоральной логики. Примеры общезначимых формул.

Раздел 9. Исчисление темпоральной логики программ. Исчисление, теорема о корректности. Теоремы о дедукции и слабой полноте. Отсутствие сильной полноты.


^ ДЕНОТАЦИОННАЯ СЕМАНТИКА


1. Бестиповое λ-исчисление. Синтаксис. λ–Термы. Подтермы. Вхожде­ние подтерма в терм. Множество свободных переменных терма. Свобод­ные и связанные вхождения переменных, а также области действия для λ. α–Эквивалентность λ–термов. Терм свободный для подстановки. Опе­рация подстановки терма в терм вместо всех свободных вхождений пере­менной. Свойства подстановки. β–Редукции. Редексы. Нормальные формы. Нормализуемые термы. Теорема Чёрча-Россера (доказательство через па­раллельные редукции и их свойства). Единственность нормальной формы. β–Эквивалентность и ее свойствами.

^ 2. λ-Исчисление как язык программирования. Натуральные числа Чёрча и определение представимых функций. Представимость любых всю­ду определенных рекурсивных функций. Термы True, False, Cond и их свойства. Свойства терма IsNull. Кодировка пар: термы First, Second, Pair и их свойства. Отнимание 1 в λ–исчислении. Теорема о неподвиж­ной точке. Представимость простейших функций. Представимость компози­ции. Представимость примитивной рекурсии. Представимость μ–оператора. Неразрешимость проблемы существования нормальной формы для термов.

^ 3. Типизированное λ–исчисление. Простые и составные типы. Прави­ла приписывания типов. Типизируемые термы. Теорема о нормализации типизируемых термов (без доказательства).

^ 4. Семантика Скотта для бестипового λ-исчисления. Направленные множества, Полные частично упорядоченные множества (пчум). Топология Скотта. Критерий непрерывности в топологии Скотта. Монотонность непре­рывных отображений. Декартовым произведением семейств пчум. Пчум всех непрерывных отображений полных чум. Теорема о непрерывности функ­ций от двух аргументов. Теорема о непрерывности аппликации. Теорема о непрерывности λ–абстракции. Проекция полных чумов. Ретракты и ретрак­ции. Свойства проекций полных чумов. Перенесение проекций с полных чум на пчумы их непрерывных отображений. Определение пчум D∞. Опреде­ление отображений Φmn и их свойства. Определение операции · на D∞, ее непрерывность, связь с операцией применения (аппликации) на Dn+1×Dn. Связь операции · и упорядочения. Теорема о функциональной полно­те . Изоморфизм и гомеоморфизм упорядоченных множеств D∞ и [D∞→ D∞]. Представление непрерывных функций на с помощью опе­рации ·. Определение семантики Скотта для λ–термов. Теорема о связи β–эквивалентности и семантики Скотта.

5. Графиковая модель λ–исчисления. Определение графиковой моде­ли, ее отличие от модели Скотта.


^ ДОПОЛНИТЕЛЬНЫЕ ГЛАВЫ ЛИНЕЙНОЙ АЛГЕБРЫ


1. Введение. Особенности компьютерных вычислений. Обратная устойчивость. Гарантированная оценка точности.
2.1 Системы с квадратной матрицей, число обусловленности, определитель, упрощение с помощью ортогональных преобразований. Решение систем
2.2 Решение систем полного ранга. Метод регуляризации
3.1 Особенности спектра симметричных матриц. Теорема Штурма, последовательности Штурма
3.2 Вычисление собственных значений симметричных матриц. Примеры
3.3 Двусторонние последовательности Штурма и собственные векторы симметричных матриц.
3.4 Примеры: собственные функции оператора Лапласа, полиномы Лежандра и др.
4.1 Теорема Шура. Уравнение Сильвестра
4.2 Эпсилон-спектр, примеры, критерий отсутствия спектра на кривой.
4.3 Обобщенные уравнения Ляпунова
4.4 Задача дихотомии спектра, проекторы на инвариантные подпространства.
4.5 Дихотомия окружностью
4.6 Линейная дихотомия, эллиптическая дихотомия.
4.7 Одномерные спектральные портреты и канонический вид матриц.
4.8 Разложение полинома на множители


^ ИСТОРИЯ МАТЕМАТИКИ


1. История Российской академии наук.
2. Сибирское отделение Российской АН.
3. Новосибирский государственный университет.
4. Институт гидродинамики СО РАН.
5. Институт математики СО РАН.
6. История алгебры.
7. История геометрии.
8. История математического анализа.
9. История кибернетики.
10. История математической экономики.
11. История дискретной математики.
12. История комбинаторики.
13. История теории вероятностей.
14. История теории чисел
15. История криптографии.
16. История теоремы Ферма.
17. История гипотезы Римана.
18. История гипотезы Пуанкаре.


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

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


^ ДИСКРЕТНЫЙ АНАЛИЗ И КОМБИНАТОРИКА


1. Комбинаторика перечисления и кодирование.

Системы счисления и кодирование натуральных чисел. Задачи о нумерациях подмножеств конечного множества. Коды Грея. Нумерации объектов в порядке минимального изменения. -нумерации множества слов. Алгоритмы построения нумерующих отображений. Отображения конечных множеств, их кодирование и подсчет числа. Кодирование деревьев. Число деревьев. Примеры подсчёта с помощью рекуррентных уравнений и производящих функций.
  1. ^ Комбинаторика слов.

Некоторые классические символьные последовательности и способы их задания.

Универсальные слова. Задачи восстановления символьных последовательностей по их фрагментам. Коды без перекрытий. Комбинаторная сложность слов. Псевдослучайные последовательности. Последовательности де Брейна и их число. Графы перекрытия подслов символьных последовательностей. Задачи быстрой сборки слов. Алгоритмы сборки. Аддитивная сложность символьных последовательностей и ее связь с задачами быстрого умножения и вычисления полиномов. Оценки аддитивной сложности индивидуальных последовательностей.

^ 3. Кодирование структурированной информации и вложения дискретных пространств.

Понятия близости, расстояния, метрики. Структуры метрических пространств на множествах подмножеств, словах, символьных последовательностях. Реализация метрик графами.

Гиперкубовая архитектура вычислительных систем. Графы гиперкубов. Кодирование дискретных объектов и вложения в гиперкубы. Изоморфные и изометрические вложения. Вложения с растяжением ребер. Алгоритмы построения вложений.

Применение методов и алгоритмов вложения. Локально изометрическое кодирование табло. Сеточные графы структур cистолических вычислителей. Вложения деревьев. Суффиксные деревья. Префиксные коды.

^ 4. Булевы функции и дискретные модели генных сетей.

Булевы функции, их число, способы задания. Представление формулами. Нормальные формы. Единственность совершенной и сокращённой форм. Представления многочленами Жегалкина. Полнота систем булевых функций. Теорема Поста. K-значные логические функции. Схемы из функциональных элементов. Конечные автоматы.

Ориентированные графы и сети. Достижимость вершин. Алгоритмы нахождения внутренне и внешне устойчивых множеств. Базы и ядра. Алгоритм построения разрезов циклов. Логические производящие функции. Булевы методы в задачах теории графов. Диаметр, радиус и центр в ориентированных графах и алгоритмы их нахождения. Дискретные модели генных сетей. Анализ функционирования регуляторного контура генной сети.


^ УЧЕБНЫЙ СЕМИНАР КАФЕДРЫ


Научно-исследовательский семинар кафедры, в рамках которого в соответствии с ФГОС ВПО по направлению "010100 – Математика" производится обоснование темы, обсуждение плана и промежуточных результатов, что является основной формой планирования и корректировки индивидуальных планов научно-исследовательской работы магистрантов.


^ КОМБИНАТОРНЫЕ ЗАДАЧИ НА ГРАФАХ КЭЛИ


1. Основы теории графов Кэли.
    1. Группы: основные понятия, определения
      1. Симметрическая группа
      2. Гипероктаэдральная группа
    2. Графы: основные понятия, определения
      1. Регулярные и транзитивные графы
      2. Дистанционно–регулярные и дистанционно–транзитивные графы
    3. Графы Кэли
      1. Простейшие примеры графов Кэли
      2. Основные свойства графов Кэли
      3. Граф Хэмминга: дистанционно-транзитивный граф Кэли
      4. Граф Джонсона: дистанционно-транзитивный граф, не являющийся

графом Кэли
      1. Граф Кнезера: когда он является графом Кэли?
      2. Графы Кэли на симметрической группе
      3. Графы Кэли на гипероктаэдральной группе

2. Гамильтоновость. Графов Кэли
    1. Гамильтоновость гиперкуба
    2. Комбинаторные условия гамильтоновости
    3. Гипотезы Ловаса и Бабаи
    4. Гамильтоновость графов Кэли на произвольной конечной группе
    5. Гамильтоновость графов Кэли на симметрической группе
    6. Гамильтоновость Pancake графа
    7. Другие циклы Pancake графа
      1. Циклы длины шесть
      2. Циклы длины семь

3. Задача определения диаметра графов Кэли
    1. Диаметр графов Кэли на абелевых и неабелевых группах.
    2. Диаметр графов Кэли на симметрической и знакопеременной группах
    3. Pancake problem: комбинаторная задача в информатике и биоинформатике
      1. Оценки Гейтса и Пападимитроу на диаметр Pancake графа
      2. Улучшенные оценки Садбороу
      3. Точные значения диаметра Pancake графа
    4. Burnt Pancake problem: обобщение Pancake problem
      1. Оценки Кохена и Блюма на диаметр Burnt Pancake граф
      2. Улучшенные оценки Хейдари и Садбороу
      3. Точные значения диаметра Burnt Pancake графа