Структуры и алгоритмы обработки данных

1. Структуры и алгоритмы обработки данных

Лекция 1. Введение
Б1.Б.10 Структура и алгоритмы обработки данных
Экзамен, курсовая работа 3 семестр
Зачет 4 семестр
Кафедра корпоративных информационных систем
Института информационных технологий, Г313
к.т.н., доцент Андрианова Елена Гельевна
[email protected] , [email protected]
+79037748505

2. Тренды ИТ-индустрии 2018

1. Облачные технологии
2. Интернет вещей
3. Технологии больших данных
4. Кибербезопасность
Следствие: вовлеченность бизнеса в IT-проекты.
«В соответствии с теорией циклов Кондратьева
современный IT-рынок находится в самом начале
очередного технологического цикла, который эксперты
называют NBIC-конвергенция (конвергенция нано-, био-,
информационных и когнитивных технологий). Она
должна стать таким же прорывом, как в свое время
прядильные, а потом паровые машины. И основной
будущий тренд в сфере услуг, не только в IT,
но и в конвергенции самых различных сервисов и услуг»
2

3. Тренды ИТ-индустрии 2018

О Digital McKinsey
Digital McKinsey – глобальная
экспертная группа, объединяющая
специалистов McKinsey по цифровым
технологиям.
В состав Digital McKinsey входят более
2 000 экспертов из разных стран мира,
среди которых более 800
разработчиков, проектировщиков, ИТархитекторов, специалистов по
обработке данных, тренеров по
внедрению методологии
Agile и консультантов,
специализирующихся на применении
передовых
аналитических методов.
3

4. Тренды ИТ-индустрии 2018

4

5. Тренды ИТ-индустрии 2018

5

6.

6

7.

7

8.

8

9.

9

10.

10

11.

11

12.

12

13.

13

14. Тенденция развития ИТ- индустрии

Постепенно ИТ перестает быть технической
дисциплиной, становясь фундаментом для бизнесов,
которые изначально далеки от информационных
технологий:
«Крупнейший в мире таксопарк UBER не имеет
автомобилей, самый популярный медиаресурс Facebook
не создает контента, одна из крупнейших розничных
компаний Alibaba не имеет собственных магазинов,
а огромная гостиничная сеть AirBnB не владеет ни одним
номером»
14

15. Программа «Цифровая Экономика»

15

16. Программа «Цифровая Экономика»

16

17. Программа «Цифровая Экономика»

17

18. Программа «Цифровая Экономика»

До 2024 года в России должно быть создано:
• 10 крупных высокотехнологичных ITкомпаний, которые смогут успешно
конкурировать на мировом рынке
• ещё 500 компаний малого и среднего
масштаба
• а также 10 платформ для различных отраслей
экономики.
На долю России должно приходиться 10% от
мирового объема услуг в сфере хранения и
обработки данных. В настоящее время этот
показатель составляет около 1%.
18

19. Программа «Цифровая Экономика»

Программа строится по пяти направлениям:
• нормативное регулирование
• образование и кадры
• формирование исследовательских компетенций и
технических заделов
• ИТ-инфраструктура
• кибербезопасность.
Основными сквозными цифровыми технологиями,
которые входят в рамки программы, являются:
• большие данные
• нейротехнологии и искусственный интеллект (ИИ)
• системы распределенного реестра
• квантовые технологии
• и новые производственные технологии.
19

20. Программа «Цифровая Экономика»

Помимо этого, авторы проекта собираются уделить
особое внимание:
• развитию промышленного Интернета
• компонентов робототехники и сенсорики
• технологиям беспроводной связи
• и виртуальной и дополненной реальности.
В разделе "Кадры и образование" прописано, что
количество выпускников организаций высшего
образования по направлениям подготовки,
связанным с информационнотелекоммуникационными технологиями, должно
составлять через восемь лет 120 тыс. человек в год.
20

21.

21

22.

Проблематика проектирования и реализации ИС
22

23. Модели данных

Структурой данных называют данные и совокупность правил и
ограничений, которые отражают связи, существующие между данными.
Другое определение звучит так:
Структуры данных – это объекты определенного уровня абстракции, для
представления которых в памяти компьютера можно использовать
различные структуры хранения данных (таблицы, стек, граф, списки,
дерево и т.п.).
Различают абстрактные структуры данных, используемые для уточнения
связей между элементами, и конкретные структуры, используемые для
представления данных в программах.
Все абстрактные структуры данных можно разделить на группы):
структуры, элементы которых никак не связаны между собой, структуры
с неявными связями элементов – таблицы, и структуры, связь элементов
которых указывается явно – графы.
23

