Программа дисциплины по кафедре Экономическая кибернетика Структуры данных

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

Содержание

Пазюк К.Т.
Корнилов А.М.
Зубарев А.Е.
Лысак С.Г.
2 Требования к уровню освоения содержания дисциплины
3 Объем дисциплины и виды учебной работы
4 Содержание дисциплины
5 Практические занятия (семинары)
Краткие характеристики практических занятий
Конструирование системы линейных списков
Алгоритмическая реализация операции
Алгоритмы работы с бинарными деревьями
Многосвязное представление данных
Алгоритмы сортировки
6 Лабораторный практикум
Краткие характеристики лабораторных занятий
Операции с записями
Реализация дека в компьютере
Реализация очереди в компьютере
7 Контроль знаний студента
...
Полное содержание

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

Тихоокеанский государственный университет

Утверждаю

Проректор по учебной работе

______________ С.В. Шалобанов

“_____” ________________200_ г.

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

по кафедре Экономическая кибернетика

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

Утверждена научно-методическим советом университета для направлений подготовки(специальностей) в области экономики и управления

специальности : «Прикладная информатика в экономике»

Хабаровск 2007 г.

Программа разработана в соответствии с требованиями государственного образовательного стандарта, предъявляемыми к минимуму содержания дисциплины и других стандартов с учетом особенностей региона и условий организации учебного процесса Тихоокеанского государственного университета.

Программу составил (и)

	Серебрякова Т.А.	Ст. преподаватель, кафедра «ЭК»


	Ф.И.О. автора (ов)	Ученая степень, звание, кафедра

Программа рассмотрена и утверждена на заседании кафедры протокол № ______ от «____»__________________ 200_г
Зав.кафедрой__________«__»______200_г			Пазюк К.Т.
Подпись дата			Ф.И.О.

Программа рассмотрена и утверждена на заседании УМК и рекомендована к изданию протокол № ______ от «____»_____________ 200_г
Председатель УМК _______«__»_______ 200_г				Корнилов А.М.
Подпись дата				Ф.И.О.

Директор института _______«__»_______ 200_г	Зубарев А.Е.
(декан факультета) Подпись дата	Ф.И.О.

Директор института _______«__»_______ 200_г	Лысак С.Г.
(декан факультета) Подпись дата	Ф.И.О.

1 Цели и задачи дисциплины

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

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

В конечном итоге программы представляют собой конкретные формулировки абстрактных алгоритмов, основанные на конкретном языке и структурах данных. Алгоритмы и структуры данных всегда используются совместно: выбор алгоритма существенно зависит от структуры данных и наоборот (хотя интуитивно понятно, что структуры данных - первичны). Поэтому главная задача дисциплины «Структуры данных» научить студентов представлять данные на физическом и логическом уровнях для целенаправленного их использования при разработке прикладных и системных программ; применять базовые алгоритмы программирования при создании прикладного и системного программного обеспечения.

Курс базируется на понятиях, изучаемых в дисциплинах:

- математика;

- информатика;

- дискретная математика;

- алгоритмические языки программирования;

- вычислительные машины, системы, сети и телекоммуникации.

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

- основные типы нелинейных структур данных: мультисписки, древовидные и многосвязные структуры;

- основные алгоритмы обработки структур данных: пополнения, удаления, модификации и поиска данных.

После изучения курса студент должен

знать:

- классификацию структур данных, их особенности, организацию и их представление в памяти ЭВМ;

- типичные операции над структурами данных, их возможности, особенности использования и реализацию;

- средства построения алгоритмов, их свойства и средства описания и изображение ;

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

- существующие технологии проектирования программных продуктов и особенности их выполнения;

- современные технологии программирования, их возможности, особенности использования;

- использование на разных этапах компьютерной обработки программ;

уметь:

- использовать оптимальные структуры данных при решении инженерных и экономических задач, задач управления и построением баз данных с точки зрения потребности минимальных ресурсов;

- определять операции над структурами данных;

- для поставленной задачи обоснованно выбрать соответствующие структуры данных и алгоритмы их обработки, оценить сложность этих алгоритмов;

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

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

Задачей курса является создание теоретической основы для следующих дисциплин:

- операционные системы, среды и оболочки;

- базы данных;

- объектно-ориентированные языки программирования.

2 Требования к уровню освоения содержания дисциплины

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

