Структура действия и структуры данных

Структуры действия и структуры данных
Гергель В.П., профессор ,
директор института ИТММ
Тема 1:
Методы программирования - 2
Учебный курс:

Содержание
Глава 1. Структура действия и структуры данных
1.1. Структуры данных
Структуры данных, порождаемые структурой действия
Структуры данных, для которых возможны рекурсивные вычисления
Понятие структуры данных
Схема и экземпляр структуры данных
Именование элементов структуры
Вопросы для обсуждения
из 28
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

Общая схема отображения математических моделей на ЭВМ …
из 28
А=Ф(В)
(А – выходные данные, В – исходные данные, Ф – правило преобразования)
А1=Ф1 (В1)
При отображении модели на ЭВМ данные модели и необходимые преобразования реализуются при помощи уже существующих объектов на ЭВМ
Таких уровней декомпозиции может быть несколько
Y=F(X)
Y1=F1 (X1)
• • •
Подобная ситуация прослеживается и при разработке программ для автоматизации деятельности ЭВМ (реализация уровней программного обеспечения – снизу вверх)
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
? Отображение математических моделей на аппаратуру ЭВМ можно себе представить как последовательность этапов построения иерархически-согласованных моделей
Сверху вниз - этапы построения всё более конкретных и детальных моделей, ориентированных на отображение на аппаратуру ЭВМ
Снизу вверх - этапы построения всё более общих моделей, более приближённых к объектам исследования
Общая схема отображения математических моделей на ЭВМ …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Как правило, между моделями верхнего и нижнего уровня остаётся несколько нереализованных промежуточных слоёв и ликвидация этого разрыва и есть основная задача программиста.
Общий аппарат для построения программных систем - Структуры данных и структуры действий
Общая схема отображения математических моделей на ЭВМ
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
1. Структуры данных, порождаемые структурой действия
ЭВМ является универсальной, поскольку все операторы любого алгоритма разлагаются в последовательность базовых операций. Разложение оператора рождает разложение операнда
Пример: Скалярное произведение
(a,b)= a1·b1 + a2·b2 + a3·b3
Как располагать значения ?
а = (a1,a2,a3) или а = (a3,a1,a2)
? Структура операндов определяется структурой действия
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019
1.1. Структуры данных …

из 28
Запишем алгоритм скалярного произведения для произвольной длины вектора
,…
Результат шага даётся через результат предшествующего шага. Такое описание называется рекурсией. Даёт краткое описание процесса.
Индексы можно убрать в Σ, если используется значение только последней частичной суммы.
,…
2. Структуры данных, для которых возможны рекурсивные вычисления …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019
1.1. Структуры данных …

из 28
Пусть:
Элементы векторов располагаются
последовательно слева направо,
Имеется указатель текущего элемента,
Определена операция "следующий элемент"
Предыдущее значение суммы
Новое значение суммы
Начальная установка a1 b1
Начальное значение = 0
Конечное значение (ab)
2. Структуры данных, для которых возможны рекурсивные вычисления …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019
1.1. Структуры данных …

из 27
Введение рекурсии (реализация циклов) требует установления отношения следования между элементами данных (т.е. введение понятия соседства и перехода к следующему).
? Использование рекурсивно (итеративно) описанного действия предполагает наличие структуры операндов и эта структура является свойством операндов.
2. Структуры данных, для которых возможны рекурсивные вычисления …
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Одной из наиболее общих математических абстракций является понятие алгебраической системы < А, О, R >,
где
A - множество операндов
О - множество операций ,
R - множество отношений ,
- арность операций, - арность отношений
Если операций нет модель (структура)
Если отношений нет универсальная алгебра
3. Понятие структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019
1.1. Структуры данных …

из 28
Определение 1.1. Математическая структура
S = (M1,…,Mk; p1,…,ps)
есть одно или несколько множеств М1,…,Мк, элементы которых находятся в некоторых отношениях р1,…,ps.
М1,…,Мк – базисные множества структуры.
Каждое отношение pi есть двоичная функция, аргументами которой являются элементы базисного множества. Если аргументы функции находятся в отношении, то значение pi = ИСТИНА.
Определение 1.2. Структура данных есть модель данных в виде математической структуры.
3. Понятие структуры данных …
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