24. Классификация абстрактных структур данных

В первую группу входят множества
и
кортежи,
характеристикой
элемента
которых,
является
принадлежность его некоторому
набору, т.е. отношение вхождения.
Данные
абстрактные
структуры
используют, если никакие другие
отношения элементов не являются
существенными для описываемых
объектов.
Ко второй группе относят векторы,
матрицы, массивы (многомерные),
записи, строки, а также таблицы,
включающие
перечисленные
структуры в качестве частей.
Существенным моментом этих структур, кроме вхождения элемента
данных в структуру, является их порядок, а также отношения
иерархии структур, т.е. вхождение структуры в структуру более
высокой степени общности.
В тех случаях, когда существенны связи элементов данных между
собой, в качестве модели структур данных используют графы.
24

25. Диаграммы Джексона

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

26. Диаграммы Джексона

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

27. Диаграммы Джексона

27

28. Диаграммы Джексона

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

29. Скобочные диаграммы Орра

Диаграмма Орра базируется на том же предположении о сходстве
структур программ и данных, что и диаграмма Джексона. Отличие
состоит лишь в нотации, т.е. в использовании фигурных скобок
29

30. Скобочные диаграммы Орра

30

31. Модели данных

Плюсы:·
• реляционный подход основывается
на небольшом количестве
интуитивно понятных абстракций,
на основе которых возможно
простое моделирование наиболее
распространенных предметных
областей; эти абстракции могут быть
точно и формально определены;
• теоретическим базисом
реляционного подхода к
организации БД служит простой и
мощный математический аппарат
теории множеств и математической
логики;
• реляционный подход обеспечивает
возможность ненавигационного
манипулирования данными без
необходимости знания конкретной
физической организации баз
данных во внешней памяти.
31

32. Модели данных

• Слабое представление сущностей реального мира. Процесс нормализации обычно
приводит к созданию дополнительных отношений (таблиц), которые не
соответствуют сущностям реального мира (моделируемой предметной области).
Фрагментация сущности предметной области на несколько отношений с физическим
представлением, которое отражает эту структуру, является неэффективным и
приводит к необходимости выполнения многих соединений в процессе обработки
запросов.
• Семантическая перегрузка. Реляционная модель обладает только одной
конструкцией для представления данных и связей между данными — отношением.
Для представления связи типа "многие ко многим" (*:*) между двумя сущностями А
и В необходимо создать три отношения: два для представления сущностей А и В, а
третье — для представления связи. При этом не существует механизма для
определения различий между сущностями и связями или между разными типами
связей, заданными между сущностями.
• Слабая поддержка ограничений целостности и корпоративных ограничений.
Целостность означает истинность и непротиворечивость хранимых данных и
выражается обычно в виде ограничений, отражающих правила, которые нельзя
нарушать в используемой БД. Многие СУБД не полностью поддерживают
возможность описания ограничений и их приходится встраивать в приложения. Это
небезопасно и может привести к дублированию кода и возникновению
противоречивых состояний. Также в реляционной модели не предусмотрены
средства поддержки корпоративных правил, что означает необходимость их
встраивания в СУБД или в приложение.
32

33. Модели данных

• Однородная структура данных. РМД предполагает как горизонтальную, так и
вертикальную однородность данных. Горизонтальная однородность означает, что
каждая строка в отношении должна состоять из одних и тех же атрибутов (столбцов).
А вертикальная однородность означает, что значения в некотором столбце
отношения должны принадлежать одному и тому же типу данных. Более того, на
пересечении строки и столбца должно находиться атомарное (неделимое) значение.
Эта фиксированная структура является слишком жесткой.
• Ограниченный набор операций. Реляционная модель обладает только
фиксированным набором операций, включающим операции с множествами и
кортежами (строками). Например, в геоинформационных системах требуется
обработка точек, линий, групп линий и многоугольников, имеющих географические
координаты, для работы с которыми необходимы операции определения
расстояния, нахождения пересечений и оценки включения.
• Трудности организации рекурсивных запросов. Атомарность данных означает, что в
РМД не допускаются повторяющиеся группы значений. В результате становится
чрезвычайно трудно выполнять рекурсивные запросы, т.е. запросы по отношению к
связям, которые (прямо или косвенно) соединяют отношение с самим собой.
• Проблема рассогласования. Языки, используемые для выборки данных из РСУБД, не
обладают вычислительной полнотой. Для преодоления этой трудности
предусмотрена возможность встраивания конструкций языка запросов (ЯЗ) в
высокоуровневые языки программирования (C, Pascal). Однако этот подход приводит
к возникновению проблемы рассогласования, вызванной смешиванием разных
парадигм программирования и необходимостью конвертаций значений типов
данных в различных языках.
33

