Учебник Технология программирования. Технология программирования
 Скачать 7.85 Mb.
|
|
Диаграммы Джексона. В основе диаграмм Джексона лежит предположение о том, что структуры данных, так же, как и программ, можно строить т элементов с использованием всего трех основных конструкций: последовательности, выбора и повторения. Каждая конструкция представляется в виде двухуровневой иерархии, на верхнем уровне которой расположен блок конструкции, а на нижнем - блоки элементов. Испании конструкций различаются специальными символами в правом верхнем углу блоков элементов. В изображении последовательности дополнительный символ отсутствует. В изображении выбора ставится символ «о» (латинское) - сокращение английского «или» (or). Конструкции последовательности и выбора должны содержать но два или более элементов второго уровня. В изображении повторения в блоке единственного (повторяющеюся) элемента ставится символ «*». Так схема, показанная на рис. 4.22, а, означает, что конструкция А состоит из элементов В, С и D, следующих в указанном порядке. Схема на рис. 4.22, б означает, что конструкция S состоит либо из элемента P, либоиз 127 элемента Q, либо из элемента R. Схема, изображенная на рис. 4.22, в, показывает, что конструкция I может не содержать элементов или содержать один или более элементов X. В случае, если необходимо показать, что конструкция повторения должна включать один или более элементов, используют комбинацию из двух структур последовательности и повторения (рис. 4.23). Скобочные диаграммы Орра. Диаграмма Орра базируется на том же предположении о сходстве структур программ и данных, что и диаграмма Джексона. Отличие состоит лишь в нотации. Автор предлагает для представления конструкций данных использовать фигурные скобки (рис. 4.24). 128 Пример 4.6. Рассмотрим описание структуры данных файла «Электронная ведомость», содержащего сведения о сдаче экзаменов студентами. Файл состоит из записей о результатах сдачи сессии студентами одной группы. Он имеет следующую структуру: номер группы, записи об успеваемости студентов (ФИО студента, название предмета и оценка, полученная студентом, в завершении записи специальный символ «конец записи») и специальный символ «конец файла». На рис. 4.25 показано, как выглядит описание данной структуры с использованием диаграммы Джексона, а на рис. 4.26 - с использованием скобок Орра. Сетевая модель данных. Сетевые модели данных используют в тех случаях, если отношение между компонентами данных не исчерпываются включением. Для графического представления разновидностей этой модели используют несколько нотаций. Наиболее известны из них следующие: • нотация П. Чена; • нотация Р. Баркера; • нотация IDEF1 (более современный вариант этой нотации - IDEF1X используется в CASE-системах, например в системе ERWin). Нотация Баркера является наиболее распространенной. Далее в настоящем разделе будем придерживаться именно этой нотации. 129 Базовыми понятиями сетевой модели данных являются: сущность, атрибут и связь. Сущность - реальный или воображаемый объект, имеющий существенное значение для рассматриваемой предметной области. Каждая сущность должна: • иметь уникальное имя; • обладать одним или несколькими атрибутами, которые либо принадлежат сущности, либо наследуются через связь; • обладать одним или несколькими атрибутами, которые однозначно идентифицируют каждый экземпляр сущности. Сущность представляет собой множество экземпляров реальных или абстрактных объектов (людей, событий, состояний, предметов и т. п.). Имя сущности должно отражать тип или класс объекта, а не его конкретный экземпляр (Аэропорт, а не Внуково). На диаграмме в нотации Баркера сущность изображается прямоугольником, иногда с закругленными углами (рис. 4.27. а). Каждая сущность обладает одним или несколькими атрибутами. Атрибут-любая характеристика сущности, значимая для рассматриваемой предметной области и предназначенная для квалификации, идентификации, классификации, количественной характеристики или выражения состояния сущности (рис. 4.27, б). В сетевой модели атрибуты ассоциируются с конкретными сущностями, и, соответственно, экземпляр сущности должен обладать единственным определенным значением для ассоциированного атрибута. Атрибут, таким образом, представляет собой некоторый тип характеристик или свойств, ассоциированных с множеством реальных или абстрактных объектов. Экземпляр атрибута- определенная характеристика конкретного экземпляра сущности. Он определяется типом характеристики и ее значением, называемым значением атрибута. 130 Атрибуты делятся на ключевые, т. е. входящие в состав уникального идентификатора, который называют первичным ключом, и описательные - прочие. Первичный ключ - это атрибут или совокупность атрибутов и/или связей, предназначенная для уникальной идентификации каждого экземпляра сущности (совокупность признаков, позволяющих идентифицировать объект). Ключевые атрибуты помещают в начало списка и помечают символом «#» (рис. 4.27, в). Описательные атрибуты бывают обязательными или необязательными. Обязательные атрибуты для каждой сущности всегда имеют конкретное значение, необязательные — могут быть не определены. Обязательные и необязательные описательные атрибуты помечают символами «*» и «о» соответственно. Для сущностей определено понятие супертип и подтип. Супертип- сущность обобщающая некую группу сущностей (подтипов). Супертип характеризуется общими для подтипов атрибутами и отношениями. Например, для некоторых задач супертип «учащийся» обобщает подтипы «школьник» и «студент» (рис. 4.28). Связь - поименованная ассоциация между двумя или более сущностями, значимая для рассматриваемой предметной области. Связь, таким образом, означает, что каждый экземпляр одной сущности ассоциирован с произвольным (в том числе и нулевым) количеством экземпляров второй сущности и наоборот. Если любой экземпляр одной сущности связан хотя бы с одним экземпляром другой сущности, то связь является обязательной (рис. 4.29. а). Необязательная связь представляет собой условное отношение между сущностями (рис. 4.29, б). Каждая сущность может быть связана любым количеством связей с другими сущностями модели. Связь предполагает некоторое отношение сущностей, которое характеризуется количеством экземпляров сущности, участвующих в связи с каждой стороны. 131 Различают три типа отношений (рис. 4.30): 1*1 - «один-к-одному» - одному экземпляру первой сущности соответствует один экземпляр второй; 1*n - «один-ко-многим» - одному экземпляру первой сущности соответствуют несколько экземпляров второй; n*m - «многие-ко-многим» - каждому экземпляру первой сущности может соответствовать несколько экземпляров второй и, наоборот, каждому экземпляру второй сущности может соответствовать несколько экземпляров первой. Кроме того, сущности бывают независимыми, зависимыми и ассоциированными. Независимая сущность представляет независимые данные, которые всегда присутствуют в системе. Они могут быть связаны или Не связаны с другими сущностями той же системы. Зависимая сущность представляет данные, зависящие от других сущностей системы, поэтому она всегда должна быть связана с другими сущностями. Ассоциированная сущность представляет данные, которые ассоциируются с отношениями между двумя и более сущностями. Обычно данный вид сущностей используется в модели для разрешения отношения «многие-ко-многим» (рис. 4.31). Если экземпляр сущности полностью идентифицируется своими ключевыми атрибутами, то говорят о полной идентификации сущности. В противном случае идентификация сущности осуществляется с использованием атрибутов связанной сущности, что указывается черточкой на линии связи (рис. 4.32). 132 Кроме этого, модель включает понятия взаимно исключающих, рекурсивных и неперемещаемых связей. При наличии взаимно исключающей связи экземпляр сущности участвует только в одной связи из некоторой группы связей (рис. 4.33. а). Рекурсивная связь предполагает, что сущность может быть связана сама с собой (рис. 4.33, б). Неперемещаемая связь означает, что экземпляр сущности не может быть перенесен из одного экземпляра связи в другой (рис. 4.33. в). Пример 4.7. Рассмотрим структуру базы данных для системы учета успеваемости студентов. Основными сущностями для решения указанной задачи являются: Студент и Предмет (изучаемый учебный курс). 133 Отношение между ними относится к типу «многие-ко-многим». Для разрешения этого отношения введем ассоциированную сущность Экзамен/Зачет, которая отражает текущее выполнение предметов учебного плана студентом. Предметы, которые изучает и по которым отчитывается студент, запланированы кафедрой в учебном плане. Учебный план включает список предметов каждого семестра (сущность Семестр). Для получения справок различного рода потребуются сущности, определяющие структуру организации: • Факультет; • Курс - совокупность студентов, поступивших в институт в одном ГОДУ ; • Кафедра; • Группа. Для определения момента времени, начиная с которого отсутствие положительных результатов сдачи экзамена следует считать задолженностью, необходимо хранить даты экзаменов для каждой группы (сущность Дата экзамена). На рис. 4.34 покачаны основные отношения между указанными сущностями. 134 На следующем шаге определяем атрибуты каждой сущности и уточняем их типы (атрибуты, используемые для дополнительной идентификации сущности другой сущностью, не указаны, так как они описаны в соответствующей сущности). Факультет: • DepID - уникальное имя факультета (ключевое поле); • DepName — название факультета. Курс: • CursID - уникальное имя кафедры (ключевое поле); • EnterYear - год начала обучения для большинства студентов курса. Кафедра: • SpecID - уникальное имя кафедры (ключевое поле); • SpecName - название кафедры. Семестр: • SemestrID - уникальное имя семестра обучения на конкретной кафедре (ключевое поле); • SemName - название семестра обучения на кафедре. Группа: • GroupID - уникальное имя группы (ключевое поле); • GroupName - название группы. Предмет: • SubjectID - уникальное имя предмета (ключевой атрибут); • SubjectName - название предмета; • ExamKind - вид оценки знаний (необязательный атрибут): экзамен/зачет/экзамен + зачет. Дата экзамена: • Date - дата экзамена; • AudNumber -номер аудитории. Студент: • StudentID - уникальное имя студента (ключевое поле); • Name - фамилия; • FirstName -имя; • SecondName - отчество; • StfcnterYear - год поступления в институт. Экзамен/Зачет: • Date - дача сдачи экзамена или зачета; • ExamType - тип (экзамен или зачет); • Mark - оценка. Полученная диаграмма «сущность-связь» приведена на рис. 4.35. Данная диаграмма должна быть проверена с точки зрения возможности получения всех справок, указанных в техническом задании или показанных на диаграмме потоков данных разрабатываемой системы (см. рис. 4.14). 135 136 4.6. Математические модели задач, разработка или выбор методов решения Для задач, алгоритм решения которых не очевиден, используют разного рода математические модели. Процесс построения такой модели включает: • анализ условия задачи; • выбор математических абстракций, адекватно, т.е. с требуемой точностью и полнотой представляющих исходные данные и результаты; • формальную постановку задачи; • определение методапреобразования исходных данных в результат, т.е.метода решения задачи. Для многих задач, которые часто встречаются на практике, в математике определены как модели, так и методы решения. К таким задачам, например, относится большинство задач аналитической геометрии на плоскости и в пространстве, задачи моделирования дискретных систем и т. д. Основная проблема в подобных случаях - обоснование применимости той или иной математической модели для решения конкретной задачи. В ряде случаев формальная постановка задачи однозначно определяет метод ее решения, но, как правило, методов решения существует несколько, и тогда для выбора метода решения может потребоваться специальное исследование. При выборе метода учитывают: • особенности данных конкретной задачи, связанные с предметной областью (погрешность, возможные особые случаи и т. п.); • требования к результатам (допустимую погрешность); • характеристики метода (точный или приближенный, погрешности результатов, вычислительную и емкостную сложности, сложность реализации и т. п.). Пример 4.8. Выполнить формальную постановку задачи поиска цикла минимальной длины (задачи коммивояжера). Вспомним, что задача коммивояжера или поиска цикла минимальной длины в простейшем варианте формулируется следующим образом. Задан список городов и дорог, соединяющих данные города. Известны расстояния между городами. Необходимо объехать все города, не заезжая ни в какой город дважды, и вернуться в исходный город так, чтобы суммарная длина пути была минимальной. Анализ условия задачи показывает, что математической моделью объектов системы и существующих или возможных связей между ними может являться взвешенный ориентированный или неориентированный граф G(X, Для перехода от объектов задачи к их математическим моделям необходимо [55]: 137 • сформулировать правила соответствия компонентов объекта компонентам модели; • определить вид этих соответствий (взаимно однозначные, однозначные, многозначные); • определить способ отображения свойств и характеристик компонентов объекта в характеристики выбранной математической абстракции. Все это определяется, исходя из отношений, существующих между компонентами объекта, а также свойств объекта и характеристик его компонентов. В графе G множество Э объектов системы (городов) поставлено во взаимно однозначное соответствие множеству X, а множеству связей С между парами объектов (дорог) поставлено в такое же соответствие множество ребер U. Расстояние между городами (э i , э j ) интерпретируется как вес соответствующего ребра w(x i , x j ). Таким образом, в терминах теории графов рассматриваемая задача - это поиск в ориентированном или неориентированном графе гамильтонова цикла минимальной длины. Формальная постановка задачи имеет вид - выполнить преобразование исходного графа G в граф результата G c : ( ) ( ) c c D U X G W U X G , , , ⎯→ ⎯ > < так что ( ) ( ) min, : , → = = ⊂ ∑ ∈ c c U u r c c c c u w G W X U U U причем ( ) ( ) ( ) ( ) , , , , 2 j i i i i i x x S X x x x X x ∃ ∈ ∀ = ∈ ∀ ρ где p(x i ) - количество ребер, подходящих к вершине; a S(x i ,x j ) - маршрут между вершинами x i , x j , т. е. последовательность смежных ребер, связывающих эти вершины. Следует иметь в виду, что граф имеет гамильтонов цикл, если сумма локальных степеней любой пары вершин больше или равна числу его вершин: ( ) ( ) ( ) [ ] n x x X x x j i i i ≥ + ∈ ∀ ρ ρ , В противном случае граф может не иметь гамильтонова цикла, что для нас означает, что в некоторых случаях задача может не иметь решения. Задача относится к классу NP-сложных задач, вычислительная сложность, которых не выражается и виде полинома от размерности ее входа (количества городов), а носит экспоненциальный характер, т.е. очень быстро возрастает при увеличении размерности задачи. Известно, что точное решениезадачи коммивояжера может быть получено алгоритмами, реализующими полный перебор или метод ветвей и границ. Приближенное решение дают методы поиска в глубину и двоичной свертки. 138 Поскольку по техническому заданию необходимо обеспечить получение точного решения, следует реализовать хотя бы по одному методу из указанных групп. Для выбора методов нужно провести дополнительные исследования. Определив методы решения, целесообразно для некоторых вариантов исходных данных вручную, на калькуляторе или с использованием других средств подсчитать ожидаемые результаты. Эти данные в дальнейшем будут использованы при тестировании программного обеспечения. Кроме того, выполнение операций вручную позволяет точно уяснить последовательность действий, что упростит разработку алгоритмов. Кроме того, имеет смысл продумать, для каких сочетаний исходных данных результат не существует или не может быть получен данным методом, что тоже необходимо учесть при разработке программного обеспечения. Контрольные вопросы и задания 1. В чем сущность структурного подхода к программированию? Какие этапы охватывает данный подход? 2. Что понимают под термином «спецификации»? В чем сложность их уточнения? Назовите модели, используемые в качестве функциональных спецификаций при структурном подходе. Какие характеристики проектируемого программного обеспечения описывает каждая из них? 3. В каких случаях целесообразно использовать диаграммы переходов состояний? Разработайте диаграмму переходов для калькулятора, техническое задание на который составлялось вами в соответствии заданием к предыдущей главе. 4. В чем заключается основное различие между функциональными диаграммами и диаграммами потоков данных? Постройте оба вида диаграмм для выполнения вычислений с использованием внутренней памяти калькулятора. Проанализируйте сходство и различие. В каких случаях использование диаграмм потоков данных является предпочтительным? 5. Что называют «структурами данных»? Какие данные имеются в виду? В каких случаях структуры данных необходимо описывать? Какие модели используют для описания структур данных? 6. Опишите стек и очередь с использованием предлагаемых моделей описания данных. Какие аспекты этих структур остались не описанными и почему? 7. В каких случаях используют математические модели? Что понимают под адекватностью модели? Зачем необходимо выполнять доказательство адекватности и как строятся подобные доказательства? |