Примеры
множество операндов и операций и порядок их записи (арифметическое выражение),
множество узлов детали и порядок их соединения (чертеж),
множество людей и родственные связи между ними (генеалогическое дерево),
множество населенных пунктов и пути сообщения (карта)
из 28
3. Понятие структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019
1.1. Структуры данных …

из 28
Пример 1.1. Вектор a = (a1,…,an)
Модель вектора (структура данных)
Sa= (Ma, pa)
3. Понятие структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019
1.1. Структуры данных …

из 28
? Структуры с бинарными отношениями допускают случай графического изображения
элементы множества изображаются точками или кружками;
пары (ai,aj), для которых отношение истина, соединяются стрелкой от первого аргумента ко второму.
? Образ структуры с бинарными
отношениями - ориентированный граф.
1.1. Структуры данных …
3. Понятие структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Определение 1.3. Структуры, которым соответствует ориентированный граф с вершинами, лежащими на одной ломаной, называют линейными.
Есть два особых элемента:
начальный элемент a1: (∀j) p(aj,a1)=л
не имеет предшествующего элемента;
конечный элемент an: (∀j) p(an,aj)=л
не имеет следующего элемента.
1.1. Структуры данных …
3. Понятие структуры данных
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
(-8, 5, 0) ∈ R3 – вектор с конкретными
числовыми значениями
( a1, a2, a3) ∈R3 – вектор – переменная
Переменная – множество значений и имя, которому можно присвоить конкретное значение.
Sa – схема структуры
Sа* – экземпляр структуры (экземпляр) в
соответствии с КОДАСИЛ
1.1. Структуры данных …
4. Понятие схемы и экземпляра структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

4. Понятие схемы и экземпляра структуры данных …
из 28
Экземпляр
Наличие конкретных значений для элементов можно выразить при помощи отношения "иметь значение"
p1*(ai, αi)=и, если аi имеет значение αi
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Определение 1.4. Структура данных Sa*=(Ма, R; pa, p1*)
с установленными значениями элементов, называется экземпляром.
p1* - отражает не отношения между элементами,
а индивидуальные свойства элемента
Изолированные элементы множества, не связанные
стрелками, не изображаются на графе.
4. Понятие схемы и экземпляра структуры данных …
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Схема структуры
Отношение p1 является переменной величиной.
Определение 1.5. Структура данных Sa=(Ма, R; pa, p1),
которая соответствует рассмотрению структуры как переменной величины, называется схемой структуры.
4. Понятие схемы и экземпляра структуры данных …
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Определение 1.6. Отношения делят на две части:
- отношения, описывающие отношение следования элементов и необходимые для рекурсивно описанных операций, называемые основными (по ним и ведется классификация структур);
- прочие отношения описывают индивидуальные свойства элементов, и называются вспомогательными.
Алгоритм соответствует схеме структуры.
Вычисления соответствует экземпляру.
4. Понятие схемы и экземпляра структуры данных
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Различимость элементов данных, необходимая для указания этих элементов, обеспечивается путем присваивания им уникальных имен.
5. Именование элементов структуры…
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Наличие имен для элементов можно выразить при помощи отношения "иметь имя".
N – множество имен
p2 – отношение "иметь имя"
Sa*=(Ма, R, N; pa, p1*, p2*) – экземпляр
Sa=(Ма, R, N; pa, p1, p2) – схема
5. Именование элементов структуры…
1.1. Структуры данных …
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

из 28
Пример 1.2. Матрица A=(aij)
Элемент матрицы Матрица
Формальное определение матрицы ? Есть ли начальные и конечные элементы ?
5. Именование элементов структуры
1.1. Структуры данных
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

Понятие структуры данных
Линейные структуры
Схема и экземпляр структуры
Базисные и вспомогательные отношения
Примеры структур данных из 28
Заключение
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

Роль выделения структур данных при разработке программ
Способы представления структур в ЭВМ
из 28
Вопросы для обсуждения
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019

Структуры хранения данных
из 28
Следующая тема
Структуры данных и структуры действия
ИТММ ННГУ, 2002-2019