Алгоритмы и структуры данных

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

филиал федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Тюменский государственный университет»

в г. Тобольске

Естественнонаучный факультет

Кафедра информатики, методики обучения

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

Учебно-методический комплекс

Код и направление подготовки

050100.62 – «Педагогическое образование»

Профиль подготовки

«Информатика»

Квалификация (степень) выпускника

Бакалавр

Очная форма обучения

Заочная форма обучения

Тобольск 2014

1. Цели и задачи освоения дисциплины

Цель освоения дисциплины по выбору: формирование и закрепление знаний и умений по использованию фундаментальных алгоритмов и структур данных.

2. Место дисциплины в структуре ОП ВПО

Дисциплина по выбору «Алгоритмы и структуры данных» относится к вариативной части Профессионального цикла.

Для освоения дисциплины по выбору «Алгоритмы и структуры данных» студенты используют знания, умения, навыки, способы деятельности и установки, полученные и сформированные в ходе изучения школьного курса информатики, дисциплины «Информационные технологии».

Изучение дисциплины по выбору способствует успешному выполнению курсовых и дипломных работ.

3. Требования к результатам освоения содержания дисциплины

Процесс изучения дисциплины направлен на формирование следующих компетенций:

-  способен использовать знания о современной естественнонаучной картине мира в образовательной и профессиональной деятельности, применять методы математической обработки информации, теоретического и экспериментального исследования (ОК-4)

-  владеет основами речевой профессиональной культуры (ОПК-3).

В результате изучения дисциплины студент должен

знать:

-  структуры данных, используемые для представления типовых информационных объектов;

-  основные алгоритмы и характеристики их сложности для типовых задач, часто встречающихся и ставших «классическими» в области информатики и программирования;

уметь:

-  разрабатывать алгоритмы, используя изложенные в курсе общие схемы, методы и приемы построения алгоритмов, выбирая подходящие структуры данных для представления информационных объектов;

-  доказывать корректность составленного алгоритма и оценивать основные характеристики его сложности;

-  экспериментально (с помощью компьютера) исследовать эффективность алгоритма и программы;

владеть:

-  навыками реализации алгоритмов и используемых структур данных средствами языков программирования высокого уровня;

4. Содержание и структура дисциплины

4.1. Структура и трудоемкость дисциплины

Общая трудоемкость дисциплины составляет 6 зачетных единиц (216 часов)

Очная форма обучения

Вид работы	Трудоемкость, часов
3 семестр	4 семестр	Всего
Общая трудоемкость	78	138	216
Аудиторная работа:	54	54	108
Практические занятия (ПЗ)	54	54	108
Самостоятельная работа:	24	84	108
Самостоятельное изучение разделов	12	24	36
Самоподготовка (проработка и повторение теоретического материала и материала учебников и учебных пособий, выполнение домашних заданий и т. д.),	12	60	72
Подготовка и сдача экзамена
Вид итогового контроля (зачет, экзамен)	КР	зачет с оценкой

Заочная форма обучения

Вид работы	Трудоемкость, часов
4 семестр	5 семестр	Всего
Общая трудоемкость	36	180	216
Аудиторная работа:	10	10	20
Практические занятия (ПЗ)	10	10	20
КСР	2	2	4
Самостоятельная работа:	24	164	188
Самостоятельное изучение разделов	12	64	76
Самоподготовка (проработка и повторение теоретического материала и материала учебников и учебных пособий, выполнение домашних заданий и т. д.),	12	100	112
Подготовка и сдача экзамена
Вид итогового контроля (зачет, экзамен)	КР	зачет с оценкой

4.2. Содержание разделов дисциплины

