Рабочая учебная программа для специальности
| Вид материала | Рабочая учебная программа |
- Рабочая учебная программа по детской хирургии для специальности педиатрия (1-79, 165.9kb.
- Рабочая учебная программа дисциплины акушерство для специальности 060201. 65 стоматология, 347.69kb.
- Рабочая учебная программа по общей хирургии для специальности 1-79 01 02 «Педиатрия», 500.82kb.
- Рабочая учебная программа предмета уголовный процесс по специальности 030503 Правоведение, 127.16kb.
- Рабочая учебная программа предмета менеджмент по специальности Химическая технология, 201.97kb.
- Рабочая учебная программа по общественному здоровью и здравоохранению для специальности, 549.16kb.
- Рабочая учебная программа по анатомии человека для специальности 060101 лечебное дело, 492.05kb.
- Рабочая учебная программа по поликлинической терапии для специальности 060101 лечебное, 373.72kb.
- Рабочая учебная программа по медицинской информатике и автоматизированным системам, 285.31kb.
- Рабочая учебная программа предмета автоматизация технологических процессов по специальности, 107.25kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Филиал федерального государственного бюджетного образовательного учреждения
высшего профессионального образования
«Астраханский государственный университет»
в г. Знаменске Астраханской области
«УТВЕРЖДАЮ»
Директор филиала ФГБОУ ВПО АГУ
в г. Знаменске Астраханской области
__________________В.Н.Крамаренко
Дисциплина блока общие математические и естественно-научные дисциплины
(название блока учебного плана)
Кафедра математики и информатики
(название кафедры)
Анализ комбинаторных алгоритмов
(дисциплина)
Рабочая учебная программа
для специальности
230201.65 Информационные системы и технологии (Знаменск)
(название специальности/ей)
2 курс
(номер курса)
Автор- составитель:
Лобейко В.И.
e-mail:
znamensk@aspu.ru
Анализ комбинаторных алгоритмов
(название дисциплины)
Рабочая учебная программа
Автор составитель д.т.н. профессор, Лобейко В.И.
(звание, ФИО)
Ответственный редактор
Зав. кафедрой математики и информатики, д.т.н. профессор, Лобейко В.И.
(звание, ФИО)
Рабочая учебная программа обсужден
на заседании кафедры математики и информатики
Протокол № __1_ от __30.08_2010 г.
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Основная практическая причина для анализа алгоритмов - необходимость получения оценок или границ для объема памяти или времени работы (и прочих ресурсов машины и пользователя), которые потребуются алгоритму для успешной обработки данных. Анализ полезен при проектировании программы чтобы исключить появление неработоспособных по памяти или времени систем, выявить узкие места в программе, сравнении разных алгоритмов решения одной задачи, для выявления более эффективных алгоритмов и замены устаревших.
Курс «Анализ комбинаторных алгоритмов» ставит своей целью изучение студентами важнейших разделов комбинаторного анализа и теории алгоритмов, методов оценивания эффективности алгоритмов и обоснования их корректности.
В результате обучения студент должен овладеть навыками разработки эффективных комбинаторных алгоритмов при решении задач управления, проектирования, обработки данных, системного программирования, приобрести навыки и умения в постановке и решению задач.
РАСПРЕДЕЛЕНИЕ
ЧАСОВ ПО ТЕМАМ И ВИДАМ УЧЕБНЫХ ЗАНЯТИЙ
| Наименование тем | Количество аудиторных часов | ||||
| Всего | в том числе по видам учебных занятий | ||||
| Лекции | Практические, семинарские занятия | Лабораторные занятия | Самостоятельная работа | ||
| 1 | 2 | | 4 | 5 | 6 |
| Тема 1. Введение. Тема 2. Комбинаторные объекты. Тема 3. Сортировка. Тема 4. Поиск. | 2 4 2 10 | | | 2 4 2 10 | |
| Итого аудиторных часов | 18 | | | 18 | |
| Количество часов самостоятельной работы студентов | 72 | | | | |
| Всего часов | 90 | | | | |
СОДЕРЖАНИЕ КУРСА
Тема 1. Введение.
Постановка проблемы. Примеры. Классы алгоритмов.
Тема 2. Комбинаторные объекты.
Представление комбинаторных объектов. Массивы. Основы оценки. Ссылки и указатели. Линейные списки. Стеки и очереди. Деревья. Бинарные деревья. Прохождение дерева.
Тема 3. Сортировка
Сортировка. Внутренняя сортировка: вставка, обменная сортировка, выбор, распределяющая сортировка. Внешняя сортировка.
Тема 4. Поиск.
Исчерпывающий поиск. Поиск с возвращением: общий алгоритм, усовершенствования, оценка сложности выполнения, способы программирования. Методы решета: нерекурсивное модульное решето, решето, отбраковывающее изоморфные объекты. Быстрый поиск. Последовательный поиск. Логарифмический поиск в статических таблицах: бинарный поиск, оптимальные деревья бинарного поиска, цифровой поиск. Логарифмический поиск в динамических таблицах. Методы вычисления адреса: хеширование и его варианты, хеш-функции.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
ОСНОВНАЯ
- Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы : учеб. пособ. / М. О. Асанов, Баранский, В.А., Расин, В.В. - 2-е изд. ; испр. и доп. - СПб. : Лань, 2010. - 368 с.
- Ахо А., Хопкрофт Дж., Ульман Э. Структуры данных и алгоритмы. 2007.
- Кнут Д. Искусство программирования для ЭВМ. Том 1-3. 2008.
- Мальцев, И.А. Линейная алгебра : учеб. пособ. / И. А. Мальцев. - 2-е изд. ; испр. и доп. - СПб. : Лань, 2010. - 384 с.
- Проскуряков, И.В. Сборник задач по линейной алгебре : учеб. пособие / И. В. Проскуряков. - 13-е изд. ; стер. - СПб. : Лань, 2010. - 480 с.
- Руководства и задания к лабораторным работам (//fileserver\Учебные материалы\230101-Вычислительные машины, комплексы, системы и сети\II курс\Анализ комбинаторных алгоритмов)
- Демонстрационные программы (//fileserver\Учебные материалы\230101-Вычислительные машины, комплексы, системы и сети\II курс\Анализ комбинаторных алгоритмов)
ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи
- Рейнгольд Э. и др. Комбинаторные алгоритмы: теория и практика
ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ К ЗАЧЕТУ
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. Моделирование отжига.
ПРОГРАММНЫЕ ПРОДУКТЫ
- Borland Pascal
- Borland Turbo C++
- Microsoft Visual C++
- Borland С Builder
- Borland Delphi