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