1. Элементы теории множеств

1. Доказать тождества:

; .

2. Проверить справедливость утверждений:

; .

3. Доказать равенства:

; .

4. Упростить

;

2. Булевы функции

1. Записать СДНФ, построив таблицу истинности

; .

2. Решить логические уравнения

; .

3. Упростить формулы

; .

4. Привести к минимальной ДНФ, используя один из методов минимизации функций

; .

5. Построить контактные схемы, упростить их, построить упрощенные схемы

; .

6. Построить контактные схемы и проверить, равносильны ли они

4. Кодирование

1. Существует ли: а) неразделимая схема алфавитного кодирования; б) разделимая, но не префиксная схема алфавитного кодирования; в) префиксная, но неразделимая схема алфавитного кодирования, если существует привести пример, если нет, то обосновать.

2. Азбука Морзе является или нет: а) схемой алфавитного кодирования; б) разделимой схемой алфавитного кодирования; в) префиксной схемой алфавитного кодирования. Принцип работы азбуки Морзе.

3. Является ли схема алфавитного кодирования префиксной? Разделимой?

4. Построить оптимальное префиксное алфавитное кодирование для алфавита со следующим распределением вероятностей появления букв: .

5. Проследить работу алгоритма Хаффмена на следующем примере распределения вероятностей появления букв алфавита:

; ; .

6. Применить алгоритм сжатия Лемпела-Зива к следующему исходному тексту:

; ; ; .

Примерные варианты контрольных работ Контрольная работа №1 по комбинаторному анализу

1. Сколько различных шестизначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, 7,9 чтобы цифры не повторялись и крайние цифры были нечётными?

2. На собрании должны выступить 5 человек: А, В,С, Д и К. Сколькими способами их можно расположить в списке ораторов при условии, что В не должен выступать до того, как выступит А?

3. Сколькими способами можно переставлять буквы слова «хоровод» так, чтобы три буквы «о» не стояли рядом?

4. В разложении коэффициент седьмого члена разложения относится к коэффициенту пятого члена как 10:21. Найдите средний и третий члены разложения.

5. Найдите номера членов, не содержащих иррациональности в разложении .

6. Найдите коэффициент при в выражении .

7. Найдите число целых положительных чисел, не превосходящих 600 и не делящихся ни на одно из чисел 5, 7, 11.

Контрольная работа №2 по теории графов

1. Определите минимальное остовное дерево нагруженного графа:

2. Докажите, что граф , заданный матрицей весов является гамильтоновым и найдите его минимальный гамильтонов цикл:

.

3. Найдите матрицу кратчайших путей между вершинами орграфа , заданного матрицей весов:

.

Примерные задания:

1. , , , . Найти:

1. [ ];

2. [ ].

2. Доказать равенство множеств:

1. ;

2. .

3. Выяснить какими свойствами обладает отношение R над множеством M:

1. , [рефлексивно и антисимметрично];

2. ,

[антирефлексивно, симметрично и транзитивно].

4. Найти композицию отношений заданных над множеством M:

1. , ,

[ ];

2. , ,

[ ].

5. Найти совершенную дизъюнктивную нормальную форму для булевой функции, используя разложение Шеннона по всем переменным:

1. [ ];

2. [ .].

6. Найти МДНФ для булевой функции заданной десятичным кодом:

1. [ ];

2. [ или ].

7. Найти разложение булевой функции заданной десятичным кодом в полином Жегалкина:

1. [ ];

2. [ ].

8. Выяснить каким основным классам принадлежит булева функция:

1. [ , , , , ];

2. [ , , , , ].

9. Найти общую формулу рекуррентного соотношения:

1. , , [ ];

2. , , [ ].

10. Найти минимальное дерево для графа и вычислить его вес, если его матрица весов имеет вид:

1. [ ; вес равен 5];