34. Модели данных

Другие проблемы РСУБД, связанные с параллельностью, изменениями схемы и
слабыми средствами доступа. Транзакции в бизнес-процессах обычно являются
кратковременными, поэтому элементарные операции и протоколы управления
параллельностью, реализованные в РСУБД, плохо подходят для долговременных
транзакций, появляющихся при разработке сложных проектов. Так же имеются
трудности, связанные с изменениями схемы. Администраторам баз данных приходится
вносить изменения в структуру БД, что требует корректировки программ,
осуществляющих доступ к измененным структурам. Даже с использованием
современных технологий этот процесс выполняется очень медленно и громоздко.
Реляционные СУБД задумывались для реализации ассоциативного доступа с привязкой
к некоторому контексту, поэтому они обладают слабыми средствами навигационного
доступа, основанного на перемещении между отдельными записями. Этот тип доступа
особенно важен для многих сложных приложений.
34

35. Модели данных

Узлы представляют объекты предметной области, а связи между ними
определяются расположением узлов и ребер, которые, соединяя узлы, образуют
древовидную структуру. Объекты могут иметь одинаковый тип.
Между узлами может быть задано сразу несколько ссылок, например от
родительского к дочернему узлу и обратно. Упорядочивание указателей может быть
таким, что все однотипные экземпляры будут связаны вместе. На способ
организации ссылок влияет характер алгоритма обработки, который должна
поддерживать данная структура.
В обобщенном дереве типы записей обычно упорядочены внутри структуры, как
правило, слева направо. Экземпляры записей также обычно упорядочиваются. Этот
подход позволяет существенно повысить эффективность операций извлечения
данных.
35

36. Модели данных

Сетевая модель
данных (СМД)
состоит из записей,
элементов данных и
связей типа «один ко
многим» (1:*),
установленных
между записями.
Формального
определения СМД не
существует и
несмотря на
название,
происхождение этой
модели не основано
на использовании
графов. Для
рассматриваемой
модели данных был
разработан стандарт
CODASYL,
регламентирующий
типичную
реализацию СУБД
36

37. Модели данных

Пользователи осуществляют доступ к базе данных с помощью прикладной
программы, разработанной на базовом языке программирования. Для
осуществления доступа к БД программа использует некоторую подсхему, которая
является ограниченным представлением структуры всей базы данных. Несколько
программ могут параллельно использовать одну и ту же подсхему, однако каждая из
них использует только одну подсхему одновременно. Подсхема определяется только
на одной схеме, но может перекрывать другую подсхему. CODASYL-совместимая
СУБД поддерживает несколько различных баз данных, структура каждой из которых
определяется собственной схемой.
Схема и подсхемы определяются с помощью различных DDL-языков (язык SSDDL
является декларативным расширением языка программирования). Определив схему
с помощью языка SDDL, ее необходимо транслировать из исходной формы в
объектную. После этого исходное определение каждой подсхемы также должно
быть транслировано с преобразованием в объектную форму — только после этого
оно сможет использоваться прикладной программой.
37

38. Модели данных

Внутри прикладной программы имеется временное хранилище, которое предназначено
либо для сохранения данных, извлекаемых из локального вспомогательного источника,
либо для размещения данных перед их сохранением в БД. Временное хранилище
необходимо и в тех случаях, когда программа работает с СУБД, поскольку здесь также
имеет место обмен данными между прикладной программой и базой данных.
Использование подсхемы в прикладной программе вызывает неявное создание
элементов этой подсхемы во временном хранилище. Пространство, зарезервированное
для элементов подсхемы, называется рабочей областью пользователя (User Work Area —
UWA), или UWA-областью.
Самые последние предложения комитета CODASYL касаются определения языка
описания хранилища данных или DDL-языка внутренней схемы, с помощью которых
определяются детали физической организации хранения информации. Эти подробности
включают определение исходного размера области хранения, указание того, где и как
хранятся записи, определение формата внутренних элементов данных, определение
индексов и указание характеристик хранения наборов. Некоторые выражения SDDLязыка, которые на самом деле определяют физическое устройство (а потому снижают
физическую независимость от данных), были перемещены в DDL-язык внутренней
схемы. Соответствующие изменения также предлагались для языка SDDL.
38