– освоить теоретическую часть курса на уровне, обеспечивающем ориентацию в основных принципах и направлениях развития, выбор математических методов и реализующих их программных средств для решения конкретных задач;

– приобрести практические умения и навыки при решении задач.

3 Объем дисциплины и виды учебной работы

Таблица 1. Объем дисциплины и виды учебной работы

Наименование	По учебным планам (УП)
Наименование	с максимальной трудоёмкостью	с минимальной трудоёмкостью
Общая трудоёмкость дисциплины по ГОС по УП	153
Изучается в семестрах	3
Вид итогового контроля по семестрам зачёт экзамен курсовой проект (КП) курсовая работа (КР) расчётно-графическая работа (РГР) реферат (РФ) домашние задания (ДЗ)	3
Аудиторные занятия по семестрам Всего В том числе: лекции (Л) лабораторные занятия (ЛР) практические занятия (ПЗ)	85
	34
	34 17
Самостоятельная работа Общий объем часов (С₂) В т.ч. на подготовку к лекциям на подготовку к лабораторным занятиям на подготовку к практическим занятиям на выполнение КР на выполнение РГР на написание РФ на выполнение ДЗ	68
	34 34

4 Содержание дисциплины

4.1 Разделы дисциплины и виды занятий и работ

Таблица 2. Разделы дисциплины и виды занятий и работ

№	Раздел дисциплины	Л	ЛР	ПЗ	КР	С2
1	Предмет и задачи дисциплины.	*	*	*
2	Последовательные и связанные структуры данных.	*	*	*
3	Списковые структуры данных.	*	*
4	Методы хеширования. Хеш-функция.	*
5	Мультисписки.	*		*
6	Древовидные структуры данных.	*	*
7	Сбалансированные деревья. Бинарные деревья поиска.	*	*	*
8	Многосвязные структуры данных	*		*
9	Алгоритмы, оперирующие со структурой типа графа.	*	*	*
10	Алгоритмы сортировки.	*	*	*
11	Теория сложности алгоритмов.	*		*
12	Файлы.	*

4.2. Содержание разделов дисциплины

Тема 1. Предмет и задачи дисциплины

Структура дисциплины. Задачи, преследуемые при изучении дисциплины. Иерархия структур данных: аппаратно-реализуемые типы, базовые типы алгоритмических языков, программно-реализуемые типы данных.

Тема 2 Последовательные и связанные структуры данных

Последовательные и связанные структуры данных. Описание структур хранения. Функция адресации для последовательных структур данных. Варианты структур хранения для массивов данных.

Тема 3. Списковые структуры данных

Списковые структуры данных. Сортировка и поиск в линейных списках.

Тема 4. Методы хеширования

Методы хеширования. Хеш-функция. Коллизии. Разрешение коллизий с использованием повторного, двойного хеширования, метода цепочек. Выбор хеш-функции.

Тема 5. Мультисписки

Мультисписки. Понятие мультисписка. Использование мультисписков для работы с разреженными матрицами.

Тема 6. Древовидные структуры данных.

Древовидные структуры данных.Ориентированные, упорядоченные и бинарные деревья. Математические объекты, приводящие к древовидным структурам. Структуры хранения для деревьев. Операции над деревьями: преобразование деревьев, обход и прошивка дерева

Тема 7. Сбалансированные деревья. Бинарные деревья поиска

Сбалансированные деревья. Бинарные деревья поиска. Идеально сбалансированные деревья. Сбалансированные деревья. Пополнение сбалансированных деревьев

Тема 8. Многосвязные структуры данных

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

Тема 9. . Алгоритмы, оперирующие со структурой типа графа

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

Тема 10. Алгоритмы сортировки

Алгоритмы сортировки. Задачи сортировки, внутренняя и внешняя сортировка, алгоритмы сортировки вставкой, выбором, обменом. Анализ сложности и эффективности алгоритмов поиска и сортировки

Тема 11. Теория сложности алгоритмов.

Теория сложности алгоритмов: NP сложные и труднорешаемые задачи.

Тема 12. Файлы

Файлы. Организация и обработка файлов, представление файлов В-деревьями

5 Практические занятия (семинары)

Таблица 3. Практические занятия

