ПРИМЕРНАЯ ПРОГРАММА
Наименование дисциплины
Структуры и алгоритмы компьютерной обработки данных
Рекомендуется для направления подготовки
010500 Математическое обеспечение и администрирование информационных систем
Квалификация выпускника: бакалавр
1. Цели и задачи дисциплины: изучение структур данных и алгоритмов их обработки, знакомство с фундаментальными принципами построения эффективных и надежных программ. Курс ориентирован на становление математика-программиста, должен способствовать повышению культуры мышления. Курс предназначен для овладения компьютерными методами обработки информации путем развития профессиональных навыков разработки, выбора и преобразования алгоритмов, что является важной составляющей эффективной реализации программного продукта.
2. Место дисциплины в структуре ООП:
Дисциплина относится к профессиональному циклу (Б.3).
Компетенции: ПК-2, ПК-3, ПК-7, ПК-8, ПК-9, ПК-10, ПК-11, ПК-36.
Студент должен знать:
основные этапы компьютерного решения задач;
понятие алгоритма и структуры управления; традиционные структуры данных;
основные требования методологии структурного программирования, как технологической основы разработки качественных программных компонентов;
понятие статических и динамических данных;
примеры базовых структур данных;
идеи, лежащие в основе процедурного программирования, реализацию вызова процедур в языках с блочной структурой, рекурсию;
идеи, лежащие в основе процедурного, модульного, объектно-ориентированного программирования;
математический аппарат, необходимый для оценивания времени выполнения алгоритма.
Студент должен уметь:
применять требования методологии структурного программирования при проектировании информационных моделей;
разрабатывать и записывать на языке высокого уровня алгоритмы решения классических задач программирования;
реализовывать технологию проектирования сверху-вниз;
выбирать оптимальную структуру для представления данных.
Студент должен владеть:
навыками практического программирования конкретных задач в определенной языковой среде;
применять средства структурного, модульного и объектно-ориентированного программирования для решения задач.
Данная дисциплина является предшествующей для следующих дисциплин:
базы данных и СУБД;
компьютерное моделирование;
компьютерная графика;
теория вычислительных процессов и структур;
технология разработки программного обеспечения;
исследование операций;
основы построения отказоустойчивых систем;
модели и методы принятия решений.
3. Требования к результатам освоения дисциплины:
Процесс изучения дисциплины направлен на формирование и расширение следующих компетенций:
ПК-2, ПК-3, ПК-7, ПК-8, ПК-9, ПК-10, ПК-11, ПК-36.
В результате изучения дисциплины студент должен:
Знать:
методы построения и использования сложных структур данных, нетрадиционные представления данных;
различные аспекты обработки этих структур данных;
иметь понятие о сложности алгоритмов и методах анализа сложности и эффективности;
способы представления стеков, очередей, деревьев в памяти ЭВМ;
методы сортировки (внутренней и внешней);
представления графов и алгоритмы на графах;
иметь представление о NP-сложных задачах;
основные задачи поиска и методы их решения:
различные методы разработки алгоритмов.
Уметь:
при решении конкретной задачи грамотно формулировать задачу программирования;
применять методы построения новых типов при проектировании информационных моделей;
выбирать оптимальную для данной информационной модели структуру данных;
для написания программы уметь выбирать в случае необходимости одно из известных решений;
анализировать трудоемкость метода сортировки данных;
выбрать оптимальный подход для решения задачи.
навыками использования сложных нетрадиционных структур данных для решения задач программирования;
навыками тестирования и верификации реализованной программы;
навыками использования классических алгоритмов и методов программирования.
навыками использования систематического и научного подхода к построению программ со сложными данными.
4. Объем дисциплины и виды учебной работы
Общая трудоемкость дисциплины составляет 3,5 зачетных единицы.
Вид учебной работы
|
Всего часов
|
Семестры
|
4
|
Аудиторные занятия (всего)
|
|
|
В том числе:
|
-
|
-
|
Лекции
|
51
|
51
|
Практические занятия (ПЗ)
|
17
|
17
|
Семинары (С)
|
0
|
0
|
Лабораторные работы (ЛР)
|
17
|
17
|
Самостоятельная работа (всего)
|
|
|
В том числе:
|
-
|
-
|
Курсовой проект (работа)
|
-
|
-
|
Расчетно-графические работы
|
-
|
-
|
Реферат
|
-
|
-
|
Другие виды самостоятельной работы
|
45
|
45
|
|
|
|
Вид промежуточной аттестации (зачет, экзамен)
|
|
Зачет,
Экзамен
|
Общая трудоемкость час
зач. ед.
|
130
|
130
|
3,5
|
3,5
|
5. Содержание дисциплины
5.1. Содержание разделов дисциплины
№ п/п
|
Наименование раздела дисциплины
|
Содержание раздела
|
1.
|
Алгоритмы поиска.
Хеширование
|
Последовательный поиск, двоичный поиск: анализ наихудшего и среднего случая.
Понятие функции расстановки, понятие конфликта (коллизии), методы разрешения конфликтов.
Анализ качества хэш-функций.
|
2.
|
Основные абстрактные типы данных: списки, стеки, очереди
|
Способы физического представления совокупности данных - сплошное и цепочное.
Стек: цепочная реализация и представление с помощью массива. Пакет процедур функциональной спецификации. Независимость основного алгоритма от способа реализации. Приложения стеков: анализ постфиксной записи выражений, реализация рекурсивных процедур и функций.
Очередь. Сплошное и цепочное представление очереди. Кольцевой буфер. Пакет процедур функциональной спецификации.
|
3.
|
Деревья
|
Двоичные деревья поиска: понятие, реализация на основе массива, цепочное представление, поиск, добавление и удаление элемента, способы обхода, построение, основные операции с деревом: рекурсивный и нерекурсивный варианты. Дерево-формула, способы записи выражений.
Идеально сбалансированные деревья. Алгоритмы поиска с использованием АВЛ-деревьев: определение АВЛ-дерева, включение в сбалансированное дерево, удаление элемента из сбалансированного дерева, обоснование выбора структуры данных для организации поиска.
Оптимальные деревья поиска.
Сильно ветвящиеся деревья (определение, обоснование использования, алгоритмы включения и удаления, организация поиска): В-деревья, В+ - деревья, Trie – деревья.
|
4.
|
Алгоритмы на графах
|
Основные понятия теории графов, структуры данных для представления графов, поиск в глубину и в ширину. Алгоритмы поиска минимального остовного дерева: Прима, Краскала. Поиск кратчайшего пути: алгоритм Дейкстры. Алгоритм определения компонентов двусвязности. Алгоритм минимальной раскраски вершин графа.
|
5.
|
Алгоритмы сортировки
|
Методы сортировок, их классификация.
Внутренние сортировки. Сортировки с помощью прямого включения, с двоичным включением, простым выбором, простым обменом (метод пузырька и шейкер-сортировка);
Улучшенные методы – Шелла, пирамидальная, быстрая. Нахождение медианы. Эффективность сортировок. Анализ и сравнительный анализ эффективности
Внешние сортировки. Сортировки слиянием: простым и естественным. Характеристики сортировок слиянием (однопутевое, многопутевое, однофазное, двухфазное, сбалансированное, несбалансированное). Улучшенные методы: многофазная и каскадная сортировки. Эффективность внешних сортировок.
|
6.
|
Недетерминированные алгориты
|
NP-сложные и труднорешаемые задачи. Типичные NP-задачи: раскраска графа, раскладка по ящикам, упаковка рюкзака, задача о сумме элементов подмножества.
|
7.
|
Методы разработки алгоритмов
|
Поиск с возвратом, «разделяй и властвуй», динамическое программирование, жадные приближенные алгоритмы, вероятностные алгоритмы.
|
5.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами
№ п/п
|
Наименование обеспе-чиваемых (последующих) дисциплин
|
№ № разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
1.
|
базы данных и СУБД;
|
+
|
|
+
|
|
+
|
|
|
2.
|
компьютерное моделирование;
|
+
|
+
|
+
|
+
|
+
|
+
|
+
|
3.
|
компьютерная графика;
|
+
|
+
|
+
|
+
|
+
|
|
+
|
4.
|
теория вычислительных процессов и структур;
|
+
|
+
|
+
|
+
|
+
|
+
|
+
|
5.
|
технология разработки программного обеспечения;
|
+
|
+
|
+
|
+
|
+
|
+
|
+
|
6.
|
исследование операций;
|
+
|
|
+
|
+
|
+
|
+
|
+
|
7.
|
основы построения отказоустойчивых систем;
|
+
|
|
+
|
|
|
|
|
8.
|
модели и методы принятия решений
|
+
|
+
|
+
|
+
|
+
|
+
|
+
|
5.3. Разделы дисциплин и виды занятий
№ п/п
|
Наименование раздела дисциплины
|
Лекц.
|
Практ.
зан.
|
Лаб.
зан.
|
Семин
|
СРС
|
Все-го
час.
|
1.
|
Алгоритмы поиска. Хеширование.
|
6
|
4
|
6
|
|
8
|
24
|
3.
|
Основные абстрактные типы данных: списки, стеки, очереди
|
6
|
4
|
4
|
|
4
|
18
|
4.
|
Деревья
|
10
|
6
|
4
|
|
8
|
28
|
5.
|
Алгоритмы на графах
|
6
|
4
|
4
|
|
5
|
19
|
6.
|
Алгоритмы сортировки
|
8
|
8
|
8
|
|
8
|
32
|
7.
|
Недетерминированные алгоритмы
|
4
|
2
|
4
|
|
4
|
14
|
8.
|
Методы разработки алгоритмов
|
11
|
6
|
4
|
|
8
|
29
|
6. Лабораторный практикум
№ п/п
|
№ раздела дисциплины
|
Наименование лабораторных работ
|
Трудо-емкость
(час.)
|
1.
|
1
|
Задача на тему «Хеширование»
|
4
|
2.
|
2
|
Задача на тему «Стеки» или «Очереди»
|
4
|
3.
|
3
|
Задача на тему «Бинарные деревья, упорядоченные бинарные деревья» или на тему «Дерево-формула».
Задача на тему «Trie-деревья».
|
6
|
4.
|
4
|
Задача на тему «Алгоритмы на графах»
|
4
|
5.
|
5
|
Задача на тему «Внутренние сортировки»
|
8
|
6.
|
6
|
Решение NP-сложной задачи с применением алгоритма с возвратом.
|
2
|
7.
|
7
|
Решение NP-сложной задачи с использованием либо динамического программирования, либо жадного приближенного алгоритма или при помощи вероятностных алгоритмов.
|
6
|
7. Практические занятия (семинары)
№ п/п
|
№ раздела дисциплины
|
Тематика практических занятий (семинаров)
|
Трудо-емкость
(час.)
|
1.
|
1
|
Структуры данных для представления хеш-таблиц с разными способами разрешения коллизий (внутренние цепочки, внешние цепочки, линейно и квадратичное опробование, двойное хеширование). Реализация функций добавления, удаления и поиска данных для различных способов разрешения коллизий.
Решение задач с использованием хеширования.
|
4
|
2.
|
2
|
Решение задач на тему «Стеки».
Решение задач на тему «Очереди».
|
4
|
3.
|
3
|
Решение задач на темы «Двоичные деревья», «Дерево-формула».
Выполнение упражнений на включение, исключение элементов для АВЛ-деревьев, B-деревьев, B+-деревьев.
Решение задач на тему «Trie-деревья».
|
6
|
4.
|
4
|
Реализация основных алгоритмов для различных способов представления графов.
Проблемы визуализации графов и их решения..
|
4
|
5.
|
5
|
Структуры данных и реализация методов для визуализации процесса внутренней сортировки. Построение графиков зависимости количества операций сравнения и перемещения от количества элементов в массиве.
Другие алгоритмы внешних сортировок: сортировка подсчетом, распределяющий подсчет, двухпутевые вставки, вставки в список с вычислением адреса, обменная поразрядная сортировка, параллельная сортировка Бэтчера.
Структуры данных, предназначенные для реализации внешних сортировок. Реализация простых и улучшенных методов внешних сортировок.
|
8
|
6.
|
6
|
Алгоритмы и реализация решений некоторых NP-сложных задач с применением алгоритмов с возвратом.
|
2
|
7.
|
7
|
Применение динамического программирования для решения NP-сложных задач.
Решение NP-сложных задач с применением жадных алгоритмов.
Решение NP-сложных задач с применением вероятностных алгоритмов.
|
6
|
8. Примерная тематика курсовых проектов (работ): нет
9. Учебно-методическое и информационное обеспечение дисциплины:
а) основная литература:
Вирт Н. Алгоритмы и структуры данных. / Н. Вирт ; пер. с англ. Д.Б. Подшиваловой. – 2-е изд., испр. – Спб.: Невский диалект, 2001. – 352 с.
Ахо А.. Структуры данных и алгоритмы / А.Ахо, В. Хопкрофт, Д. Ульман : пер. с англ. – М.: Вильямс, 2003. – 384 с.
Кнут Д. Э. Искусство программирования. / Д.Э. Кнут; пер. с англ. и ред. В.Т. Тертышного, И.В. Красикова; под общ. ред. Ю.В. Козаченко. – М.; СПб ; Киев : Вильямс, 2000. – Т. 3 : Сортировка и поиск. – 822 с.
Программирование алгоритмов обработки данных / О.Ф. Ускова, Н.В. Огаркова, И.Е. Воронина, М.В. Бакланов, В.М. Мельников. – СПб: БХВ - Петербург, 2003. – 192 с.
Макконнелл Дж. Анализ алгоритмов. Вводный курс / Дж. Макконнелл: ; пер. с англ . –М.: Техносфера, 2002. - 304 с.
б) дополнительная литература:
Сибуя М. Алгоритмы обработки данных:. / М. Сибуя, Т. Ямамото : пер. с япон. – М.: Мир, 1986. – 218 с.
Мейер Б. Методы программирования: В 2-х томах. / Б. Мейер., К. Бодуэн – М.: Мир, 1982.
Кормен Т. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Лейзерсон Ч., Р. Ривест : пер.с англ., под ред. А.Шеня. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд. стереотип. – 960 с.
Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. / А.А. Кубенский – СПб.: БХВ-Петербург, 2004. – 464 с.
в) программное обеспечение: в аудиториях для проведения лабораторных занятий, должно быть установлено программное обеспечение, предназначенное для разработки приложений на языках высокого уровня.
10. Материально-техническое обеспечение дисциплины:
Требования к аудиториям для проведения лекционных и практических занятий: наличие доски и средств письма на ней, оснащение проекционной техникой и компьютером.
Требования к аудиторному оборудованию для проведения лабораторных занятий: наличие компьютерных классов с современной компьютерной техникой.
11. Методические рекомендации по организации изучения дисциплины:
Методическое обеспечение аудиторной работы: учебно-методические пособия для студентов, учебники и учебные пособия, электронные и Интернет-ресурсы.
Методическое обеспечение самостоятельной работы: учебно-методические пособия по организации самостоятельной работы, контрольные задания и тесты в бумажном и электронном вариантах, тестирующие системы, дистанционные формы общения с преподавателем. Контроль самостоятельной работы реализуется с помощью опросов, тестов, вопросов по темам заданий и т.д.
Пример вопросов контроля самостоятельной работы:
Стек: цепочная реализация и представление с помощью массива. Пакет процедур функциональной спецификации.
Способы обхода, построение, основные операции с бинарным деревом: рекурсивный и нерекурсивный варианты
В+ - деревья; определение, обоснование использования, алгоритмы включения и удаления.
Алгоритмы с возвратом. Функциональное назначение алгоритмов, примеры задач с использованием алгоритмов с возвратом обобщение схемы алгоритма методом проб и ошибок.
Контрольно-измерительные материалы: задания, тесты, контрольные работы, теоретические вопросы и выполнение практических заданий.
Допуск к экзамену осуществляется на основании получения зачета по дисциплине.
ТРЕБОВАНИЯ:
зачтено
|
Выполнены все лабораторные работы из лабораторного практикума. Выполнены запланированные контрольные работы с положительным результатом. Студент отчитался по итогам самостоятельной работы (например, успешно ответил на вопросы)
|
не зачтено
|
Не выполнен хотя бы один из пунктов, указанных выше
|
Примеры экзаменационных контрольно-измерительных материалов:
Вопрос
|
Бинарное дерево поиска. Реализация с помощью массива.
|
Задача
|
Подсчитать количество узлов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).
|
Вопрос.
|
Сортировки слиянием: простым и естественным.
|
Задача.
|
Проиллюстрировать сортировку двухпутевым однофазным простым слиянием на примере следующих чисел: 7, 2, 13, 23, 2, 1, 35, 88, 2, 25, 42.
|
Вопрос.
|
Trie - деревья.
|
Задача.
|
Удалить из Trie - дерева все слова, в которые входит заданная буква.
|
Вопрос.
|
Хеширование: понятие функции расстановки, понятие коллизии
|
Задача.
|
Удалить следующие элементы из B-дерева: 45, 16, 106, 3, 73.
|
Вопрос.
|
Пирамидальная сортировка
|
Задача.
|
Задан файл записей. У каждой записи ключевое поле представляет собой код из 4 цифр и 2 латинских букв (малых). Напишите хеш-функцию и реализуйте удаление элемента из хеш-таблицы, с применением метода разрешения коллизий – двойное хеширование.
|
Вопрос.
|
В+ - деревья: определение, обоснование использования, алгоритм включения элемента
|
Задача.
|
Построить АВЛ-дерево из следующих элементов: 17, 24, 9, 3, 5, 22, 11, 30, 40
|
КРИТЕРИИ ОЦЕНОК
отлично
|
Отличное знание теоретического материала, правильное и эффективное решение задачи
|
хорошо
|
Хорошее знание теоретического материала, правильное решение задачи
|
удовлетворительно
|
Решение задачи не доведено до конца или продемонстрировано недостаточное знание теоретического материала.
|
неудовлетворительно
|
Задача не решена или серьезные пробелы в знании теоретического материала
|
Разработчики:
Воронежский государственный университет, факультет прикладной математики, информатики и механики, кафедра программного обеспечения и администрирования информационных систем
|
кандидат технических наук, доцент
|
И.Е. Воронина
|
Воронежский государственный университет, факультет прикладной математики, информатики и механики, кафедра программного обеспечения и администрирования информационных систем
|
преподаватель
|
Н.В. Огаркова
|
Эксперты:
Воронежский государственный университет, факультет прикладной математики, информатики и механики, декан
|
д.ф.-м. н., профессор
|
А.И. Шашкин
|
|
Воронежский государственный университет, факультет прикладной математики, информатики и механики,
зав. каф. вычислительной математики и прикладных информационных технологий, председатель научно-методического совета факультета ПММ
|
д.т. н., профессор
|
Т.М. Леденева
|
| |
