Основные положения дискретной математики

Матрица смежности неориентированного графа

Матрица смежности орграфа.

7.4 Операции над членами графов

1. Дополнение Н части Н определяется множеством всех ребер графа G, не принадлежащих Н.

2. Объединение Н1 Н2 определяется:

height=27 src="images/referats/7492/image231.png">;

.

3. Пересечение Н1 Н2 частей Н1 и Н2 графа G определяется:

;

.

8 ОСНОВНЫЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

Контрольная работа в обязательном порядке должна содержать титульный лист (см. приложение I), условие задачи и подробное описание ее решения. Описание решения должно содержать: используемые при решении формулы и свойства; их название (если таковое имеется); методы или способы решения задачи; результаты вычислений; выводы.

9. ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ

1. Множества и подмножества. Основные понятия. Графическое представление множеств и операций над ними.

2. Множества и подмножества. Основные понятия. Свойства операций над множествами. Тождества. Порядок доказательства тождеств.

3. Отношение на множествах. Декартово произведение.

4. Отношения на множествах. Одноместные, бинарные, n- местные отношения.

5. Отношения на множествах. Свойства отношений.

6. Функция как отношение на множествах. Отношение порядка. Отношение эквивалентности.

7. Математическое моделирование. Понятие модели. Этапы приведения к модели. Способы моделирования.

8. Алгебраические модели. Общие понятия. Алгебраические модели с одной определяющей операцией.

9. Алгебраические модели. Общие понятия. Алгебраические модели с двумя определяющими операциями.

10. Алгебраические модели. Общие понятия. Алгебраические модели, содержащие более одного класса математических объектов.

11. Теория кодирования. Общие понятия. Показать построение трехзначного двоичного кода на примере куба. Описать все возможные ситуации.

12. Теория кодирования. Общие понятия. Кодовые расстояния. Методы обнаружения ошибок.

13. Теория кодирования. Общие понятия. Групповые коды.

14. Линейная алгебра. Общие понятия. Линейные подпространства.

15. Реляционная алгебра. Понятия домена, кортежа. Операции выбора, проекции, объединения.

16. Математическая логика. Общие понятия алгебры логики. Функции алгебры логики и их таблицы истинности.

17. Булева алгебра. Общие понятия. Свойства операций и элементов булевой алгебры.

18. Булева алгебра. Дизъюнктивные нормальные формы. Совершенные дизъюнктивные нормальные формы.

19. Булева алгебра. Алгоритм преобразования формулы в совершенную дизъюнктивную нормальную форму.

20. Булева алгебра. Конъюнктивные нормальные формы. Совершенные конъюнктивные нормальные формы.

21. Исчисление высказываний. Общие понятия. Понятие равносильной формулы.

22. Исчисление высказываний. Равносильности. Способы доказательства равносильностей.

23. Исчисление высказываний. Правила равносильных преобразований. Тавтологии. Основные понятия.

24. Исчисление высказываний. Тавтологии. Методы доказательства тождественной истинности. высказываний.

25. Аксиоматическая система в исчислении. Основные понятия. Выводимые формулы. Правила вывода.

26. Булевы функции. Полнота системы булевых функций. Теорема Поста.

27. Булевы функции. Замкнутые классы. Контактные схемы.

28. Логика предикатов. Основные понятия. Операции над предикатами.

29. Логика предикатов. Основные понятия. Кванторы. Исчисление предикатов.

30. Формальные грамматики. Классификация грамматик. Порождающие грамматики.

31. Языки. Свойства языков. Операции над языками. Анализ грамматик и языков.

32. Теория алгоритмов. Понятие алгоритмической разрешимости. Рекурсивные функции.

33. Теория конечных автоматов. Машины Тьюринга. Формы представления алгоритмов.

34. Теория графов. Основные понятия.

35. Элементы комбинаторики. Основные понятия.

ЛИТЕРАТУРА

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

2. Горбатов В.А. Основы дискретной математики: учебное пособие для студентов вузов – М.: Высшая школа, 1986Г-311с.

3. Никольская И Л. Математическая логика: Учебник М.: Высшая школа 1981г.-127с.

4. Ершов Ю.А., Палютин Е.А. Математическая логика: учебное пособие для вузов 2-е издание исправленное и дополненное- М.: Наука 1987г.- 336с.

5. Клини С.К. Математическая логика М.: Мир 1973г.

6. Новиков П.С. Элементы математической логики. М.: Наука 1973г.

7. Оре О. Теория графов М.: Наука 1968г.

8. Зыков А.А. Теория конечных графов. Новосибирск: Наука 10969г.

9. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике М.: Наука 1977г.- 368с.

10. Гиндикин С.П. Алгебра логики в задачах М.: Наука 1972г.

11. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике, теории автоматов М.: Наука 1975г.

ПРИЛОЖЕНИЕ I

Оформление титульного листа

 Скачать реферат