№	№ раздела дисциплины	Наименование тем
1	1	Алгоритмы программной реализации динамических структур данных
2	2	Конструирование системы линейных списков по заданному документу
3	5	Алгоритмическая реализация операции с разреженными матрицами на базе мультисписков
4	7	Алгоритмы работы с бинарными деревьями
5	8	Многосвязное представление данных
6	9	Алгоритмы, использующие матричное описание графа
7	10	Алгоритмы сортировки
8	11	Теория сложности алгоритмов

Краткие характеристики практических занятий

Алгоритмы программной реализации динамических структур данных Задание. Семинар на тему: «Алгоритмы программной реализации динамических структур данных»

Время выполнения заданий: 2 часа.

Конструирование системы линейных списков

Задание: Реализация операции «Конструирование системы линейных списков по заданному документу».

Время выполнения заданий: 2 часа.

Алгоритмическая реализация операции

Задание. Реализация операции : «Алгоритмическая реализация операции с разреженными матрицами на базе мультисписков».

Время выполнения заданий: 2 часа.

Алгоритмы работы с бинарными деревьями

Задание.: Реализация операции «Алгоритмы работы с бинарными деревьями».

Время выполнения заданий: 2 часа.

Многосвязное представление данных

Задание. Реализация операции: «Многосвязное представление данных».

Время выполнения заданий: 2 часа.

Алгоритмы, использующие матричное описание графа

Задание. Семинар на тему: «Алгоритмы, использующие матричное описание графа».

Время выполнения заданий: 2 часа.

Алгоритмы сортировки

Задание. Семинар на тему: «Алгоритмы сортировки».

Время выполнения заданий: 3 часа.

Теория сложности алгоритмов

Задание. Семинар на тему: «Теория сложности алгоритмов».

Время выполнения заданий: 2 часа.

6 Лабораторный практикум

Таблица 4. Лабораторные занятия

№	№ раздела дисциплины	Название лабораторной работы
1	2	3
2	1	Операции со строками
3	1	Операции с записями.
1	2	Работа с массивами
4	2	Множества
5	3	Реализация списков в компьютере
	5	Реализация двунаправленных списков в компьютере
9	6	Реализация бинарных деревьев в компьютере
6	8	Реализация стека в компьютере
7	9	Реализация дека в компьютере
8	10	Реализация очереди в компьютере

Краткие характеристики лабораторных занятий

Операции со строками

Задание:

Вариант 1. Дана символьная строка. Если какой-то символ встречается в ней более одного раза, первое вхождение этого символа оставить без изменения, второе – заменить цифрой «2», третье – «3» и т.д.

Вариант 2. Дана символьная строка, содержащая русские слова, записанные строчными буквами, разделенные пробелами. Заменить первые буквы слов на прописные, а между ними оставить по одному пробелу.

Вариант3. Дана символьная строка. Если какой-то символ в ней встречается более одного раза, оставить только первое вхождение.

Вариант 4. Дана символьная строка. Русские буквы а, е, о, э в ней нужно удвоить, а между словами оставить только по одному пробелу.

Вариант 5. Дана символьная строка, содержащая русские буквы, цифры и пробелы. Написать строку задом наперед, удалив из нее все цифры и пробелы.

Вариант 6. Дана символьная строка. Определить, содержит ли строка числа, если да, то вывести на экран только четные.

Вариант 7. Дана символьная строка, состоящая из строчные букв русского и латинского алфавита без пробелов. Гласные латинские буквы в ней нужно заменить на соответствующие прописные буквы, а каждые пять символов разделить пробелами.

Вариант 8. Дана символьная строка. Вывести на экран только те символы, которые встречаются в ней более трех раз, для каждого из этих символов указать точное количество повторений.

Вариант 9. Дана символьная строка. Удалить из нее все символы, не являющиеся заглавными буквами русского или латинского алфавита.

Вариант 10. Дана символьная строка, содержащая два предложения, каждое из которых заканчивается точкой. Поменять их местами, сохранив порядок слов в предложениях.

Исполнение: получение практических навыков в работе со строками и символами.

Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, язык программирования Pascal версии 0.95 или выше.

Оценка: Рассматривают содержание направления информатики структуры данных и особенности их реализации.

Время выполнения работы: 2 часа.

Операции с записями

Задание:

Вариант 1. Разработать базу данных «Абитуриенты» (фамилия, имя, адрес, оценки по трем экзаменам, средний балл). Вывести на экран данные по абитуриентам, сдавшим вступительные экзамены со средним баллом не ниже 4,5 .