39. Модели данных

Объектно-ориентированный подход сегодня является одним из часто используемых,
применяемых при разработке программного обеспечения (ПО). Базовым понятием
объектно-ориентированной технологии является то, что всё ПО должно создаваться на
основе стандартных и повторно используемых компонентов. Традиционно разработку
программного обеспечения и управление базами данных представляли собой
совершенно разные дисциплины. Технология баз данных опирается на статические
концепции хранения информации, тогда как технология создания программного
обеспечения моделирует динамические аспекты. С появлением объектноориентированных СУБД (ООСУБД) (и в некоторых случаях объектно-реляционных СУБД
(ОРСУБД)) эти две дисциплины соединились воедино, что позволило параллельно
моделировать данные и процессы, воздействующие на эти данные (изменяющие их).
39

40. Модели данных

40

41. Модели данных

41

42. Модели данных

42

43. Модели данных

43

44. Модели данных

44

45. Модели данных

В левой нижней части
представлены приложения
для обработки простых
данных, не предъявляющие
каких-либо требований по
выполнению запросов к
информации. К ним
относятся стандартные
пакеты обработки текстов,
таблиц, графические
редакторы и т.д., то есть те
приложения, которые
используют операционную
систему для получения
доступа к хранящимся
данным.
В нижней правой части рисунка показаны приложения, обрабатывающие сложные данные, которые
также не предъявляют серьезных требований в отношении выполнения запросов. Для таких
программ, как пакеты автоматизированного проектирования, наиболее подходящим вариантом
использования является ООСУБД. В верхней левой части находятся приложения, использующие
простые данные, но нуждающиеся в выполнении сложных запросов. К этой категории можно отнести
типовые программы, автоматизирующие деятельность предприятия (учётные системы), для которых
наиболее подходящим типом СУБД являются реляционные СУБД. В верхней правой части
располагаются приложения, связанные с обработкой сложных данных, в отношении которых
требуется выполнять сложные запросы. Для их создания лучше всего подходят объектнореляционные СУБД.
45

46. Модели данных -Слабо- полу-структурированная модель данных

Слабоструктурированными данными (ССД) называют данные, которые являются
недостаточно формализованными, или неполными, и имеют структуру, которая
впоследствии может непредсказуемо измениться.
Подобная информаций не может быть описана с помощью определённой неизменной
схемы, поэтому иногда её называют не имеющей схемы или описывающей саму себя.
Характерной особенностью слабоструктурированных данных является то, что
описательная информация, которая обычно выделяется в отдельную схему, присутствует
в самих данных. В некоторых формах представления ССД не предусмотрено применение
отдельной схемы, но если она существует, то налагает на информацию очень слабые
ограничения. В отличие от этого, для реляционных СУБД требуется заранее
определенная схема, позволяющая распределить данные по таблицам, а вся
информация, которая управляется этой системой, должна соответствовать такой
структуре.
Объектно-ориентированные СУБД допускают создание более развитой структуры по
сравнению с реляционными СУБД, но также требуют, чтобы все данные укладывались в
заранее заданную (объектно-ориентированную) схему. Если в СУБД должны храниться
слабоструктурированные данные, то она формирует схему на основе этой информации,
а не налагает на неё фиксированную схему.
46

47. Модели данных -Слабо- полу-структурированная модель данных

47

48. Модели данных -Слабо- полу-структурированная модель данных

48

49. Модели данных -Слабо- полу-структурированная модель данных

Основными преимуществами
языка XML являются:
• Наличие открытого
стандарта,
регламентирующего
допустимые синтаксические
конструкции, что позволяет
реализовать поддержку
языка XML на различных
программно-аппаратных
платформах.
• Простой синтаксис,
основанный на применении
текста, обеспечивающего
лёгкое восприятие
человеком.
• Способность к расширению
с помощью определяемых
пользователем тегов, что
позволяет использовать этот
язык для описания данных
любой предметной области.
49