№ раздела	Наименование раздела	Содержание раздела	Форма текущего контроля
1	2	3	4
1.	Линейные структуры данных	Понятие типа данного. Структуры данных. Классификация структур данных. Стек, очередь и дек как абстрактные типы данных: функциональные спецификации и аксиомы. Стек, очередь и дек как линейные списки с ограниченными наборами операций. Представление и реализация (непрерывная, ссылочная в связанной памяти и на базе вектора). Примеры алгоритмов, использующих стек, очередь, дек.	ДЗ, КР
2.	Нелинейные структуры. Деревья.	Иерархические списки. Деревья. Ориентированные. Упорядоченные. Бинарные. Сбалансированные. Сильноветвящиеся. Представление деревьев в памяти ЭВМ. Последовательное и связанное размещение элементов. Операции над деревьями. Обход дерева, упорядочивание, поиск, включение/ удаление вершины.	ДЗ, КР
3.	Задачи поиска	Исчерпывающий поиск: поиск с возвращением, метод ветвей и границ, динамическое программирование. Быстрый поиск: последовательный и бинарный поиск. Выбор в линейных списках. Использование деревьев в задачах поиска: бинарные, случайные бинарные, оптимальные и сбалансированные деревья поиска. Задача поиска подстроки. Алгоритм Кнута-Мориса-Пратта.	ДЗ, КР
4.	Задачи сортировки	Внутренняя и внешняя сортировки. Алгоритмы сортировки: сортировка обменом, сортировка вставкой, сортировка посредством выбора, слияние списков, сортировка списков путем слияния, быстрая и поразрядная сортировки. Пирамидальная сортировка. Внешняя сортировка Простое слияние. Естественное слияние. Анализ сложности и эффективности алгоритмов поиска и сортировки.	ДЗ
5.	Алгоритмы на графах	Представления графов: матрица смежности, матрица инцидентности, списки смежности, списки дуг. Алгоритмы поиска в глубину и ширину. Остовные деревья графа. Кратчайшие пути в графе. Потоки в сетях. Поиск максимального потока. Алгоритм Форда-Фалкерсона.	ДЗ
6.	Комбинаторные алгоритмы	Комбинаторика. Комбинаторные структуры. Перестановки. Сочетания. Генерация объекта по номеру и номера по объекту. Размещения с повторениями. Подмножества.	ДЗ
7.	Теория сложности алгоритмов	NP-сложные и труднорешаемые задачи. Алгоритмы для NP-сложных задач.	Устный опрос

Разделы дисциплины, изучаемые в 3 семестре

№ раз- дела	Наименование разделов	Количество часов
Всего	Аудиторная работа	Внеауд. работа СР
ПЗ
1	2	3	4	5
1	Линейные структуры данных	22	14	8
2	Нелинейные структуры. Деревья.	18	12	6
3	Задачи поиска	38	28	10
	Итого:	78	54	24

Разделы дисциплины, изучаемые во 4 семестре

№ раз- дела	Наименование разделов	Количество часов
Всего	Аудиторная работа	Внеауд. работа СР
ПЗ
1	2	3	4	5
4	Задачи сортировки	46	18	28
5	Алгоритмы на графах	42	16	26
6	Комбинаторные алгоритмы	40	16	24
7	Теория сложности алгоритмов	10	4	6
	Итого:	138	54	84

4.3. Лабораторные работы не предусмотрены

4.4. Практические занятия (семинары)

