Программная инженерия Нижний Новгород 017 Лабораторный

1.3. Дисциплины, освоение которых необходимо при изучении данного курса 
Курс опирается на материал вводного курса «Языки и методы программирования», 
изучаемого в 1-2 семестрах и направленного на освоение компьютерных систем как 
инструмента автоматизации исполнения алгоритмов обработки информации (общее 
представление о компьютерных системах, понятие алгоритма, способы разработки 
алгоритмов, программа на языке высокого уровня, выполнение программы, тестирование и 
отладка, модульное и структурное программирование, основы объектно-ориентированного 
подхода к разработке программ).
В курсе используются основные понятия математической логики (логические 
переменные и операции двоичной логики), ряд понятий алгебры (алгебраические операции, 
циклическая группа), теория графов (орографы и их подграфы), дискретной математики 
(рекурсивные описания, конечные автоматы), понятия функций и математической 
структуры. 
5 

---

 
10 
2. Содержание курса
1. Структура действия и структуры данных. 
1.1. Структуры данных. 
1.1.1. Разложение действия на элементарные части (структура действия). Порождение 
структуры операндов структурой действия. 
1.1.2. Рекурсия как средство повышения эффективности программирования и 
определяемая ею собственная структура операндов (векторы, матрицы и др., 
примеры структур). 
1.1.3. Структура алгоритмов и структура данных. Связь с математическим понятием 
структуры. Графический образ структуры. 
1.1.4. Переменные величины и схемы структур. Значения переменных структур и 
экземпляры схем. Элементы структуры, имена, значения. Основные и 
вспомогательные базисные множества и отношения в структуре. 
1.2. Структуры хранения. 
1.2.1. Структуры хранения, представляющие структуры программ. 
1.2.2. Структура машинной памяти. Примеры структур хранения данных. Вектор 
памяти. Массивы. Адресная арифметика как средство задания отношений в 
структуре хранения. Структуры хранения, операции над структурами и типы. 
1.3. Динамические структуры. 
1.3.1. Переработка информации как преобразование структур данных. Преобразования, 
приводящие к рекурсивным отношениям исходных и результирующих структур. 
1.3.2. Динамические структуры - класс структур с частичным упорядочением (по 
включению) структур данных, примеры динамических структур (стеки, очереди, 
деки). 
1.4. Динамические структуры и структуры хранения. 
1.4.1. Динамические структуры и распределение памяти; средства поддержания 
динамической структуры. Выражение отношений программными средствами. 
Пример: структура типа стека и ее структура хранения. 
1.4.2. Сравнение структур хранения и хранения динамических структур. 
1.4.3. Хранение динамических структур при ограниченной памяти. Степень 
использования памяти. Управление размещением. Пример: организация хранения 
очереди; введение циклических структур. Пример: хранение двух стеков. 
Хранение 
нескольких 
динамических 
структур 
и 
необходимость 
перераспределения памяти в процессе обработки информации. 
1.5. Динамическое распределение памяти. 
1.5.1. Статическое и динамическое распределение памяти. Управление памятью. 
1.5.2. Управление памятью путем перепаковки структур хранения, представляющих 
отношения адресной арифметикой. Пример системы управления памятью путем 
перепаковки. Хранение нескольких стеков в общем массиве памяти (начальное 
распределение памяти; переполнение стека; оценка наличия свободной памяти; 
гипотеза о росте потребности в памяти; перераспределение свободной памяти; 
перепаковка памяти). 
1.5.3. Роль гипотез о росте структур при разработке систем управления памятью. 
Пример использования гипотезы о сохранении тенденции роста с момента 
7 
9 

---

 
11 
последней перепаковки. Система управления памятью и математическая модель 
распределения ресурса. 
1.6. Распределение памяти для структур хранения, представляющих основные 
отношения с помощью адресных указателей. 
1.6.1. Представление основных отношений с помощью адресных указателей 
(сцепление). Задание линейных структур сцеплением (ссылки, кванты памяти; 
звенья; указатель структуры и признак конца). Линейный список. 
1.6.2. Хранение динамических структур с использованием сцепления. Стек свободной 
памяти. Исключение операций перепаковки. Пример системы хранения стеков, 
очередей и деков.