СДАЛ / Все тесты и билеты / ДМАТ11 / ПЗ_ДМАТ11

3

ПРОГРАММА

для подготовки к экзамену/зачёту по дисциплине «Дискретная математика»

I или II семестр 2006/2007 уч.г.

Индекс ДМАТ11.

1. Теоретическая часть.

1. Основные понятия и обозначения.

2. Множества и операции над множествами. Мощность множества.

3. Векторы, прямые произведения и проекции векторов.

4. Отношения. Бинарные отношения, их свойства

5. Операции и алгебры.

6. Алгебры с одной и с двумя операциями.

7. Булевы переменные и булевы функции

8. Полная система булевых функций.

9. Булевы алгебры. Принцип двойственности. Нормальные формы.

10. Логические связки. Формальные теории.

11. Логика высказываний. Логика предикатов.

12. Комбинаторные конфигурации. Подстановки. Биноминальные коэффициенты.

13. Коды и кодирование. Шифрование и обеспечение информационной безопасности.

14. Понятие, свойства и способы задания алгоритмов. Алгебраические структуры. Алгоритмизация и программирование.

15. Машины Поста и Тьюринга. Тезис Тьюринга. Эквивалентность формализаций алгоритма. Проблема остановки.

16. Определения, элементы и способы представления графов. Виды графов.

17. Операции над графами и их частями.

18. Циклы в графах. Маршруты и деревья. Эйлеровы графы. Гамильтоновы графы. Поиск в глубину и в ширину на графе.

19. Графы и бинарные отношения.

Образец типового билета

МОСКОВСКАЯ ФИНАНСОВО-ЮРИДИЧЕСКАЯ АКАДЕМИЯ

2005/06 уч. год

ДИСЦИПЛИНА «ДИСКРЕТНАЯ МАТЕМАТИКА»

Применяя табл. истинности доказать равносильности

X Þ Y ≡  X Ú Y

Составить таблицу истинности выражения.

X Ù ( Y Ú Z ) Þ ( X Ù Y ) Ú ( X Ù Y )

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

А\ ( В U С) = (А\ В ) ∩ (А\С)

Надо послать 6 писем. Сколькими способами это можно сделать, если для доставки писем имеется 3 курьера?

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

Представить в виде суммы ( а + b )ⁿ при n = 6

По заданной .машине Т с внешним алфавитом А = {|, Ù} и слову u найти слово Т (u):

Составить кодовое слово с проверкой чётности в блочном двоичном (m, n) – коде ,

при m = 2 , n = 3 Е (00) = Е (10) =

Укажите расстояние Хемминга d (а ,b) = , и вес W(a + b) = , где « + » операция сложения по mod 2

а = 01101101

b = 10101101

Получите кодовое слово b, используя порождающую матрицу Е

a = 001

Е =
	1	0		0	1	1	0
	0	1		0	0	1	1
	0	0		1	1	1	1

Литература.

1. Осипова В.А Основы дискретной математики. Учебное пособие. М: Инфра-М, Форум – 2006, 160с.

2. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие – М.: Логос, 2003.

3. Новиков Ф.А. Дискретная математика для программистов. – СПб, Питер, 2003.

Зав. кафедрой А. Байков