Geum.ru

Республики Беларусь «24»

Вид материалаПояснительная записка

Содержание


Структуры и организация данных в эвм
Кафедра программного обеспечения вычислительной техники и автоматизированных систем
Рекомендована к утверждению в качестве типовой
Разработана на основании Образовательного стандарта РД РБ 02100.5.112-98.
Содержание дисциплины
Примерный перечень лабораторных работ
Примерный перечень курсовых работ
Литература основная
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   18

Утверждена


УМО вузов Республики Беларусь

по образованию в области информатики

и радиоэлектроники

« 03 » июня 2003 г.

Регистрационный № ТД-40-003/тип.


^ СТРУКТУРЫ И ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ


Учебная программа для высших учебных заведений

по специальности І-40 01 01 Программное обеспечение

информационных технологий


Согласована с Учебно-методическим управлением БГУИР

« 28 » мая 2003 г.


Составитель:

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


Рецензенты:

А.Я. Кулешов, старший научный сотрудник лаборатории обработки и распознавания изображений Института технической кибернетики Национальной академии наук Беларуси, кандидат технических наук;

^ Кафедра программного обеспечения вычислительной техники и автоматизированных систем Учреждения образования «Белорусский национальный технический университет» (протокол № 15 от 06.05.2002 г.)


^ Рекомендована к утверждению в качестве типовой:

Кафедрой программного обеспечения информационных технологий Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники» (протокол № 16 от 18.03.2002 г.);


Научно-методическим советом по направлению І-40 Вычислительная техника УМО вузов Республики Беларусь по образованию в области информатики и радиоэлектроники (протокол № 2 от 20.06.2002 г.)


^

Разработана на основании Образовательного стандарта РД РБ 02100.5.112-98.




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



Типовая программа «Структуры и организации данных в ЭВМ» разработана в соответствии с Образовательным стандартом РД РБ 02100.5.112-98 для студентов специальности І-40 01 01 Программное обеспечение информационных технологий высших учебных заведений. Она предусматривает формирование представления о многообразии структур данных, способов описания объектов и процессов различных предметных областей, о влиянии выбранных структур данных на функции обработки и эффективность программных средств в целом. Целью изучения является получение теоретических сведений и практических навыков по выбору и разработке конкретных структур данных для представления объектов обработки и преобразования из одной формы представления в другую.

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

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

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

^

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ



Тема 1. ВВЕДЕНИЕ. ЦЕЛИ И ЗАДАЧИ КУРСА. ИНФОРМАЦИЯ И ЕЕ ПРЕДСТАВЛЕНИЕ В ПАМЯТИ. АДРЕСАЦИЯ ПАМЯТИ. АДРЕСНОЕ ПРОСТРАНСТВО, БАЗИРОВАНИЕ, СМЕЩЕНИЕ. СТРУКТУРИРОВАНИЕ АЛГОРИТМОВ И ДАННЫХ



Тема 2. БАЗОВЫЕ СТРУКТУРЫ ДАННЫХ

2.1. Примитивные структуры данных. Основные операции: создать, уничтожить, выбрать, обновить. Целые и действительные числа и их представление в памяти. Символьная информация и ее хранение. Логическая информация и ее хранение. Указатели и их хранение.

2.2. Статические структуры данных. Вектор. Матрица. Массив. Последовательное распределение памяти. Записи и таблицы. Структуры хранения в памяти. Множества и их хранение в памяти. Основные операции над множествами.


Тема 3. ДИНАМИЧЕСКИЕ СТРУКТУРЫ

3.1. Основные операции. Инфиксная, суффиксная и префиксная формы записи. Алгоритм вычисления суффиксных выражений. Корректность формул. Алгоритм преобразования инфиксного выражения в суффиксное. Алгоритм преобразования для выражения, содержащего скобки.

3.2. Использование суффиксного выражения для получения объектного кода. Устранение недостатков компиляции. Вычисление с помощью стека. Стековая машина.

3.3. Очередь. Основные операции. Простые и циклические очереди. Использование очереди несколькими процессами. Моделирование систем с разделением времени.

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


Тема 4. СТРОКОВЫЕ ПЕРЕМЕННЫЕ

Строковые данные. Формальные системы обработки строк. Алгоритмы Маркова. Основные понятия. Получение продукции. Алгоритмы с метками. Понятие грамматики. Назначение метаязыка. Форма Бэкуса–Наура. Синтаксическое дерево. Нисходящий и восходящий разбор. Лексический, синтаксический и семантический анализ.


Тема 5. НЕЛИНЕЙНЫЕ ДИНАМИЧЕСКИЕ СТРУКТУРЫ

5.1. Нелинейные структуры. Граф, дерево, текст. Способы представления деревьев. Построение предметного указателя. Бинарные деревья. Примитивные операции. Примеры приложений, поиск дубликатов. Представление арифметических выражений и распараллеливание.

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

Прошивка бинарных деревьев. Представление произвольного дерева в виде эквивалентного бинарного.

5.2. Граф. Формы представления: матричная, в виде списков вершин и ребер. Путевая матрица. Алгоритм определения цикличности (рекурсии). Использование списковых структур для представления графов.

Применение графов. Определение критического пути в ориентированном графе. Применение в машинной графике.

5.3. Многосвязные структуры. Представление разряженных матриц с помощью линейных списков и многосвязной структуры.


^ ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ЛАБОРАТОРНЫХ РАБОТ

  1. Использование базовых структур данных (вектор, матрица, массив, запись) для описания объектов.
  2. Использование стека. Преобразование инфиксной формы записи в суффиксную.
  3. Очередь. Моделирование работы системы разделения времени.
  4. Список. Построение связанных словарей.
  5. Деревья. Грамматический разбор предложений. Нисходящий разбор.
  6. Представление списков в виде бинарных деревьев.
  7. Прошивка бинарных деревьев.
  8. Представление графов в виде списковых структур.
  9. Определение скрытой рекурсии.
  10. Алгоритм Маркова.


^ ПРИМЕРНЫЙ ПЕРЕЧЕНЬ КУРСОВЫХ РАБОТ

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



^

ЛИТЕРАТУРА




ОСНОВНАЯ

  1. Вирт Н. Алгоритмы и структуры данных и программ. –М.: Мир, 1985.
  2. Берзтис А.Т. Структуры данных: Пер. с англ. –М: Статистика, 1985.
  3. Трамбле Ж., Соренсон П. Введение в структуры данных. –М.: Машиностроение, 1982.


ДОПОЛНИТЕЛЬНАЯ
  1. Костин А.Е., Шаньгин Я.Ф. Организация и обработка структур данных в вычислительных системах. –М.: Высш. шк., 1987.
  2. Языки программирования АДА, Си, Паскаль. Сравнение и оценка /Под ред. А. Фьюэра, Н. Джехани. –М.: Радио и связь, 1982.
  3. Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. –М.: Мир, 1989.
  4. Данные в языках программирования. –М.: Мир, 1982.
  5. Замулин А.В. Типы данных в языках программирования и базах данных. – Новосибирск: Наука, 1987.
  6. Бауэр Гооз Ф. Информатика. Вводный курс: В 2 кн. –М.: Мир, 1990.
  7. Кинг Д. Создание эффективного ПО. –М.:Мир,1991.