Российской федерации
Скачать 97.88 Kb.
|
| МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Саратовский государственный университет имени Н.Г. Чернышевского Факультет компьютерных наук и информационных технологий УТВЕРЖДАЮ ___________________________ "__" __________________20__ г. Рабочая программа дисциплины Типы и структуры данных Направление подготовки 231000 Программная инженерия Профиль подготовки Разработка программно-информационных систем Квалификация (степень) выпускника Бакалавр Форма обучения очная Саратов, 2011 год 1. Цели освоения дисциплины «Типы и структуры данных» Целями освоения данной дисциплины являются формирование общих представлений о типах и структурах данных, способах представления данных в ЭВМ, алгоритмах обработки структур данных, развитие у студентов компетенций в области применения различных типов и структур данных при решении конкретной задачи. 2.Место дисциплины «Типы и структуры данных» в структуре ООП бакалавриата «Программная инженерия» Дисциплина «Типы и структуры данных» входит в раздел «Профессиональный цикл. Базовая часть» ФГОС-3 направления подготовки «Программная инженерия». Для успешного усвоения данной дисциплины необходимы компетенции, сформированные у обучающихся в результате обучения в средней общеобразовательной школе, а также при изучении таких дисциплин как «Основы программирования». Сформированные в процессе изучения дисциплины «Типы и структуры данных» компетенции, необходимы студенту при освоении таких дисциплин профессионального цикла, как «Объектно-ориентированное программирование», «Теория кодирования и передачи данных». 3 Компетенции обучающегося, формируемые в результате освоения дисциплины «Типы и структуры данных» В результате освоения дисциплины «Типы и структуры данных» студент должен обладать следующими профессиональными компетенциями:
В результате освоения дисциплины обучающийся должен:
4. Структура и содержание дисциплины «Типы и структуры данных» Общая трудоемкость дисциплины составляет 4 зачетных единицы 144 часа (из них 72 часа аудиторных).
Простые типы данных. Представление различных типов данных в ЭВМ. Самостоятельная работа – подробное изучение представления различных типов данных в ЭВМ, подготовка к контрольной работе.
Списки. Реализация списков посредством массивов и указателей. Связанные списки. Стеки. Очереди. Стеки и рекурсивные процедуры. Самостоятельная работа – изучение и сравнение различных абстрактных типов данных, подготовка к контрольной работе.
Основная терминология. Способы обхода деревьев. Реализация деревьев. Двоичные деревья. Реализация двоичных деревьев с помощью указателей. Коды Хаффмана. Самостоятельная работа – подробное изучение реализации деревьев, подготовка к контрольной работе.
Система обозначений для множеств. Реализация множеств. Словари. Структуры данных, основанные на хеш-таблицах. Оценка эффективности хеш-функций. Деревья двоичного поиска. Нагруженные деревья. Реализация множеств посредством сбалансированных деревьев. Самостоятельная работа – подробное изучение реализаций множеств, подготовка к контрольной работе. Контрольная работа №1.
Основные определения. Представление ориентированных графов. Задача нахождения кратчайшего пути. Алгоритм Дейкстры. Кратчайший путь между двумя парами вершин. Алгоритм Флойда. Обход ориентированных графов. Орграфы. Сильная связность. Самостоятельная работа – сравнение алгоритмов Дейкстры и Флойда, подготовка к контрольной работе.
Основные определения. Представление неориентированных графов. Остовные деревья минимальной стоимости. Алгоритм Прима. Алгоритмы Крускала. Обход неориентированных графов. Поиск в глубину, поиск в ширину. Точки сочленения и двусвязные компоненты. Самостоятельная работа – сравнение алгоритмов Прима и Крускала, подробное изучение поиска в глубину и ширину, подготовка к контрольной работе.
Модель внешних вычислений. Хранение данных в файлах. Ускорение операций с файлами. Хешированные файлы, индексированные файлы, несортированные файлы с плотным индексом. Внешние деревья поиска. В-деревья. Проблемы управления памятью. Управление блоками одинакового размера. Алгоритм Дойча-Шорра-Уэйта. Фрагментация и уплотнение пустых блоков. Уплотнение памяти. Алгоритм Морриса. Самостоятельная работа – подробное изучение алгоритмов управления памятью, подготовка к контрольной работе. Контрольная работа №2.
Эффективность алгоритмов. Анализ рекурсивных программ. Алгоритмы «разделяй и властвуй». «Жадные» алгоритмы. Самостоятельная работа – подробное изучение эффективности алгоритмов, подготовка к экзамену. 5. Образовательные технологии В учебном процессе при реализации компетентностного подхода используются такие активные и интерактивные формы проведения занятий как модельный метод обучения, метод развивающей кооперации, разбор конкретных ситуаций, командное выполнение заданий с распределением ролей. Широко используются мультимедийные презентации при представлении лекционного материала. 6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины «Типы и структуры данных». 7. Учебно-методическое и информационное обеспечение дисциплины «Типы и структуры данных» а) основная литература:
б) дополнительная литература:
в) программное обеспечение и Интернет-ресурсы
8. Материально-техническое обеспечение дисциплины «Типы и структуры данных» Для данного курса необходимо наличие компьютерного класса, оборудованного соответствующим программным обеспечением для работы на языке С++ (например, Visual Studio или подобной средой разработки программ). Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по направлению и профилю подготовки «Разработка программно-информационных систем».
Программа одобрена на заседании кафедры математической кибернетики и компьютерных наук от года 22.02.2011, протокол № 13.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
Похожие:
 | Федерации установлены Федеральным законом от 27 декабря 2002 г. N 184-фз "О техническом регулировании", а правила применения национальных... |  | Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. №184-фз "О техническом... |
| Российской Федерации об охране здоровья граждан от 22 июля 1993 г. N 5487-1 (Ведомости Съезда народных депутатов Российской Федерации... | | Настоящим Федеральным законом в соответствии с Конституцией Российской Федерации и Федеральным законом "Об обязательном пенсионном... |
| Дерального закона Российской Федерации «О таможенном регулировании в Российской Федерации», другими законами Российской Федерации... | | Дерального закона Российской Федерации «О таможенном регулировании в Российской Федерации», другими законами Российской Федерации... |
| Конституцией Российской Федерации, а также в соответствии с общепризнанными принципами и нормами международного права и международными... | | Конституция Российской Федерации в редакции Федерального конституционного закона от 30. 12. 2008 №6 и 7-фкз // Российская газета.... |
| Российской Федерации от 12 февраля 1998 г. N 179, проблема сохранения музейных предметов и музейных коллекций относится к числу приоритетных... | | Федерации – это государственная награда Российской Федерации- россии, высшее звание, присваиваемое за заслуги перед государством... |