Рабочая программа дисциплины Структуры и алгоритмы компьютерной обработки данных (Наименование дисциплины)
| Вид материала | Рабочая программа |
- Рабочая программа дисциплины Структуры и алгоритмы обработки данных (Наименование дисциплины), 185.25kb.
- Рабочая программа дисциплины Структуры и алгоритмы обработки данных (Наименование дисциплины), 183.25kb.
- Примерная программа наименование дисциплины Структуры и алгоритмы компьютерной обработки, 215.14kb.
- Программа дисциплины структуры и алгоритмы компьютерной обработки данных для специальности, 506.16kb.
- Рабочая программа Наименование дисциплины Алгоритмы и методы компьютерной лингвистики, 210.54kb.
- Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
- Программа дисциплины «Структуры данных», 88.1kb.
- Программа дисциплины Базы данных Семестры, 12.06kb.
- Структуры и алгоритмы компьютерной обработки данных, 62.4kb.
- Программа курса Алгоритмы программирования, 47.59kb.
МИНОБРНАУКИ РОССИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ В Г. ТАГАНРОГЕ
(ТТИ Южного федерального университета)
Факультет автоматики и вычислительной техники
УТВЕРЖДАЮ
Декан ФАВТ ______________ Ю.М. Вишняков
"_____"__________________2011 г.
Рабочая программа дисциплины
Структуры и алгоритмы компьютерной обработки данных
(Наименование дисциплины)
Направление подготовки
230100.62 «Информатика и вычислительная техника»
Профиль подготовки
Автоматизированные Информационно- управляющие системы и комплексы
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
(очная, очно-заочная и др.)
г. Таганрог
2011
1. Цели освоения дисциплины
Целью освоения дисциплины «Структуры и алгоритмы компьютерной обработки данных» является изучение применяемых в программировании (и информатике) структур данных, их спецификации и реализации в различных классах задач, алгоритмов обработки данных, анализ этих алгоритмов, прикладное применение алгоритмов, взаимосвязь алгоритмов и структур, изучение различных форм организации данных в программах и методов их обработки.
Цели дисциплины соответствуют всем 3-м целям ООП по направлению 230100.62 «Информатика и вычислительная техника», а именно:
1 цель направления. Удовлетворение потребностей личности в интеллектуальном, культурном и нравственном развитии путем получения высшего образования в области информатики и вычислительной техники;
2 цель направления. Организация базовой бакалаврской подготовки, позволяющей всем выпускникам продолжить свое образование как с целью получения диплома инженера или магистра в области информатики и вычислительной техники, так и с целью дальнейшего самосовершенствования.
3 цель направления. Удовлетворение потребностей общества в квалифицированных кадрах путем подготовки специалистов по проектированию, разработке и эксплуатации автоматизированных информационно-управляющих систем и комплексов.
а также будет способствовать достижению локальных целей профиля подготовки «Автоматизированные информационно-управляющие системы и комплексы»:
1 цель профиля. Развитие у студентов теоретических знаний и практических навыков, позволяющих выпускникам понимать и применять фундаментальные и передовые знания и научные принципы, лежащие в основе современных автоматизированных информационно-управляющих систем и комплексов при формулировании и решении инженерных задач;
2 цель профиля. Подготовка высококвалифицированных специалистов, способных решать задачи исследования, проектирования, разработки, настройки, тестирования и эксплуатации современных автоматизированных информационно-управляющих систем и комплексов в различных областях профессиональной деятельности, а также задачи планирования и проведения экспериментальных исследований свойств и характеристик данных систем;
2. Место дисциплины в структуре ООП по направлению подготовки 230100.62 «Информатика и вычислительная техника
Дисциплина «Структуры и алгоритмы компьютерной обработки данных» относится к дисциплинам по выбору. В процессе изучения дисциплины студенты знакомятся с основными тенденциями в создании структур данных, методах оптимального использования памяти и времени для обработки данных и управления процессами обработки данных; используют различные (динамические и статистические ) структуры данных в соответствии с запросами алгоритмов; получают опыт в математических методах анализа алгоритмов; получают навыки классификации алгоритмических задач по сложности, сводимости алгоритмических задач к известным задачам определенного класса.
Дисциплина базируется на понятиях, изучаемых в дисциплинах: «Математика», «Основы информатики», «Программирование и основы алгоритмизации», «Дискретная математика». Для освоения дисциплины студенту необходимо владеть основами применения языков программирования высокого уровня, владеть технологией применения различных систем счисления, иметь представление о типах данных, используемых в прикладном программировании.
Материалы дисциплины используются при изучении дисциплин профессионального цикла, при выполнении курсовых работ и проектов, а также выпускной квалификационной работы.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Структуры и алгоритмы обработки данных»:
– имеет навыки работы с компьютером как средством управления информацией (ОК-12);
– осваивать методики использования программных средств для решения практических задач (ПК-2);
– разрабатывать модели компонентов информационных систем, включая модели баз данных (ПК-4.)
В результате освоения дисциплины обучающийся должен:
- Знать: Основные методы разработки машинных алгоритмов и программ, структуры данных, используемые для представления типовых информационных объектов; Основные машинные алгоритмы и характеристики их сложности для типовых задач; Списковые и древообразные структуры; Основные алгоритмы шифрования и дешифрования данных; Основы сжатия данных; Методы поиска; Критерии определения эффективности поиска и сортировки.
- Уметь: Использовать оптимальные методы поиска и сортировки данных; Создавать и использовать абстрактные типы данных, экспериментально (с помощью компьютера) исследовать эффективность алгоритма и программы; Индексировать данные; Хешировать данные.
- Владеть: Разработкой алгоритмов, используя общие схемы, методы и приемы построения алгоритмов; Технологией представления разнородных данных в виде алгоритмических структур.
- Демонстрировать способность и готовность: Анализировать существующие структуры данных на предмет оптимальности применения в конкретной задаче.
4. Структура и содержание дисциплины «Структуры и алгоритмы компьютерной обработки данных».
Общая трудоемкость дисциплины составляет 4 зачетных единицы, 144 часа, 72 часа аудиторная нагрузка, 40 час – самостоятельная работа.
| Вид учебной работы | Всего часов |
| Общая трудоемкость дисциплины | 144/4 ЗЕТ |
| Аудиторные занятия | 36 |
| - лекции | 36 |
| - практические занятия | 36 |
| - лабораторные работы | |
| - другие виды аудиторных занятий | |
| Самостоятельная работа | 40 |
| Курсовой проект (работа) | |
| Контроль самостоятельной работы | 18 |
| Аттестация | 34 Экзамен (5 семестр) |
4.1. Разделы дисциплины и виды занятий
| № п/п | Раздел Дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Форма промежуточной аттестации (по семестрам) | ||||
| лек | лаб | пр | СРС | КСР | |||||
| | Основные понятия и определения. | 5 | 1 | 2 | - | 2 | 2 | - | Собеседование, практические занятия, устный опрос. |
| | Абстрактные типы . | 5 | 2 | 2 | |||||
| | Работа с динамической памятью. | 5 | 3 | 2 | 2 | 2 | Собеседование, практические занятия, устный опрос, дискуссионный форум. | ||
| | Линейные списковые структуры. | 5 | 2 | 2 | |||||
| | Обработка прямоугольных таблиц. | 5 | 5 | 2 | 2 | 2 | Собеседование, практические занятия, индивидуальное домашнее задание. | ||
| | Нелинейные структуры. | 5 | 2 | 2 | |||||
| | Двоичные деревья. | 5 | 7 | 2 | 2 | 2 | Собеседование, практические занятия, устный опрос. | ||
| | Сбалансированные деревья. | 5 | 2 | 2 | |||||
| | Анализ эффективности алгоритмов поиска и сортировки с помощью деревьев. | 5 | 9 | 2 | 2 | 2 | Собеседование, практические занятия, устный опрос, дискуссионный форум. | ||
| | Внешняя сортировка. | 5 | 11 | 2 | 2 | 2 | Собеседование, практические занятия, индивидуальное домашнее задание. | ||
| | Пирамиды. | 5 | 13 | 2 | 4 | 4 | Собеседование, практические занятия, тестирование. | ||
| | Графы. | 5 | 15 | 2 | 4 | 4 | Собеседование, практические занятия, устный опрос. | ||
| | Теория сложности алгоритмов. | 5 | 17 | 2 | 4 | 4 | Собеседование, практические занятия, устный опрос. | ||
| | Сжатие и кодирование информации. | 5 | 4 | 8 | Собеседование, практические занятия, индивидуальное домашнее задание, тестирование | ||||
| ИТОГО | 36 | | 36 | 40 | | | |||
Раздел 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 | Программирование алгоритмов простой сортировки. Сравнение эффективности простых методов сортировки. | 8 |
| 2 | 4-6 | Работа с динамической памятью. Создание линейных односвязных и двусвязных списковых структур. Обход списков. Включение и удаление элементов из списка. | 10 |
| 3 | 7-9 | Создание сбалансированного двоичного дерева. Реализация алгоритма сортирующее дерево. | 10 |
| 4 | 10-12 | Решение задачи обхода и достижимости вершин графа. | 4 |
| 5 | 13-14 | Кодирование и сжатие данных | 4 |
Для практических задач оформляется стандартный отчет. Выполнение любой практической работы заканчивается ее защитой. Максимальной оценкой за выполненную и защищенную практическую работу является 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.
Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению подготовки 230100.62 «Информатика и вычислительная техника» профиль подготовки «Автоматизированные информационно- управляющие системы и комплексы».
Автор ____________________________ Крючек М.И.
Зав. кафедрой _________________________ Финаев В.И.
Программа одобрена на заседании УМК ФАВТ от 20.01.2011 года, протокол № 1.