Файл: Дискретная математика.pdf

57

22.Что называется простой импликантой частично определенной булевой функции? Как найти все простые импликанты частично определенной булевой функции?

23.Какая система ДНФ булевых функций называется минималь-

ной?

24.Что называется простой импликантой системы булевых функ-

ций?

25.Модифицируйте метод Квайна — Мак-Класки для получения всех простых импликант системы булевых функций.

26.Как строится импликантная матрица Квайна для системы булевых функций?

27.Какие аргументы системы частично определенных булевых функций называются фиктивными? Как их найти?

28.Что называется простой импликантой системы частично определенных булевых функций? Как найти все простые импликанты системы частично определенных булевых функций?

29.Приведите пример бинарного графа булевой функции. Запишите эту функцию в ДНФ.

30.Постройте различные бинарные графы одной и той же булевой функции.

31.Сколько условных вершин может быть в бинарном графе булевой функции? Какова может быть глубина бинарного графа?

32.Приведите пример бинарного графа системы булевых функций. Запишите эти функции в ДНФ.

33.Постройте различные бинарные графы одной и той же системы булевых функций.

34.Сколько условных и заключительных вершин может быть в бинарном графе системы булевых функций?

35.Какова может быть глубина бинарного графа системы булевых функций?

36.Напишите программы для вычисления значения булевой функции по таблице истинности при различных способах ее хранения.

37.Опишите алгоритм вычисления значения булевой функции по

ДНФ.

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

39.Разработайте способ хранения и алгоритм вычисления системы булевых функций по таблице истинности.

40.Разработайте способ хранения и алгоритм вычисления системы булевых функций по минимальной системе ДНФ булевых функций.

58

Библиографический список

1.Асанов, М. Дискретная математика: графы, матроиды, алгоритмы

/М.О. Асанов, В.А. Баранский, В.В. Расин. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. — 288 с.

2.Белоусов, А.И. Дискретная математика: учеб. для вузов / А.И. Белоусов, С.Б. Ткачёв, под ред. В.С. Зарубина, А.П. Крищенко. — 3-е изд., стер. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. — 744 с. (Сер. Математика в техническом университете; Вып. ХIХ).

3.Иванов, Б.Н. Дискретная математика. Алгоритмы и программы: учеб. пособие / Б.Н. Иванов. — М.: Лаборатория Базовых Знаний,

2003. — 288 с.

4. Кристофидес, Н. Теория графов. Алгоритмический подход

/ Н. Кристофидес. — М.: Мир, 1978. — 429 с.

5. Кузнецов, О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский. — 2-е изд., перераб. и доп. — М.: Энергоатомиздат, 1988. – 480с.

6.Кузнецов, О.П.. Дискретная математика для инженера / О.П. Кузнецов. — 3-е изд., перераб. и доп. — СПб.: Лань, 2004. — 400 с.: ил. — (Учебники для вузов. Специальная литература).

7.Липский, В. Комбинаторика для программистов / В. Липский. —

М.: Мир, 1988. — 201 с.

8.Муромцев, В.В. Проектирование полнопереборных алгоритмов: учеб. пособие./ В.В. Муромцев. — Белгород: Изд-во БелГТАСМ,

2001. — 67 с.

9.Новиков, Ф.А. Дискретная математика для программистов: учеб. для вузов / Ф.А. Новиков. — 3-е изд. — СПб.: Питер, 2008. — 384 с.: ил. — (Серия «Учебник для вузов»).

10.Прикладная теория цифровых автоматов / К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский и др. — Киев: Вища школа, 1987. – 357 с.

11.Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика

/Э. Рейнгольд, Ю. Нивергельт, Н. Дэо. — М.: Мир, 1980. — 476 с.

12.Рязанов, Ю.Д. Булевы функции. Способы задания и реализация: учеб. пособие / Ю.Д. Рязанов. — Белгород: Изд-во БТИСМ,

1993. — 124 с.

13.Рязанов, Ю.Д. Множества и комбинаторные объекты: учеб. пособие / Ю.Д. Рязанов — Белгород: Изд-во БГТУ, 2008. — 99 с.

14.Рязанов, Ю.Д. Дискретная математика: учеб. пособие. / Ю.Д. Рязанов. — Белгород: Изд-во БГТУ, 2010. — 274 с. — ISBN

59

15.Седжвик, Р. Фундаментальные алгоритмы на C++. Ч. 5: Алгоритмы на графах: пер. с англ / Р. Седжвик. — СПб.: ООО

«ДиаСофтЮП», 2002. — 496 с.

16.Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти. — М.: Техносфера, 2005. — 400 с.

17.Шапорев, С.Д. Дискретная математика: курс лекций и практических занятий / С.Д. Шапорев. — СПб.: БХВ-Петербург,

2007. — 400 с.

18.Яблонский, С.В. Введение в дискретную математику: учеб. пособие для вузов / под ред. В.А. Садовничего. — 4-е изд.,

стер. — М.: Высш. шк., 2003. – 384 с.

Учебное издание

Рязанов Юрий Дмитриевич

Теория вычислительных процессов

Лабораторный практикум

Отпечатано в Белгородском государственном технологическом университете им. В. Г. Шухова

308012, г. Белгород, ул. Костюкова, 46