Вариант 2. Разработать базу данных «Отдела кадров университета» (фамилия, имя, отечество, стаж педагогической деятельности). Вывести на экран данные по преподавателям, имеющих стаж более 10 лет.

Вариант 3. Разработать базу данных «Научно-техническая библиотека» (фамилия, имя, отечество, автор книги, название книги, город и издательство, год выпуска, тематика). Вывести на экран данные о книгах по программированию.

Вариант 4. Разработать базу данных «Легковые автомобили». Название (марка), завод-изготовитель, год выпуска, стоимость. Вывести на экран данные обо всех автомобилях стоимостью менее 80 тысяч рублей.

Вариант 5. Разработать базу данных «Администратор железнодорожных касс» (номер поезда, пункты и время отправления и прибытия). Вывести на экран данные о поездах, следующих до Екатеринбурга.

Вариант 6. Разработать базу данных «Магазин по продаже персональных компьютеров» (процессор, ОЗУ, ПЗУ, винчестер и т.п., стоимость). Вывести на экран данные о компьютерах, стоимость которых менее 16 тысяч рублей.

Вариант 7. Разработать базу данных «Районная поликлиника» (фамилия, имя, отечество, адрес, рост, вес, давление). Вывести на экран данные по гипертоникам.

Вариант 8. Разработать базу данных «Кондитерская» (наименование тортов, способ изготовления, цена срок годности, калорийность). Вывести а экран данные о бисквитных тортах.

Вариант 9. Разработать базу данных «Домашняя фонотека» (название аудиокассет, компакт дисков, авторы и исполнители песен). Вывести на экран данные о произведениях одного автора.

Вариант 10. Разработать базу данных «Список родственников» (фамилия, имя, отечество, дата рождения, адрес, № телефона). Вывести на экран данные обо всех родственниках, родившихся в январе.

Исполнение: получение навыков в организации ввода/выводы значений комбинированных типов данных, получение практических навыков программирования задач с использованием записей; получение навыков в задании переменных множественного типа и выполнение простейших операций над ними, знакомство с задачами, в которых целесообразно использовать переменные множественных типов.

Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, язык программирования Pascal версии 0.95 или выше.

Оценка: Рассматривают содержание направления информатики структуры данных и особенности их реализации.

Время выполнения работы: 2 часа.

Работа с массивами

Задание:

Вариант 1. В массиве из 20 целых чисел найти наибольший элемент и поменять его местами с первым элементом.

Вариант 2. В массиве из 10 целых чисел найти наименьший элемент и поменять его местами с последним элементом.

Вариант 3. В массиве из 15 вещественных чисел найти наибольший элемент и поменять его местами с последним элементом.

Вариант 4. В массиве из 25 вещественных чисел найти наименьший элемент и поменять его местами с первым элементом.

Вариант 5. Упорядочить по неубыванию массив, содержащий 20 целых чисел.

Вариант 6. Упорядочить по невозрастанию массив, содержащий 15 вещественных чисел.

Вариант 7. Дан массив целых чисел, содержащий 20 элементов, записать в этот же массив сначала все отрицательные числа и нули, затем все положительные, сохраняя порядок их следования.

Вариант 8. Дан массив целых чисел, содержащий 10 элементов, записать в этот же массив сначала все положительные, затем все отрицательные числа и нули, сохраняя порядок их следования.

Вариант 9. Дан массив вещественных чисел, содержащий 15 элементов, записать в этот же массив сначала все отрицательные числа и нули, затем все положительные, сохраняя порядок их следования.

Вариант 10. Дан массив вещественных чисел, содержащий 15 элементов, записать в этот же массив сначала все отрицательные числа, затем нули, затем все положительные.

Исполнение: Получение практических навыков в работе с массивами, знакомство с алгоритмами упорядочения.

Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, язык программирования Pascal версии 0.95 или выше.

Оценка: Рассматривают содержание направления информатики структуры данных и особенности их реализации.

Время выполнения работы: 4 часа.

Множества.

Задание:

Вариант 1. Даны три множества Х1,Х2, Х3, содержащие целые числа из диапазона [1..100]. Сформировать новое множество Y=

, из которого выделить подмножество чисел, кратных 3.

Вариант 2. Даны три множества Х1,Х2, Х3, содержащие целые числа из диапазона [1..100]. Сформировать новое множество Y=

, из которого выделить подмножество нечетных чисел.

Вариант 3. Дано множество, состоящее из различных символов. Вывести на экран упорядоченные по убыванию символы русского алфавита.

