Учебный план набора 2003 года и последующих лет Распределение учебного времени Лекции 68 часов
| Вид материала | Лекции |
Содержание1 Цели и задачи дисциплины и ее место в учебном процессе 2 Содержание дисциплины 3 Учебно-методические материалы по дисциплине 4 Рейтинговая система оценки знаний |
- Курс 4 Семестр 7 Учебный план набора 2003 и последующих лет Распределение учебного, 57.04kb.
- Курс 4 Семестр 7 Учебный план набора 2009 года Распределение учебного времени Лекции, 1025.06kb.
- Курс 4 Семестр 2 Учебный план набора 2008 года и последующих лет Распределение учебного, 236.24kb.
- Программа по дисциплине "Теория информации" для студентов специальности 090106, 124.66kb.
- Рабочая программа учебной дисциплины фтпу 21/01 утверждаю, 631.81kb.
- И. М. Губкина календарный план дисциплина: «Интегральное исчисление и ряды» учебный, 52.15kb.
- Рабочая программа по дисциплине «Логика» для специальности 04. 01. 01 «Социальная работа», 101.71kb.
- План лекции 0 2и распределение учебного времени введение мин, 388.44kb.
- Тематический план курса «Административное право» и распределение учебного времени, 1452.8kb.
- Рабочая программа по дисциплине "Технико-экономический анализ деятельности предприятий", 356.09kb.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Томский государственный университет систем управления и
радиоэлектроники
УТВЕРЖДАЮ
Проректор по учебной работе
__________ М.Т. Решетников
"____"___________ 2007 г.
РАБОЧАЯ ПРОГРАММА
по дисциплине "Структуры и алгоритмы обработки данных"
специальности 230105 (220400) "Программное обеспечение
вычислительной техники и автоматизированных систем"
| Факультет систем управления | |
| Кафедра автоматизированных систем управления | |
| Курс | второй |
| Семестр | четвертый |
| Учебный план набора 2003 года и последующих лет | |
| Распределение учебного времени | |
| Лекции | 68 часов |
| Лабораторные работы | 34 часов |
| Курсовое проектирование | 17 часов |
| Всего ауд. занятий | 119 часов |
| Самостоятельная работа | 91 часов |
| Общая трудоемкость | 210 часов |
| | |
| Зачет | Четвертый семестр |
| Дифференцированный зачет | Четвертый семестр |
| Экзамен | Четвертый семестр |
2007 г.
Рабочая программа составлена на основании государственного образовательного стандарта по специальности 230105 (220400) - "Программное обеспечение вычислительной техники и автоматизированных систем", утвержденного 27.03.2000 г. Рассмотрена и утверждена на заседании кафедры АСУ. Протокол № __ от “___” _______ 2007 г.
| Разработчик, доктор техн. наук, доцент каф.АСУ | ____________ | А.Н. Горитов |
| | | |
| Зав. обеспечивающей кафедрой | ____________ | А.М. Кориков |
| | | |
Рабочая программа согласована с факультетом, профилирующей и выпускающей кафедрами специальностей
| | | |
| Декан ФСУ | ____________ | Н.В. Замятин |
| | | |
| Зав. профилирующей кафедрой | ____________ | А.М. Кориков |
| | | |
| Зав. выпускающей кафедрой | ____________ | А.М. Кориков |
^ 1 ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ И ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
Дисциплина "Структуры и алгоритмы обработки данных" входит в число базовых дисциплин для специальности "Программное обеспечение вычислительной техники и автоматизированных систем". Она ставит своей целью изучение основных структур представления данных в оперативной памяти ЭВМ, способов их описания, основных операций над структурированными данными.
Данная дисциплина является продолжением дисциплины "Программирование". Она базируется также на дисциплинах "Дискретная математика".
После изучения дисциплины студенты должны:
- знать основные типы структур данных: таблицы, списковые, древовидные, файловые и основные алгоритмы обработки структурированных данных для пополнения, удаления, модификации, поиска, упорядочения;
- уметь разрабатывать алгоритмы и программы обработки данных на алгоритмических языках;
- быть ознакомлены с методами организации и обработки информации в базах данных, базовыми структурами данных языков программирования.
Дисциплина "Структуры и алгоритмы обработки данных " дает теоретическую основу для последующих дисциплин: "Системное программное обеспечение", "Теория языков программирования и методы трансляции", "Теория вычислительных процессов", "Базы и банки данных и знаний" и "Экспертные системы".
^ 2 СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
2.1 Лекции
Тема 1. Данные и ЭВМ
Лекций - 2 часа, самостоятельная работа - 1 час.
Предмет дисциплины и ее задачи. Связь с другими дисциплинами учебного плана направления и специальности.
Данные реального мира, объекты предметной области, абстрактные алфавиты кодирования, байтовый алфавит.
Тема 2. Фундаментальные структуры данных
Лекций - 8 часа, самостоятельная работа - 4 час.
Базовые типы данных, обрабатываемые командами ЭВМ. Представление чисел, символьных и логических данных, указателей в оперативной памяти. Понятие структуры данных. Классификация структур. Важнейшие операции над структурами.
Массивы, их представление в памяти. Информационный вектор. Строковые данные. Операции над строками.
Записи и структуры. Квалифицированные имена. Иерархия данных в записях. Записи с вариантами. Представление записей в памяти ЭВМ.
Множества. Операции над множествами. Представление в памяти.
Последовательный файл. Особенности файла как структуры данных. Основные действия над файлом. Файлы со сложной структурой. Прямой доступ.
Тема 3. Линейные динамические структуры
Лекций - 8 час, самостоятельная работа - 4 часа
Структуры данных и алгоритмы. Стек, очередь и дек как линейные списки (последовательности) с ограниченными наборами операций (доступа). Стек, очередь и дек как абстрактные типы данных. Представление и реализация (непрерывная, ссылочная в связанной памяти и на базе вектора).
Примеры алгоритмов, использующих стек, очередь, дек.
Связный список. Односвязные, двусвязные, кольцевые списки и операции над ними. Представление и реализация (непрерывная, ссылочная в связанной памяти).
Тема 4. Древовидные структуры данных
Лекций - 12 час., самостоятельная работа - 6 час.
Определение дерева, леса, бинарного дерева. Графическое и текстовое (скобочное) представление леса. Спецификация дерева, леса, бинарного дерева: базовые функции и аксиомы. Естественное соответствие бинарного дерева и леса.
Обходы бинарных деревьев: рекурсивные и не рекурсивные алгоритмы. Обходы дерева или леса.
Представления и реализации бинарных деревьев: ссылочная реализация в связанной памяти, ссылочная реализация ограниченного бинарного дерева на базе вектора.
Пример использования бинарных деревьев в задаче упаковки сообщений: префиксные коды и бинарные деревья, метод кодирования Фано-Шеннона, критерий оптимальности кода, алгоритм кодирования (сжатия) информации по Хаффмену (построение дерева, кодирование и декодирование).
Тема 5. Сортировка
Лекций - 8 час., самостоятельная работа - 4 час.
Задача сортировки (внешней и внутренней).
Быстрая сортировка Хоара. Процедура разделения. Рекурсивный и не рекурсивный алгоритмы быстрой сортировки. Анализ сложности.
Пирамидальная сортировка: турнирная сортировка, построение пирамиды и полное упорядочение. Анализ сложности алгоритма.
Распределяющая (поразрядная) сортировка.
Сравнение алгоритмов и программ внутренней сортировки. Нижняя граница сложности задачи сортировки.
Внешняя сортировка. Простое слияние. Естественное слияние. Многофазная сортировка.
Тема 6. Исчерпывающий поиск
Лекций - 8 час., самостоятельная работа - 4 час.
Поиск с возвратом. Общий алгоритм. Пример: задача о ферзях. Усовершенствования. Оценка сложности выполнения: метод Монте-Карло. Другие способы программирования поиска с возвращением: рекурсия и использование макросредств.
Метод ветвей и границ. Общая схема. Задача коммивояжера: решение методом ветвей и границ.
Динамическое программирование. Пример и общая идея. Вычисление чисел Фибоначчи. Восходящее и нисходящее динамическое программирование. Задача определения наиболее длинной общей подпоследовательности. Задача определения порядка умножения цепочки матриц.
Тема 7. Быстрый поиск
Лекций - 8 час., самостоятельная работа - 4 час.
Поиск и другие операции над таблицами. Последовательный и бинарный поиск. Бинарные деревья поиска. Случайные бинарные деревья поиска. Подсчет числа структурно различных бинарных деревьев с заданным числом узлов. Среднее время поиска в случайных деревьях.
Рандомизированные бинарные деревья поиска.
Сбалансированные по высоте бинарные деревья (АВЛ-деревья). Включение в АВЛ-дерево. Исключение из АВЛ-дерева. Оценка сложности в худшем случае: деревья Фибоначчи.
Красно-черные деревья (КЧ- деревья). Включение в КЧ- деревья. Исключение из КЧ- деревьев.
Реализация упорядоченных линейных списков на базе АВЛ- деревьев, КЧ- деревьев или рандомизированных деревьев. Операции поиска, вставки и удаления элементов; операции сцепления и расщепления списков.
2-3-деревья. Включение элемента в 2-3 дерево. Исключение элемента из 2-3 дерева. Поиск элемента в 2-3 дереве.
2-3-4-деревья. Включение элемента в 2-3-4 дерево. Исключение элемента из 2-3-4 дерева. Поиск элемента в 2-3-4 дереве.
Б-деревья. Включение элемента в Б- дерево. Исключение элемента из Б- дерева. Поиск элемента в Б- дереве.
Метод поиска с использованием функции расстановки (хеширование). Разрешение коллизий: метод внутренних и внешних цепочек, метод открытой адресации. Коэффициент загрузки, оценки сложности. Выбор функции расстановки.
Задача поиска подстроки. Алгоритм Кнута-Мориса-Пратта. Алгоритм Боуера-Мура. Алгоритм Рабина-Карпа.
Тема 8. Алгоритмы на графах
Лекций - 10 час., самостоятельная работа - 5 час.
Графы: определения и примеры. Упорядоченный граф. Представления графов: матрица инциденций, матрица смежности, список пар, списки смежности.
Поиск в графе: Основные методы обработки графов. Поиск в ширину. Поиск в глубину.
Связные компоненты: Определение компонент связности. Топологическая сортировка.
Двусвязность: Точки сочленения и их свойства. Алгоритм выделения компонент двусвязности графа.
Эйлеров путь в графе. Алгоритм построения Эйлерова пути.
Гамильтонов путь в графе. Нахождение Гамильтонова пути в графе с помощью алгоритма с возвратом.
Циклы: Фундаментальное множество циклов графа. Алгоритм отыскания фундаментального множества циклов в графе.
Остовные деревья графа: Связные компоненты. Построение и свойства остовных деревьев при поиске в глубину и в ширину.
Остовные деревья минимального веса: Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала.
Кратчайшие пути в графе: Кратчайшие пути от фиксированной вершины. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. Кратчайшие пути в бесконтурном графе.
Кратчайшие пути между всеми парами вершин: Матрица смежности, матрица достижимости и транзитивное замыкание отношения, алгоритм Уоршалла. Алгоритм Флойда-Уоршалла вычисления расстояний между всеми парами вершин, одновременное построение путей.
Тема 9. NP-полные и труднорешаемые задачи
Лекций - 4 час., самостоятельная работа - 2 час.
Массовая и индивидуальная задачи. Сложность алгоритма и кодирование входных и выходных данных. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP.
Различные формы постановки задач комбинаторной оптимизации: оптимизационная, вычислительная, форма распознавания. Примеры.
Полиномиальная преобразуемость задач. NP-трудные и NP-полные задачи. Задача о выполнимости булева выражения, представленного в конъюнктивной нормальной форме. Доказательство NP-полноты задачи о выполнимости.
Практическое решение NP-полных задач.
2.2 Лабораторные занятия.
| 1. Перечислимые и интервальные типы данных. | 2 часа |
| 2. Операции над множествами. | 4 часа |
| 3. Записи. | 4 часа |
| 4. Последовательный файл в языке Паскаль. | 4 часа |
| 5. Методы сортировки файлов. | 4 часа |
| 6. Линейные структуры: очереди, стеки. | 4 часа |
| 7. Связные списки. | 4 часа |
| 8. Двоичные деревья. | 4 часа |
| 9. Алгоритмы на графах. | 4 часа |
2.3 Курсовая работа
Курсовая работа по дисциплине "Структуры и алгоритмы обработки данных в ЭВМ" имеет цель привить практические навыки по выбору структур данных и языковых конструкций, обеспечивающих построение эффективных алгоритмов обработки информации для задач, в которых сложность данных превышает сложность алгоритмов их обработки.
При выполнении курсовой работы строит модель предметной области, разрабатывает ее представление при помощи абстрактной структуры данных и дается ее логическое представление. Затем выбирается представление структур данных конструкциями языков программирования, составляется и отлаживается на ЭВМ программа обработки данных. Задача обработки включает в себя поиск, сортировку, выбор элементов по заданному признаку с использованием динамических структур.
Типичными предметными областями для курсовой работы могут быть:
- Текущая информация о ходе приема абитуриентов в институт.
- Сведения об успеваемости в сессию потока студентов.
- Информация о распределении выпускников на работу.
- Расписание прибытия и отправления самолетов или поездов.
- Анкетная информация отдела кадров завода.
- Сведения о вкладах в сберегательном банке.
- Обработка библиотечной информации и т.д.
Основные этапы курсовой работы и затраты времени
| N этапа | Содержание работы | число | часов |
| | | | |
| | | ауд. | Самост. |
| | | | |
| 1 | Тематика курсовой работы | | |
| | Выдача заданий | 2 | 2 |
| 2 | Выбор структуры данных и представление структур данных в программе | 3 | 4 |
| 3 | Составление программы обработки данных | 4 | 16 |
| 4 | Отладка и выполнение программы на ЭВМ | 4 | 9 |
| 5 | Оформление пояснительной записки и защита курсовой работы | 4 | 6 |
| | Всего | 17 | 37 |
2.4 Формы самостоятельной работы
| № | Наименование работы | Число часов | Формы контроля |
| 1 | Проработка лекционного материала Темы самостоятельных заданий по лекционному курсу: 1. Динамическое кодирование по Хаффману. 2. Деревья Фибоначчи. 3. Оптимальные бинарные деревья поиска. 4. Каскадная сортировка 5. Метод построения максимального потока в сети 6. Алгоритм нахождения компонент связности. 7. Алгоритм нахождения сильносвязных компонент. 8. Алгоритм порождения клик графа. | 34 | Экзамен |
| 2 | Подготовка к лабораторным работам и оформление отчетов. . . . . . . . . . . . . . . . . . . . . . | 20 | Защита отчета |
| 3 | Выполнение курсового проекта. . . . . . . . . . . . . | 37 | Защита проекта |
| | Всего часов самостоятельной работы по дисциплине. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . | 91 | |
^ 3 УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
Основная литература
- Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с. (50 экз.)
- Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. – М.: Лаборатория базовых знаний, 2003. – 288 с. (50 экз.)
Дополнительная литература
- Окулов С. М. Программирование в алгоритмах. – 2-е изд., доп. – М.: БИНОМ. Лаборатория знаний, 2006 . – 384 с. (30 экз.)
- Ускова О.Ф. и др. Программирование алгоритмов обработки данных: Учебное пособие. – СПб: БХВ-Петербург, 2003. – 188 с. (19 экз.)
- Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. – Москва: Техносфера, 2004. – 368 с. (13 экз.)
- Андерсон Д.А. Дискретная математика и комбинаторика. – М.: Издательский дом "Вильямс", 2004. – 960 с. (10 экз.)
- Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. – СПб: Питер, 2002. – 302 с. (19 экз.)
- Липский В. Комбинаторика для программистов. – М.: Мир,1989.– 213 с. (9 экз.)
- Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы. – М.: Мир, 1976. – 736 с. (3-е изд.: Уч. пос. – М.: Издательский дом «Вильямс», 2000. – 720 с.) (5 экз.)
- Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. - М.: Мир, 1978. – 846 с. (2-е изд.: Уч. пос. – М.: Издательский дом «Вильямс», 2000. – 832 с.) (15 экз.)
- Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах. – М.: Высшая школа, 1987. – 248 с. (9 экз.)
- Стоун Г.С., Сиворек Д.П. Введение в организацию ЭВМ и структуры данных. – М.: Машиностроение, 1980. – 320 с. (10 экз.)
^ 4 РЕЙТИНГОВАЯ СИСТЕМА ОЦЕНКИ ЗНАНИЙ
Общие положения
- Максимальное количество баллов – 120;
Рейтингу 60–79 соответствует оценка «удовлетворительно»;
Рейтингу 80–99 соответствует оценка «хорошо»;
Рейтингу 100–120 соответствует оценка «отлично».
- Экзамен «автомат» студент получает при условии: а) получил зачет по лабораторным работам; б) набрал не менее 80 баллов.
- Баллы за лабораторные работы начисляются за успешно работающую компьютерную программу и отчет. Студент получает максимальный балл в случае своевременной сдачи отчета по лабораторной работе. Своевременной считается сдача отчета на следующем занятии после получения задания. При сдаче отчета на третьем занятии с момента получения задания баллы снижаются до 50%. После этого срока баллы за данную работу не начисляются.
- Студент может получить дополнительные баллы за регулярное посещение лекций
Лабораторные работы:
Лабораторные работы: 9 работ 12,0 баллов = 108 баллов
Лабораторная работа должна быть защищена на следующем занятии.
Мотивы снижения баллов за лабораторную работу:
1. Защита после установленного срока на одно занятие снижает количество баллов на 50 %, при большей задержки – количество снимаемых баллов составляет 75 %.
2. При плохой защите количество баллов уменьшается на 50 %.
3. Неполный отчет по лабораторной работе уменьшает количество баллов на 50 %.
4. Не выполнение лабораторной работы в учебное время уменьшает количество начисляемых баллов на 30 %.
5. На лабораторные работы, защищаемые во время сессии, баллы не начисляются.
Посещение лекций
За посещение лекций может быть дополнительно начислено 12 баллов.
Курсовая работа:
| Выбор темы (сложность и оригинальность) | до 15 баллов |
| Первое контрольное собеседование (анализ задачи, проект решения, алгоритм программы) | до 15 баллов |
| Второе контрольное собеседование (представление предварительных материалов курсовой работы) | до 15 баллов |
| Использование изучаемых структур данных | до 20 баллов |
| Творческие моменты в алгоритме и программе | до 15 баллов |
| Полнота пояснительной записки | до 15 баллов |
| Оформление пояснительной записки | до 10 баллов |
| Защита курсовой работы | до 15 баллов |
| Максимальное количество баллов | 120 баллов |
Рейтингу 60–79 соответствует оценка «удовлетворительно».
Рейтингу 80–99 соответствует оценка «хорошо».
Рейтингу 100–120 соответствует оценка «отлично».
Мотивы снижения баллов за курсовую работу:
1. Защита курсовой работы после зачетной недели (во время сессии) снимает все баллы.
2. Не соответствие выполненной работы заданию на курсовую работу снимает все баллы.
3. Не соответствие пояснительной записки установленным требованиям, а также не полнота освящение разделов пояснительной записки снижает количество баллов на 30 %.
4. Не обоснованный выбор и не эффективное использование изученных в теоретическом курсе структур данных снижает количество начисляемых баллов на 50 %.
5. Не выполнение курсовой работы в учебное время снижает количество баллов на 30 %.
Максимальный рейтинг по изучаемой дисциплине = 240 баллов.