Рабочая программа дисциплины Структуры и алгоритмы обработки данных (Наименование дисциплины)
| Вид материала | Рабочая программа |
- Рабочая программа дисциплины Структуры и алгоритмы обработки данных (Наименование дисциплины), 185.25kb.
- Рабочая программа дисциплины Структуры и алгоритмы компьютерной обработки данных (Наименование, 153.24kb.
- Примерная программа наименование дисциплины Структуры и алгоритмы компьютерной обработки, 215.14kb.
- Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
- Программа дисциплины структуры и алгоритмы компьютерной обработки данных для специальности, 506.16kb.
- Программа дисциплины «Структуры данных», 88.1kb.
- Программа дисциплины Базы данных Семестры, 12.06kb.
- Программа курса Алгоритмы программирования, 47.59kb.
- Рабочая программа дисциплины "Алгоритмы и средства цифровой обработки сигналов" для, 61.24kb.
- Цель любой программы обработка данных, т е. надо грамотно построить структуры данных, 165.23kb.
МИНОБРНАУКИ РОССИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ В Г. ТАГАНРОГЕ
(ТТИ Южного федерального университета)
Факультет автоматики и вычислительной техники
УТВЕРЖДАЮ
Декан ФАВТ ______________ Ю.М.Вишняков
"_____"__________________2011 г.
Рабочая программа дисциплины
Структуры и алгоритмы обработки данных
(Наименование дисциплины)
Направление подготовки
^ 220400.62 «Управление в технических системах»
Профиль подготовки
Управление и информатика в технических системах
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
(очная, очно-заочная и др.)
г. Таганрог
2011
^ 1. Цели освоения дисциплины
Целью освоения дисциплины «Структуры и алгоритмы обработки данных» является изучение применяемых в программировании (и информатике) структур данных, их спецификации и реализации в различных классах задач, алгоритмов обработки данных, анализ этих алгоритмов, прикладное применение алгоритмов, взаимосвязь алгоритмов и структур, изучение различных форм организации данных в программах и методов их обработки. Применение СУБД в алгоритмизации и структуризации данных.
Изучение данной дисциплины будет способствовать достижению целей 2 и 3 основной образовательной программы по направлению подготовки 220400.62 «Управление в технических системах»:
^ Цель направления 2. Организация базовой бакалаврской подготовки, позволяющей всем выпускникам продолжить свое образование как с целью получения диплома инженера или магистра в области автоматизации и управления, так и с целью дальнейшего самосовершенствования;
^ Цель направления 3. Удовлетворение потребностей общества в квалифицированных кадрах путем подготовки специалистов по проектированию, разработке и эксплуатации автоматизированных систем и средств контроля и управления,
а также будет способствовать достижению локальной цели профиля подготовки «Управление и информатика в технических системах»:
^ Цель 1 профиля. Развитие у студентов теоретических знаний и практических навыков, позволяющих выпускникам понимать и применять фундаментальные и передовые знания и научные принципы, лежащие в основе современных средств и систем автоматизации и управления при формулировании и решении инженерных задач;
^ 2. Место дисциплины в структуре ООП по направлению подготовки 220400.62 «Управление в технических системах».
Дисциплина «Структуры и алгоритмы обработки данных» относится к дисциплинам по выбору. В процессе изучения дисциплины студенты знакомятся с основными тенденциями в создании структур данных, методах оптимального использования памяти и времени для обработки данных и управления процессами обработки данных; используют различные (динамические и статистические ) структуры данных в соответствии с запросами алгоритмов; получают опыт в математических методах анализа алгоритмов; получают навыки классификации алгоритмических задач по сложности, сводимости алгоритмических задач к известным задачам определенного класса.
Дисциплина базируется на понятиях, изучаемых в дисциплинах: «Математика», «Основы информатики», «Программирование и основы алгоритмизации», «Дискретная математика». Для освоения дисциплины студенту необходимо владеть основами применения языков программирования высокого уровня, владеть технологией применения различных систем счисления, иметь представление о типах данных, используемых в прикладном программировании.
Материалы дисциплины используются при изучении дисциплин профессионального цикла, при выполнении курсовых работ и проектов, а также выпускной квалификационной работы.
^ 3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Структуры и алгоритмы обработки данных»:
Выпускник должен обладать следующими профессиональными компетенциями:
– способностью владеть основными приемами обработки и представления экспериментальных данных (ПК-5);
– способностью разрабатывать информационное обеспечение систем с использованием стандартных СУБД (ПК-11);
В результате освоения дисциплины обучающийся должен:
- Знать: Основные методы разработки машинных алгоритмов и программ, структуры данных, используемые для представления типовых информационных объектов; Основные машинные алгоритмы и характеристики их сложности для типовых задач; Списковые и древообразные структуры; Основные алгоритмы шифрования и дешифрования данных; Основы сжатия данных; Методы поиска; Критерии определения эффективности поиска и сортировки.
- Уметь: Использовать оптимальные методы поиска и сортировки данных; Создавать и использовать абстрактные типы данных, экспериментально (с помощью компьютера) исследовать эффективность алгоритма и программы; Индексировать данные; Хэшировать данные.
- Владеть: Разработкой алгоритмов, используя общие схемы, методы и приемы построения алгоритмов; Технологией представления разнородных данных в виде алгоритмических структур.
- Демонстрировать способность и готовность: Анализировать существующие структуры данных на предмет оптимальности применения в конкретной задаче.
^ 4. Структура и содержание дисциплины «Структуры и алгоритмы обработки данных».
Общая трудоемкость дисциплины составляет 4 зачетных единицы, 144 часа
| Вид учебной работы | Всего часов |
| Общая трудоемкость дисциплины | 144/4 ЗЕТ |
| Аудиторные занятия | 36 |
| - лекции | 18 |
| - практические занятия | |
| - лабораторные работы | 18 |
| - другие виды аудиторных занятий | |
| Самостоятельная работа | 58 |
| Курсовой проект (работа) | |
| Контроль самостоятельной работы | 18 |
| Аттестация | 34 Экзамен (3 семестр) |
^ 4.1. Разделы дисциплины и виды занятий
| № п/п | Раздел Дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | ^ Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||||
| лек | лаб | пр | СРС | КСР | |||||
| | ^ Основные понятия и определения. | 3 | 1 | 2 | 4 | - | 4 | 2 | Собеседование, Л/Р, устный опрос. |
| | Абстрактные типы . | 3 | 4 | ||||||
| | ^ Работа с динамической памятью. | 3 | 3 | 2 | 4 | Собеседование, Л/Р, устный опрос, дискуссионный форум. | |||
| | ^ Линейные списковые структуры. | 3 | 5 | 4 | 5 | ||||
| | ^ Обработка прямоугольных таблиц. | 3 | 5 | 2 | 4 | Собеседование, Л/Р, индивидуальное домашнее задание. | |||
| | ^ Нелинейные структуры. | 3 | 4 | ||||||
| | Двоичные деревья. | 3 | 7 | 2 | 5 | 4 | 5 | Собеседование, Л/Р, устный опрос. | |
| | ^ Сбалансированные деревья. | 3 | 4 | ||||||
| | Анализ эффективности алгоритмов поиска и сортировки с помощью деревьев. | 3 | 9 | 2 | 4 | Собеседование, Л/Р, устный опрос, дискуссионный форум. | |||
| | ^ Внешняя сортировка. | 3 | 11 | 2 | 2 | 4 | 2 | Собеседование, Л/Р, индивидуальное домашнее задание. | |
| | Пирамиды. | 3 | 13 | 2 | 4 | Собеседование, Л/Р, тестирование. | |||
| | Графы. | 3 | 15 | 2 | 4 | Собеседование, Л/Р, устный опрос. | |||
| | ^ Теория сложности алгоритмов. | 3 | 17-18 | 2 | 2 | 4 | 2 | Собеседование, Л/Р, устный опрос. | |
| | ^ Сжатие и кодирование информации. | 3 | 6 | Собеседование, Л/Р, индивидуальное домашнее задание | |||||
| ИТОГО | 18 | 18 | | 58 | 18 | | |||
Раздел 1. Основные понятия и определения. Понятие типа данного. Классификация данных. Структуры данных. Классификация структур данных. Способы представления структур данных. Задачи сортировки. Внутренняя сортировка. Определение эффективности методов сортировки. Простые и усовершенствованные методы сортировки данных: метод простого выбора, метод простых включений, метод простых перестановок, метод Шелла, быстрая сортировка, метод бинарных включений.
Раздел 2. Абстрактные типы . Абстрактный тип данных: спецификация, представление, реализация.
Раздел 3. Работа с динамической памятью. Понятие кучи. Переменная типа указатель. Основные процедуры и функции для работы с динамической памятью. Линейные и нелинейные динамические структуры. Рекурсивное описание данных. Способы представления динамических структур.
Раздел 4. Линейные списковые структуры. Односвязные линейные списки. Способы представления. Очередь, стек, дек. Организация линейных списков. Добавление и удаление элементов. Обход списков. Двусвязные списки. Двусвязные кольцевые списки. Создание списков. Обход списков. Операции добавления и удаления элементов.
Раздел 5. Обработка прямоугольных таблиц. Индексирование. Хеширование. Индексируемый массив. Массив –индекс. Плотная , разреженная, селективная индексация. Бинарный поиск Использование бинарного поиска в индексах. Хеширование. Хэш-функция. Возникновение коллизий. Разрешение коллизий методом открытой адресации с линейным опробованием. Разрешение коллизий методом цепочек.
Раздел 6. Нелинейные структуры. Иерархические списки. Деревья, леса, бинарные деревья; обходы деревьев задачи поиска данных, кодовые деревья, оптимальные префиксные коды; исчерпывающий поиск: перебор с возвратом.
Раздел 7. Двоичные деревья. Представление нелинейных структур и в виде массивов. Двоичные деревья поиска. Создание двоичных деревьев. Операции добавления и удаления элементов. Способы обхода деревьев. Сортирующее дерево.
Раздел 8. Сбалансированные деревья. AVL -дерево. Алгоритм балансировки дерева. В – деревья.
Раздел 9. Анализ эффективности алгоритмов поиска и сортировки с помощью деревьев. Оптимальные префиксные коды; исчерпывающий поиск: перебор с возвратом, метод ветвей и границ, динамическое программирование.
Раздел 10. Внешняя сортировка. Файлы. Представление файлов в виде деревьев. Естественное слияние отсортированных последовательностей. Внешняя сортировка.
Раздел 11. Пирамиды. Понятие пирамиды. Максимальные и минимальные пирамиды. Представление пирамид в виде дерева и в виде вектора. Достоинства и недостатки двух способов представления. Создание пирамиды. Добавление и удаление элементов в пирамиде. Алгоритм пирамидальной сортировки.
Раздел 12. Графы. Алгоритмы на графах: представление графов, схемы поиска в глубину и ширину, минимальное остовое дерево, кратчайшие пути;
Раздел 13. Теория сложности алгоритмов. NP – сложные и труднорешаемые задачи.
Раздел 14. Сжатие и кодирование информации. Задачи сжатия и кодирования информации. Классические алгоритмы сжатия и кодирования информации. Определение эффективности алгоритмов.
^ 5. Образовательные технологии
Используется:
1. при чтении лекций – компьютерная и проекционная техника, основой является разбор методик на демонстрационных примерах;
2. при проведении практических и лабораторных занятий – интерактивная доска, пакеты прикладных программ для разработки программного обеспечения (среда разработки Visual Studio);
3. Решение типовых задач в среде Visual Studio c примерами на языке C#.
4. В электронном виде используется интерактивные учебные материалы по лабораторным работам курса «Структуры и алгоритмы обработки данных», что стимулирует академическую активность обучающихся.
5. Анализируются интерактивные блоки программ в виде модулей для проверки.
6. В локальной сети кафедры САУ применяются интерактивные электронные обучающие системы для самостоятельной проработки материала и самоконтроля студента.
7. Для рейтингового контроля успеваемости используется программа электронного тестирования.
6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов
^ 6.1. Лабораторные занятия
| № | Раздел дисциплины | Наименование работы | Часов |
| 1 | 1-3 | Программирование алгоритмов простой сортировки. Сравнение эффективности простых методов сортировки. | 4 |
| 2 | 4-6 | Работа с динамической памятью. Создание линейных односвязных и двусвязных списковых структур. Обход списков. Включение и удаление элементов из списка. | 5 |
| 3 | 7-9 | Создание сбалансированного двоичного дерева. Реализация алгоритма сортирующее дерево. | 5 |
| 4 | 10-12 | Решение задачи обхода и достижимости вершин графа. | 2 |
| 5 | 13-14 | Кодирование и сжатие данных | 2 |
Для лабораторных работ оформляется стандартный отчет. Выполнение любой лабораторной работы заканчивается ее защитой. Максимальной оценкой за выполненную и защищенную лабораторную работу является 5, минимальной – 3. Оценка 5 подразумевает полное знание принципов работы соответствующего алгоритма и его взаимодействия с другими подсистемами в подзадачами, практическое умение реализовать данный алгоритм на уровне языка C#. Оценка 3 предполагает знание основных принципов работы соответствующего алгоритма.
^ 6.2. Индивидуальные занятия
Индивидуальные занятия по курсу проводятся в индивидуальном порядке в соответствии с целями и задачами дисциплины. В рамках курса «Структуры и алгоритмы обработки данных» предусмотрено выполнение индивидуального задания «Разработка комплексного алгоритма и прикладного приложения для задач нечеткой логики»:
6.3. Контрольные задания и вопросы для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины, а также для контроля самостоятельной работы обучающегося по отдельным разделам дисциплины
^ 6.3.1. Аннотация к тестовым заданиям
Тестовые задания по учебной дисциплине «Структуры и алгоритмы обработки данных» содержат 200 вопросов по теоретическим и практическим разделам курса и включают в себя вопросы следующих типов: выбор правильного ответа, установление правильной последовательности, сопоставление значений, ввод правильного ответа.
Задания структурированы по следующим разделам: Алгоритмы сортировки, Линейные структуры, деревья, графы, кодирование и сжатие данных.
^ 7. Учебно-методическое и информационное обеспечение дисциплины «Структуры и алгоритмы обработки данных».
а) основная литература:
1. Никалаус Вирт. Алгоритмы и структуры данных.: -Санкт-Петербург: «Невский диалект», 2001.
2. Ахо А., Хопкрофт Дж., Ульман Дж., Построение и анализ вычислительных алгоритмов.-М. Мир, 1989.- 369с.
3. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы.- М.,:Мир, 1976.-736с.(3-е изд.: Уч. Пос. – М.: Издательский дом «Вильямс», 2000. -720с.)
4. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.,:Мир, 1978.-846с.(2-е изд.: Уч. Пос. – М.: Издательский дом «Вильямс», 2000. -832с.)
5. Материалы представленные на сайте /kmi
б) дополнительная литература:
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые
задачи. – М.:Мир,1982.- 416 с.
в) программное обеспечение и Интернет-ресурсы:
.NET FrameWork, Visual Studio.
itmy.info/
manual.ru/
oding.net/
^ 8. Материально-техническое обеспечение дисциплины
Для проведения занятий по курсу «Структуры и алгоритмы обработки данных» используется лаборатория Г-341а кафедры САУ, задействуются 10 персональных компьютеров.
Компьютерные программы .NET FrameWork, Visual Studio.
Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению подготовки 220400.62 «Управление в технических системах» профили подготовки «Управление и информатика в технических системах».
Автор ____________________________ Крючек М.И.
Зав. кафедрой САУ _________________________ Финаев В.И.
Программа одобрена на заседании УМК ФАВТ от 20.01.2011 года, протокол № 1.