ВОПРОСЫ
к экзамену по дисциплине «Дискретная математика»
для студентов специальностей 230101.65 –-«Вычислительные машины, комплексы, системы и сети» и 230105.65 – «Программное обеспечение вычислительной техники и автоматизированных систем»
(1 курс, 2 семестр)
1. Основные понятия теории множеств.
2. Понятия заданного множества, пустого множества, конечного, бесконечного, универсального, операции включения, мощности множества, булеан.
3. Основные операции над множествами.
4. Свойства операций над множествами.
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.Конъюнкция.
36.Дизъюнкция.
37.Импликация, антецедент, консеквент.
38.Эквивалентность высказываний.
39.Штрих Шеффера.
40.Равносильность высказываний.
41.Основные законы алгебры Буля.
42.Булевы функции.
Профессор, ведущий дисциплину Г.Д. Нестеров
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.