Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2

1Область применения и нормативные ссылки

2Цели освоения дисциплины

3Компетенции обучающегося, формируемые в результате освоения дисциплины

4Место дисциплины в структуре образовательной программы

1. 
   Программирование.
   
2. 
   Дискретная математика.
   
3. 
   Теоретические основы информатики.
   

1. 
   понимание основных концепций, принципов, теорий и фактов, связанных с информатикой;
   
2. 
   умение применять основы информатики и программирования к проектированию, конструированию и тестированию программных продуктов;
   
3. 
   навыки моделирования, анализа и использования формальных методов конструирования программного обеспечения;
   
4. 
   способность оценивать временную и емкостную сложность программного обеспечения.
   

1. 
   Объектно-ориентированный анализ и программирование.
   
2. 
   Криптографические методы защиты.
   
3. 
   Распределенные алгоритмы и параллельное программирование.
   
4. 
   Моделирование информационных систем.
   
5. 
   Оптимизация и математические методы принятия решений.
   

5Тематический план учебной дисциплины

Дополнительные разделы комбинаторики

1. 
   Рекурсивные алгоритмы и рекуррентные соотношения. Задачи, приводящие к однородным рекуррентным соотношениям.
   
2. 
   Метод исключения для решения однородных рекуррентных соотношений. Матричный метод решения однородных рекуррентных соотношений, задача о блуждающей точке.
   
3. 
   Рекуррентные соотношения с переменными коэффициентами, полиномиальные производящие функции, их свойства.
   
4. 
   Неоднородные рекуррентные соотношения, задача о поиске хроматического многочлена графа-цикла. Экспоненциальные производящие функции, сложность вычисления det A «по определению».
   
5. 
   Сложность вычисления det A разложением по строке и приведением к треугольному виду. Операции над производящими функциями. Свертка. Три задачи, приводящие к числам Каталана.
   
6. 
   Вывод формулы для чисел Каталана. Лемма Бернсайда, задача об ожерелье на плоскости и в пространстве.
   
7. 
   Симметрическая группа подстановок. Разложение подстановки в произведение циклов. Цикловой индекс группы подстановок. Теорема Пойа. Задача об окрашивании граней тетраэдра, задача об окрашивании ребер куба, задача о числе различных булевых функций от 3 аргументов.
   
8. 
   Метод «разделяй и властвуй», доказательство нижней оценки сложности поиска максимального элемента попарными сравнениями, сложность сортировки бинарными вставками и слиянием.
   
9. 
   Алгоритмы на графах: максимальное паросочетание, теорема Бержа, алгоритм чередующихся цепей, метод «волны» для поиска чередующихся цепей.
   
10. 
    Потоки в сетях, теорема и алгоритм Форда–Фолкерсона. Задача о максимальном потоке.
    
11. 
    Метод аугментальных цепей в задаче о максимальном потоке. Поиск максимального паросочетания с помощью потоков.
    
12. 
    Задача о максимальном потоке минимальной стоимости: метод удаления циклов положительной стоимости в остаточной сети.
    
13. 
    Алгоритм Флойда и его использование для поиска циклов положительной стоимости в остаточной сети. Сведение транспортной задачи и задачи о назначении к задаче о максимальном потоке минимальной стоимости.
    
14. 
    Полиномиальные алгоритмы в теории расписаний: типы расписаний, построение самого дешевого расписания для системы независимых заданий и одного исполнителя.
    
15. 
    Полиномиальный алгоритм для поиска оптимального расписания для системы заданий единичной длительности с древовидным графом для произвольного числа исполнителей и с произвольным графом для 2 исполнителей.
    
16. 
    Полиномиальные алгоритмы построения оптимального расписания с прерываниями для независимых заданий и почти оптимального расписания с прерываниями для зависимых заданий.
    
17. 
    Конвейерная задача.
    
18. 
    Задача о рюкзаке: «жадный» алгоритм, метод ветвей и границ.
    
19. 
    Задача коммивояжера: алгоритм Литтла, приближенный алгоритм Кристофидиса.
    
20. 
    Задача об упаковках в контейнеры: «жадный» алгоритм, алгоритм Джонсона.
    
21. 
    Генетические алгоритмы. Применение генетических алгоритмов для задач оптимизации.
    
22. 
    Применение генетических алгоритмов в криптографии и вычислении определенных интегралов.
    

6Формы контроля знаний студентов

Критерии оценки знаний, навыков

Порядок формирования оценок по дисциплине

7Содержание дисциплины

8Образовательные технологии

• 
  проработать конспект лекций;
  
• 
  проанализировать основную и дополнительную литературу, рекомендованную по изучаемому разделу;
  
• 
  проанализировать варианты решений, предложенные преподавателем на практических занятиях;
  
• 
  при затруднениях сформулировать вопросы к преподавателю.
  

9Оценочные средства для текущего контроля и аттестации студента

1. Вопросы для оценки качества освоения дисциплины

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

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

2. Базовый учебник

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

1. 
   Коффман Э.Г. Теория расписаний и вычислительные машины. М.: Наука, 1984.
   
2. 
   Левитин А.В. Алгоритмы: введение в разработку и анализ. М.: Издательский дом «Вильямс», 2006.
   
3. 
   Сэджвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах: Пер. с англ. СПб: ООО «ДиаСофтЮП», 2002.
   

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

4. 
   Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2000.
   
5. 
   Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. М.: Лаборатория Базовых Знаний, 2002.
   
6. 
   Сигал М.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. М.: ФИЗМАТЛИТ, 2002.
   

5. Программные средства

• 
  Средства разработки, тестирования, отладки программ, написанных на языке Pascal (Pascal ABC, Free Pascal).
  
• 
  Система контроля стиля программирования Style Checker;
  
• 
  LMS, как основа для организации дистанционной поддержки дисциплины.
  

11Материально-техническое обеспечение дисциплины