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


Вопросы для зачета
1. Понятие множества. Подмножества. Основные операции над множествами: пересечение, объединение, дополнение. Свойства операций.
2. Конечные множества. Правило суммы. Правило включения-исключения. Правило произведения. Число всех подмножеств конечного множества.
Принцип математической индукции.
4. Высказывания и операции над ними.
5. Формулы логики высказываний.
6. Равносильность формул. Основные формулы равносильности.
7. Тождественно истинные формулы.
8. Принцип двойственности.
9. Правила вывода.
10. Предикаты и операции над ними.
11. Правила де Моргана для предикатов.
12. Примеры равносильных и неравносильных формул логики предикатов.
13. Пример выполнимой формулы, которая не выполнима ни на одном непустом конечном множестве.
14. Булевы функции. Число булевых функций от n переменных.
15. Булевы функции одной и двух переменных.
16. Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ).
17. Представление булевой функции в виде СДНФ.
18. Основные замкнутые классы булевых функций.
19. Размещения, сочетания, перестановки.
20. Бином Ньютона.
21. Свойства биномиальных коэффициентов.
22. Бином Ньютона для целых отрицательных степеней.
23. Рекуррентные последовательности.
24. Нахождение общего члена рекуррентной последовательности.
25. Числа Фибоначчи. Производящие функции.
26. Начальные понятия теории графов. Матрица смежности. Матрица инцидентности.
27. Пути на графе. Достижимость. Степени матрицы смежности. Связные графы.
28. Деревья. Остовное дерево связного графа.
29. Внешне и внутренне устойчивые множества вершин.
30. Ядро графа.
31. Проверка ацикличности орграфа по его матрице смежности.
32. Порядковая функция ацикличного орграфа.
33. Полугруппы и моноиды преобразований конечного множества.
34. Группы подстановок.
35. Кольца и поля вычетов.
36. Кодирование. Линейные коды.
37. Коды, обнаруживающие и исправляющие ошибки.
38. Коды Хэмминга.
39. Формальные языки. Их задание с помощью формальных грамматик.
40. Регулярные и контекстно свободные языки.
41. Построение дерева вывода (грамматического разбора).
42. Представление регулярных языков конечными автоматами.
43. Построение конечного автомата, представляющего язык, заданный праволинейной формальной грамматикой.
44. Построение формальной грамматики, определяющей язык, представленный конечным автоматом.

Приложенные файлы

  • docx 23687881
    Размер файла: 14 kB Загрузок: 1

Добавить комментарий