Geum.ru

Дискретная математика введение

Вид материалаЗадача

Содержание


Програма курса
Теория булевых функций.
Теория графов
Подобный материал:
ДИСКРЕТНАЯ МАТЕМАТИКА


ВВЕДЕНИЕ


Настоящее пособие предназначено для самостоятельной работы студентов заочной и вечерней форм обучения. Пособие содержит список основных тем и разделов, изучаемых в программе дискретной математики. По каждой позиции списка указаны точные ссылки на учебник, позволяющие студентам легко в нем ориентироваться. В этих ссылках указывается страница, где начинается изложение соответствующего материала.

Ссылки в тексте приводятся в виде сокращений:

В -Виленкин Н.Я. Комбинаторика.
КА- Кузнецов О.П.,Адельсон-Вельский Г.М. Дискретная математика для инженеров.
У- Уилсон Р. Введение в теорию графов.

Програма курса

КОМБИНАТОРИКА


Задача о выборе с возвращением (размещения с повторениями). Задача о независимом выборе из различных совокупностей. Число размещений (без повторений). Число перестановок. Число сочетаний. Число разбиений на подмножества данного объема (перестановки с повторениями). Задача о размещении неразличимых предметов по ячейкам (сочетания с повторениями). Производящая функция чисел сочетаний. Доказательство соотношения с ее помощью.

ТЕОРИЯ БУЛЕВЫХ ФУНКЦИЙ.


Функции алгебры логики от n переменных. Их число. Задание булевой функции таблицей истинности и формулой. Фиктивные переменные. Булевы функции от одной и двух переменных. Конъюнктивные нормальные формы. Дизъюнктивные нормальные формы. Свойства операций И,ИЛИ,НЕ. Эквивалентные преобразования и правила упрощения. Исключение конъюнкций с помощью покрытия интервалов. Алгебра Жегалкина, представление булевых функций.

ТЕОРИЯ ГРАФОВ


Определение графа. Вершины, ребра, дуги. Связность. Циклы. Деревья. Матрица смежности. Матрица инцидентности. Алгоритм построения остовного дерева графа с минимальной суммой мер.
Алгоритм перечисления циклов графа.

Литература


1. Виленкин Н.Я. Комбинаторика.М,"Наука",1969.


2. Кузнецов О.П.,Адельсон-Вельский Г.М. Дискретная математика для инженеров.

М."Энергоатомиздат",1988


3. Уилсон Р. Введение в теорию графов.М."Мир",1977


Вопросы к экзамену по дискретной математике.


1. Задача о выборе с возвращением (размещения с повторениями).


2. Задача о независимом выборе из различных совокупностей.


3. Число размещений (без повторений).


4. Число перестановок.


5. Число сочетаний.


6. Число перестановок с повторениями.


7. Задача о сочетаниях с повторениями.


8. Производящая функция чисел сочетаний. Ее применение.


9. Функции алгебры логики от $ n $ переменных. Их число.


10. Задание булевой функции таблицей истинности и формулой.

11. Булевы функции от одной и двух переменных.


12. Свойства операций И,ИЛИ,НЕ.


13. Эквивалентные преобразования и правила упрощения.


14. Конъюнктивные и дизъюнктивные нормальные формы.

15. Исключение конъюнкций с помощью покрытия интервалов.


16. Алгебра Жегалкина, представление булевых функций с помощью полиномов Жегалкина.


17. Определение графа. Вершины, ребра, дуги.


18. Связность. Циклы. Деревья.


19. Матрица смежности. Матрица инцидентности.


20. Алгоритм построения остовного дерева графа

с минимальной суммой мер.


Контрольные работы


Контрольная работа 1. Дискретная математика.


1) Для булевой функции построить таблицу истинности, СДНФ,СКНФ.

2) Булеву функцию представить полиномом Жегалкина.

3) Сколько решений в неотрицательных целых числах имеет уравнение



4) В классе 30 детей. Нужно 30 из них отправить на экскурсию в Эрмитаж,

10- в Русский Музей, 10- на просмотр кинофильма. Сколькими способами

можно это сделать?