Geum.ru

Примерная программа наименование дисциплины Структуры и алгоритмы компьютерной обработки данных Рекомендуется для направления подготовки

Вид материалаПримерная программа

Содержание


2. Место дисциплины в структуре ООП
3. Требования к результатам освоения дисциплины
4. Объем дисциплины и виды учебной работы
Аудиторные занятия (всего)
Самостоятельная работа (всего)
Другие виды самостоятельной работы
5. Содержание дисциплины
5.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами
5.3. Разделы дисциплин и виды занятий
6. Лабораторный практикум
7. Практические занятия (семинары)
8. Примерная тематика курсовых проектов (работ)
10. Материально-техническое обеспечение дисциплины
11. Методические рекомендации по организации изучения дисциплины
Методическое обеспечение самостоятельной работы
Контрольно-измерительные материалы
Критерии оценок
Подобный материал:


ПРИМЕРНАЯ ПРОГРАММА


Наименование дисциплины

Структуры и алгоритмы компьютерной обработки данных


Рекомендуется для направления подготовки

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. Учебно-методическое и информационное обеспечение дисциплины:

а) основная литература:

  1. Вирт Н. Алгоритмы и структуры данных. / Н. Вирт ; пер. с англ. Д.Б. Подшиваловой. – 2-е изд., испр. – Спб.: Невский диалект, 2001. – 352 с.
  2. Ахо А.. Структуры данных и алгоритмы / А.Ахо, В. Хопкрофт, Д. Ульман : пер. с англ.  – М.: Вильямс, 2003. – 384 с.
  3. Кнут Д. Э. Искусство программирования. / Д.Э. Кнут; пер. с англ. и ред. В.Т. Тертышного, И.В. Красикова; под общ. ред. Ю.В. Козаченко. – М.; СПб ; Киев : Вильямс, 2000. – Т. 3 : Сортировка и поиск. – 822 с.
  4. Программирование алгоритмов обработки данных / О.Ф. Ускова, Н.В. Огаркова, И.Е. Воронина, М.В. Бакланов, В.М. Мельников. – СПб: БХВ - Петербург, 2003. – 192 с.
  5. Макконнелл Дж. Анализ алгоритмов. Вводный курс / Дж. Макконнелл: ; пер. с англ . –М.: Техносфера, 2002. - 304 с.


б) дополнительная литература:

  1. Сибуя М. Алгоритмы обработки данных:. / М. Сибуя, Т. Ямамото : пер. с япон. – М.: Мир, 1986. – 218 с.
  2. Мейер Б. Методы программирования: В 2-х томах. / Б. Мейер., К. Бодуэн – М.: Мир, 1982.
  3. Кормен Т. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Лейзерсон Ч., Р. Ривест : пер.с англ., под ред. А.Шеня. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд. стереотип. – 960 с.
  4. Кубенский А.А. Структуры и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. / А.А. Кубенский – СПб.: БХВ-Петербург, 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



КРИТЕРИИ ОЦЕНОК

отлично
Отличное знание теоретического материала, правильное и эффективное решение задачи

хорошо
Хорошее знание теоретического материала, правильное решение задачи

удовлетворительно
Решение задачи не доведено до конца или продемонстрировано недостаточное знание теоретического материала.

неудовлетворительно
Задача не решена или серьезные пробелы в знании теоретического материала


Разработчики:

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

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


Эксперты:

Воронежский государственный университет, факультет прикладной математики, информатики и механики, декан
д.ф.-м. н., профессор
А.И. Шашкин



Воронежский государственный университет, факультет прикладной математики, информатики и механики,

зав. каф. вычислительной математики и прикладных информационных технологий, председатель научно-методического совета факультета ПММ

д.т. н., профессор
Т.М. Леденева