Материал: Программная инженерия. Экзаменационные вопросы по ДМ

Экзаменационные вопросы по дискретной математике

1. Сети. Потоки в сетях. Теорема Форда – Фалкерсона. Нахождение максимального потока в сети.

2. Функции. Бинарные отношения. Тотальность, сюръективность, инъективность, биективность. Примеры.

3. Бинарные отношения. Свойства. Матрица смежности и граф отношения. Эквивалентные отношения. Примеры.

4. Алгебраические структуры. Полугруппы, моноиды, группы. Примеры.

5. Группы. Абелевы группы, аддитивные, мультипликативные группы. Конечные группы. Таблицы Кэли. Циклические группы. Декартово произведение группы.

6. Группы подстановок. Симметрическая группа . Умножение подстановок. Единичный элемент. Обратная подстановка. Число элементов группы .

7. Циклы. Теорема о представлении подстановки в виде произведения независимых циклов. Транспозиции. Четные и нечетные подстановки. Знакопеременная группа .

8. Кольца. Свойства колец. Коммутативные кольца. Делители . Области целостности. Примеры. Подкольца. Единица кольца. Поля. Примеры.

9. Идеалы. Главные идеалы. Теорема об идеалах поля (только (0) и (1)). Следствие об идеалах в кольце .

10. Сравнения. Классы вычетов по модулю (по идеалу ). Свойства сравнений. Малая теорема Ферма. Функция Эйлера. Теорема Эйлера (теория чисел).

11. Характеристика кольца. Теорема о характеристике кольца без делителей . Примеры. Кольца классов вычетов. Примеры.

12. Простые идеалы. Необходимое и достаточное условие того, что идеал кольца — простой.

13. Поля классов вычетов. Минимальные поля. Примеры.

14. Евклидовы кольца. Свойства евклидовых колец (8 свойств). Примеры.

15. Кольцо многочленов . Условия того, что кольцо — евклидово кольцо. Примеры.

16. Приводимые и неприводимые многочлены в кольце . Примеры. Теорема о разложении в на произведение неприводимых множителей. Теорема Безу.

17. Расширения полей. Теорема о том, что кольцо классов вычетов по модулю неприводимого многочлена есть поле. Степень расширения. Число элементов этого поля.

18. Поля Галуа. Примеры полей Галуа, как расширения полей. Таблицы сложения и умножения.