Производящие функции. Основные определения, замечания, свойства. Вычисления всех к – элементных подмножеств в n – элементном множестве. Вычисления всех к – элементных подмножеств в n – элементном множестве с повторениями. Применение к вычислению числа бинарных деревьев с n вершинами.
ТЕМА 12. МЕТОД ВКЛЮЧЕНИЙ И ИСКЛЮЧЕНИЙ (1 час)
Метод включений и исключений. Основная теорема. Вычисление числа к – элементных подмножеств в множестве с повторениями. Подсчет числа инверсий в n – элементном множестве.
АЛГЕБРА ЛОГИКИ
ТЕМА 13. АЛГЕБРА ВЫСКАЗЫВАНИЙ. ОСНОВНЫЕ ПОНЯТИЯ (4 часа)
Функции алгебры логики. Два класса симметрических функций. Элементарные функции алгебры логики. Формулы. Реализация функций формулами. Сложение n-разрядных двоичных чисел. Задача о вызове свободного лифта. Эквивалентность формул.
ТЕМА 14. АЛГЕБРА ВЫСКАЗЫВАНИЙ. ЛОГИЧЕСКИЕ ВЫВОДЫ (4 часа)
Свойство элементарных функций. Правило тождественных преобразований. Принцип резолюций. Принцип двойственности. Общезначимость и противоречивость логики высказываний. СДНФ. СКНФ. Полином Жегалкина. Логические следствия.
ТЕМА 15. ПОЛНОТА И ЗАМКНУТОСТЬ, ВАЖНЕЙШИЕ ЗАМКНУТЫЕ КЛАССЫ, ТЕОРЕМА О ПОЛНОТЕ, ПРЕДСТАВЛЕНИЯ О РЕЗУЛЬТАТАХ ПОСТА (4 часа) (по С. В. Яблонскому Ведение в дискретную математику, стр. 30-42). МАШИНЫ ТЬЮРИНГА - МАШИННЫЕ КОДЫ И ИХ ПРЕОБРАЗЛВАНИЯ (стр. 113 -129.)
