Лекции Костенко К. И. ФКТиПМ, КубГУ. 146 стр. отсканированные
тетрадные страницы с хорошим почерком.
Лекции по вопросам за 1 семестр:
Мощность множеств.
Отображения. Обратные отображения.
Отношения. Представление и операции над отношениями.
Свойства отношений на множестве.
Отношения эквивалентности.
Отношения порядка.
Основные комбинаторные правила.
Размещения.
Сочетания без повторений
Сочетания с повторениями.
Разбиения множеств на части.
Формула включений – исключений.
Ф. А. Л. Существенность переменных.
Формулы. Эквивалентность формул.
Теорема о замене равных. Соотношения эквивалентности.
Разложение ф. а. л. по переменным.
Минимальные ДНФ.
Геометрическая интерпретация минимальных ДНФ.
Максимальные конъюнкции и их свойства.
Полные системы функций. Теорема редукции.
Полиномы Жегалкина.
Классы Т0 и Т1.
Двойственные функции.
Класс S. Лемма о несамодвойственной функции.
Класс M.
Лемма о немонотонной функции.
Класс L. Лемма о нелинейной функции.
Критерий полноты в P2.
Предполные классы и их свойства.
Способы задания графов.
Пути и циклы в графах.
Транзитивное замыкание графов.
Изоморфизм и планарность графов.
Непланарность графов K33 и A5.
Критерий планарности графов.
Деревья и их свойства.
Циклы Эйлера. Теорема Эйлера (необходимость).
Циклы Эйлера (достаточность).
Циклы Гамильтона. Переборный алгоритм.
Достаточное условие существования циклов Гамильтона.
Суммы графов.
Фундаментальное семейство циклов (построение).
Фундаментальное семейство циклов (доказательство фундаментальности)
Хроматическое число графов. Критерий 2-хроматичности.
Оценка значения хроматического числа графа. Критические графы.
Ядра графов.
Минимальные основные деревья в графах
Лекции по вопросам за 1 семестр:
Мощность множеств.
Отображения. Обратные отображения.
Отношения. Представление и операции над отношениями.
Свойства отношений на множестве.
Отношения эквивалентности.
Отношения порядка.
Основные комбинаторные правила.
Размещения.
Сочетания без повторений
Сочетания с повторениями.
Разбиения множеств на части.
Формула включений – исключений.
Ф. А. Л. Существенность переменных.
Формулы. Эквивалентность формул.
Теорема о замене равных. Соотношения эквивалентности.
Разложение ф. а. л. по переменным.
Минимальные ДНФ.
Геометрическая интерпретация минимальных ДНФ.
Максимальные конъюнкции и их свойства.
Полные системы функций. Теорема редукции.
Полиномы Жегалкина.
Классы Т0 и Т1.
Двойственные функции.
Класс S. Лемма о несамодвойственной функции.
Класс M.
Лемма о немонотонной функции.
Класс L. Лемма о нелинейной функции.
Критерий полноты в P2.
Предполные классы и их свойства.
Способы задания графов.
Пути и циклы в графах.
Транзитивное замыкание графов.
Изоморфизм и планарность графов.
Непланарность графов K33 и A5.
Критерий планарности графов.
Деревья и их свойства.
Циклы Эйлера. Теорема Эйлера (необходимость).
Циклы Эйлера (достаточность).
Циклы Гамильтона. Переборный алгоритм.
Достаточное условие существования циклов Гамильтона.
Суммы графов.
Фундаментальное семейство циклов (построение).
Фундаментальное семейство циклов (доказательство фундаментальности)
Хроматическое число графов. Критерий 2-хроматичности.
Оценка значения хроматического числа графа. Критические графы.
Ядра графов.
Минимальные основные деревья в графах