50. Модели данных -Слабо- полу-структурированная модель данных

• Возможность повторного использования,
обеспечиваемая с помощью
унифицированного описания единой схемы,
регламентирующей набор тегов.
• Отделение данных от способов его
представления. Ряд технологий, таких как XSL
и XSLT позволяют определить способ
отображения сохранённых данных и
преобразовать их в различные форматы.
• Наличие большого количество связанных
технологий, которые позволяют
использовать данных язык для практически
любой предметной области. При этом
существует набор стандартов,
регламентирующих синтаксические
конструкции, присутствующие в конкретном
языке, основанном на XML. Так же во многих
объектно-ориентированных языках
программирования и во многих СУБД
присутствуют различные средства обработки
XML данных от примитивной обработки
(технологии SAX и DOM) до построения
запросов, например, с помощью языка
XQuery.
50

51. Модели данных -Слабо- полу-структурированная модель данных

51

52. Актуальность дисциплины

Структуры данных – необходимые компоненты любой программы или
программного комплекса.
1. Знание теории структур данных и, в частности, методов представления
данных на логическом и машинном уровнях, а также допустимых операций
над различными структурами, необходимо для глубокого изучения и
уяснения таких разделов, как автоматизированные системы управления,
компиляторы языков программирования, операционные системы, а также
системы программного имитационного моделирования, управления базами
данных, искусственного интеллекта и т.д.
2. Выбор структур данных является одним из важных этапов разработки
программ и от правильности этого выбора зависит эффективность
программы, трудоёмкость её написания и время решения программой тех
задач, ради которых она создавалась.
3. Появление в составе современных языков программирования библиотек
и классов структур данных, например, векторов, списков, различных видов
деревьев, карт и т.п. не отменяет необходимости знания специалистами
тонкостей использования этих структур данных и алгоритмов их обработки
Это же справедливо и для алгоритмов обработки данных и их структур
52

53. Задачи дисциплины:

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

54. В результате изучения учащиеся должны

Знать:
• Разновидности структур данных, используемых на различных уровнях
представления данных, определяемых этапами проектирования программы;
• Основные алгоритмы обработки структур данных: пополнение, удаление,
модификация, поиск, сортировка (упорядочение);
• Языковые средства описания различных структур данных;
Уметь:
• Проводить структурирование информационного пространства заданной
предметной области;
• На основе анализа разрабатываемой задачи (программы) выбирать наиболее
рациональные и экономичные структуры данных, обеспечивающие эффективную
реализацию задачи (программы);
• Разрабатывать эффективные алгоритмы обработки данных и программировать их
на известных языках программирования.
Владеть:
• Методологией проектирования программ со сложной организацией данных,
начиная с разработки модели предметной области и кончая описанием алгоритмов и
структур данных средствами языка программирования.
54

55. Литература

1. Вирт Н. Алгоритмы и структуры данных : Новая версия для Оберона + CD: Пер. с
англ. / Н. Вирт. — М.: ДМК Пресс, 2012. — 272 с.: ил. — (Классика
программирования).
2. Круз Р. Структуры данных и проектирование программ [Текст] / Р.Круз; Пер. с
англ. — М.: БИНОМ. Лаборатория знаний, 2011. — 765 с.: ил. — (Программисту).
3. Алексеев В.Е. Графы и алгоритмы. Структуры данных. Модели вычислений :
учебник для вузов / В. Е. Алексеев, В.А. Таланов. — М.: ИНТУИТ, 2012. — 319 с.:
ил. — (Основы информационных технологий).
4. Лафоре Роберт Структуры данных и алгоритмы в Java : Пер. с англ. / Р. Лафоре. —
СПб.: Питер, 2013. — 702 c.: ил. — (Классика computer science).
5. Ахо А. В. Структуры данных и алгоритмы [Текст] / Ахо А.В., Хопкрофт Д., Ульман
Дж.Д.; Пер. с англ. — М.: Вильямс, 2007. — 391 с.
6. Кнут Д. Э. Искусство программирования [Текст]. Т1. / Дональд Э. Кнут. — М.:
Вильямс, 2014. — 712 с.
7. Сыромятников В.П. Анализ и оценка сложности алгоритмов : Учеб. пособие / В. П.
Сыромятников. — М.: МИРЭА, 2011. — 207 с.
8. Андреева Л. П. Структуры данных и алгоритмы [Электронный ресурс]: метод.
указания по выполнению лаб. работ / Л. П. Андреева. — М.: МГТУ МИРЭА, 2012.
55

