Учебно-методический комплекс рабочая учебная программа для студентов очной формы обучения специальности

Основные понятия и определения. Представление графов. Операции над графами.

4. Связность. Решение задач практического и теоретического характера по теме №4.

Компоненты связности. Теоремы Менгера и Холла. Потоки в сетях. Связность в орграфах. Кратчайшие пути.

5. Деревья. Решение задач практического и теоретического характера по теме №5.

Свободные деревья. Ориентированные, упорядоченные и бинарные деревья. Кратчайший остов.

6. Циклы. Решение задач практического и теоретического характера по теме №6.

Фундаментальные циклы и разрезы. Эйлеровы циклы. Гамильтоновы циклы.

7. Независимость и покрытия. Решение задач практического и теоретического характера по теме №7.

Независимые и покрывающие множества. Построение независимых множеств вершин. Доминирующие множества.

8. Раскраска графов. Решение задач практического и теоретического характера по теме №8.

Хроматическое число. Планарность.

3. Перечень примерных тем рефератов.

   1. 
      Тема №1. Представление абстрактных объектов.
      
   2. 
      Тема №2. Генерация комбинаторных объектов.
      
   3. 
      Сортировка и поиск.
      
   4. 
      Метод поиска в глубину.
      
   5. 
      Жадный алгоритм построения минимального остовного дерева.
      
   6. 
      Алгоритм ближайшего соседа построения остовного дерева.
      
   7. 
      Поиск блоков в глубину.
      
   8. 
      Алгоритм определения максимального паросочетания.
      
   9. 
      Алгоритмы раскрашивания.
      

4. 
   Перечень примерных тем коллоквиума.
   
   1. 
      Множества. Способы задания множеств. Основные операции над множествами.
      
   2. 
      Доказательство основных законов алгебры множеств. Принцип двойственности.
      
   3. 
      Взаимно-однозначное соответствие. Эквивалентные множества. Мощность множеств.
      
   4. 
      n-местное отношение. Бинарное отношение. Способы задания бинарного отношения на конечном множестве. Виды бинарных отношений.
      
   5. 
      Основные свойства матриц бинарных отношений.
      
   6. 
      Отношения эквивалентности. Основное свойство классов эквивалентности. Ранг отношения. Класс вычетов.
      
   7. 
      Отношения толерантности. Отношения частичного порядка. Линейный порядок.
      
   8. 
      Соединение. Соединение с повторением. Соединение без повторения. Перестановка. Количество перестановок. Размещение. Количество размещений. Сочетания. Количество сочетаний. Основные свойства сочетаний.
      
   9. 
      Бином Ньютона (теорема с доказательством).
      
   10. 
       Доказательство свойств биномиальных коэффициентов. Треугольник Паскаля.
       
   11. 
       Доказательство полиномиальной формулы
       
   12. 
       Метод включений и исключений. Формула включений-исключений. Задача о беспорядках.
       
   13. 
       Формальный степенной ряд. Производящая функция. Равенство формальных степенных рядов. Сложение и вычитание формальных степенных рядов. Умножение и деление формальных степенных рядов.
       
   14. 
       Рекуррентное соотношение. Возвратная последовательность. Характеристический многочлен. Общее решение рекуррентного соотношения. Теорема о рекуррентных соотношениях.
       
   15. 
       Граф. Ориентированный граф. Неориентированный граф. Смежность и инцидентность. Способы задания графа. Матрицы графа. Степени вершины.
       
   16. 
       Подграф. Часть графа. Виды графов. Изоморфизм графов. Теорема об изоморфизме графов.
       
   17. 
       Маршруты в ориентированных и неориентированных графах. Связность. Достижимость.
       
   18. 
       Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов.
       
   19. 
       Задача о построении кратчайшего остовного дерева. Алгоритм Прима. Проблема Штейнера.
       
   20. 
       Задача о построении дерева кратчайших расстояний. Алгоритм Дейкстры.
       
   21. 
       Задача о построении матрицы кратчайших расстояний. Алгоритм Флойда.
       
   22. 
       Сеть. Поток в сети. Задача о максимальном потоке в сети. Разрез.
       
   23. 
       Доказать теорему Форда – Фалкерсона.
       
   24. 
       Остаточная пропускная способность. Остаточная сеть. Алгоритм Форда – Фалкерсона нахождения максимального потока.
       
   25. 
       Геометрическая реализация графа. Теорема о реализации конечного графа в трёхмерном евклидовом пространстве.
       
   26. 
       Планарный граф. Грань графа. Доказать формулу Эйлера для планарных графов.
       
   27. 
       Доказать, что граф К₅ не планарен. Доказать, что граф К₃₃ не планарен.
       
   28. 
       Независимое множество вершин графа. Вершинная раскраска. Правильная раскраска. Хроматическое число графа. Доказать теорему о 5 красках.
       
   29. 
       Эйлеров путь. Эйлеров граф. Алгоритм построения эйлерова пути в эйлеровом графе. Критерий эйлеровости графов.
       
   30. 
       Гамильтонов граф. Теорема Дирака.
       
   31. 
       Задача коммивояжёра. Метод ветвей и границ.
       
   32. 
       Хроматическое число. Планарность графов. Теорема о пяти краках.
       

