|
|
| (не показана 51 промежуточная версия 1 участника) |
| Строка 1: |
Строка 1: |
| | Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП | | Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП |
| − |
| |
| − | Курс читает доцент [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
| |
| − |
| |
| − | ==Объявления==
| |
| − |
| |
| − | ==Вопросы к экзамену==
| |
| − |
| |
| − | # Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
| |
| − | # Верхняя оценка биномиального коэффициента. Поведение последовательности биномиальных коэффициентов. Асимптотика суммы биномиальных коэффициентов.
| |
| − | # Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа п-сетей с h ребрами.
| |
| − | # Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.
| |
| − | # Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
| |
| − | # Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.
| |
| − | # Полнота в k-значной логике. Теорема о представимости функций k-значной логики в 1-й форме. Теорема о полноте системы Поста в k-значной логике.
| |
| − | # Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов.
| |
| − | # Теорема о существовании алгоритма распознавания полноты в k-значной логике.
| |
| − | # Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
| |
| − | # Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого.
| |
| − | # Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
| |
| − | # Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата.
| |
| − | # Полнота для конечных автоматов. Операция суперпозиции. Теорема о несуществовании конечных полных систем в функциональной системе автоматных функций с операцией суперпозиции.
| |
| − | # Зависимость с запаздыванием. Операция обратной связи. Теорема о существовании конечных полных систем в функциональной системе автоматных функций с операциями суперпозиции и обратной связи. Несводимость операций суперпозиции и обратной связи друг к другу.
| |
| − | #Дизъюнктивные нормальные формы. Импликанта и простая ипликанта функции. Сокращенная ДНФ и способы ее построения.
| |
| − | #Тупиковые, минимальные и кратчайшие ДНФ, алгоритм построения всех тупиковых ДНФ.
| |
| − | #Ядровая импликанта и ядро функции, ДНФ Квайна. ДНФ "сумма тупиковых". Теорема Журавлева о критерии вхождения простой импликанты функции в ДНФ "сумма тупиковых".
| |
| − | #Локальные алгоритмы. Теорема Журавлева о невозможности построения ДНФ "сумма тупиковых" в классе локальных алгоритмов.
| |
| − | # Схемы из функциональных элементов (СФЭ). Метод Лупанова построения СФЭ в базисе из элементов конъюнкции, дизъюнкции и отрицания для функций алгебры логики.
| |
| − |
| |
| − | ==Лекции==
| |
| − |
| |
| − | '''Лекция 1'''. Комбинаторика. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.
| |
| − |
| |
| − | Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов. [1] стр. 171-183, 213-214, [6], [[Media: dmus1-selezn.pdf| Слайды к лекции 1]]
| |
| − |
| |
| − | '''Лекция 2'''. Графы. Граф и сеть. Оценки числа графов и сетей различных видов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.
| |
| − |
| |
| − | Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа п-сетей с h ребрами. Планарные графы. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. [1] стр. 222-227, [2] стр. 33-37
| |
| − |
| |
| − | '''Лекция 3'''. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.
| |
| − |
| |
| − | Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея. [5] стр. 28-31 [[Media: dmus3-selezn.pdf| Слайды к лекции 3]]
| |
| − |
| |
| − | '''Лекция 4'''. Многозначные логики. Способы представления k-значных функций. Полнота. Система Поста.
| |
| − |
| |
| − | Функции k-значной логики. Способы представления k-значных функций: 1-я и 2-я формы, полиномы. Полные системы. Теорема о полноте системы Поста в k-значной логике. [1] стр. 43-50, 69-73. [[Media: dmus4-selezn.pdf| Слайды к лекции 4]]
| |
| − |
| |
| − | '''Лекция 5'''. Многозначные логики. Алгоритм распознавания полноты конечных систем k-значных функций. Теорема Кузнецова о функциональной полноте.
| |
| − |
| |
| − | Теорема о существовании алгоритма распознавания полноты в k-значной логике. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. [1] стр. 50-56. [[Media: dmus5-selezn.pdf| Слайды к лекции 5]]
| |
| − |
| |
| − | '''Лекция 6'''. Многозначные логики. Теорема Яблонского. Теорема Слупецкого.
| |
| − |
| |
| − | Существенные функции. Три леммы о существенных функциях. Теорема Яблонского. Теорема Слупецкого. [1] стр. 56-65.
| |
| − |
| |
| − | '''Лекция 7'''. Многозначные логики. Особенности многозначных логик.
| |
| − |
| |
| − | Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. [1] стр. 67-69.
| |
| − |
| |
| − | '''Лекция 8'''. Эксперименты с автоматами. Алгоритмическая неразрешимость проблемы полноты для автоматов.
| |
| − |
| |
| − | Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата. Проблема полноты для конечных автоматов. Теорема о существовании конечных полных систем автоматов. Теорема о несводимости операций суперпозиции и обратной связи друг к другу. Теорема об алгоритмической неразрешимости распознавания полноты систем автоматов. [2] стр. 83-86, [1] стр. 86-113
| |
| − |
| |
| − | '''Лекция 9'''. Проблема минимизации ДНФ. Локальные алгоритмы. Построение ДНФ сумма тупиковых в классе локальных алгоритмов. Невозможность построения ДНФ сумма минимальных в классе локальных алгоритмов. [3] стр. 12-21
| |
| − |
| |
| − | '''Лекция 10'''. Асимптотически наилучший метод синтеза СФЭ. Инвариантные классы и их свойства. Синтез СФЭ для функций из некоторых инвариантных классов. [4] стр. 65-69, , [3] стр. 5-10
| |
| − |
| |
| − | '''Лекция 11'''. Нижние оценки сложности реализации функций алгебры логики π-схемами и формулами.
| |
| − |
| |
| − | '''Лекция 12'''. Эквивалентные преобразования формул двузначной логики. Пример Линдона.
| |
| − |
| |
| − | '''Лекция 13'''. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
| |
| − |
| |
| − | '''Лекция 14'''. Конечные поля и их основные свойства. Коды Боуза-Чоудхури-Хоквингема.
| |
| − |
| |
| − | '''Литература'''
| |
| − |
| |
| − | # Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
| |
| − | # Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
| |
| − | # Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ им. М.В. Ломоносова, 2001.
| |
| − | # Нигматуллин Р.Г. Сложность булевых функций. Казань: Изд-во Казанского университета, 1983.
| |
| − | # Харари Ф. Теория графов. М.: Мир, 1973.
| |
| − | # Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
| |
| − |
| |
| − |
| |
| − |
| |
| | | | |
| | [[Категория:Лекционные курсы кафедры МК]] | | [[Категория:Лекционные курсы кафедры МК]] |
