Программа дисциплины «Структуры данных»

Вид материала

Программа дисциплины

Содержание II.Пояснительная записка 4.Учебная задача курса 5. Формы контроля Основные абстрактные типы данных Основные операторы множеств Методы анализа алгоритмов Управление памятью IV. Учебно-методическое обеспечение дисциплины 2. Тематика заданий по различным формам текущего контроля 3. Методические рекомендации (материалы) преподавателю 4. Методические указания студентам Тематический расчет часов Самостоятельная работа

Подобный материал:

• Программа дисциплины Базы данных Семестры, 12.06kb.
• Структура программы. Часть Структуры данных. 24. Классификация структур данных. Операции, 41.26kb.
• Рабочая программа дисциплины Структуры и алгоритмы обработки данных (Наименование дисциплины), 183.25kb.
• Рабочая программа дисциплины Структуры и алгоритмы обработки данных (Наименование дисциплины), 185.25kb.
• Программа дисциплины структуры и алгоритмы компьютерной обработки данных для специальности, 506.16kb.
• Рабочая программа дисциплины Структуры и алгоритмы компьютерной обработки данных (Наименование, 153.24kb.
• Программа дисциплины по кафедре Экономическая кибернетика Структуры данных, 333.41kb.
• Рабочей программы дисциплины Структуры и алгоритмы обработки данных по направлению, 21.62kb.
• Примерная рабочая программа по дисциплине: базы данных, 104.62kb.
• Цель любой программы обработка данных, т е. надо грамотно построить структуры данных, 165.23kb.

Г О С У Д А Р С Т В Е Н Н Ы Й У Н И В Е Р С И Т Е Т

ВЫСШАЯ ШКОЛА ЭКОНОМИКИ

ПЕРМСКИЙ ФИЛИАЛ


Программа дисциплины

«Структуры данных»

для направления 080700.62 «Бизнес-информатика»

(вторая ступень высшего профессионального образования)

Утверждена Учебно-методическим Советом ПФ ГУ-ВШЭ Председатель______________Третьякова Е.А. «_______»________________________2008 г.

Одобрена на заседании кафедры Информационные технологии в бизнесе протокол ______________________________________ Зав. кафедрой______________________Казаченко Т.А. «______»_________________________________2008 г.

Пермь 2008 год

II.Пояснительная записка

1. Автор программы: к.ф.-м.н., доцент Шестакова Л.В.

2. Требования к студентам: Данная дисциплина предназначена для студентов дневного отделения специальности «Бизнес-информатика». Для успешного изучения данного курса студенты должны владеть основными знаниями и навыками, полученными при изучении дисциплины «Информатика и программирование»: знать принцип организации и функционирования персонального компьютера в различных режимах, характеристики его основных устройств; знать принципы представления и кодирования информации различных типов (текстовой, графической) в памяти компьютера, знать основные алгоритмические структуры; иметь навыки программирования на каком-либо языке высокого уровня, например, Pascal.

3. Аннотация: Основная цель курса состоит в том, чтобы будущие специалисты в области компьютерных наук, являясь разработчиками алгоритмов и программных продуктов различного назначения, получили знания в области структур данных, необходимые в профессиональной деятельности. Структуры данных и алгоритмы являются фундаментом современной методологии разработки программ.

Программа курса предполагает проведение лекционных и лабораторных занятий в классе, оборудованном IBM-совместимыми компьютерами.

Обязательное программное обеспечение, используемое при изучении данного курса: операционная система Microsoft Windows XP со справочной системой, компилятор с языка высокого уровня, например, Pascal.

4.Учебная задача курса: В результате изучения курса студенты должны:

• знать основные этапы решения задачи на компьютере; различия между типом данных, структурой данных и абстрактным типом данных; основные абстрактные типы данных (списки, стеки, очереди; деревья); абстрактные типы данных, основанные на математической модели множеств; основные структуры данных, подходящие для представления графов.
  
• уметь реализовывать списки, стеки, очереди, отображения, деревья, множества.
  
• иметь представление о методах анализа программ, динамическом программировании, алгоритмах локального поиска, проблемах управления памятью.
  
• обладать навыками программирования на языке высокого уровня.
  
• 5. Формы контроля: При изучении курса предусмотрено несколько форм контроля:
  
• текущий контроль: согласно графику контрольных мероприятий выполняется домашнее задание;
  
• итоговый контроль заключается в проведении экзамена;
  
• итоговая оценка: складывается в соответствии с «Положением о рейтинге…», принятом в ПФ ГУ ВШЭ.
  

III. Содержание программы

1. Построение и анализ алгоритмов
   

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

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

Абстрактный тип данных список. Реализация списков посредством массивов, указателей. Реализация операторов списка. Абстрактный тип данных стек. Реализация стеков с помощью массивов. Реализация операторов стека. Абстрактный тип данных очередь. Реализация очередей посредством указателей, циклических массивов. Реализация операторов очереди. Отображения. Реализация отображений посредством массивов, списков. Стеки и рекурсивные процедуры.

3. Деревья
   

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

4. Основные операторы множеств
   

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

5. Методы анализа алгоритмов
   

Эффективность алгоритмов. Анализ рекурсивных программ. Решение рекуррентных соотношений. Общее решение рекуррентных уравнений.

6. Управление памятью
   

Проблемы управления памятью. Управление блоками одинакового размера. Управление блоками разного размера. Задача уплотнения памяти.

IV. Учебно-методическое обеспечение дисциплины:

1. Литература:

Базовые учебники:

1. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д.Ульман. Структуры данных и алгоритмы.: Уч.пос.-М.: Издательский дом «Вильямс», 2007.-400 с.
   

Основная:

1. . Н. Вирт. Алгоритмы и структуры данных. СПб.: издательство «Невский диалект», 2007.- 352 с.
   

Дополнительная:

1. С. Окулов, Основы программирования. М.:- Бином. Лаборатория знаний, 2006.-440 с.
   

2. Тематика заданий по различным формам текущего контроля:


Тематика домашнего задания:

1. Многочлен можно представить в виде связанного списка, где каждая ячейка имеет три поля: коэффициент, показатель степени, указатель на следующую ячейку. Для описанного представления многочлена напишите программу дифференцирования многочлена.
   
2. Многочлен можно представить в виде связанного списка, где каждая ячейка имеет три поля: коэффициент, показатель степени, указатель на следующую ячейку. Для описанного представления многочлена напишите программу сложения многочленов.
   
3. Многочлен можно представить в виде связанного списка, где каждая ячейка имеет три поля: коэффициент, показатель степени, указатель на следующую ячейку. Для описанного представления многочлена напишите программу умножения многочленов.
   
4. Очередь с двусторонним доступом – это список, в котором добавлять и удалять элементы можно с обоих концов. Разработать реализацию такой очереди с использованием массивов.
   
5. Очередь с двусторонним доступом – это список, в котором добавлять и удалять элементы можно с обоих концов. Разработать реализацию такой очереди с использованием указателей.
   
6. Очередь с двусторонним доступом – это список, в котором добавлять и удалять элементы можно с обоих концов. Разработать реализацию такой очереди с использованием курсоров.
   
7. Возможно хранение двух стеков в одном массиве, если один располагается в начале массива и растет к концу массива, а второй располагается в конце массива и растет к началу. Напишите процедуру PUSH(x, S) вставки элемента x в стек S, где S – один или другой из этих двух стеков.
   
8. Напишите программу вставки, удаления и поиска элементов отсортированного списка, используя для реализации списка массив.
   
9. Напишите программу вставки, удаления и поиска элементов отсортированного списка, используя для реализации списка указатели.
   
10. Напишите программу вставки, удаления и поиска элементов отсортированного списка, используя для реализации списка курсоры.
    

Перечень вопросов для самоконтроля студентов:

Перечень вопросов для самоконтроля студентов представлен в Приложении 1 «Перечень вопросов для самоконтроля по дисциплине «Структуры данных» для направления «Бизнес-информатика».


Тематика практических занятий:

Перечень практических занятий с указанием темы, плана семинара, заданиями для работы на семинаре представлен в Приложении 2 «Планы лабораторных занятий по дисциплине «Структуры данных» для направления «Бизнес-информатика».

3. Методические рекомендации (материалы) преподавателю:

На практических занятиях используются следующие методы обучения и контроля усвоения материала:

1. Выполнение работ по тематике занятия сопровождается контрольным опросом;
   
2. Обсуждение практических ситуаций.
   

4. Методические указания студентам:

Студенту рекомендуется следующая схема подготовки к лабораторному занятию:

1. проработать конспект лекций;
   
2. проанализировать основную и дополнительную литературу, рекомендованную по изучаемому разделу;
   
3. при затруднениях сформулировать вопросы к преподавателю.
   

3. Рекомендации по использованию информационных технологий:
   

Обязательное программное обеспечение, используемое при изучении данного курса: операционная система Microsoft Windows XP со справочной системой, компилятор с языка высокого уровня, например, Pascal.


Автор программы Л.В. Шестакова

к.ф.-м.н., доцент

5. Тематический расчет часов
   

№ п/п	Наименование разделов и тем	Аудиторные часы			Самостоятельная работа	Всего часов
		Лекции	Семинарские или практические занятия	Всего
	Построение и анализ алгоритмов	4	4	8	4	12
	Основные абстрактные типы данных	4	4	8	10	18
	Деревья	6	6	12	10	22
	Основные операторы множеств	6	6	12	10	22
	Методы анализа алгоритмов	4	4	8	8	16
	Управление памятью	4	4	8	10	18
	Всего:	28	28	56	52	108

Автор программы Л.В. Шестакова

к.ф.-м.н., доцент