Тема 5. Размещения центров и медиан. Покрытия и паросочетания. (4 часов)

Центры, главные центры, абсолютные центры, главные абсолютные центры в графе. Алгоритмы нахождения абсолютных центров. Р-центры в графе, подходы к решению задачи. Медианы и Р-медианы в графе. Методы решения задачи о Р-медиане. Задачи о покрытии минимальной мощности и максимального веса. Задачи о паросочетании максимальной мощности и минимального веса.

КОМБИНАТОРИКА

Тема 6. Комбинаторные объекты. Размещения (2 часа)

Функции и размещения. Теорема о числе всех функций и сопровождающие понятия. Теорема о числе всех взаимно однозначных функций и сопровождающие понятия. Теорема о числе всех перестановок и сопровождающие понятия. Теорема о числе всех упорядоченных размещений n объектов по m ящикам и сопровождающие понятия.

Тема 7. Перестановки. Генерирование перестановок (3 часа)

Перестановки. Суперпозиция перестановок, тождественная и обратная перестановки, группы перестановок. Разложения на циклы. Лемма 1 о суперпозиции перестановок. Знак суперпозиции перестановок. Лемма о знаке произвольного цикла. Лемма о знаке произвольной перестановки. Схема маршрутов, как способ нахождения порядка перестановки. Знак перестановки. Генерирование всех перестановок на основе отношения лексикографического порядка. Графовая модель интерпретации последовательности перестановок, полученных с помощью различных алгоритмов.

Тема 8. Подмножества множества с повторениями и без повторений. Генерирование подмножеств множества (3 часа)

Подмножества множества. Генерирование подмножеств множеств с помощью перечисления целых чисел. Подмножества множества. Генерирование подмножеств множеств с помощью бинарного кода Грэя. Графовая модель представления последовательности всех подмножеств множества, сгенерированных с помощью кода Грэя. Множества с повторениями. Генерирование всех подмножеств множества с повторениями. Графовая модель всех подмножеств множества с повторениями.

Тема 9. К-элементные подмножества множества с повторениями и без повторений. Генерирование к-элементных подмножеств множества (3 часа)

K-элементные подмножества. Биноминальные коэффициенты. Треугольник Паскаля. Тождество Коши. Алгебраическое и комбинаторные доказательства. Доказательство формулы для числа всех к – элементных подмножеств в n-элементном множестве, алгебраическое и комбинаторное. K-элементные подмножества множества с повторениями. Теорема о числе к-элементных подмножеств в множестве с повторениями. Генерирование K-элементные подмножеств. Генерирование всех К - элементных подмножеств таким образом, что каждое последующее подмножество образуется из предыдущего удалением одного элемента и добавлением другого.

Графовая модель представления всех к - элементных подмножеств сгенерированных таким образом, что каждое последующее подмножество образуется из предыдущего удалением одного элемента и добавлением другого.

ТЕМА 10. РАЗБИЕНИЯ МНОЖЕСТВА И РАЗБИЕНИЯ ЧИСЕЛ (3часа)

Разбиения множества. Определения и основные свойства. Число Белла. Число Стирлинга II-го рода. Число Стирлинга I-го рода. Разбиение чисел. Теорема, связанная с диаграммой Феррерса. Теорема о числе разбиений числа n на попарно различные слагаемые (Липский «Комбинаторика для программистов»).

ТЕМА 11. ПРОИЗВОДЯЩИЕ ФУНКЦИИ (2 часа)

Производящие функции. Основные определения, замечания, свойства. Вычисления всех к – элементных подмножеств в n – элементном множестве. Вычисления всех к – элементных подмножеств в n – элементном множестве с повторениями. Применение к вычислению числа бинарных деревьев с n вершинами.

ТЕМА 12. МЕТОД ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ (1 час)

Метод включений и исключений. Основная теорема. Вычисление числа к – элементных подмножеств в множестве с повторениями. Подсчет числа инверсий в n – элементном множестве.

АЛГЕБРА ЛОГИКИ

ТЕМА 13. АЛГЕБРА ВЫСКАЗЫВАНИЙ. ОСНОВНЫЕ ПОНЯТИЯ (4 часа)

Функции алгебры логики. Два класса симметрических функций. Элементарные функции алгебры логики. Формулы. Реализация функций формулами. Сложение n-разрядных двоичных чисел. Задача о вызове свободного лифта. Эквивалентность формул.

ТЕМА 14. АЛГЕБРА ВЫСКАЗЫВАНИЙ. ЛОГИЧЕСКИЕ ВЫВОДЫ (4 часа)

Свойство элементарных функций. Правило тождественных преобразований. Принцип резолюций. Принцип двойственности. Общезначимость и противоречивость логики высказываний. СДНФ. СКНФ. Полином Жегалкина. Логические следствия.

ТЕМА 15. ПОЛНОТА И ЗАМКНУТОСТЬ, ВАЖНЕЙШИЕ ЗАМКНУТЫЕ КЛАССЫ, ТЕОРЕМА О ПОЛНОТЕ, ПРЕДСТАВЛЕНИЯ О РЕЗУЛЬТАТАХ ПОСТА (4 часа) (по С. В. Яблонскому Ведение в дискретную математику, стр. 30-42). МАШИНЫ ТЬЮРИНГА - МАШИННЫЕ КОДЫ И ИХ ПРЕОБРАЗЛВАНИЯ (стр. 113 -129.)

ТЕМА 16. АЛГЕБРА ПРЕДИКАТОВ (4 часа)

Согласно лекциям.