Российской федерации






Скачать 97.88 Kb.
НазваниеРоссийской федерации
Дата публикации16.02.2015
Размер97.88 Kb.
ТипДокументы
l.120-bal.ru > Документы > Документы
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Саратовский государственный университет имени Н.Г. Чернышевского
Факультет компьютерных наук и информационных технологий

УТВЕРЖДАЮ

___________________________

"__" __________________20__ г.


Рабочая программа дисциплины
Типы и структуры данных
Направление подготовки

231000 Программная инженерия
Профиль подготовки

Разработка программно-информационных систем

Квалификация (степень) выпускника

Бакалавр
Форма обучения

очная

Саратов,

2011 год

1. Цели освоения дисциплины «Типы и структуры данных»

Целями освоения данной дисциплины являются формирование общих представлений о типах и структурах данных, способах представления данных в ЭВМ, алгоритмах обработки структур данных, развитие у студентов компетенций в области применения различных типов и структур данных при решении конкретной задачи.
2.Место дисциплины «Типы и структуры данных» в структуре ООП бакалавриата «Программная инженерия»

Дисциплина «Типы и структуры данных» входит в раздел «Профессиональный цикл. Базовая часть» ФГОС-3 направления подготовки «Программная инженерия». Для успешного усвоения данной дисциплины необходимы компетенции, сформированные у обучающихся в результате обучения в средней общеобразовательной школе, а также при изучении таких дисциплин как «Основы программирования».

Сформированные в процессе изучения дисциплины «Типы и структуры данных» компетенции, необходимы студенту при освоении таких дисциплин профессионального цикла, как «Объектно-ориентированное программирование», «Теория кодирования и передачи данных».
3 Компетенции обучающегося, формируемые в результате освоения дисциплины «Типы и структуры данных»

В результате освоения дисциплины «Типы и структуры данных» студент должен обладать следующими профессиональными компетенциями:

  • Способность к формализации в своей предметной области с учетом ограничений используемых методов исследования (ПК-2);

  • Способность формализовать предметную область программного проекта и разработать спецификации для компонентов программного продукта (ПК-6);

В результате освоения дисциплины обучающийся должен:

  • Знать:

  • способы представления различных структур данных в ЭВМ;

  • алгоритмы обработки структур данных;

  • технологии программирования с использованием абстрактных типов данных.

  • Уметь:

  • выбрать наиболее эффективный алгоритм для решения задачи;

  • выбрать подходящие структуры данных;

  • разрабатывать спецификации для конкретных компонентов программного продукта.

  • Владеть:

  • навыками самостоятельной оценки использования структур данных и алгоритмов их обработки;

  • навыками реализации абстрактных типов данных в конкретные структуры данных на языке программирования;

  • навыками реализации выбранного алгоритма на языке программирования;

  • навыками формализации предметной области программного продукта.


4. Структура и содержание дисциплины «Типы и структуры данных»

Общая трудоемкость дисциплины составляет 4 зачетных единицы 144 часа (из них 72 часа аудиторных).




п/п

Раздел дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

Формы текущего контроля успеваемости (по неделям семестра)

Формы промежуточной аттестации (по семестрам)













Лек.

Лаб

ПР

С




1

Понятие типа данных

3

1

2

2




2

Участие в лабораторных занятиях – 1 нед.

Контрольная работа №1– 10 нед.

2

Основные абстрактные типы данных

3

2-4

6

6




6

Участие в лабораторных занятиях – 2-4 нед.

Контрольная работа №1– 10 нед.

3

Деревья

3

5-7

6

6




6

Участие в лабораторных занятиях – 5-7 нед.

Контрольная работа №1 – 10 нед.

4

Множества

3

8-10

6

6




6

Участие в лабораторных занятиях – 8-10 нед.

Контрольная работа №1– 10 нед.

5

Ориентированные графы

3

11-13

6

6




6

Участие в лабораторных занятиях – 11-13 нед.