Вариант 4. Даны множества Х1 и Х2, содержащие целые числа из диапазона [1..255]. Сформировать новое множество Y=

и выделить из него все четные числа и числа, делящиеся без остатка на 19.

Вариант 5. Дано множество Х1, содержащее целые числа из диапазона [1..255]. Сформировать новое множество Y путем выделения из множества Х1 нечетных чисел и чисел, делящихся без остатка на 17.

Вариант 6. Дано множество Х1, содержащее целые числа из диапазона [50..100]. Сформировать новое множество Y1 путем выделения из множества Х1 нечетных чисел и множество Y2 путем выделения из множества Х1 чисел кратных 5. на экран вывести множество

.

Вариант 7. Дано множество Х1, содержащее символы из диапазона [a..z]. Сформировать новое множество Y1 путем выделения из множества Х1 всех символов в алфавите позже f и раньше m, и множество Y2 путем выделения из множества Х1 символов, расположенных раньше g или позже j. На экнран вывести множество

.

Вариант 8. Ввести с клавиатуры множество – последовательность символов из диапазона от А до Я. Определить число различных (без повторений) букв, входящих в данную последовательность.

Вариант 9. Написать программу для проверки правильности ввода букв латинского алфавита. Если введенный символ не является буквой латинского алфавита, вывести на экран соответствующее сообщение. Результат ввода вывести на экран.

Вариант 10. подсчитать по введенном текстовом отрывке отдельно количество цифр, латинских букв и знаков пунктуации.

Исполнение: получение навыков в организации ввода/выводы значений комбинированных типов данных, получение практических навыков программирования задач с использованием записей; получение навыков в задании переменных множественного типа и выполнение простейших операций над ними, знакомство с задачами, в которых целесообразно использовать переменные множественных типов.

Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, Pascal версии 0.95 или выше.

Оценка: Рассматривают содержание направления информатики структуры данных и особенности их реализации.

Время выполнения работы: 2 часа.

Реализация списков в компьютере

Задание:

инициализация списка: присвоение текущему и начальному указателю неопределенного значения;
помещение в список элемента: если текущий указатель определен, то указатель вставляемого (нового) элемента устанавливается равным указателю текущего элемента, указатель текущего элемента устанавливается на вставляемый элемент, после чего текущий указатель устанавливается на вставляемый элемент, в противном случае текущий и начальный указатели устанавливаются на новый элемент, указатель которого устанавливается неопределенным;
получение значения текущего элемента;
изменение значения текущего элемента;
переход к следующему элементу;
переход к начальному элементу;
сортировка списка;
уничтожение списка.

Исполнение: Составлять алгоритм решения поставленной задачи.
Разрабатывать приложение для работы в операционной системе Windows .

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

Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, Pascal версии 0.95 или выше.

Оценка: Рассматривают содержание направления информатики структуры данных и особенности их реализации.

Время выполнения работы: 4 часа.

Реализация двунаправленных списков в компьютере

Задание:

инициализация списка: присвоение текущему, начальному и конечному указателю неопределенного значения;
помещение в список элемента: если текущий указатель определен, то вставка в список нового элемента, в противном случае текущий, конечный и начальный указатели устанавливаются на новый элемент, оба указателя которого устанавливаются неопределенными;
удаление элемента из списка: возможны четыре варианта, если удаляемый элемент: 1)неначальный и неконечный, 2)неначальный и конечный, то затем указатель на последний элемент устанавливается равным текущему указателю; 3)начальный и конечный (т.е. единственный в списке), то удалить текущий элемент и установить в текущий указатель неопределенное значение; 4)начальный и неконечный, то присвоить начальному и текущему указателям значение указателя на следующий элемент текущего элемента, удалить текущий элемент и затем присвоить указателю на предыдущий элемент нового текущего элемента неопределенное значение;
получение значения текущего элемента;
изменение значения текущего элемента;
переход к следующему элементу;
переход к предыдущему элементу;
переход к начальному элементу;
переход к конечному элементу;
уничтожение списка.

Исполнение: Составлять алгоритм решения поставленной задачи.
Разрабатывать приложение для работы в операционной системе Windows .

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

Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, Pascal версии 0.95 или выше.

Оценка: Рассматривают содержание направления информатики структуры данных и особенности их реализации.

Время выполнения работы: 4 часа.