5. 
   Перечень вопросов к экзамену.
   
   1. 
      Множества. Способы задания множеств. Основные операции над множествами.
      
   2. 
      Доказательство основных законов алгебры множеств. Принцип двойственности.
      
   3. 
      Взаимно-однозначное соответствие. Эквивалентные множества. Мощность множеств.
      
   4. 
      n-местное отношение. Бинарное отношение. Способы задания бинарного отношения на конечном множестве. Виды бинарных отношений.
      
   5. 
      Основные свойства матриц бинарных отношений.
      
   6. 
      Отношения эквивалентности. Основное свойство классов эквивалентности. Ранг отношения. Класс вычетов.
      
   7. 
      Отношения толерантности. Отношения частичного порядка. Линейный порядок.
      
   8. 
      Соединение. Соединение с повторением. Соединение без повторения. Перестановка. Количество перестановок. Размещение. Количество размещений. Сочетания. Количество сочетаний. Основные свойства сочетаний.
      
   9. 
      Бином Ньютона (теорема с доказательством).
      
   10. 
       Доказательство свойств биномиальных коэффициентов. Треугольник Паскаля.
       
   11. 
       Доказательство полиномиальной формулы
       
   12. 
       Метод включений и исключений. Формула включений-исключений. Задача о беспорядках.
       
   13. 
       Формальный степенной ряд. Производящая функция. Равенство формальных степенных рядов. Сложение и вычитание формальных степенных рядов. Умножение и деление формальных степенных рядов.
       
   14. 
       Рекуррентное соотношение. Возвратная последовательность. Характеристический многочлен. Общее решение рекуррентного соотношения. Теорема о рекуррентных соотношениях.
       
   15. 
       Граф. Ориентированный граф. Неориентированный граф. Смежность и инцидентность. Способы задания графа. Матрицы графа. Степени вершины.
       
   16. 
       Подграф. Часть графа. Виды графов. Изоморфизм графов. Теорема об изоморфизме графов.
       
   17. 
       Маршруты в ориентированных и неориентированных графах. Связность. Достижимость.
       
   18. 
       Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов.
       
   19. 
       Задача о построении кратчайшего остовного дерева. Алгоритм Прима. Проблема Штейнера.
       
   20. 
       Задача о построении дерева кратчайших расстояний. Алгоритм Дейкстры.
       
   21. 
       Задача о построении матрицы кратчайших расстояний. Алгоритм Флойда.
       
   22. 
       Сеть. Поток в сети. Задача о максимальном потоке в сети. Разрез.
       
   23. 
       Доказать теорему Форда – Фалкерсона.
       
   24. 
       Остаточная пропускная способность. Остаточная сеть. Алгоритм Форда – Фалкерсона нахождения максимального потока.
       
   25. 
       Геометрическая реализация графа. Теорема о реализации конечного графа в трёхмерном евклидовом пространстве.
       
   26. 
       Планарный граф. Грань графа. Доказать формулу Эйлера для планарных графов.
       
   27. 
       Доказать, что граф К₅ не планарен. Доказать, что граф К₃₃ не планарен.
       
   28. 
       Независимое множество вершин графа. Вершинная раскраска. Правильная раскраска. Хроматическое число графа. Доказать теорему о 5 красках.
       
   29. 
       Эйлеров путь. Эйлеров граф. Алгоритм построения эйлерова пути в эйлеровом графе. Критерий эйлеровости графов.
       
   30. 
       Гамильтонов граф. Теорема Дирака.
       
   31. 
       Задача коммивояжёра. Метод ветвей и границ.
       
   32. 
       Хроматическое число. Планарность графов. Теорема о пяти краках.
       

