Дискретная математика 2 (группа 141)

Лектор - доц. Селезнева Светлана Николаевна.

Программа курса

• Лекция 1 (7.02.2014 г.). Комбинаторные объекты и комбинаторные числа. Правило суммы и правило произведения. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Теорема о числе сочетаний с повторениями.

Задачи к лекции: найти число объектов определенного вида.

• Лекция 2 (14.02.2014 г.). Свойства биномиальных коэффициентов и их последовательностей. Формула бинома Ньютона. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи.

Задачи к лекции: при помощи производящих функций вычислить комбинаторную сумму или доказать комбинаторное тождество; при помощи формулы включений-исключений найти число объектов определенного вида.

• Лекция 3 (21.02.2014 г.). Функции натурального аргумента (последовательности). Рекуррентные уравнения. Линейные однородные рекуррентные уравнения (ЛОРУ). Частное решение ЛОРУ, лемма о линейной комбинации частных решений ЛОРУ. Общее решение ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ), их частные и общие решения. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ.

Задачи к лекции: решить заданное ЛОРУ или ЛНРУ.

• Лекция 4 (28.02.2014 г.). Схемы из функциональных элементов (СФЭ) в некотором базисе. Сложность и глубина СФЭ. Линейные программы и их связь с СФЭ.

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

• Лекция 5 (7.03.2014 г.). Сумматор. Сложность одноразрядного сумматора. Теорема о верхней оценке сложности n-разрядного сумматора в базисе из конъюнкции, дизъюнкции и отрицания. Вычитатель. Теорема о верхней оценке сложности n-разрядного вычитателя в базисе из конъюнкции, дизъюнкции и отрицания.

Задачи к лекции: построить n-разрядный сумматор или вычитатель при заданном n.

• Лекция 6 (14.03.2014 г.). Умножитель. Леммы о сложности СФЭ для умножения на разряд и на степень двойки. Лемма о соотношении сложностей СФЭ для (n+1)-разрядного и n-разрядного умножителей. Теорема Карацубы о сложности СФЭ для n-разрядного умножителя.

Задачи к лекции: построить n-разрядный умножитель при заданном n.