ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 20.11.2019
Просмотров: 9500
Скачиваний: 184
Кроме
этого
,
модель
включает
понятия
взаимно
исключающих
,
рекурсивных
и
неперемещаемых
связей
.
При
наличии
взаимно
исключающей
связи
экземпляр
сущности
участвует
только
в
одной
связи
из
некоторой
группы
связей
(
рис
. 4.33,
а
).
Рекурсивная
связь
предполагает
,
что
сущность
может
быть
связана
сама
с
собой
(
рис
. 4.33,
б
).
Неперемещаемая
связь
означает
,
что
экземпляр
сущности
не
может
быть
перенесен
из
одного
экземпляра
связи
в
другой
(
рис
. 4.33,
в
).
Пример
4.7.
Рассмотрим
структуру
базы
данных
для
системы
учета
успеваемости
студентов
.
Основными
сущностями
для
решения
указанной
задачи
являются
:
Студент
и
Предмет
(
изучаемый
учебный
курс
).
Отношение
между
ними
относится
к
типу
«
многие
-
ко
-
многим
».
Для
разрешения
этого
отношения
введем
ассоциированную
сущность
Экзамен
/
Зачет
,
которая
отражает
текущее
выполнение
предметов
учебного
плана
студентом
.
Предметы
,
которые
изучает
и
по
которым
отчитывается
студент
,
запланированы
кафедрой
в
учебном
плане
.
Учебный
план
включает
список
предметов
каждого
семестра
(
сущность
Семестр
).
Для
получения
справок
различного
рода
потребуются
сущности
,
определяющие
структуру
организации
:
•
Факультет
;
•
Курс
-
совокупность
студентов
,
поступивших
в
институт
в
одном
году
;
•
Кафедра
;
•
Группа
.
Для
определения
момента
времени
,
начиная
с
которого
отсутствие
положительных
результатов
сдачи
экзамена
следует
считать
задолженностью
,
необходимо
хранить
даты
экзаменов
для
каждой
группы
(
сущность
Дата
экзамена
).
На
рис
. 4.34
показаны
основные
отношения
между
указанными
сущностями
.
На
следующем
шаге
определяем
атрибуты
каждой
сущности
и
уточняем
их
типы
(
атрибуты
,
используемые
для
дополнительной
идентификации
сущности
другой
сущностью
,
не
указаны
,
так
как
они
описаны
в
соответствующей
сущности
).
Факультет
:
•
DepID-
уникальное
имя
факультета
(
ключевое
поле
);
•
DepName -
название
факультета
.
Курс
:
•
CursID -
уникальное
имя
кафедры
(
ключевое
поле
);
•
EnterYear -
год
начала
обучения
для
большинства
студентов
курса
.
Кафедра
:
•
SpecID -
уникальное
имя
кафедры
(
ключевое
поле
);
•
SpecName -
название
кафедры
.
Семестр
:
• SemestrlD -
уникальное
имя
семестра
обучения
на
конкретной
кафедре
(
ключевое
поле
);
•
SemName -
название
семестра
обучения
на
кафедре
.
Группа
:
•
GroupID -
уникальное
имя
группы
(
ключевое
поле
);
•
GroupName -
название
группы
.
Предмет
:
•
SubjectID -
уникальное
имя
предмета
(
ключевой
атрибут
);
•
SubjectName -
название
предмета
;
•
ExamKind -
вид
оценки
знаний
(
необязательный
атрибут
):
экзамен
/
зачет
/
экзамен
+
зачет
.
Дата
экзамена
:
•
Date -
дата
экзамена
;
•
AudNumber -
номер
аудитории
.
Студент
:
•
StudentID -
уникальное
имя
студента
(
ключевое
поле
);
•
Name -
фамилия
;
•
FirstName -
имя
;
•
SecondName -
отчество
;
•
StEnterYear -
год
поступления
в
институт
.
Экзамен
/
Зачет
:
•
Date -
дата
сдачи
экзамена
или
зачета
;
•
ЕхатТуре
-
тип
(
экзамен
или
зачет
);
•
Mark -
оценка
.
Полученная
диаграмма
«
сущность
-
связь
»
приведена
на
рис
. 4.35.
Данная
диаграмма
должна
быть
проверена
с
точки
зрения
возможности
получения
всех
справок
,
указанных
в
техническом
задании
или
показанных
на
диаграмме
потоков
данных
разрабатываемой
системы
(
см
.
рис
. 4.14).
4.6.
Математические
модели
задач
,
разработка
или
выбор
методов
решения
Для
задач
,
алгоритм
решения
которых
не
очевиден
,
используют
разного
рода
математические
модели
.
Процесс
построения
такой
модели
включает
:
•
анализ
условия
задачи
;
•
выбор
математических
абстракций
,
адекватно
,
т
.
е
.
с
требуемой
точностью
и
полнотой
представляющих
исходные
данные
и
результаты
;
•
формальную
постановку
задачи
;
•
определение
метода
преобразования
исходных
данных
в
результат
,
т
.
е
.
метода
решения
задачи
.
Для
многих
задач
,
которые
часто
встречаются
на
практике
,
в
математике
определены
как
модели
,
так
и
методы
решения
.
К
таким
задачам
,
например
,
относится
большинство
задач
аналитической
геометрии
на
плоскости
и
в
пространстве
,
задачи
моделирования
дискретных
систем
и
т
.
д
.
Основная
проблема
в
подобных
случаях
-
обоснование
применимости
той
или
иной
математической
модели
для
решения
конкретной
задачи
.
В
ряде
случаев
формальная
постановка
задачи
однозначно
определяет
метод
ее
решения
,
но
,
как
правило
,
методов
решения
существует
несколько
,
и
тогда
для
выбора
метода
решения
может
потребоваться
специальное
исследование
.
При
выборе
метода
учитывают
:
•
особенности
данных
конкретной
задачи
,
связанные
с
предметной
областью
(
погрешность
,
возможные
особые
случаи
и
т
.
п
.);
•
требования
к
результатам
(
допустимую
погрешность
);
•
характеристики
метода
(
точный
или
приближенный
,
погрешности
результатов
,
вычислительную
и
емкостную
сложности
,
сложность
реализациии
т
.
п
.).
Пример
4.8.
Выполнить
формальную
постановку
задачи
поиска
цикла
минимальной
длины
(
задачи
коммивояжера
).
Вспомним
,
что
задача
коммивояжера
или
поиска
цикла
минимальной
длины
в
простейшем
варианте
формулируется
следующим
образом
.
Задан
список
городов
и
дорог
,
соединяющих
данные
города
.
Известны
расстояния
между
городами
.
Необходимо
объехать
все
города
,
не
заезжая
ни
в
какой
город
дважды
,
и
вернуться
в
исходный
город
так
,
чтобы
суммарная
длина
пути
была
минимальной
.
Анализ
условия
задачи
показывает
,
что
математической
моделью
объектов
системы
и
существующих
или
возможных
связей
между
ними
может
являться
взвешенный
ориентированный
или
неориентированный
граф
G(X, <U, L>),
где
X, U, L -
множества
вершин
,
ребер
и
весов
ребер
соответственно
.
Для
перехода
от
объектов
задачи
к
их
математическим
моделям
необходимо
[55]:
•
сформулировать
правила
соответствия
компонентов
объекта
компонентам
модели
;
•
определить
вид
этих
соответствий
(
взаимно
однозначные
,
однозначные
,
многозначные
);
•
определить
способ
отображения
свойств
и
характеристик
компонентов
объекта
в
характеристики
выбранной
математической
абстракции
.
Все
это
определяется
,
исходя
из
отношений
,
существующих
между
компонентами
объекта
,
а
также
свойств
объекта
и
характеристик
его
компонентов
.
В
графе
G
множество
Э
объектов
системы
(
городов
)
поставлено
во
взаимно
однозначное
соответствие
множеству
X,
а
множеству
связей
С
между
парами
объектов
(
дорог
)
поставлено
в
такое
же
соответствие
множество
ребер
U.
Расстояние
между
городами
(
)
j
i
э
э
,
интерпретируется
как
вес
соответствующего
ребра
(
)
.
,
j
i
x
x
w
Таким
образом
,
в
терминах
теории
графов
рассматриваемая
задача
-
это
поиск
в
ориентированном
или
неориентированном
графе
гамильтонова
цикла
минимальной
длины
.
Формальная
постановка
задачи
имеет
вид
-
выполнить
преобразование
исходного
графа
G
в
граф
результата
G
c
:
(
)
(
)
c
c
D
U
X
G
W
U
X
G
,
,
,
→
>
<
так
что
( )
( )
∑
→
=
=
⊂
min
:
r
c
c
c
c
u
w
G
W
X
U
U
U
c
r
U
u
∈
причем
(
) ( )
(
)
(
)
,
,
,
2
,
i
i
i
i
i
i
x
x
S
X
x
x
x
p
X
x
∃
∈
∀
=
∈
∀
где
( )
i
x
p
-
количество
ребер
,
подходящих
к
вершине
; a
(
)
i
i
x
x
S
,
-
маршрут
между
вершинами
,
,
i
i
x
x
т
.
е
.
последовательность
смежных
ребер
,
связывающих
зги
вершины
.
Следует
иметь
в
виду
,
что
граф
имеет
гамильтонов
цикл
,
если
сумма
локальных
степеней
любой
пары
вершин
больше
или
равна
числу
его
вершин
:
(
) ( )
( )
[
]
.
,
n
x
p
x
p
X
x
x
j
i
i
i
≥
+
∈
∀
В
противном
случае
граф
может
не
иметь
гамильтонова
цикла
,
что
для
нас
означает
,
что
в
некоторых
случаях
задача
может
не
иметь
решения
.
Задача
относится
к
классу
NP-
сложных
-
задач
,
вычислительная
сложность
которых
не
выражается
в
виде
полинома
от
размерности
ее
входа
(
количества
городов
),
а
носит
экспоненциальный
характер
,
т
.
е
.
очень
быстро
возрастает
при
увеличении
размерности
задачи
.
Известно
,
что
точное
решение
задачи
коммивояжера
может
быть
получено
алгоритмами
,
реализующими
полный
перебор
или
метод
ветвей
и
границ
.
Приближенное
решение
дают
методы
поиска
в
глубину
и
двоичной
свертки
.
Поскольку
по
техническому
заданию
необходимо
обеспечить
получение
точного
решения
,
следует
реализовать
хотя
бы
по
одному
методу
из
указанных
групп
.
Для
выбора
методов
нужно
провести
дополнительные
исследования
.
Определив
методы
решения
,
целесообразно
для
некоторых
вариантов
исходных
данных
вручную
,
на
калькуляторе
или
с
использованием
других
средств
подсчитать
ожидаемые
результаты
.
Эти
данные
в
дальнейшем
будут
использованы
при
тестировании
программного
обеспечения
.
Кроме
того
,
выполнение
операций
вручную
позволяет
точно
уяснить
последовательность
действий
,
что
упростит
разработку
алгоритмов
.
Кроме
того
,
имеет
смысл
продумать
,
для
каких
сочетаний
исходных
данных
результат
не
существует
или
не
может
быть
получен
данным
методом
,
что
тоже
необходимо
учесть
при
разработке
программного
обеспечения
.
Контрольные
вопросы
и
задания
1.
В
чем
сущность
структурного
подхода
к
программированию
?
Какие
этапы
охватывает
данный
подход
?
2.
Что
понимают
под
термином
«
спецификации
»?
В
чем
сложность
их
уточнения
?
Назовите
модели
,
используемые
в
качестве
функциональных
спецификаций
при
структурном
подходе
.
Какие
характеристики
проектируемого
программного
обеспечения
описывает
каждая
из
них
?