Учебно-методический комплекс для специальности
| Вид материала | Учебно-методический комплекс |
- Б. В. Мартынов учебно-методический комплекс по дисциплине «логистика» для студентов, 1097.34kb.
- Л. Л. Гришан Учебно-методический комплекс по дисциплине «Аудит» Ростов-на-Дону, 2010, 483.53kb.
- Учебно-методический комплекс по дисциплине Сети ЭВМ и телекоммуникации (наименование, 743.2kb.
- О. А. Миронова Учебно-методический комплекс дисциплины «международная торговля» Ростов-на-Дону, 727.71kb.
- А. Б. Тазаян Учебно-методический комплекс дисциплины "Философия права" (для студентов, 524.1kb.
- Е. С. Прокопенко учебно-методический комплекс по дисциплине «антикризисное управление», 589.33kb.
- О. А. Миронова Учебно-методический комплекс дисциплины «основы международного бизнеса», 782.97kb.
- Учебно-методический комплекс для студентов специальности "Менеджмент организации", 1323.36kb.
- Учебно-методический комплекс Для специальности: 080401 Товароведение и экспертиза товаров, 1272.71kb.
- Учебно-методический комплекс для студентов специальности 030501 «Юриспруденция» очной, 674.44kb.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Филиал федерального государственного бюджетного образовательного учреждения
высшего профессионального образования
«Астраханский государственный университет»
в г. Знаменске Астраханской области
«УТВЕРЖДАЮ»
Директор филиала ФГБОУ ВПО АГУ
в г. Знаменске Астраханской области
__________________В.Н.Крамаренко
Дисциплина блока общие математические и естественно-научные дисциплины
(название блока учебного плана)
Кафедра математики и информатики
(название кафедры)
Анализ комбинаторных алгоритмов
(дисциплина)
учебно-методический комплекс
для специальности
230201.65 Информационные системы и технологии (Знаменск)
(название специальности/ей)
2 курс
(номер курса)
Автор - составитель:
Лобейко В.И.
e-mail:
znamensk@aspu.ru
Анализ комбинаторных алгоритмов
(название дисциплины)
учебно-методический комплекс
Автор составитель д.т.н. профессор, Лобейко В.И.
(звание, ФИО)
Ответственный редактор
Зав. кафедрой математики и информатики, д.т.н. профессор, Лобейко В.И.
(звание, ФИО)
учебно-методический комплекс обсужден
на заседании кафедры математики и информатики
Протокол № __1_ от __30.08_2010 г.
учебно-методический комплекс рассмотрен и одобрен
на заседании методического совета филиала ФГБОУ ВПО АГУ
в г. Знаменск
Протокол №_1__от _31.08_2011 г.
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Основная практическая причина для анализа алгоритмов - необходимость получения оценок или границ для объема памяти или времени работы (и прочих ресурсов машины и пользователя), которые потребуются алгоритму для успешной обработки данных. Анализ полезен при проектировании программы чтобы исключить появление неработоспособных по памяти или времени систем, выявить узкие места в программе, сравнении разных алгоритмов решения одной задачи, для выявления более эффективных алгоритмов и замены устаревших.
Курс «Анализ комбинаторных алгоритмов» ставит своей целью изучение студентами важнейших разделов комбинаторного анализа и теории алгоритмов, методов оценивания эффективности алгоритмов и обоснования их корректности.
В результате обучения студент должен овладеть навыками разработки эффективных комбинаторных алгоритмов при решении задач управления, проектирования, обработки данных, системного программирования, приобрести навыки и умения в постановке и решению задач.
РАСПРЕДЕЛЕНИЕ
ЧАСОВ ПО ТЕМАМ И ВИДАМ УЧЕБНЫХ ЗАНЯТИЙ
| Наименование тем | Количество аудиторных часов | ||||
| Всего | в том числе по видам учебных занятий | ||||
| Лекции | Практические, семинарские занятия | Лабораторные занятия | Самостоятельная работа | ||
| 1 | 2 | 3 | 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
КАЛЕНДАРНЫЙ ПЛАН ЛАБОРАТОРНЫХ ЗАНЯТИЙ
| Порядковый номер | Содержание занятия | Количество аудиторных часов | Объем материала | Форма контроля | Задания для самостоятельной работы студентов |
| | Постановка проблемы. Примеры. Классы алгоритмов. | 2 часа | [1, стр. 10 — 13] [2, стр 13 -16] | Отчет по лабораторной работе. | Разработка различного класса алгоритма |
| | Представление комбинаторных объектов. Основы оценки. Массивы. | 4 часа | [2, стр. 20 — 35] [5, стр 30 - 40] | Отчет по лабораторной работе. | Описание и представление, оценивание комбинаторных объектов. |
| | Сортировка. Внутренняя сортировка: вставка, распределяющая сортировка. Внешняя сортировка. Методы решета: не рекурсивное модульное решето, решето, отбраковывающее изоморфные объекты. | 2 часа | [3, стр 45- 55] [5, стр 61 - 67] | Отчет по лабораторной работе. | Рассмотрение изоморфных объектов, составление сортировки на основе метода решета |
| | Исчерпывающий поиск. Поиск с возвращением: общий алгоритм, усовершенствования, Быстрый поиск. Последовательный поиск. Логарифмический поиск в статических таблицах: бинарный поиск. Логарифмический поиск в динамических таблицах. | 8 часа | [1. стр. 70 — 80] [2, стр, 90 -100] | Отчет по лабораторной работе. | Разработка и усовершенствования, алгоритма с быстрым поиском. Осуществление логарифмического поиска в статистических и динамических таблицах, |
КРИТЕРИИ ОЦЕНКИ РЕЗУЛЬТАТОВ.
«5» («отлично») - уровень выполнения требований значительно выше удовлетворительного: использование дополнительного материала, самостоятельность суждений, отражение своего отношения к предмету обсуждения, отсутствие ошибок в изложении учебного материала, логичность и полнота изложения. Вопросы раскрыты на высоком уровне, выявлены полнота материала, систематичность и последовательность в изложении основных теоретических положений и вопросов; показаны умения четко и коротко излагать сущность вопросов, способность формулировать основные идеи темы, умение дискутировать. Представлен полный ответ на дополнительные вопросы. Обоснованы все ключевые моменты вопросов.
«4» («хорошо») - уровень выполнения требования выше удовлетворительного: полнота раскрытия вопроса; самостоятельность суждений; не более 1-2 недочетов; незначительные нарушения логики изложения материала. Вопросы раскрыты полностью, выявлены систематичность и последовательность в изложении основных теоретических вопросов, обоснованы все ключевые моменты темы. Не отражены при дискутировании умения четко и ясно излагать основные идеи темы, её результаты. Не на все дополнительные вопросы был дан полный ответ.
«3» («удовлетворительно») - достаточный минимальный уровень выполнения требований предъявляемых к работе: не более 1 ошибки или 2-3 недочетов; отдельные нарушения логики изложения материала. Вопросы раскрыты не полностью, обоснованы не все ключевые моменты вопросов. Представлена последовательность в изложении основных теоретических положений вопросов. Сущность темы не отражена в ответах на дополнительные вопросы. Возможны ошибки при изложении материала, не показано умение дискутировать.
«2» («неудовлетворительно») - уровень выполнения требования ниже удовлетворительного: наличие более 2 ошибок или 4 недочетов; нарушение логики, неполнота, нераскрытость обсуждаемого вопроса; отсутствие аргументации либо ошибочность её основных положений. Вопросы раскрыты не полностью, общая идея верная, но не выявлены систематичность и последовательность в изложении основных теоретических положений. Большинство ключевых моментов темы не обоснованы или имеются неверные обоснования. Возможны ошибки в схемах или чертежах. Ни на один дополнительный вопрос не получен ответ. Не выявлено умение дискутировать, не показано умение излагать материал четко и ясно.
Классификация ошибок и недочетов, влияющих на снижение оценки.
ОШИБКИ:
-неправильный ответ на поставленный вопрос;
-неумение ответить на поставленный вопрос;
-неправильное определение понятия, замена существенной характеристики понятия несущественной;
-незнание фактического материала, неумение привести самостоятельные примеры, подтверждающие высказанное суждение;
-неправильное раскрытие причин, закономерностей, условия протекания того или иного изученного явления.
НЕДОЧЕТЫ:
-неточный или неполный ответ на поставленный вопрос;
-при правильном ответе неумение полно обосновать его или проиллюстрировать примерами;
-неумение точно сформулировать ответ;
-неправильное произношение терминов;
-неточности в определении понятия, точности формулировки осуществляется после наводящих вопросов.
КРИТЕРИИ ОЦЕНКИ РЕЗУЛЬТАТОВ.
«Зачтено» - уровень выполнения требований выше удовлетворительного: полнота раскрытия вопроса, самостоятельность суждений. Допускаются отдельные неточности или незначительные нарушения логики в изложении материала. Не более 2-3 недочетов.
«Не зачтено» - уровень выполнения требований ниже удовлетворительного: неполнота, нераскрытость вопроса; отсутствие аргументации или ошибочность её основных положений; нарушение логики изложения. Более 2 ошибок или 4 недочетов.
Классификация ошибок и недочетов, влияющих на снижение оценки.
ОШИБКИ:
-неправильный ответ на поставленный вопрос;
-неумение ответить на поставленный вопрос;
-неправильное определение понятия, замена существенной характеристики понятия несущественной;
-незнание фактического материала, неумение привести самостоятельные примеры, подтверждающие высказанное суждение;
-неправильное раскрытие причин, закономерностей, условия протекания того или иного изученного явления.
НЕДОЧЕТЫ:
-неточный или неполный ответ на поставленный вопрос;
-при правильном ответе неумение полно обосновать его или проиллюстрировать примерами;
-неумение точно сформулировать ответ;
-неправильное произношение терминов;
-неточности в определении понятия, точности формулировки осуществляется после наводящих вопросов.
МАТЕРИАЛЬНАЯ БАЗА
Лабораторные занятия проводятся в компьютерных классах кафедры ИC на базе ПК IBM PC Pentium.
ТРЕБОВАНИЯ К УРОВНЮ УСВОЕНИЯ МАТЕРИАЛА
Для сдачи данной дисциплины студент должен полностью раскрыть тему, ясно и последовательно изложить содержание вопроса, привести примеры, дать определения ключевым понятиям и терминам изучаемого курса. В конце ответа сделать обобщения и выводы.
Ошибки и недочеты
- повторное перетягивание билета;
- отказ отвечать на тот или иной вопрос билета или дополнительный вопрос;
- нарушение логики при ответе (отрывочные сведения);
- неправильный ответ на вопрос;
- неверное толкование термина;
- неполный ответ на вопрос;
- неумение точно и лаконично сформулировать ответ;
- ответ после наводящих вопросов;
- отсутствие выводов и заключения при достаточно полном ответе;
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ
ДИСЦИПЛИНЫ И ОРГАНИЗАЦИИ САМОСТОЯТЕЛЬНОЙ
РАБОТЫ СТУДЕНТОВ
Самостоятельная работа студентов – совокупность всей самостоятельной деятельности обучаемых как в отсутствие преподавателя, так и в контакте с ним, в учебной аудитории и за ее пределами (в том числе и в ходе учебных занятий). При изучении данной дисциплины целесообразно использовать следующие формы учебной работы:
- обзорные лекции;
- самостоятельная работа студентов с учебной и методической литературой;
- выполнение контрольных заданий (упражнений, тестов, задач).
Планируя время на изучение дисциплины, студентам можно руководствоваться предложенным учебно-методическим планом, где указано распределение времени, отведенного на изучение дисциплины, между лекциями, семинарами и самостоятельной подготовкой.
В ходе самостоятельной работы студентам необходимо разбираться с изучаемым вопросом, используя учебники (смотри список основной литературы) и материалы лекций. Для подготовки докладов к семинарским занятиям, или для углубления знаний по той или иной теме, целесообразно воспользоваться дополнительной литературой (смотри список дополнительной литературы). Учебники и другую литературу можно взять в библиотеке.
При подготовке докладов, сообщений можно воспользоваться Интернет-ресурсами. При этом следует обратить внимание на то, чтобы используемая информация была актуальна и достоверна.
При подготовке докладов следует выписывать полные ссылки из тех источников, которыми воспользовались. Это позволит преподавателю проверить качество выполненной работы.
Для проверки знаний можно использовать тестовые материалы или вопросы для самостоятельной подготовки, предложенные в УМК.
Для контроля усвоения данной дисциплины учебным планом предусмотрен зачет. Вопросы к зачету приведены в разделе «Контрольные вопросы по дисциплине в целом».
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ ПРЕПОДАВАТЕЛЕЙ
Не старайтесь записать дословно все, что говорит преподаватель — это невозможно, да и не нужно. Если вы будете к этому стремиться, в ваших записях неизбежны недописанные' предложения, пропуски, а значит — нарушения логики изложения материала, которые сделают конспект бесполезным. Учитесь формулировать мысли кратко и своими словами, записывая только самое существенное.
Учитесь «на слух» отделять главное от второстепенного. Но это не означает, что записывать нужно только основные положения и определения, которые без примеров и иллюстраций могут впоследствии, при чтении конспектов, оказаться непонятными. Поэтому факты, которые приводит лектор, также лучше отмечать; иногда для этого бывает достаточно нескольких ключевых слов.
Записи должны быть сжатыми, логично связанными, представлять собой нечто вроде развернутого плана лекции.
Если в лекции предлагаются схемы, таблицы, чертежи, обязательно полностью заносите их в тетрадь, выполняя аккуратно и внимательно.
По ходу лекции преподаватель обычно отмечает те или иные мысли, положения, поэтому сразу делайте соответствующие смысловые выделения в ваших записях. Для этого можно использовать не только разные виды подчеркиваний (прямая, волнистая линии, пунктир и т. п.), разноцветные выделения, но и различные значки, например:! — «важно», ? — «проверить, уточнить», NB (nota bene) — «обратить внимание» и др.
Оставляйте в тетради поля, которые можно использовать в дальнейшем для уточняющих записей, комментариев, дополнений и т. п.
Используйте красную строку для выделения смысловых частей в записях.
Постарайтесь выработать свою собственную систему сокращения часто встречающихся слов или их замены определенными знаками. Это даст вам возможность меньше писать, больше слушать и думать.
Сразу после лекции постарайтесь просмотреть записи и по свежим следам восстановить пропущенное, дописать недописанное, завершить выделение существенных моментов.