Изменения

Перейти к: навигация, поиск

Список заданий по ДМ 2017 осень

2235 байт добавлено, 22:17, 10 февраля 2018
Нет описания правки
<wikitex>
= Дискретная математика, 1 семестр =
Задания, помеченные 🤔 - задания повышенной сложности. Задания, помеченные 😱 - задания очень высокой сложности. ✋ помечены задания, где мы передаем привет курсу "Алгоритмы и структуры данных", 👻 - задания только для групп M3132-M3135.
# Пусть $<math>R$ </math> и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
# Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
# Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
# Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^+(A)$ множество непустых последовательностей из элементов $A$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^+(Seq^+(A))$.
# Пусть $A$ - комбинаторные объекты. Обозначим как $Seq^1(A) = Seq^+(A)$, $Seq^k(A) = Seq^+(Seq^{k-1}(A))$. Выведите рекуррентную формулу для числа элементов в зависимости от веса для $Seq^k(A)$.
# Разбиения на множества. Проинтерпретируйте разбиения $n$-элементного множества на $k$ множеств как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 2 рода.# Разбиения на циклы. Проинтерпретируйте разбиения $n$-элементного множества на $k$ циклов как конструируемый помеченный комбинаторный объект. Получите альтернативную рекуррентную формулу для чисел Стирлинга 1 рода.# Будем называть граф циклическим мультибамбуком, если он устроен следующим образом: есть цикл, из каждой вершины которого выходит путь. Предложите способ посчитать непомеченные циклические мультибамбуки.# Предложите способ посчитать помеченные циклические мультибамбуки.# Подсчет помеченных унициклических графов. Граф называется унициклическим, если он содержит ровно один цикл. Предложите способ подсчета помеченных унициклических графов.# Подсчет помеченных двудольных графов. Граф называется двудольным, если его вершины можно разбить на два множества, таких что ребра соединяют только вершины различных множеств. Сколько существует помеченных двудольных графов?# Подсчет помеченных связных двудольных графов. Сколько существует помеченных связных двудольных графов? = ЭТО КОНЕЦ БЛИЗКО =
Анонимный участник

Навигация