56. Язык программирования

Рейтинг PYPL (PopularitY of
Programming Languages)
основана на количестве
поисковых запросов учебных
пособий в Google.
С 2005 года во всём мире
Java является самым
популярным языком
программирования. За
последние 5 лет больше
всего интерес проявляется
к языку Python,
а PHP теряет популярность,
но не уступает своему
преследователю C#. В топе
языков ещё JavaScript, C++
совместно с C, R и Ruby.
56

57. Язык программирования

Индекс TIOBE- индекс, демонстрирующий
популярность языков программирования среди
профессионалов. Индекс обновляется раз в месяц и
основывается на количестве поисковых запросов на
таких ресурсах как Google, Bing, Yahoo!, Wikipedia,
Amazon, YouTube and Baidu. Необходимо отметить,
что, по задумке создателей, TIOBE демонстрирует не
самый «лучший» язык, а самый «популярный» язык
за тот или иной промежуток времени (лидирует Java,
Python занимает всего четвертую позицию, замыкают
десятку JavaScript, PHP. А начинает двадцатку — Ruby)
57

58.

58

59.

59

60. Основные определения

Под программным обеспечением ЭВМ понимают совокупность программ,
предназначенных как для поддержания должного функционирования ЭВМ,
так и для выполнения ею полезных функциональных задач некоторой
прикладной области.
Когда употребляют термин «программа», подразумевают не только
последовательность операторов некоторого языка программирования, но и
набор различных информационных объектов, над которыми выполняют те или
иные действия операторы программы. Такие информационные объекты
программы называют данными.
-Данные (data): Информация, представленная в формализованном виде,
пригодном для передачи, интерпретации или обработки с участием человека
или автоматическими средствами (ГОСТ 34.321-96 Информационные технологии
(ИТ). Система стандартов по базам данных. Эталонная модель управления
данными)
-3.8 Термины, относящиеся к данным, информации и документам 3.8.1 данные
(data) факты об объекте (3.6.1) 3.8.2 информация (information) значимые
данные (3.8.1) (ISO 9000:2015)
-Данные – это представлений фактов, понятий, инструкций, идей или какойлибо другой информации в формализованном виде, приемлемом для
обработки, интерпретации, общения или передачи как человеком, так и
техническими средствами, при помощи некоторых процессов или алгоритмов
(Международный стандарт ISO)
60

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

- это совокупность элементов данных, между которыми существуют некоторые
отношения, причем элементами данных могут быть простые данные и
структуры данных.
Структуру данных S можно определить как
S=(D,R) где
• D - множество элементов данных;
• R - множество отношений между элементами данных.
Под отношениями между данными понимают функциональные связи между
ними и указатели на то, где находятся эти данные.
Структура данных – это логическая или математическая модель организации данных.
Фактически, структура данных может рассматриваться как представление именно этих
данных в памяти ЭВМ (физическая структура), и является общим свойством любого
информационного объекта, с которым имеет дело какая-либо программа. Во-вторых,
структура данных – это собственно реализация логического понятия данных, объект
(больший или меньший) в программе и в памяти ЭВМ. Это может быть отдельная
переменная, массив или более сложный программный объект, например, список,
дерево и т.п. Важно помнить, что любая структура данных размещается в памяти ЭВМ
(в первую очередь, в оперативной памяти), занимает некоторое, возможно весьма
большое, количество ячеек этой памяти и характеризуется начальным адресом своего
размещения. Для описания этой ситуации используется понятие «место в памяти».
61

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

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

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

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

64. Уровни структур данных