Реализация бинарных деревьев в компьютере

Задание:

инициализация бинарного дерева: текущий указатель устанавливается неопределенным, а количество узлов нулевым;
помещение в бинарное дерево элемента: для нового элемента в бинарном дереве создается соответствующий узел, указатели на преемников которого пусты (поиск позиции для такого узла начинается с корня и проходит согласно правилам, определяющим структуру бинарного дерева);
получение значения текущего элемента;
переход к корню;
переход к левому преемнику;
переход к правому преемнику;
переход к предшественнику;
поиск заданного элемента: если искомый элемент находится в дереве, то текущий указатель устанавливается на него и возвращается сигнализирующее об успехе поиска значение, в противном случае только возвращается сигнализирующее о неуспехе поиска значение;
уничтожение бинарного дерева.

инициализация стека: создание циклического двунаправленного списка заданной длины и присвоение указателю стека указателя на начало этого списка;
помещение в стек элемента: помещение в позицию указателя стека элемента и сдвиг указателя стека на одну позицию в сторону конца списка;
извлечение элемента из стека: сдвиг указателя стека на одну позицию в сторону начала списка и извлечение из позиции указателя стека элемента;
уничтожение стека.

инициализация дека: создание циклического двунаправленного списка заданной длины и присвоение указателям дека ссылок на смежные элементы этого списка;
помещение в дек элемента в позицию 1-го указателя: если 1-й указатель дека не равен 2-му, то помещение в позицию 1-го указателя элемента и сдвиг этого указателя на одну позицию в сторону от 2-го указателя;
помещение в дек элемента в позицию 2-го указателя: если 2-й указатель дека не равен 1-му, то помещение в позицию 2-го указателя элемента и сдвиг этого указателя на одну позицию в сторону от 1-го указателя;
извлечение элемента из дека с позиции 1-го указателя: если дек не пуст, то сдвиг 1-го указателя на одну позицию в сторону 2-го указателя и извлечение из позиции 1-го указателя элемента;
извлечение элемента из дека с позиции 2-го указателя: если дек не пуст, то сдвиг 2-го указателя на одну позицию в сторону 1-го указателя и извлечение из позиции 2-го указателя элемента;
уничтожение дека.

Исполнение: Составлять алгоритм решения поставленной задачи.
Разрабатывать приложение для работы в операционной системе Windows .

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

Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, Pascal версии 0.95 или выше.

Оценка: Рассматривают содержание направления информатики структуры данных и особенности их реализации.

Время выполнения работы: 4 часа.

Реализация очереди в компьютере

Задание:

инициализация очереди: создание циклического однонаправленного списка заданной длины и присвоение начальному и конечному указателям позиции начала списка;
помещение в очередь элемента: если количество элементов в очереди меньше длины списка, то помещение в позицию конечного указателя элемента, сдвиг конечного указателя на следующую незанятую позицию в списке и увеличение количества элементов в очереди на 1;

7 Контроль знаний студента

7.1 Входной контроль

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

7.2 Текущий контроль

Текущий контроль знаний осуществляется в процессе выполнения практических заданий путём индивидуального и группового опроса, собеседования; защиты лабораторных работ. Результаты текущего контроля знаний учитываются при промежуточной аттестации и зачёте. Примерный перечень вопросов:

Основные алгебраические структуры.
Множества и их спецификации.
Булева алгебра.
Основные понятия теории графов.
Алгоритмы представления, хранения и обработки текстовой и числовой информации.
Стандартные типы данных.
Типы данных, определенные пользователем.
Записи.
Файлы.
Динамические структуры данных.
Программирование рекурсивных алгоритмов.

7.3 Выходной контроль

Зачет по дисциплине включает в себя отчет по лекционному материалу, и лабораторным занятиям.

Примерный перечень вопросов к зачету по всему курсу:

Классификация структур данных.
Массивы. Функция адресации.
Линейные списки. Основные процедуры по ведению линейных списков.
Стек и очередь в форме связанных списков.
Сортировка записей списка.
Поиск записей в списках.
Процедуры хеширования и поиск данных.
Представление древовидных структур.
Бинарные деревья. Формы представления бинарных деревьев.
Обход бинарного дерева. Понятие о прошивке бинарных деревьев.
Основные функции по обработке бинарных деревьев.
Сортировка массивов выбором.
Сортировка массива включением.
Сортировка массива обменом.
Деревья поиска и их построение.
Идеально сбалансированные и сбалансированные бинарные деревья.
Добавление вершин в сбалансированное дерево.
В-деревья.
Графы и их представление в ЭВМ.
Матрица смежности графа и булевы операции над нею.
Путевая матрица графа.
Связанное представление графа.
Сетевые структуры и их применение.
Принципы хранения файлов.
Реализация метода ветвей и границ.
Теория сложности алгоритмов.

