tehnologia (1018792), страница 24
Текст из файла (страница 24)
Учебный план включает список предметов каждого семестра(сущность Семестр).Для получения справок различного рода потребуются сущности, определяющиеструктуру организации:• Факультет;• Курс - совокупность студентов, поступивших в институт в одном ГОДУ;• Кафедра;• Группа.Для определения момента времени, начиная с которого отсутствие положительныхрезультатов сдачи экзамена следует считать задолженностью, необходимо хранить датыэкзаменов для каждой группы (сущность Дата экзамена). На рис. 4.34 покачаны основныеотношения между указанными сущностями..133На следующем шаге определяем атрибуты каждой сущности и уточняем их типы(атрибуты, используемые для дополнительной идентификации сущности другой сущностью,не указаны, так как они описаны в соответствующей сущности).Факультет:• 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).1341354.6. Математические модели задач, разработка или выбор методов решенияДля задач, алгоритм решения которых не очевиден, используют разного родаматематические модели. Процесс построения такой модели включает:• анализ условия задачи;• выбор математических абстракций, адекватно, т.е. с требуемой точностью иполнотой представляющих исходные данные и результаты;• формальную постановку задачи;• определение метода преобразования исходных данных в результат, т.е.
методарешения задачи.Для многих задач, которые часто встречаются на практике, в математике определеныкак модели, так и методы решения. К таким задачам, например, относится большинствозадач аналитической геометрии на плоскости и в пространстве, задачи моделированиядискретных систем и т. д.Основная проблема в подобных случаях - обоснование применимости той или инойматематической модели для решения конкретной задачи.В ряде случаев формальная постановка задачи однозначно определяет метод еерешения, но, как правило, методов решения существует несколько, и тогда для выбораметода решения может потребоваться специальное исследование. При выборе методаучитывают:• особенности данных конкретной задачи, связанные с предметной областью(погрешность, возможные особые случаи и т. п.);• требования к результатам (допустимую погрешность);• характеристики метода (точный или приближенный, погрешности результатов,вычислительную и емкостную сложности, сложность реализации и т.
п.).Пример 4.8. Выполнить формальную постановку задачи поиска цикла минимальнойдлины (задачи коммивояжера).Вспомним, что задача коммивояжера или поиска цикла минимальной длины впростейшем варианте формулируется следующим образом. Задан список городов и дорог,соединяющих данные города. Известны расстояния между городами.
Необходимо объехатьвсе города, не заезжая ни в какой город дважды, и вернуться в исходный город так, чтобысуммарная длина пути была минимальной.Анализ условия задачи показывает, что математической моделью объектов системы исуществующих или возможных связей между ними может являться взвешенныйориентированный или неориентированный граф G(X, <U, L>), где X, U, L - множествавершин, ребер и весов ребер соответственно.Для перехода от объектов задачи к их математическим моделям необходимо [55]:136• сформулировать правила соответствия компонентов объекта компонентам модели;• определить вид этих соответствий (взаимно однозначные, однозначные,многозначные);• определить способ отображения свойств и характеристик компонентов объекта вхарактеристики выбранной математической абстракции.Все это определяется, исходя из отношений, существующих между компонентамиобъекта, а также свойств объекта и характеристик его компонентов.В графе G множество Э объектов системы (городов) поставлено во взаимнооднозначное соответствие множеству X, а множеству связей С между парами объектов(дорог) поставлено в такое же соответствие множество ребер U.
Расстояние между городами(эi , эj) интерпретируется как вес соответствующего ребра w(xi , xj).Таким образом, в терминах теории графов рассматриваемая задача - это поиск вориентированном или неориентированном графе гамильтонова цикла минимальной длины.Формальная постановка задачи имеет вид - выполнить преобразование исходногографа G в граф результата Gc:DG ( X , < U , W > ) ⎯⎯→G c ( X ,U c )так чтопричемU c ⊂ U , U c = X c : W (Gc ) =∑ w(u ) → min,u c ∈U cr(∀ xi ∈ X )ρ (xi ) = 2, (∀ xi , xi ∈ X )∃ S (xi , x j ),где p(xi) - количество ребер, подходящих к вершине; a S(xi,xj) - маршрут между вершинамиxi, xj, т.
е. последовательность смежных ребер, связывающих эти вершины.Следует иметь в виду, что граф имеет гамильтонов цикл, если сумма локальныхстепеней любой пары вершин больше или равна числу его вершин:(∀xi , xi ∈ X )[ρ (xi ) + ρ (x j )] ≥ nВ противном случае граф может не иметь гамильтонова цикла, что для нас означает,что в некоторых случаях задача может не иметь решения.Задача относится к классу NP-сложных задач, вычислительная сложность, которых невыражается и виде полинома от размерности ее входа (количества городов), а носитэкспоненциальный характер, т.е.
очень быстро возрастает при увеличении размерностизадачи. Известно, что точное решение задачи коммивояжера может быть полученоалгоритмами, реализующими полный перебор или метод ветвей и границ. Приближенноерешение дают методы поиска в глубину и двоичной свертки.137Поскольку по техническому заданию необходимо обеспечить получение точногорешения, следует реализовать хотя бы по одному методу из указанных групп. Для выбораметодов нужно провести дополнительные исследования.Определив методы решения, целесообразно для некоторых вариантов исходныхданных вручную, на калькуляторе или с использованием других средств подсчитатьожидаемые результаты. Эти данные в дальнейшем будут использованы при тестированиипрограммного обеспечения.
Кроме того, выполнение операций вручную позволяет точноуяснить последовательность действий, что упростит разработку алгоритмов.Кроме того, имеет смысл продумать, для каких сочетаний исходных данных результатне существует или не может быть получен данным методом, что тоже необходимо учестьпри разработке программного обеспечения.Контрольные вопросы и задания1. В чем сущность структурного подхода к программированию? Какие этапыохватывает данный подход?2.
Что понимают под термином «спецификации»? В чем сложность их уточнения?Назовите модели, используемые в качестве функциональных спецификаций при структурномподходе. Какие характеристики проектируемого программного обеспечения описываеткаждая из них?3. В каких случаях целесообразно использовать диаграммы переходов состояний?Разработайте диаграмму переходов для калькулятора, техническое задание на которыйсоставлялось вами в соответствии заданием к предыдущей главе.4. В чем заключается основное различие между функциональными диаграммами идиаграммами потоков данных? Постройте оба вида диаграмм для выполнения вычислений сиспользованием внутренней памяти калькулятора.
Проанализируйте сходство и различие. Вкаких случаях использование диаграмм потоков данных является предпочтительным?5. Что называют «структурами данных»? Какие данные имеются в виду? В какихслучаях структуры данных необходимо описывать? Какие модели используют для описанияструктур данных?6. Опишите стек и очередь с использованием предлагаемых моделей описанияданных.
Какие аспекты этих структур остались не описанными и почему?7. В каких случаях используют математические модели? Что понимают подадекватностью модели? Зачем необходимо выполнять доказательство адекватности и какстроятся подобные доказательства?1385. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРИ СТРУКТУРНОМПОДХОДЕКак уже упоминалось ранее, сущность структурного подхода заключается в декомпозиции программы илипрограммной системы по функциональному принципу. Все предлагаемые методы декомпозиции используютинтерфейсы простейшего типа: примитивные интерфейсы и традиционные меню.
и рассчитаны на анализ ипроектирование как структур данных, так и обрабатывающих их программ.Причем в большинстве случаев первичным считают проектирование обрабатывающих компонентов,проектирование же структур данных выполняют параллельно. Существует и альтернативный подход, прикотором первичным считают проектирование данных, а обрабатывающие программы получают, анализируяполученные структуры данных.В любом случае проектирование программного обеспечения начинают с определения его структуры.5.1. Разработка структурной и функциональной схемПроцесс проектирования сложного программного обеспечения начинают с уточненияего структуры, т. е.
определения структурных компонентов и связей между ними. Результатуточнения структуры может быть представлен в виде структурной и/или функциональнойсхем и описания (спецификаций) компонентов.Структурная схема разрабатываемого программного обеспечения. Структурнойназывают схему, отражающую состав и взаимодействие по управлению частейразрабатываемого программного обеспечения.Структурные схемы пакетов программ не информативны, поскольку организация программ ипакеты не предусматривает передачи управления между ними.
Поэтому структурные схемыразрабатывают для каждой программы пакета, а список программ пакета определяют,анализируя функции, укачанные в техническом задании.Самый простой вид программного обеспечения - программа, которая в качествеструктурных компонентов может включать только подпрограммы и139библиотеки ресурсов. Разработку структурной схемы программы обычно выполняютметодом пошаговой детализации (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
