ДисМатЭкзамен
.docБилеты к экзамену "Дискретная математика" направление работы бакалавры МКН, лектор Лебедев В.Н. 2015 год.
БИЛЕТ 1. 1) В четыре различные урны кладут пять различных шаров. Найдите число разложений, при которых ровно одна урна пуста. 2) Булевы функции, их свойства.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 2.
1 )В четыре различные урны кладут пять одинаковых шаров. Найдите число разложений, при которых ровно одна урна пуста
2)Теорема о представлении булевых функций в виде СДНФ.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 3.
1 )В три одинаковые урны кладут три одинаковых шара. Найдите общее число возможных разложений , используя лемму Бернсайда.
2 )Теорема о задании булевых функций в виде полинома Жегалкина.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 4.
1 )В три одинаковые урны кладут три различных шара. Найдите общее число возможных разложений , используя лемму Бернсайда.
2 )Основные замкнутые классы T_0, T_1, S, M, L
булевых функций, примеры.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 5.
1)В четыре различные урны кладут пять различных шаров. Найдите число разложений, при которых нет пустых урн. Примените формулу включения-исключения.
2 )Замкнутость класса T_0.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 6.
1)Найдите число различно окрашенных по граням тетраедра в четыре цвета. Два тетраедра одинаково окрашены, если один из другого можно получить вращениями в пространстве. Примените лемму Бернсайда.
2 )Замкнутость класса T_1.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 7.
1)В четыре различные урны кладут пять различных шаров. Найдите число разложений, при которых ровно нет пустых урн. Примените формулу включения- исключения.
2) Замкнутость класса S.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 8.
1)Найдите число удачных трамвайных билетов. Билет удачный, если три цифры числа справа можно переставить так, чтобы получить число слева. Например, 221|212, или 123|231.
2) Замкнутость класса M.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 9.
1) Подбрасывают 7 различных кубика. Найдите число комбинаций типа 3+4 (на некоторых трех одна и та же цифра и оставшихся четырех кубиках одна и та же цифра) , и цифры различаются. Например 3335555.
2)Замкнутость класса L.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 10.
1) Подбрасывают 7одинаковых кубика. Найдите число комбинаций типа 3+4 (на некоторых трех одна и та же цифра и оставшихся четырех кубиках одна и та же цифра) , и цифры различаются. Например 3335555.
2)Теорема Поста о полноте в классе булевых функций. Примеры. Доказательство необходимости условий теоремы.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 11.
1)Подбрасывают 4 различных кубика.
Найдите число комбинаций, когда ровно две пары одинаковых цифр. Например 1122?
2) Построение
функций 0, 1,
из функций не сохраняющей ноль, не
сохраняющей единицу, не монотонной и
не самодвойственной.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 12.
1)Подбрасывают 5 одинаковых кубика.
Найдите число комбинаций, когда ровно две пары одинаковых цифр. Например 11 22 3?
2) Построение функции конъюнкции из нелинейной и функций 0,
1, не
.
Достаточность условий теоремы Поста (
первый
этап без доказательства).
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 13.
3)Подбрасывают 3 различных кубика.
Число комбинаций, когда цифры на кубиках различны?
4) Базисы в классе булевых функций.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 14
1) Можно ли из
системы функций {10001001, 00100100, xyz+yz+x}
получить {
}
и если да, опишите определяющее
выражение?
2) Упорядоченные наборы с повторениями, их число.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 15
1) Можно ли из
системы функций {10001000, xz+yz+x}
получить {
}
, и если да, опишите определяющее
выражение?
2) Упорядоченные наборы без повторения, их число.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 16
1) Можно ли из
системы функций {10010111, 1,
}
получить функцию
подстановками ?
2 ) Неупорядоченные наборы с повторениями, их число.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 17
1) Можно ли из
системы функций {10010110,
}
получить функцию
подстановками?
2)Неупорядоченные наборы без повторения, их число.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 18
1) Можно ли из
системы функций {11000010, xz+yz}
получить {
}
, и если да, опишите определяющее
выражение?
2) Формула включения-исключения.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 19
1) Можно ли из
системы функций {11000011, 00111110, xz+yz+xz}
получить {
}
, и если да, опишите определяющее
выражение?
2) Бином Ньютона.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 20
1) Можно ли из
системы функций {0, 1,
,
}
получить функцию
подстановками?
2 )Оценки комбинаторных величин. Формула Стирлинга (без доказательства)
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 21
1) Можно ли из
системы функций {11001010, xz+xzy+1}
получить {
}
, и если да, опишите определяющее
выражение?
2) Группа. Подгруппа. Отношение эквивалентности. Признак подгруппы конечной группы.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 22
1) Можно ли из
системы функций {0, + ,
,
}
получить функцию
подстановками?
2)Разложение группы на смежные классы по ее подгруппе. Теорема Лагранжа.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А
БИЛЕТ 23
1) Можно ли из
системы функций {10010111, 1,
}
получить функцию
подстановками ?
2)Лемма Бернсайда о числе классов эквивалентностей слов относительно заданной группы перестановок.
Кафедра ФИиОУ, зав кафедрой проф., д.ф.-м.н. Воронин А.А