6. 
   Учебно-методическое обеспечение дисциплины.
   
   1. 
      Основная литература.
      
      1. 
         Игошин В. И. Математическая логика и теория алгоритмов. Учебное пособие для студентов ВУЗов. – М.: «Академия», 2008.
         
      2. 
         Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов. – М.: «Академия», 2007.
         
   2. 
      Дополнительная литература
      
      1. 
         Акритас А. Основы компьютерной алгебры с приложениями. – М.: “Мир”, 1994.
         
      2. 
         Балюкевич, Э. Л. Дискретная математика. Учебн [Электронный ресурс]: практическое пособие / Э. Л. Балюкевич, Л. Ф. Ковалева, А. Н. Романников. – М.: Евразийский открытый институт, 2012. – 173 с. – 978-5-374-00334-5. Режим доступа: http://biblioclub.ru/index.php?page=book&id=93277 (дата обращения 10.11.2013).
         
      3. 
         Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
         
      4. 
         Белоусов А. И. Дискретная математика. – М: Изд-во МГТУ им.Баумана, 2004.
         
      5. 
         Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.
         
      6. 
         Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.
         
      7. 
         Дискретная математика [Электронный ресурс]: учебник / Новосибирск: НГТУ, 2012. – 278 с. – 978-5-7782-1815-4. Режим доступа: http://biblioclub.ru/index.php?page=book&id=135675 (дата обращения 10.11.2013).
         
      8. 
         Ерусалимский, Я. М. Дискретная математика. Теория, задачи, приложения [Электронный ресурс] : учебное пособие / Я. М. Ерусалимский. - М.: Вузовская книга, 2009. - 288 с. - 978-5-9502-0423-4. Режим доступа: http://biblioclub.ru/index.php?page=book&id=129626 (дата обращения 10.11.2013).
         
      9. 
         Зайцева С. С. Дискретная математика. – Тюмень: Изл-во ТюмГУ, 2007.
         
      10. 
          Ковалева, Л. Ф. Дискретная математика в задачах [Электронный ресурс] : учебное пособие / Л. Ф. Ковалева. - М.: Евразийский открытый институт, 2011. - 142 с. - 978-5-374-00514-1. Режим доступа: http://biblioclub.ru/index.php?page=book&id=93273 (дата обращения 10.11.2013).
          
      11. 
          Кристофидес Н. Теория графов: алгоритмический подход. – М.: Мир, 1978.
          
      12. 
          Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергия, 1980.
          
      13. 
          Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
          
      14. 
          Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1984.
          
      15. 
          Окулов, С. М. Дискретная математика. Теория и практика решения задач по информатике [Электронный ресурс] : учебное пособие / С. М. Окулов. - М.: БИНОМ. Лаборатория знаний, 2012. - 427 с. - 978-5-9963-0893-4. Режим доступа: http://biblioclub.ru/index.php?page=book&id=120543 (дата обращения 10.11.2013).
          
      16. 
          Редькин, Н. П. Дискретная математика [Электронный ресурс] : учебник / Н. П. Редькин. - М.: Физматлит, 2009. - 263 с. - 978-5-9221-1093-8. Режим доступа: http://biblioclub.ru/index.php?page=book&id=75709 (дата обращения 10.11.2013).
          
      17. 
          Тюрин, С. Ф. Дискретная математика: Практическая дискретная математика и математическая логика [Электронный ресурс] / С. Ф. Тюрин, Ю. А. Аляев. - М.: Финансы и статистика, 2010. - 385 с. - 978-5-279-03463-5. Режим доступа:http://biblioclub.ru/index.php?page=book&id=63603 (дата обращения 10.11.2013).
          
      18. 
          Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРА-М; Новосибирск: НГТУ, 2003.
          
      19. 
          Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.
          
      20. 
          Нефёдов В.Н., Осипова В.А. Курс дискретной математики. – М.: Из-во МАИ, 1992.
          
      21. 
          Фомичев, В. М. Дискретная математика и криптология. Курс лекций [Электронный ресурс] / В. М. Фомичев. - : Диалог-МИФИ, 2003. - 397 с. - 5-86404-185-8. Режим доступа: http://biblioclub.ru/index.php?page=book&id=89387 (дата обращения 10.11.2013).
          
      22. 
          Хаггарти, Р. Дискретная математика для программистов [Электронный ресурс] / Р. Хаггарти. - М.: РИЦ "Техносфера", 2012. - 400 с. - 978-5-94836-303-5. Режим доступа: http://biblioclub.ru/index.php?page=book&id=89024 (дата обращения 10.11.2013).
          
      23. 
          Харари Ф. Теория графов. – М.: Мир, 1973.
          
      24. 
          Холл М. Комбинаторика. – М.: Мир, 1970.
          
      25. 
          Шеннон К. Работы по теории информации и кибернетике. – М.: ИЛ, 1963.
          
      26. 
          Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986.
          

7. 
   Система балловых оценок по дисциплине.