Применяются три уровня структур данных:
1. Содержательный - исследуются конкретные объекты об работки, их свойства и
отношения между объектами, важны не только значения, но и смысл данных
2. Логический - структура данных считается машинно-независимым логическим
понятием, выделяются следующие задачи:
• определение массивов данных как объектов исследования,
• выделение состава массива,
• определение структуры данных по заданным требованиям,
• разработка количественных методов оценки эффективности различных видов
структур данных.
3. Физический – среда хранения данных (память ЭВМ) и представление в ней
значений (ячейки, разряды ячеек, их адреса и взаимное расположение значений.),
т.е. отображение данных в памяти ЭВМ.
Пример: выполнить ввод данных в память ЭВМ, используя некоторую буферную
область (содержательный уровень). Использовать кольцевую очередь (логический
уровень), которая в работающей программе может быть реализована при помощи
одномерного массива как непрерывного блока в памяти или при помощи связного
списка, допускающего разнесённое размещение в памяти своих элементов
(физический уровень).
64

65. Классификация структур данных

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

66. Классификация структур данных

3. по характеру упорядоченности элементов данных структуры
данных
- линейные (вектора, массивы, стеки, деки, записи)
- нелинейные (многосвязные списки, древовидные структуры,
графы)
В зависимости от характера взаимного расположения элементов в
памяти ЭВМ линейные структуры, в свою очередь, можно разделить
на:
структуры с последовательным распределением их элементов в
памяти (векторы, строки, массивы, стеки и очереди на базе
массивов)
структуры с произвольным связанным распре-делением элементов в
памяти (односвязные, двусвязные, кольце-вые, ассоциативные
списки).
4. По способу создания
обычные – переменные стандартных типов, обычные (т.е. не
динамические) массивы, записи и т.п.;
динамические (создаваемые и разрушаемые с помощью
специальных
операций
или
процедур
динамического
выделения и освобождения памяти) – динамические массивы,
динамические переменные, связные списки, деревья.
66

67. Классификация структур данных

5.
В зависимости от постоянства во время работы программы
различают:
• статические (неизменяющиеся) структуры – переменные
различных
типов,
записи,
массивы,
в
том
числе
динамические, а также списки, деревья и графы в тех
случаях, когда они являются фиксированными и могут быть
построены на основе, например, массива.
• динамические (изменяющиеся) – списки, деревья, очереди,
стеки, в общем случае графы.
6. По месту размещения в памяти ЭВМ:
6.1. существующие в оперативной памяти (или внутренние) –
ими могут быть все ранее рассмотренные примеры структур
данных. Кроме того, такие структуры могут размещаться:
– в регистрах процессора – регистровые, обычно переменные
стандартных типов, размер которых не превышает разрядности
процессора;
– в стеке – локальные (в некоторых языках принято
обозначение «автоматические»)
– любые не статические и не динамические структуры;
– в свободной (динамически выделяемой) памяти или «куче» –
глобальные, локальные статические (для языков Си и Си++) и
все динамические структуры.
6.2.
хранящиеся
на
внешних
носителях
(внешних
запоминающих устройствах) – файлы и системы файлов.
67

68. Классификация структур данных

7.
При несовпадении типов данных в операциях и неявном
преобразовании типов с созданием временных объектов:
7.1. данные, создаваемые самим программистом (независимо от
способа и времени создания), в англоязычной литературе по
программированию часто обозначаемые словом persistent –
«устойчивый» («постоянный», «постоянно существующий»).
Таким являются структуры всех данных, явно созданных
программистом при написании программы;
7.2. создаваемые и разрушаемые непосредственно во время
работы программы без участия программиста, обычно во
вспомогательных целях, например, при несовпадении типов
данных в каких-либо операциях. Для них используется термин
transient – «временный», «преходящий».
Обычно уничтожаются сразу после их использования. Как
правило, такие структуры данных являются безымянными,
создаются не программистом, а самим компилятором (ещё один
вариант – компилятор строит код программы так, чтобы эти
данные были созданы и разрушены в нужные моменты работы
программы).
68

69.

69

70.

70

71.

Вопросы и задания для самоконтроля
1.1. Что означает понятие «структуры данных»?
1.2. По каким признакам классифицируются структуры данных?
1.3. На каких уровнях рассматриваются структуры данных?
1.4. Поясните различие между уровнями структур данных.
1.5. Как структуры данных различаются по сложности? Приведите примеры
структур данных различной степени сложности.
1.6. Какие структуры данных обладают линейной архитектурой?
1.7. Как структуры данных различаются по архитектуре? Приведите примеры
струк- тур данных различных архитектур.
1.8. Какие структуры данных обладают прямоугольной архитектурой?
1.9. Что может означать термин «динамическая структура данных»?
1.10. Что означает термин «связная структура данных»?
1.11. Какие структуры данных являются связными?
1.12. Как структуры данных различаются по месту размещения в памяти?
1.13. К каким структурам данных относятся файлы?
1.14. Пусть имеется 32-разрядная вычислительная система, в которой
действительное число занимает двойное машинное слово. Сколько байт занимает
в памяти массив, содержа- щий 2K действительных чисел (1K = 1024)?
1.15. Сколько кибибайт занимает блок памяти из 65536 однобайтовых ячеек?
71