Контрольная работа №2– 17 нед.

6

Неориентированные графы

3

14-16

6

6




6

Участие в лабораторных занятиях – 14-16 нед.

Контрольная работа №2– 17 нед.

7

Структуры данных для внешней памяти. Управление памятью.

3

17

2

2




2

Участие в лабораторных занятиях – 17 нед.

Контрольная работа №2 – 17 нед.

8

Понятие эффективности алгоритмов

3

18

2

2




2

Участие в лабораторных занятиях – 18 нед.

Промежуточная аттестация

Зачет




ИТОГО

3




36

36




36







  1. Понятие типа данных

Простые типы данных. Представление различных типов данных в ЭВМ.

Самостоятельная работа – подробное изучение представления различных типов данных в ЭВМ, подготовка к контрольной работе.

  1. Основные абстрактные типы данных.

Списки. Реализация списков посредством массивов и указателей. Связанные списки. Стеки. Очереди. Стеки и рекурсивные процедуры.

Самостоятельная работа – изучение и сравнение различных абстрактных типов данных, подготовка к контрольной работе.

  1. Деревья

Основная терминология. Способы обхода деревьев. Реализация деревьев. Двоичные деревья. Реализация двоичных деревьев с помощью указателей. Коды Хаффмана.

Самостоятельная работа – подробное изучение реализации деревьев, подготовка к контрольной работе.

  1. Множества

Система обозначений для множеств. Реализация множеств. Словари. Структуры данных, основанные на хеш-таблицах. Оценка эффективности хеш-функций. Деревья двоичного поиска. Нагруженные деревья. Реализация множеств посредством сбалансированных деревьев.

Самостоятельная работа – подробное изучение реализаций множеств, подготовка к контрольной работе.

Контрольная работа №1.

  1. Ориентированные графы

Основные определения. Представление ориентированных графов. Задача нахождения кратчайшего пути. Алгоритм Дейкстры. Кратчайший путь между двумя парами вершин. Алгоритм Флойда.

Обход ориентированных графов. Орграфы. Сильная связность.

Самостоятельная работа – сравнение алгоритмов Дейкстры и Флойда, подготовка к контрольной работе.

  1. Неориентированные графы

Основные определения. Представление неориентированных графов. Остовные деревья минимальной стоимости. Алгоритм Прима. Алгоритмы Крускала. Обход неориентированных графов. Поиск в глубину, поиск в ширину. Точки сочленения и двусвязные компоненты.

Самостоятельная работа – сравнение алгоритмов Прима и Крускала, подробное изучение поиска в глубину и ширину, подготовка к контрольной работе.

  1. Структуры данных для внешней памяти. Управление памятью

Модель внешних вычислений. Хранение данных в файлах. Ускорение операций с файлами. Хешированные файлы, индексированные файлы, несортированные файлы с плотным индексом. Внешние деревья поиска. В-деревья. Проблемы управления памятью. Управление блоками одинакового размера. Алгоритм Дойча-Шорра-Уэйта. Фрагментация и уплотнение пустых блоков. Уплотнение памяти. Алгоритм Морриса.

Самостоятельная работа – подробное изучение алгоритмов управления памятью, подготовка к контрольной работе.

Контрольная работа №2.

  1. Понятие эффективности алгоритмов

Эффективность алгоритмов. Анализ рекурсивных программ. Алгоритмы «разделяй и властвуй». «Жадные» алгоритмы.

Самостоятельная работа – подробное изучение эффективности алгоритмов, подготовка к экзамену.

5. Образовательные технологии

