3.4. Организация и методика межсессионного и итогового контроля знаний

Перечень контрольных точек, работ, тестов	Сроки проведения контроля	Разделы и темы рабочей программы
ВТОРОЙ СЕМЕСТР
1. Отчет по лб.1 Отчет по лб.2 Отчет по лб.3 Отчет по лб.4 Отчет по лб.5 Отчет по лб.6 Отчет по лб.7 Отчет по лб.8 Экзамен	2 неделя. 4 неделя 6 неделя 8 неделя 10 неделя 12 неделя 14 неделя 16 неделя по расписанию сессии	Тема 2.1 Тема 1.3 Тема 3.1 Тема 3.6 Тема 3.4 Тема 3.5 Тема 3.7 Тема 3.9 Темы 1.1 – 3.9

Итоговый контроль знаний осуществляется в следующих формах: - на экзамене -2 семестр;

4. Учебно-методические материалы по дисциплине

4.1 Основная и дополнительная литература

Основная литература

1. О.Е. Акимов Дискретная математика.- Москва: Лаборатория базовых знаний, 2003. – 376 с.

2. Ю.В. Капитонова Лекции по дискретной математике. – СПБ:БХВ-Петербург, 2004. - 614 с.

3. Б.Н. Иванов Дискретная математика.- Москва: Лаборатория Базовых Знаний, 2002. – 320 с.

4. Ф.А. Новиков Дискретная математика для программистов. – СПБ: Питер, 2003. – 301 с.

Дополнительная литература

5. О.П. Кузнецов Дискретная математика для инженера. – М: Энергия, 1980.-342 с

6. Ю.А. Шиханович Введение в современную математику. М.: Наука,1965.

7. Фор Р., Кофман А., Дени-Папен М. Современная математика. М.:Мир, 1966.

4.2. Методические указания

Методические указания к лабораторным работам (машинописный вид)

4.3. Перечень обучающих и контролирующих компьютерных программ

Обучающая система по разделам 1,2,3. (В электронном виде)

4.4. Раздаточный материал

Задания к лабораторным работам. (печатный вид)

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

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. 1-факторизация.

39. 2-факторизация.

40. Древесность.

41. Вершинное и реберное число покрытия.

42. Вершинное и реберное число независимости.

43. Теорема Галлаи.

44. Инварианты alfa00, alfa’00, alfa11, alfa’11.

45. Критические вершины и ребра относительно alfa0.

46. Плоские и планарные графы. Теорема Эйлера.

47. Гомеоморфность графов. Теорема Понтрягина-Куратовского.

48. Элементарное стягивание.

49. Двойственные графы. Комбинаторная двойственность.

50. Крупность, число скрещиваний.

51. Хроматическое число.

52. Реберная раскраска.

53. Хроматический многочлен.

54. Алгоритм Зыкова

55. Матрицы смежностей и инциденций.

56. Род, толщина.

57. Матрицы циклов и коциклов и связи между ними.

58. Вершинная группа графа.

59. Реберная группа графов.

60. Сумма, произведение и композиция групп.

61. Степенная группа.

62. Композиция перестановок.

63. Разложение перестановки в произведение транспозиций.

64. Разложение перестановки в произведение циклов.

65. Графы с данной группой.

66. Гомоморфизмы графов.

67. Графы критические относительно хроматического числа.

68. Теорема Менгера в вершинной форме.

69. Теорема Фалкерсона.

70. Однозначно-раскрашиваемые графы.

71. Пара связности. Функция связности.

72. Полная раскраска. Ахроматическое число.

73. Теорема Хивуда о раскраске карт.

74. Связность. Реберная связность.

75. Группа перестановок.

76. Сеть. Теорема Форда и Фалкерсона.

77. Теорема о элементарном гомоморфизме.

78. Теорема Менгера в реберной форме.

Коэффициент обеспеченности дисциплины методическими материалами К_D=1.02

Преподаватель В.А. Лукиных

Зав. Кафедрой С.П. Орлов