Дискретные модели управляющих систем — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
==Лекции==
 
==Лекции==
  
 +
Лекция 1. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.
 +
 +
Размещения, перестановки, размещения с повторениями, сочетания, их число рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов.
 +
 +
Лекция 2. Графы и сети. Оценки графов и сетей различных типов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.
 +
 +
Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа π-сетей с h ребрами. Планарные графы. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.
 +
 +
Лекция 3. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.
 +
 +
Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея.
 +
 +
Лекция 4. Проблема полноты. Теорема о полноте систем функций двузначной логики. Алгоритм распознавания полноты систем функций k-значной логики.
 +
 +
Лекция 5. Теорема Слупецкого. Особенности k-значных логик.
 +
 +
Лекция 6. Эксперименты с автоматами. Алгоритмическая неразрешимость проблемы полноты для автоматов.
 +
 +
Лекция 7. Проблема минимизации ДНФ. Локальные алгоритмы. Построение ДНФ сумма тупиковых в классе локальных алгоритмов. Невозможность построения ДНФ сумма минимальных в классе локальных алгоритмов.
 +
 +
Лекция 8. Асимптотически наилучший метод синтеза СФЭ. Инвариантные классы и их свойства. Синтез СФЭ для функций из некоторых инвариантных классов.
 +
 +
Лекция 9. Нижние оценки сложности реализации функций алгебры логики π-схемами и формулами.
 +
 +
Лекция 10. Эквивалентные преобразования формул двузначной логики. Пример Линдона.
 +
 +
Лекция 11. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
 +
 +
Лекция 12. Конечные поля и их основные свойства. Коды Боуза-Чоудхури-Хоквингема.
  
 
==Вопросы к экзамену==
 
==Вопросы к экзамену==

Версия 16:44, 2 марта 2015

Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП

Курс читает доцент Селезнева Светлана Николаевна

Лекции

Лекция 1. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.

Размещения, перестановки, размещения с повторениями, сочетания, их число рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов.

Лекция 2. Графы и сети. Оценки графов и сетей различных типов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.

Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа π-сетей с h ребрами. Планарные графы. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.

Лекция 3. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.

Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея.

Лекция 4. Проблема полноты. Теорема о полноте систем функций двузначной логики. Алгоритм распознавания полноты систем функций k-значной логики.

Лекция 5. Теорема Слупецкого. Особенности k-значных логик.

Лекция 6. Эксперименты с автоматами. Алгоритмическая неразрешимость проблемы полноты для автоматов.

Лекция 7. Проблема минимизации ДНФ. Локальные алгоритмы. Построение ДНФ сумма тупиковых в классе локальных алгоритмов. Невозможность построения ДНФ сумма минимальных в классе локальных алгоритмов.

Лекция 8. Асимптотически наилучший метод синтеза СФЭ. Инвариантные классы и их свойства. Синтез СФЭ для функций из некоторых инвариантных классов.

Лекция 9. Нижние оценки сложности реализации функций алгебры логики π-схемами и формулами.

Лекция 10. Эквивалентные преобразования формул двузначной логики. Пример Линдона.

Лекция 11. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.

Лекция 12. Конечные поля и их основные свойства. Коды Боуза-Чоудхури-Хоквингема.

Вопросы к экзамену

(весенний семестр 2014/2015 учебного года, аспиранты 1 г/о кафедр ИО, МК, ММП, лектор — доцент С.Н. Селезнева)


Литература

  • Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
  • Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.