В учебном процессе при реализации компетентностного подхода используются такие активные и интерактивные формы проведения занятий как модельный метод обучения, метод развивающей кооперации, разбор конкретных ситуаций, командное выполнение заданий с распределением ролей. Широко используются мультимедийные презентации при представлении лекционного материала.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины «Типы и структуры данных».
7. Учебно-методическое и информационное обеспечение дисциплины «Типы и структуры данных»

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

  1. Круз Р. Л. Структуры данных и проектирование программ (Data Structures and Program Design) — М.: БИНОМ. Лаб. Знаний, 2008.

  2. Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы (Data Structures and Algorithms).— Киев: Вильямс, 2007.

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

  1. Кузнецов В. А., Караваев А. М. Оптимизация на графах (алгоритмы и реализация) — Петрозаводск: Изд-во ПетрГУ, 2007.

  2. Каррано Фр. М., Причард Дж.  Дж. Абстракция данных и решение задач на C++: Стены и зеркала (Data Abstraction and Problem Solving with C++) — Киев: Изд. дом "Вильямс", 2003. - 847 с.

в) программное обеспечение и Интернет-ресурсы

  1. Алексеев В. Е., Таланов В. А. Структуры данных и модели вычислений.http://www.intuit.ru/department/algorithms/dscm/



8. Материально-техническое обеспечение дисциплины «Типы и структуры данных»

Для данного курса необходимо наличие компьютерного класса, оборудованного соответствующим программным обеспечением для работы на языке С++ (например, Visual Studio или подобной средой разработки программ).

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по направлению и профилю подготовки «Разработка программно-информационных систем».



Автор

доцент

каф. МКиКН



___________



А. С. Иванова


Программа одобрена на заседании кафедры математической кибернетики и компьютерных наук от года 22.02.2011, протокол № 13.



Заведующий кафедрой

математической кибернетики и компьютерных наук



___________



А. С. Иванов


Декан факультета КНиИТ,

доцент



___________



А. Г. Федорова

Добавить документ в свой блог или на сайт

Похожие:

Российской федерации iconНациональный стандарт российской федерации
Федерации установлены Федеральным законом от 27 декабря 2002 г. N 184-фз "О техническом регулировании", а правила применения национальных...

Российской федерации iconНациональный стандарт российской федерации
Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. №184-фз "О техническом...

Российской федерации iconПорядок оказания медицинской помощи при проведении физкультурных и спортивных мероприятий
Российской Федерации об охране здоровья граждан от 22 июля 1993 г. N 5487-1 (Ведомости Съезда народных депутатов Российской Федерации...

Российской федерации iconРоссийская федерация федеральный закон о трудовых пенсиях в российской федерации
Настоящим Федеральным законом в соответствии с Конституцией Российской Федерации и Федеральным законом "Об обязательном пенсионном...

Российской федерации iconРазвитие и постоянные существенные изменения правового регулирования...
Дерального закона Российской Федерации «О таможенном регулировании в Российской Федерации», другими законами Российской Федерации...

Российской федерации iconРазвитие и постоянные существенные изменения правового регулирования...
Дерального закона Российской Федерации «О таможенном регулировании в Российской Федерации», другими законами Российской Федерации...

Российской федерации iconРоссийская федерация федеральный закон о социальной защите инвалидов в российской федерации
Конституцией Российской Федерации, а также в соответствии с общепризнанными принципами и нормами международного права и международными...

Российской федерации iconЗакон Российской Федерации от 25 октября 1991 г. №1807-1 «О языках народов Российской Федерации»
Конституция Российской Федерации в редакции Федерального конституционного закона от 30. 12. 2008 №6 и 7-фкз // Российская газета....

Российской федерации iconОб актуальных проблемах сохранения музейного фонда Российской Федерации
Российской Федерации от 12 февраля 1998 г. N 179, проблема сохранения музейных предметов и музейных коллекций относится к числу приоритетных...

Российской федерации iconРеферат на тему: «Герои Российской Федерации. Подвиг ценою в жизнь»
Федерации – это государственная награда Российской Федерации- россии, высшее звание, присваиваемое за заслуги перед государством...

Вы можете разместить ссылку на наш сайт:


Литература


При копировании материала укажите ссылку ©ucheba 2000-2015
контакты
l.120-bal.ru
..На главную