9 Контроль самостоятельной работы студентов-заочников

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

Исполнение: Составлять алгоритм решения поставленной задачи.
Разрабатывать приложение для работы в операционной системе Windows .

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

Содержание задания:

Разработать информационную системы с применением динамических структур данных. Для решения поставленной задачи рекомендуется использовать динамические структуры (списки, деревья, очереди, стеки и т.п.) в том случае, если для решения поставленной задачи их использование окажется более целесообразным. Обеспечить возможность выполнения следующих операций над выбранными структурами данных:

инициализацию;
добавление новых элементов;
удаление элементов;
перемещение по структуре данных;
поиск элементов структуры данных, отвечающих заданным критериям;
вывод всех элементов структуры данных на экран.

Порядок выполнения работы:

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

Содержание пояснительной записки:

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

Номер варианта для выполнения контрольной работы выбирается по последней цифре зачетной книжки.

Варианты:

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

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

10.1 Рекомендуемая литература

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

Альфред Ахо, Джон Э. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. - М.: Издательский дом "Вильямс", 2001. – 384 с.
Арт Фридман, Ларс Кландер, Марк Михаэлис, Херб Шильдт. С/С++ Алгоритмы и приемы программирования.-М.: Издательство БИНОМ,2003.-560с.
Ахо А.В. Структуры данных и алгоритмы:Пер. с англ. / Хопкрофт Д.Э., Ульман Д.Д. - М.,Спб,Киев: Вильямс, 2001
Браун Кен. Основные концепции структур данных и реализация в С++. -М.: Мир., 2002.– 320 с.
Голубь. Н.Г.. Искусство программирования на ассемблере. Лекции и упражнения.СПб.: ООО «ДиаСофтЮП», 2002. – 656 с.
Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. -М.:"Мир", 1976. - 734 с.
Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., "Мир", 1978 г., переиздание - М.,Изд-во "Вильямс", 2000 г.
Дейт К.Дж. Введение в системы баз данных: Пер. с англ. - М.,Спб.,Киев: Вильямс, 2001
Н. Вирт. Алгоритмы и структуры данных.- М.:Мир – 2001.– 352 с.
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. -М.: МЦНМО, 2001. – 960 с.
Широков Л.А Исследование систем управления: Учеб. пособие Ч.1: Объекты системного исследования. Структурное и информационное моделирование систем управления. - М.: МГИУ, 1999
Э. Майника. Алгоритмы оптимизации на сетях и графах.–М.: Мир., 1981.– 324 с.

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

Кормен Т. Алгоритмы: построение и анализ. / Лейзерсон Ч., Ривест Р. МЦМНО, 2001
. Макконнел Дж. Основы современных алгоритмов. Техносфера, 2002

Учебно-методическое обеспечение учебного процесса по курсу «Структуры данных» дополняется в ходе лекционных и лабораторных занятий.

11 Материально-техническое обеспечение дисциплины

Для освоения данной дисциплины необходима лаборатория, оснащенная локальной вычислительной сетью. В качестве рабочих станций целесообразно иметь персональные компьютеры с процессором не ниже Pentium и оперативной памятью не менее 32 Mб. Персональный компьютер с ОС Windows, MS Office, Pascal версии 0.95 или выше.

12 Методические рекомендации по организации изучения дисциплины

На основании программы разрабатываются рабочие учебные программы дисциплины с учетом фактического количества часов, отведенных на ее изучение. Исходя из этого, в рабочей программе отдельные разделы программы могут быть либо усилены, либо сокращены, либо опущены.

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

Базовыми для дисциплины являются курсы:

математика;

- информатика;

- дискретная математика;

- алгоритмические языки программирования;

- вычислительные машины, системы, сети и телекоммуникации.

Знания и навыки, полученные при изучении данного курса могут применяться студентами в дипломном проектировании.

Программа рассчитана на 153 часа.

Программа составлена в соответствии с государственными образовательными стандартами высшего профессионального образования.

Blog