Специальные главы дискретной математики

Темы семинарских занятий по курсу

«Специальные главы дискретной математики»,

НГТУ, 2-й курс, осень 2002 года.

Семинар 1-2. Множества (счетные, континуальные, конечные), отношения, порядок, функция.

Семинар 2-3. Термы, предикаты, кванторы, переменные, интерпретация, модель, выполнимость.

Семинар 4. Комбинаторика. Сочетания, размещения, перестановки.

Семинар 5. Комбинаторика. Урновые схемы, лотереи.

Семинар 6. Комбинаторика. Организация перебора.

Семинар 7. Рекуррентные соотношения.

Семинар 8^*. Процессы. Автоматы, рекурсия, протоколы.

На экзамен выносятся следующие темы:

1.  Понятие отношения, функции. Пример задач:

a)  Даны функции f₁ из A в B, f₂ из C в D, f₃ из BÈD в E. При каких условиях отношение (f₁Èf₂)×f₃ будет функцией?

b)  Доказать, что объединение (пересечение) двух функций f₁ и f₂ из A в B является функцией из A в B тогда и только тогда, когда f₁ = f₂.

c)  Доказать тождество A¸A=Æ.

2.  Понятия счетного, конечного, континуального множества. Пример задачи:

a)  Доказать, что из всякого бесконечного множества можно выделить счетное подмножество.

b)  Пусть область определения функции счетна. Доказать, что область значений этой функции конечна или счетна.

3.  Сочетания, размещения, перестановки (в том числе и с повторами). Пример задач:

a)  Сколькими способами можно выбрать 6 карт из колоды, содержащей 52 карты, так, чтобы среди них были карты каждой масти?

b)  Сколько существует n-значных натуральных чисел, у которых цифры расположены в неубывающем порядке?

c)  Лотереи.

4.  Урновые схемы. Решение типовых схем. Примеры задач:

a)  Сколько существует n-значных чисел, у которых сумма цифр равна k, где k <= 9 (первая цифра отлична от нуля)?

b)  Сколько можно построить функций со значениями на множестве из m элементов, если функции зависят от n переменных x₁,…,x_n, где x_i может принимать одно из k_i значений?

c)  Найти число способов размещения n различных шаров по m урнам так, чтобы m₁ урн содержали по p₁ шаров, m₂ – по p₂ шаров и т.д., m_k урн по p_k шаров (m = m₁ + … + m_k, n = m₁p₁ + … +m_k p_k), если

a)  урны различны;

b)  урны, содержащие  одинаковое число шаров, неразличимы.

5.  Рекуррентные соотношения. Их построение и способы решения. Примеры задач:

a)  Найти точное решение для последовательности чисел, определяемых соотношениями: x₀=1, x₁=0.5, x_n+1=2.5 x_n-x_n-1.

b)  Получить общее решение рекуррентного соотношения: x_n=x_n-1-1/3 x_n-2.