№ ПЗ	№ раздела	Наименование практических занятий	Кол-во часов
1	2	3	4
1	1	Тип данных. Структуры данных. Классификация	2
2	1	Односвязные и двусвязные линейные списки. Представления и реализация.	2
3	1	Односвязные и двусвязные линейные списки. Основные операции.	2
4	1	Абстрактные типы. Стек, очередь, дек.	2
5	1	Стек, очередь, дек. Реализация на основе линейных списков	2
6	1	Примеры алгоритмов, использующих стек, очередь, дек.	4
7	2	Иерархические списки. Рекурсивная обработка.	2
8	2	Деревья. Основные понятия и определения	2
9	2	Деревья. Представления и реализация.	2
10	2	Деревья. Операции над деревьями.	4
11	2	Примеры использования бинарных деревьев	2
12	3	Поиск с возвращением. Общий алгоритм. Пример.	4
13	3	Метод ветвей и границ. Общая схема. Задача коммивояжера.	4
14	3	Динамическое программирование. Пример и общая идея.	2
15	3	Одномерное динамическое программирование. Задача о банкомате.	2
16	3	Двумерное динамическое программирование. Задача о рюкзаке	2
17	3	Последовательный и бинарный поиск.	4
18	3	Бинарные деревья поиска. Случайные бинарные деревья поиска.	4
19	3	Оптимальные и сбалансированные деревья поиска	4
20	3	Задача поиска подстроки. Алгоритм Кнута-Мориса-Пратта.	2
21	4	Квадратичные сортировки (обменом, вставкой, выбором).	4
22	4	Быстрая сортировка	2
23	4	Поразрядная сортировка	2
24	4	Слияние списков. Сортировка слиянием.	4
25	4	Пирамида (куча). Пирамидальная сортировка	2
26	4	Файлы. Внешняя сортировка Простое слияние.	2
27	4	Внешняя сортировка Естественное слияние.	2
28	5	Графы. Основные понятия и определения. Представление графов	2
29	5	Алгоритм поиска в глубину	2
30	5	Алгоритм поиска в ширину	2
31	5	Остовные деревья. Минимальное оставное дерево. Алгоритмы Краскала и Прима	4
32	5	Кратчайшие пути от фиксированной вершины. Алгоритм Дейкстры. Алгоритм Форда-Беллмана.	4
33	5	Поиск максимального потока. Алгоритм Форда-Фалкерсона.	2
34	6	Комбинаторные структуры. Общие алгоритмы	4
35	6	Перестановки. Сочетания	4
36	6	Генерация объекта по номеру и номера по объекту.	4
37	6	Размещения с повторениями. Подмножества.	4
38	7	NP-сложные и труднорешаемые задачи. Алгоритмы для NP-сложных задач.	4

4.5. Курсовой проект (курсовая работа) не предусмотрен

4.6. Самостоятельное изучение разделов дисциплины

№ раздела	Вопросы, выносимые на самостоятельное изучение	Кол-во часов
1	2	3
1	Изучение специальной учебной литературы.	2
1	Выполнение домашнего задания по теме «Односвязные и двусвязные линейные списки»	2
1	Выполнение домашнего задания по теме «Стек, очередь, дек»	2
2	Выполнение домашнего задания по теме «Деревья»	2
3	Изучение специальной учебной литературы.	2
3	Выполнение домашнего задания по теме «Поиск с возвращением»	2
3	Выполнение домашнего задания по теме «Метод ветвей и границ»	2
3	Выполнение домашнего задания по теме «Динамическое программирование»	2
3	Выполнение домашнего задания по теме «Последовательный и бинарный поиск»	2
3	Выполнение домашнего задания по теме «Бинарные деревья поиска»	2
3	Выполнение домашнего задания по теме «Задача поиска подстроки»	2
3	Подготовка к контрольной работе	2
4	Изучение специальной учебной литературы.	6
4	Выполнение домашнего задания по теме «Квадратичные сортировки»	4
4	Выполнение домашнего задания по теме «Быстрая и поразрядная сортировки»	4
4	Выполнение домашнего задания по теме «Сортировка слиянием»	2
4	Выполнение домашнего задания по теме «Пирамидальная сортировка»	2
4	Выполнение домашнего задания по теме «Внешняя сортировка»	4
5	Изучение специальной учебной литературы.	6
5	Выполнение домашнего задания по теме «Графы. Алгоритмы поиска»	4
5	Выполнение домашнего задания по теме «Остовные деревья»	4
5	Выполнение домашнего задания по теме «Графы. Кратчайшие пути»	4
5	Выполнение домашнего задания по теме «Поиск максимального потока»	2
6	Изучение специальной учебной литературы.	6
6	Выполнение домашнего задания по теме «Комбинаторные структуры. Общие алгоритмы»	4
6	Выполнение домашнего задания по теме «Перестановки. Сочетания»	4
6	Выполнение домашнего задания по теме «Генерация объекта по номеру и номера по объекту»	4
6	Выполнение домашнего задания по теме «Размещения с повторениями. Подмножества»	4
6	Подготовка к зачету	14
7	Составить конспект по теме «Теория сложности алгоритмов»	6

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

