Министерство образования и науки Федеральное государственное образовательное учреждение «Тюменский государственный университет» Институт математики и компьютерных наук Кафедра математики и информатики |
динамическое программирорование Учебно-методический комплекс. Рабочая программа очной формы обучения |
Тюменский государственный университет 2013 |
, Динамическое программирование. Учебно-методический комплекс. Рабочая программа для студентов направления 020501.65 Биоинженерия и биоинформатика очной формы обучения. Тюмень, 2013, 18 стр. Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки. Рабочая программа дисциплины (модуля) опубликована на сайте ТюмГУ: Динамическое программирование [электронный ресурс] / Режим доступа: http://www. umk3.utmn. ru, свободный. Рекомендовано к изданию кафедрой математики и информатики. Утверждено проректором по учебной работе Тюменского государственного университета. Ответственный редактор: , к. т.н., и. о. зав. кафедрой |
© Тюменский государственный университет, 2013 © , 2013 |
1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
1.1 Цели и задачи дисциплины
Рабочая программа учебной дисциплины "Динамическое программирование" предназначена для подготовки студентов специальности 020501 – Биоинженерия и биоинформатика.
Изучение дисциплины требует от студентов знаний и навыков уверенной работы с компьютером (опытный пользователь) и программирования.
Целями преподавания дисциплины являются:
- изучение основных принципов динамического программирования;
- изучение основных структур динамической памяти;
- изучения принципов поиска по матрицам, деревьям и графам;
- освоение понятия алгоритмической сложности.
В связи с этим, задачами преподавания дисциплины «Динамическое программирование» являются:
- программировать сложные типы данных;
- составлять алгоритмы поиска в различных структурах;
- программировать простые и сложные алгоритмы;
1.2. Компетенции выпускника ООП бакалавриата, формируемые в результате освоения данной ООП ВПО.
В результате освоения ООП бакалавриата выпускник должен обладать следующими компетенциями:
код | Формулировка компетенции | Результат обучения в целом | Результаты обучения по уровням освоения материала | Виды занятий | Оценочные средства | ||
минимальный | базовый | повышенный | |||||
ОК-14 | способностью понимать сущность и значение информации в развитии современного информационного общества, сознавать опасности и угрозы, возникающие в этом процессе, соблюдать основные требования информационной безопасности, в том числе защиты государственной тайны | Знает | На базовом уровне сущность и значение информации | В достаточном объеме способность понимать информацию | В совершенстве понимать информацию и смысл информации | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы |
Умеет | На базовом уровне сознавать опасности и угрозы | В достаточном объеме сознавать опасности и угрозы, профилактику и меры по их предотвращению | В совершенстве сознавать опасности и угрозы и меры по их предотвращению | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
Владеет | На базовом уровне основными понятиями информационной безопасности | В достаточном объеме основными понятиями безопасности и защиты информации | В совершенстве основными понятиями информационной безопасности, в том числе защиты государственной тайны. | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
ОК-15 | владением основными методами, способами и средствами получения, хранения, переработки информации, наличием навыков работы с компьютером как средством управления информацией | Знает | На базовом уровне основные методы получения информации | В достаточном объеме методы получения информации, а также средства ее хранения и переработки | В совершенстве методы и средствами получения, хранения, переработки информации, наличием навыков работы с компьютером как средством управления информацией | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы |
Умеет | На базовом уровне работать с компьютером | В достаточном объеме владеет компьютерной грамотностью | В совершенстве знает устройство компьютера и приемы работы с ним | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
Владеет | На базовом уровне понятиями компьютерной грамотности | В достаточном объеме понятиями компьютерной грамотности | В совершенстве понятиями компьютерной грамотности | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
ПК-1 | способностью грамотно и самостоятельно проводить теоретическую и экспериментальную научно-исследовательскую работу в области биоинженерии, биоинформатики и смежных дисциплин, а также оформлять ее в письменной форме, излагать в устной форме и участвовать в различных формах дискуссий | Знает | На базовом уровне теоретическую научно-исследовательскую работу | В достаточном объеме теоретическую и экспериментальную научно-исследовательскую работу | В совершенстве теоретическую и экспериментальную научно-исследовательскую работу, принимает участие в написании статей | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы |
Умеет | На базовом уровне излагать материал | В достаточном объеме излагать материал в устной форме | В совершенстве излагать материал в устной форме, участвовать в обсуждениях | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
Владеет | Базовыми навыками участвовать в различных формах дискуссий. | В достаточном объеме навыками участия в дискуссиях, конференциях и прочих мероприятиях | В совершенстве приемами участия в публичных выступлениях | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
ПК-6 | способностью создавать новые программные средства и базы данных, а также использовать ресурсы сети Интернет | Знает | На базовом уровне способы создания программных средств | В достаточном объеме способы создания программных средств и может применить их на практике | В совершенстве способы создания программных средств, знает как практически выполнить | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы |
Умеет | На базовом уровне создавать новые программные средства и базы данных. | В достаточном объеме создавать базы данных и успешно применять знания на практике | В совершенстве способы создания программных продуктов и внедрять готовые продукты в производство | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
Владеет | На базовом уровне навыками использовать ресурсы сети Интернет. | В достаточном объеме навыками поиска конкретной информации | В совершенстве навыками работы с найденным материалом | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
ПК-7 | способностью порождать новые идеи, выявлять фундаментальные проблемы, формировать задачи, связанные с реализацией профессиональных функций, использовать для их решения методы изученных ими наук | Знает | На базовом уровне способы порождать новые идеи | В достаточном объеме способы получения новых идей | В совершенстве приобретать новые идеи | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы |
Умеет | На базовом уровне выявлять фундаментальные проблемы | В достаточном объеме выявлять фундаментальные проблемы и формировать задачи | В совершенстве выявлять фундаментальные проблемы, формировать задачи, связанные с реализацией функций | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы | ||
Владеет | На базовом уровне формировать задачи | В достаточном объеме формировать задачи, связанные с реализацией в профессиональной деятельности | В совершенстве формировать задачи, связанные с реализацией в профессиональной деятельности и использовать для их решения методы изученных ими наук | Лекции, лабораторные занятия | Собеседование, контрольная работа, программы компьютерного тестирования, электронные практикумы |
1.3. Место дисциплины в структуре ООП бакалавриата
Дисциплина " Динамическое программирование " относится к вариативной части естественно-математического цикла. Содержание дисциплины "Динамическое программирование" базируется на знаниях, полученных в курсах Информатика, "Информатика. Программирование". Приобретенные знания и навыки будут использованы студентами при изучении дисциплины "Системный анализ" и "Базы данных".
В результате освоения дисциплины обучающийся должен:
Знать:
- основные понятия и принципы динамического программирования;
- типы данных, и их внутренне представление;
- типы деревьев и методы поиска в деревьях;
- структуры представления графов и операции поиска на графах;
- способы представления файлов деревьями.
Уметь:
- разрабатывать структуры данных для размещения в памяти компьютера;
- программировать сложные типы данных;
- составлять алгоритмы поиска в различных структурах;
- программировать простые и сложные алгоритмы;
- проводить отладку программы с использованием анализа выходных данных;
- оценивать сложность алгоритма.
Владеть навыками:
- программирования;
- разнообразии алгоритмов поиска и сортировки;
- методах оценки сложности алгоритмов.
2. СТРУКТУРА И ТРУДОЕМКОСТЬ ДИСЦИПЛИНЫ.
Семестр 4. Форма промежуточной аттестации - зачет. Общая трудоемкость дисциплины составляет 2 зачетных единицы, 72 часа.
3. ТЕМАТИЧЕСКИЙ ПЛАН.
Тематический план
№ | Тема | недели семестра | Виды учебной работы и самостоятельная работа, в час. | Итого часов по теме | В том числе в интерактивной форме | Итого количество баллов | |||
Лекции* | Семинарские (практические) занятия* | Лабораторные занятия* | Самостоятельная работа* | ||||||
Модуль 1 | |||||||||
Введение в предмет | 1 | 1 | 1 | 2 | 4 | 2 | 0-10 | ||
Алгоритмы и их свойства | 2-3 | 2 | 2 | 4 | 8 | 2 | 0-10 | ||
Динамическое программирование | 4-6 | 2 | 2 | 4 | 8 | 2 | 0-10 | ||
Всего | 5 | 5 | 10 | 20 | 6 | 0-30 | |||
Модуль 2 | |||||||||
Линейные однонаправленные списки. Операции над списками | 7-9 | 1 | 1 | 3 | 5 | 2 | 0-10 | ||
Линейные двунаправленные списки | 10-11 | 2 | 2 | 3 | 7 | 2 | 0-10 | ||
Бинарные деревья поиска | 12 | 2 | 2 | 4 | 8 | 2 | 0-10 | ||
Всего | 5 | 5 | 10 | 20 | 6 | 0-30 | |||
Модуль 3 | |||||||||
Работа с графами | 13-14 | 3 | 3 | 10 | 16 | 2 | 0-20 | ||
Сложность алгоритмов | 15-18 | 3 | 3 | 10 | 16 | 2 | 0-20 | ||
Всего | 6 | 6 | 20 | 32 | 4 | 0-40 | |||
Итого (часов, баллов): | 16 | 16 | 40 | 72 | 16 | 0-100 | |||
Из них в интерактивной форме | 18 |
Виды и формы оценочных средств в период текущего контроля
№ темы | Устный опрос | Письменные работы | Информационные системы и технологии | Итого количество баллов | |||||||
Коллоквиумы | Собеседование | ответ на семинаре | контрольная работа | тест | реферат | эссе | электронные практикум | другие формы | |||
Введение в предмет | 0-10 | 0-10 | |||||||||
Алгоритмы и их свойства | 0-10 | 0-10 | |||||||||
Динамическое программирование | 0-6 | 0-4 | 0-10 | ||||||||
Линейные однонаправленные списки. Операции над списками | 0-10 | 0-10 | |||||||||
Линейные двунаправленные списки | 0-10 | 0-10 | |||||||||
Бинарные деревья поиска | 0-4 | 0-6 | 0-10 | ||||||||
Работа с графами | 0-10 | 0-10 | 0-20 | ||||||||
Сложность алгоритмов | 0-10 | 0-10 | 0-20 | ||||||||
0-100 |
Планирование самостоятельной работы студентов
№ | Модули и темы | Виды СРС | Неделя семестра | Объем часов | Кол-во баллов | ||
обязательные | дополнительные | ||||||
Модуль 1 | |||||||
Введение в предмет | Доработка лекционного материала. Чтение литературы. | Поиск дополнительного материала по данной теме | 1 | 2 | 0-10 | ||
Алгоритмы и их свойства | Доработка лекционного материала. Чтение литературы. | Поиск дополнительного материала по данной теме | 2-3 | 4 | 0-10 | ||
Динамическое программирование | Доработка лекционного материала. Чтение литературы. | Поиск дополнительного материала по данной теме | 4-6 | 4 | 0-10 | ||
Всего по модулю 1: | 10 | 0-30 | |||||
Модуль 2 | |||||||
Линейные однонаправленные списки. Операции над списками | Доработка лекционного материала. Чтение литературы. | Поиск дополнительного материала по данной теме | 7-9 | 3 | 0-10 | ||
Линейные двунаправленные списки | Доработка лекционного материала. Чтение литературы. | Поиск дополнительного материала по данной теме | 10-11 | 3 | 0-10 | ||
Бинарные деревья поиска | Доработка лекционного материала. литературы. | Поиск дополнительного материала по данной теме | 12 | 4 | 0-10 | ||
Всего по модулю 2: | 10 | 0-30 |
| ||||
Модуль 3 |
| ||||||
Работа с графами | Доработка лекционного материала. Чтение литературы. | Поиск дополнительного материала по данной теме | 13-14 | 10 | 0-20 |
| |
Сложность алгоритмов | Доработка лекционного материала. Чтение литературы. | Поиск дополнительного материала по данной теме | 15-18 | 10 | 0-20 |
| |
Всего по модулю 3: | 20 | 0-40 | |||||
ИТОГО: | 40 | 0-100 | |||||
4. РАЗДЕЛЫ ДИСЦИПЛИНЫ И МЕЖДИСЦИПЛИНАРНЫЕ СВЯЗИ С ОБЕСПЕЧИВАЕМЫМИ (ПОСЛЕДУЮЩИМИ) ДИСЦИПЛИНАМИ
№ п/п | Наименование обеспечиваемых (последующих) дисциплин | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1. | Системный анализ | + | + | + | + | + | |||
2 | Базы данных | + | + | + | + | + | + |
5. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ.
Введение. Задачи и назначение курса. Формы представления информации: на уровне пользователя, в компьютере. Необходимость алгоритмов для программирования.
Тема 1. Алгоритмы и их свойства. Программа и алгоритм. Основные свойства алгоритма. Понятие данных. Способы представления алгоритма. Словесное описание алгоритма. Основные конструкции алгоритма. Графическое представление алгоритма. Понятие алгоритмического языка. Методы разработки алгоритмов: итерации, рекурсии, полный перебор, балансировка.
Тема 2. Динамическое программирование. Организация массивов. Многомерные массивы. Операции над массивами. Динамические массивы. Быстрый поиск: бинарный и последовательный поиски в массивах, хеширование.
Тема 3. Линейные однонаправленные списки. Операции над списками. Построение списка. Операции над списками. Кольцевые списки. Построение и вывод кольца. Построение других структур на базе однонаправленных списков в динамической памяти: очереди, стеки, деки. Проведение операций над элементами структур.
Тема 4. Линейные двунаправленные списки. Формирование линейного двунаправленного списка. Способы организации поиска. Двунаправленные кольцевые списки. Деки на базе двунаправленных списков. Формирование дека и его просмотр. Проведение операций над элементами структур.
Тема 5. Бинарные деревья поиска. Построение бинарного дерева поиска. Дерево отрезков. Способы обхода дерева. Изображение бинарного дерева. Поиск вершины в бинарном дереве. Операции над вершинами в деревьях. Идеально сбалансированные бинарные деревья. Балансированные по высоте деревья (АВЛ-деревья). Математический анализ АВЛ-деpевьев. Построение АВЛ-дерева. Деревья Фибоначчи. Алгоритмы балансировки.
Тема 6. Работа с графами. Представления графов. Список ребер. Списки смежности. Реализация простейших операций над графами. Ортогональные списки смежности. Структуры Вирта. Модифицированные структуры Вирта. Обходы графов. Путь между фиксированными вершинами. Кратчайшие пути между всеми парами вершин. Вычисление длин кратчайших путей между вершинами. Контуры в ориентированных графах. Вычисление компонент связности, двусвязности. Остовы. Построение остова наименьшей стоимости. Построение алгоритмов с возвратом. Алгоритмы раскраски графа. Задачи поиска; исчерпывающий поиск: перебор с возвратом, метод ветвей и границ.
Тема 7.Сложность алгоритмов. Понятие о сложности алгоритма. Временная и емкостная оценки сложности. Верхние и средние оценки сложности алгоритма. Анализ сложности рекурсивных алгоритмов. Сложность операций с бинарными деревьями. Оптимизация алгоритмов.
6. ПЛАНЫ ЛАБОРАТОРНЫХ ЗАНЯТИЙ
Тема 1. Организация массивов. Операции над массивами. Сортировки. Однонаправленные списки. Операции над списками. Очередь. Операции над элементами очереди.
Кольца. Операции над кольцами. Стек. Работа со стеком. Дек. Работа с деком.
Тема 2. Двунаправленные списки. Работа с производными структурами: кольцами и деком.
Деревья. Построение дерева. Обходы деревьев. Операции с деревьями. Поиск заданной вершины в дереве. Построение идеально сбалансированного дерева. Деревья Фибоначчи. Построение АВЛ-дерева.
Тема 3. Представление формул с помощью дерева. Вычисление формул. Представление графов с помощью ортогональных списков смежности.
Тема 4. Представление ориентированного графа с помощью динамической структуры Вирта. Представление графа. Обходы графов.
Тема 5. Реализация программы отыскания множества вершин, принадлежащих контуру заданной длины.
Тема 6. Представление графа. Вычисление компонент связности, двусвязности. Реализация программы нахождения стягивающего дерева связного графа (рекурсивный обход графа в глубину). Реализация программы нахождения стягивающего дерева связного графа с использованием нерекурсивного обхода графа в ширину.
Тема 7. Реализация программы поиска гамильтонова пути в связном неориентированном графе. Реализация программы нахождения всех клик в графе, заданном структурой Вирта.
Реализация программы последовательной раскраски вершин графа при помощи обхода графа в глубину. Реализация программы последовательной раскраски графа при помощи обхода графа в ширину. Реализация программы последовательной раскраски графа, представленного с помощью модифицированных списков смежности.
7. УЧЕБНО - МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ. ОЦЕНОЧНЫЕ СРЕДСТВА ДЛЯ ТЕКУЩЕГО КОНТРОЛЯ УСПЕВАЕМОСТИ, ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ПО ИТОГАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ (МОДУЛЯ).
Для самостоятельной работы студентов преподаватель раздает индивидуальные задания по заданной теме. При проверке задания с каждым студентов проводится собеседование, по результатам которого начисляются баллы за самостоятельную работу обучаемого.
Пример самостоятельной работы:
ВОПРОСЫ К ЗАЧЕТУ
Нелинейные структуры данных: классификация; деревья: ориентированные, упорядоченные и бинарные; представление деревьев в памяти компьютера: последовательное и связанное размещение элементов; операции над деревьями; графы и их представление в компьютере; алгоритмы, оперирующие со структурами типа графа; задачи поиска; исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое программирование; быстрый поиск: бинарный и последовательный поиски в массивах, хеширование; использование деревьев в задачах поиска: бинарные, случайные бинарные, оптимальные и сбалансированные деревья поиска; алгоритмы поиска на графах; задачи сортировки; внутренняя и внешняя сортировки; алгоритмы сортировки; анализ сложности и эффективности алгоритмов поиска и сортировки; файлы: организация и обработка, представление деревьями: B-деревья; теория сложности алгоритмов: NP-сложные и трудно решаемые задачи.8. ОБРАЗОВАТЕЛЬНЫЕ ТЕХНОЛОГИИ.
Активные формы: лекции, практические (лабораторные) занятия, контрольные работы. В течении семестра студенты выполняют предложенные задания, готовят сообщения. По каждой теме проводится контроль знаний.
Интерактивные формы: практическое решение ситуационных задач.
9. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ
9.1 Основная литература:
1. Балдин, Константин Васильевич. Математическое программирование: учебник / , , . - Москва: Дашков и К, 2010. - 220 с; 20 см. - Библиогр.: с. 199-202. - ISBN 978-5-91131-924-3 (в пер.).
2. Иванова, Галина Сергеевна. Программирование: учебник для студентов вузов, обучающихся по направлению 230100 "Информатика и вычислительная техника" / . - Москва: КНОРУС, 2013. - 432 с.; 21 см. - (Бакалавриат). - Библиогр. с. 426. - ISBN 978-5-406-02142-2 (в пер.): 464.31 р. ГРИФ: Рекомендовано УМО
3. Павловская, Татьяна Александровна. C#: программирование на языке высокого уровня: учебник / . - Санкт-Петербург: Питер, 2010. - 432 с: ил.; 24 см. - Библиогр.: с. 425-426. - Алф. указ.: с. 427-432. - ISBN 978-5-91180-174-8 (в пер.): 335.00 р. ГРИФ: Рекомендовано МО
4. Павловская, Татьяна Александровна. C/C ++: структурное и объектно-ориентированное программирование: практикум / . - Санкт-Петербург: Питер, 2010. - 352 с.: ил.; 24 см. - (Учебное пособие). - Библиогр.: с. 339-340. - Алф. указ: с. 341-347. - ISBN 978-5-49807-666-9: 245.00 р.
5. Приемы объектно-ориентированного проектирования: паттерны проектирования: перевод с английского = Design Patterns: Elements of Reusable Object-Oriented Software / Э. Гамма [и др.]. - Санкт-Петербург: Питер, 2013. - 368 с.: ил. ; 24 см. - (Библиотека программиста). - Библиогр.: с. 353-358. - Алф. указ.: с. 359-366. - ISBN 978-5-459-01720-5.
6. Чиртик, Александр Анатольевич. Программирование на C++: трюки и эффекты / . - Санкт-Петербург: Питер, 2010. - 352 с.: ил.; 24 см + 1 эл. опт. диск (CD-ROM). - ISBN 978-5-49807-102-2.
9.2 Дополнительная литература:
1. , Графы и алгоритмы. Структуры данных. Модели вычислений. Гриф УМО РФ,- Интуит, 2009.
2. , Организация структур данных и решение задач на С++, - Эком, 2009.
3. . Теория алгоритмов. Гриф УМО МО РФ, - Бином. Лаборатория знаний, 2008.
4. К. Касперски, Техника оптимизации программ. Эффективное использование памяти. БХВ, 2005.
5. , C/C++ в задачах и примерах, 2-е издание,- БХВ, 2009.
6. Структуры и алгоритмы обработки данных. Примеры на языке С. - Финансы и статистика, 2004.
7. , Евстигнеев в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.
8. , Технологии организации, хранения и обработки данных. Учебное пособие, - Инфра-М, 2001.
9. Кнут программирования, тт.1-3. - Вильямс, 2000.
9.3 Программное обеспечение: Компьютерный класс.
10. ТЕХНИЧЕСКИЕ СРЕДСТВА И МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ).
1. Аудитории для лекций и практических, (лабораторных занятий) оснащенные необходимым материальным оснащением.
2. Наличие рекомендованной литературы.
3. Наличие электронных версий методических материалов.
