Тема контрольной работы: Контрольная работа по дискретной матиматике

Задания для контрольной работы

1)    Запишите определение булевой алгебры.

2)    Напишите формулы для подсчета количества перестановок,
сочетаний, размещений (без повторений).

3)    Для данного сообщения С построить схему оптимального кодирования Хафмена. С=bebbcbbacaccacfbfceccaccbcdfafbef

4)  Сколько слов можно получить, переставляя
буквы в слове ФУНКЦИЯ?

5) В группе 8 человек. Сколько способов выбрать старосту
и его заместителя?

6)  Выяснить,
является ли функция тождественно истинной или тождественно ложной:



















.

7) Постройте оптимальную переключательную схему с
функцией проводимости:

.

Задание 2
Напишите формулы для подсчета количества перестановок, сочетаний, размещений (без повторений).

Перестановки:
Перестановка без повторений из n элементов – упорядоченная (n,n)-выборка без повторений.
По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из n элементов определяется следующей формулой:

Эту формулу, кстати, легко получить, если учесть, что Pn=Ann. Тогда получим:

Сочетания:
Сочетание без повторений из n элементов по k – неупорядоченная (n,k)-выборка без повторений.
Общее количество сочетаний без повторений из n элементов по k определяется формулой:

Размещение:
Размещение без повторений из n элементов по k – упорядоченная (n,k)-выборка без повторений.
Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: n≥k. Количество размещений без повторений из n элементов по k определяется следующей формулой:

Задание 5
В группе 8 человек. Сколько способов выбрать старосту и его заместителя?

Решение.
Старостой может быть выбран любой из 8 студентов, заместителем - любой из оставшихся 7, т. е. n1=8, n2=7. По правилу умножения общее число N способов выбора старосты и его заместителя: 8×7=56 способов