72.

Понятие о типах данных
Вопросы и задания для самоконтроля
2.1. Какие структуры данных относятся к простым?
2.2. Что означает понятие «тип данных»?
2.3. Какую информацию можно извлечь из типа данных?
2.4. На какие группы разделяются типы данных в основных языках
программирования?
2.5. На какие группы могут разделяться типы, предназначенные для описания
цело- численных значений?
2.6. Пусть имеется некоторое отрицательное целое число. Какое значение
имеет старший разряд этого числа?
2.7. Считываемые из файла текстовые данные выводятся на дисплей неверно.
В чём может быть причина этого?
2.8. Работая с программой, пользователь вводит число 100000. При контроле
введенных данных на дисплей выводится число -31072. В чем может быть
причина этого?
2.9. Можно ли в двоичной системе счисления точно представить значение
0,0625?
2.10. Можно ли в двоичной системе счисления с ограниченной разрядностью
точно представить значение 0,95?
72

73.

Понятие о типах данных
Вопросы и задания для самоконтроля
2.11. Что такое указатели?
2.12. Для чего используются указатели?
2.13. Какие операции можно выполнять над указателями?
2.14. Что представляют собой указатели на указатели? Для чего они могут
применяться?
2.15. Можно ли получить адрес указателя?
2.16. Что означает понятие «модифицируемое L-выражение»?
2.17. Что означает понятие «немодифицируемое L-выражение»?
2.18. Может ли указатель содержать нулевое значение?
2.19. Может ли явно созданная в памяти структура данных иметь адрес,
равный нулю?
73

74.

Структурность данных и технология программирования
Зачем знать СД?
1. Организовать их хранение и обработку максимально эффективным
образом - с точки зрения минимизации затрат как памяти, так и
процессорного времени
2. Возможность структурирования сложного программного изделия
(выполнения коллективом)
Два подхода
1. Структуризация алгоритмов и известного, как "нисходящее"
проектирование или "программирование сверху вниз",
2. Структуризация данных и известного, как "восходящее" проектирование
или "программирование снизу вверх".
74

75.

Структурность данных и технология программирования
Инкапсуляция.
Смысл ее состоит в том, что сконструированный новый тип данных "строительный блок" - оформляется таким образом, что его внутренняя
структура становится недоступной для программиста - пользователя этого
типа.
Инкапсуляция чрезвычайно полезна и как средство преодоления
сложности, и как средство защиты от ошибок.
Первая цель достигается за счет того, что сложность внутренней структуры
нового типа данных и алгоритмов выполнения операций над ним
исключается из поля зрения программиста-пользователя.
Вторая цель достигается тем, что возможности доступа пользователя
ограничиваются лишь заведомо корректными входными точками,
следовательно, снижается и вероятность ошибок.
Программист, оперирующий объектами, указывает в программе ЧТО нужно
сделать с объектом, а не КАК это надо делать.
75

76.

Структурность данных и технология программирования
Технология баз данных развивалась параллельно с технологией языков
программирования и не всегда согласованно с ней.
Отчасти этим, а отчасти и объективными различиями в природе задач,
решаемых системами управления базами данных (СУБД) и системами
программирования, вызваны некоторые терминологические и понятийные
различия в подходе к данным в этих двух сферах.
Ключевым понятием в СУБД является понятие модели данных, в основном
тождественное понятию логической структуры данных (физическая
структура данных в СУБД не рассматривается вообще)
Но сами СУБД являются программными пакетами, выполняющими
отображение физической структуры в логическую (в модель данных). Для
реализации этих пакетов используются те или иные системы
программирования, разработчики СУБД, следовательно, имеют дело со
структурами данных в терминах систем программирования. Для
пользователя же внутренняя структура СУБД и физическая структура данных
совершенно прозрачна; он имеет дело только с моделью данных и с
другими понятиями логического уровня
76