В ходе освоения дисциплины при проведении аудиторных занятий используются следующие образовательные технологии: практические занятия, с использованием активных и интерактивных форм проведения занятий.

5.1. Интерактивные образовательные технологии, используемые в аудиторных занятиях

Семестр	Вид занятия	Используемые интерактивные образовательные технологии	Количество часов
3	ПЗ	Проектирование, дискуссии, мозговой штурм	18
4	ПЗ	Проектирование, дискуссии, мозговой штурм	18
Итого:	36

6. Оценочные средства для текущего контроля успеваемости и промежуточной аттестации

6.1. Вопросы к зачету по дисциплине

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.  Размещения с повторениями. Подмножества.

6.2. Образцы заданий к контрольной работе

Задание 1

Реализуйте структуру данных «очередь». Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop Удалить из очереди первый элемент. Программа должна вывести его значение.

front Программа должна вывести значение первого элемента, не удаляя его из очереди.

size Программа должна вывести количество элементов в очереди.

clear Программа должна очистить очередь и вывести ok.

exit Программа должна вывести bye и завершить работу.

Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

Задание 2

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

Формат входных данных

На вход программы поступают три натуральных числа N, x и y, разделенные пробелом (1 ≤ N ≤ 2∙108, 1 ≤ x, y ≤ 10).

Формат выходных данных

Выведите одно число – минимальное время в секундах, необходимое для получения N копий.

Примеры

Входные данные	Выходные данные
4 1 1	3
5 1 2	4

Задание 3

На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.

Формат входных данных

В первой строке входных данных содержатся два числа: N и M (1 <= N,M <= 100), где N – количество ОВП, а M – количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.

Формат выходных данных

Если способ рассадить ОВП существует, то  выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

Пример

Входные данные	Выходные данные
3 2 1 2 1 3	YES 2 3

7. Учебно-методическое обеспечение дисциплины

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

1.  Микрюков и программирование: учеб. пособие / . – Ростов н/Д: Феникс, 2007. – 304с.

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

1.  Алексеев и алгоритмы. Структуры данных. Модели вычислений: учебник.- М.: ИНТУИТ, 2006.

2.  Ахо Хопкрофт Джон, Ульман Структуры данных и алгоритмы: Пер. с англ.: Уч. пос.- М.: Издательский дом “Вильямс”, 2000. – 384 с.

3.  Алгоритмы и структуры данных.: - Санкт-Петербург: «Невский диалект», 2001. – 360 с.

4.  Окулов в алгоритмах. – 2-е изд., доп. – М.: БИНОМ. Лаборатория знаний, 2006 . – 384 с.

5.  и др. Программирование алгоритмов обработки данных: Учебное пособие. – СПб: БХВ-Петербург, 2003. – 188 с.

7.3. Периодические издания.

1.  Журналы: Информатика и образование.

7.4. Интернет-ресурсы

1.  Алгоритмы, методы, исходники – http://algolist. manual. ru/

2.  Алгоритмы. Инфо – http://algoritmy. info/

3.  Википедия – http://ru. wikipedia. org

4.  Дистанционная подготовка по информатике – http://informatics. mccme. ru/moodle/

5.  FreePascal. ru - Информационный портал для разработчиков на Free Pascal & Lazarus – http://www. freepascal. ru/

7.5. Методические указания к лабораторным занятиям не предусмотрены

7.6. Методические указания к практическим занятиям.

Практические занятия нацелены на закрепление теоретических знаний, приобретение студентами навыков работы в соответствующих программных инструментах и получение практического опыта проектирования алгоритмов и разработки приложений.

7.7. Методические указания к курсовому проектированию не предусмотрен.

7.8. Программное обеспечение дисциплины

1.  Операционные системы Windows 2000/ XP, Ubuntu.

2.  Трансляторы языков высокого уровня: Free Pascal 2.4 и выше.

3.  Microsoft Office.

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

1.  Сетевой компьютерный класс с выходом в Интернет. 

2.  Учебный сервер кафедры.