Примерный перечень вопросов к экзамену

Элементы теории множеств

1. Операции над множествами и их свойства. Принцип двойственности. Декартово произведение множеств. Примеры.

2. Элементы комбинаторики. Правила суммы и произведения. Число (к, п) - размещений.

3. Элементы комбинаторики. Правила суммы и произведения. Число (к, п) - сочетаний.

4. Элементы комбинаторики. Правила суммы и произведения. Число (к, п) - размещений с повторениями.

5. Элементы комбинаторики. Правила суммы и произведения. Число (к, п) - сочетаний с повторениями.

6. Перестановки с повторениями, мультимножества. Полиномиальная формула. Бином Ньютона. Треугольник Паскаля.

7. Перестановки с повторениями, мультимножества. Полиномиальная формула. Принцип включения и исключения. Инверсии.

8. Бинарные отношения и их свойства. Примеры. Отношение эквивалентности.

9. Классы эквивалентности и их свойства.

10. Отношение эквивалентности как разбиение множества.

11. Отображение множеств. Примеры. Прообраз элемента. Прообраз множества. Свойства прообраза множеств.

12. Свойства отображений. Примеры. Обратное отображение. Свойства биективных отображений.

13. Понятие эквивалентности множеств и свойства этого понятия.

14. Конечные множества и их мощность.

15. Счетные множества. Примеры. Критерий счётности множества.

16. Счетные множества. Примеры. Подмножества счётного множества.

17. Счетные множества. Примеры. Объединение счётного набора счётных множеств.

18. Счетные множества. Примеры. Декартово произведение счётных множеств.

19. Счетные множества. Примеры. Счётность множества многочленов с рациональными коэффициентами.

20. Бесконечные множества и их свойства.

21. Несчётность множества (0, 1).

22. Мощность континуума. Мощность объединения не более чем счётной совокупности множеств мощности континуума.

23. Мощность множества последовательностей из нулей и единиц.

24. Мощность множества последовательностей из натуральных чисел.

25. Мощность декартового произведения множеств мощности континуума.

26. Сравнение мощностей. Теорема Кантора - Бернштейна.

27. Мощность совокупности подмножеств данного множества.

28. Мощность совокупности подмножеств множества натуральных чисел.

29. Бинарное отношение частичной упорядоченности. Частично упорядоченные множества. Изоморфность частично упорядоченных множеств. Упорядоченные и вполне упорядоченные множества. Примеры.

30. Свойство отображений, сохраняющих порядок.

31. Отрезок вполне упорядоченного множества. Неизоморфность вполне упорядоченного множества своему отрезку.

32. Понятие порядкового типа и порядкового числа. Сравнение порядковых чисел.

Основы математической логики

33. Высказывания и операции над ними. Пропозициональные формы. Тавтологии и противоречия. Свойства тавтологий.

34. Истинностные функции и таблицы. Существование пропозициональных форм, порождающих заданную истинностную функцию.

35. Исключительность отрицания конъюнкций и штриха Шеффера.

35. Понятие формальной теории. Формальная теория для исчисления высказываний. Выводимость (А=>А).

36. Исчисление предикатов. Основные определения.

37. Интерпретация. Примеры.

38. Теории первого порядка.

Теория графов

40. Графы основные определения. Задача Рамсея.

41. Графы. Обход графов. Критерии эйлеровости графов.

42. Обход графов. Алгоритм оптимиста.

43. Алгоритм Дейкстры. Обоснование алгоритма.

44. Алгоритм Флойда. Обоснование алгоритма Флойда.

45. Алгоритм Форда. Обоснование алгоритма Форда.

46. Транспортные сети. Алгоритм построения полного потока.

47. Транспортные сети. Алгоритм поиска увеличивающей цепи. Обоснование.

48. Алгоритм Форда - Фалкерсона поиска максимального потока. Обоснование.

49. Матрицы, ассоциированные с графом (матрица смежности, матрица Кирхгофа, матрица инцидентности).