Основы проектирования информационных систем. Модели

Введение Введение Принципы моделирования Принципы моделирования Принципы моделирования Принципы моделирования Визуальное представление моделей Визуальное представление моделей Визуальное представление моделей Визуальное представление моделей Конечные автоматы Конечные автоматы Конечные автоматы Конечные автоматы Пример с удалением комментариев Пример с удалением комментариев Пример с удалением комментариев Пример с удалением комментариев Регулярные выражения Регулярные выражения Регулярные выражения Регулярные выражения Системы потоков Системы потоков Системы потоков Системы потоков Стохастические модели Стохастические модели Стохастические модели Стохастические модели Марковские процессы Марковские процессы Марковские процессы Марковские процессы Дискретные цепи Маркова Дискретные цепи Маркова Дискретные цепи Маркова Дискретные цепи Маркова Процессы размножения и гибели Процессы размножения и гибели Процессы размножения и гибели Процессы размножения и гибели Системы массового обслуживания Системы массового обслуживания Системы массового обслуживания Системы массового обслуживания Внутри «прибора»: параллельные процессы Внутри «прибора»: параллельные процессы Внутри «прибора»: параллельные процессы Внутри «прибора»: параллельные процессы Структурный системный анализ Структурный системный анализ Структурный системный анализ Структурный системный анализ Функциональные модели IDEF0 Функциональные модели IDEF0 Функциональные модели IDEF0 Функциональные модели IDEF0

Системы и модели Система – совокупность взаимодействующих компонентов и взаимосвязей между ними. Система – совокупность взаимодействующих компонентов и взаимосвязей между ними. Модель – упрощенное представление системы (упрощенное представление реальности). Модель – упрощенное представление системы (упрощенное представление реальности). «Мы строим модель для того, чтобы лучше понимать разрабатываемую систему». «Мы строим модель для того, чтобы лучше понимать разрабатываемую систему». Гради Буч Модель дает полное, точное и адекватное описание системы, имеющее конкретное назначение. Это назначение называется целью модели. Модель дает полное, точное и адекватное описание системы, имеющее конкретное назначение. Это назначение называется целью модели.

Значение моделирования ??? В каких случаях разумно моделировать? Будет ли от этого толк? Что такое ХОРОШАЯ модель?

Резюме Создаваемые человеком системы сложны. Для понимания и планирования разработки/изменений организационных и информационных систем применяются упрощенные представления – модели. Создаваемые человеком системы сложны. Для понимания и планирования разработки/изменений организационных и информационных систем применяются упрощенные представления – модели. В организационной/информационной системе присутствуют структура и процессы. В организационной/информационной системе присутствуют структура и процессы. Модели могут отражать статические свойства системы (структуру) и/или ее динамические свойства (процессы). Модели могут отражать статические свойства системы (структуру) и/или ее динамические свойства (процессы). Модель не тождественна системе. Модель не тождественна системе. Модель отвечает на НЕКОТОРЫЕ вопросы о системе. Модель отвечает на НЕКОТОРЫЕ вопросы о системе. Модель должна иметь цель – множество вопросов, на которые ей предстоит ответить (с желаемой точностью). Модель должна иметь цель – множество вопросов, на которые ей предстоит ответить (с желаемой точностью).

Модель как проекция. Точка зрения модели При моделировании систем реального мира и нетривиальных программных систем выбор проекций неочевиден. При моделировании систем реального мира и нетривиальных программных систем выбор проекций неочевиден. Проекция (точка зрения) определяет, на какие вопросы может ответить модель. Проекция (точка зрения) определяет, на какие вопросы может ответить модель.

Границы модели Сложные системы, как правило, открыты – они взаимодействуют с внешним миром. Сложные системы, как правило, открыты – они взаимодействуют с внешним миром. Проекцию чего следует включить в модель? Если усеченный цилиндр стоит на столе, то следует ли изображать стол? А следует ли изображать реальное положение такого цилиндра, если он лежит? Проекцию чего следует включить в модель? Если усеченный цилиндр стоит на столе, то следует ли изображать стол? А следует ли изображать реальное положение такого цилиндра, если он лежит? Приходится принимать решения о границах моделируемой системы – границах модели. Приходится принимать решения о границах моделируемой системы – границах модели.

Цель, точка зрения, границы модели – главные вопросы Цель определяет возможный набор точек зрения (часто – единственную возможную точку зрения) и допустимые границы модели. Цель определяет возможный набор точек зрения (часто – единственную возможную точку зрения) и допустимые границы модели. Невозможность задать границы модели, соответствующие цели – признак того, что, возможно, цель модели выбрана неверно. Невозможность задать границы модели, соответствующие цели – признак того, что, возможно, цель модели выбрана неверно.

Задачи моделирования Визуализировать систему в ее текущем или желаемом состоянии. Визуализировать систему в ее текущем или желаемом состоянии. Описать структуру или поведение системы. Описать структуру или поведение системы. Получить шаблон, позволяющий сконструировать систему. Получить шаблон, позволяющий сконструировать систему. Документировать принимаемые решения. Документировать принимаемые решения.

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

Сфера применения Бизнес-процессы, организация деятельности предприятия, бухгалтерия, документооборот… Бизнес-процессы, организация деятельности предприятия, бухгалтерия, документооборот… Производство, строительство, транспорт… Производство, строительство, транспорт… Разработка программного обеспечения. Разработка программного обеспечения. Сложные информационные системы: ИПС, системы семантического анализа, обработка текстовых корпусов, системы параллельных вычислений… Сложные информационные системы: ИПС, системы семантического анализа, обработка текстовых корпусов, системы параллельных вычислений… Игры. Игры. Эко-, био- и социальные системы. Эко-, био- и социальные системы. Системы искусственного интеллекта, описание деятельности мозга. Системы искусственного интеллекта, описание деятельности мозга. …

Типы моделей. Общий взгляд Структурная (подчеркивает организацию системы). Структурная (подчеркивает организацию системы). Поведенческая (отображает процессы, динамику). Поведенческая (отображает процессы, динамику). С другой стороны: Математическая, физическая, … Математическая, физическая, … Что может отражать модель? Структурные сущности (классы, интерфейсы, кооперации, варианты использования)… Структурные сущности (классы, интерфейсы, кооперации, варианты использования)… Поведенческие сущности (взаимодействия, автоматы, деятельность)… Поведенческие сущности (взаимодействия, автоматы, деятельность)… Зависимости, ассоциации, обобщения, цепочки ответственности… Зависимости, ассоциации, обобщения, цепочки ответственности…

Немного терминологии Какие сущности могут быть полезны при моделировании? Класс Класс Интерфейс Интерфейс Кооперация Кооперация Вариант использования Вариант использования Деятельность Деятельность Взаимодействие Взаимодействие Последовательность Последовательность Автомат Автомат

Понятный частный пример Веб-ресурс Структура. Классы. Структура. Классы. Варианты использования. Варианты использования. Повышение эффективности с точки зрения пользователя.Повышение эффективности с точки зрения пользователя. Достижение коммерческих целей.Достижение коммерческих целей. Взаимодействия клиент – сервер. Взаимодействия клиент – сервер. Потоки запросов. Потоки запросов. Обеспечение функциональности, клиентское и серверное программирование. Обеспечение функциональности, клиентское и серверное программирование. Структура и процессы с точки зрения разработчика.Структура и процессы с точки зрения разработчика. Развертывание, продвижение, сопровождение. Развертывание, продвижение, сопровождение.

Принципы моделирования 1. Выбор модели оказывает решающее воздействие на подход к решению проблемы и на то, как будет выглядеть решение. 2. У каждой модели есть точка зрения и своя степень точности. 3. Лучшие модели – те, что ближе к реальности. 4. Наилучший подход – использовать совокупность моделей, почти независимых друг от друга.

О выборе модели Аристотель ( г. до н.э.) Гиппарх (125 г. до н.э.) Аристарх Самосский (III в. до н.э.) Целлариус «Небесный атлас» (1660 г.) Коперник ( г.)

Еще о выборе модели 1596 – – 1650 Как жили до декартовой системы координат? Как жили до декартовой системы координат? Какие были модели геометрической информации? Какие были модели геометрической информации?

И еще о выборе модели Реляционная база данных отделы программирования моделирования Лаб. 1Лаб. 2Лаб. 3 Птичкин Воробьев Грачев Проекты QW237-SD AVP-2008 IDEF0-55 Орлов

Системная архитектура Аспекты представления системы: проектирование, дизайн реализация процессы, взаимодействия развертывание варианты использования словарь, функциональность сборка системы, конфигурирование поведение производительность, масштабируемость, пропускная способность топология системы, распределение, поставка, установка

Визуальное представление модели Чертеж, карта, макет, … Чертеж, карта, макет, …

Визуальное представление модели Блок-схема Блок-схема

Визуальное представление модели Граф переходов между состояниями Граф переходов между состояниями off работа on подготовка включение проверка готовности включение установка параметров выключение

Визуальное представление модели Диаграмма «заполнить форму» - стандарт IDEF0 Диаграмма «заполнить форму» - стандарт IDEF0 Ожидать завершения ввода данных Проверить, все ли данные внесены Вывести сообщение о неполноте данных Пустая форма Данные Требование полноты данных Значения полей формы Заполненная форма Не все данные Возврат к заполнению формы

Визуальное представление модели Отдел обслуживания клиентов Отдел продаж Склад Заказать товар Обработать заказ Подобрать товар Отгрузить заказ Выставить счет Получить заказ Оплатить счет Закрыть заказ

Визуальное представление модели Диаграмма (неформальная) Диаграмма (неформальная)

Визуальное представление модели Диаграмма (неформальная) Диаграмма (неформальная)

Наши задачи Получить представление о разнообразии моделей. Получить представление о разнообразии моделей. Прочувствовать специфику некоторых классов систем. Прочувствовать специфику некоторых классов систем. Осознать, что база моделирования – это выбор адекватной модели и удачного набора точек зрения. Осознать, что база моделирования – это выбор адекватной модели и удачного набора точек зрения. Согласиться с тем, что необходимы формальные стандарты моделирования. Согласиться с тем, что необходимы формальные стандарты моделирования. Рассмотреть бегло один из таких стандартов – IDEF0 (Integration DEFinition 0) – функциональное моделирование (Function Modeling). Рассмотреть бегло один из таких стандартов – IDEF0 (Integration DEFinition 0) – функциональное моделирование (Function Modeling). И чуть более подробно – другой стандарт – UML (Unified Modelling Language) И чуть более подробно – другой стандарт – UML (Unified Modelling Language)

Конечные автоматы (Finite state machine) Автомат – это поведение, специфицирующее последовательность состояний, через которые проходит объект за время своего существования в ответ на события (стимулы), а также его реакцию на эти события. Автомат – это поведение, специфицирующее последовательность состояний, через которые проходит объект за время своего существования в ответ на события (стимулы), а также его реакцию на эти события. Термины и понятия Термины и понятия Состояние Состояние Событие (стимул)Событие (стимул) Переход Переход Деятельность (activity)Деятельность (activity) Действие (action)Действие (action)

Конечные автоматы: строгое определение Конечный автомат может быть задан параметрами: Q – конечное множество состояний Q – конечное множество состояний q 0 Q – начальное состояние q 0 Q – начальное состояние F Q – множество заключительных состояний F Q – множество заключительных состояний – конечное множество входных символов – конечное множество входных символов – заданное отображение Q Q (функция переходов) = (q i, b), где b – заданное отображение Q Q (функция переходов) = (q i, b), где b

Конечные автоматы: классы 1. Детерминированные и недетерминированные. 2. «С памятью» или без оной. Автомат Мура – выходные сигналы зависят только от текущего состояния.Автомат Мура – выходные сигналы зависят только от текущего состояния. Автомат Мили - выходные сигналы зависят как от текущего состояния, так и от текущих значений входных сигналов. Иначе говоря:Автомат Мили - выходные сигналы зависят как от текущего состояния, так и от текущих значений входных сигналов. Иначе говоря: В автомате Мура все действия привязаны к состояниям.В автомате Мура все действия привязаны к состояниям. В автомате Мили все действия привязаны к переходам.В автомате Мили все действия привязаны к переходам. В реальных ситуациях модель обычно представляет собой комбинацию машин Мура и Мили.В реальных ситуациях модель обычно представляет собой комбинацию машин Мура и Мили.

Пример: светофор таймер

Пример: из жизни хищника состояниестимулы охотникдобыча 1. сытый убежать 2 2 спать 2. голодный убежать 2 2 съесть 1 1 действия …

Пример: система климат-контроля простой охлаждение активация активен обогрев жарко холодно жарко холодно t 0 ОК готов t 0 ОК

Задача: анализ текста В тексте возведение в степень обозначалось двумя идущими подряд звездочками. Решено заменить это обозначение на '^' (так что, к примеру, 'x**y' заменится на 'x^y'). Как это проще всего сделать? Исходный текст разрешается читать символ за символом, получающийся текст требуется печатать символ за символом. состояние очередной входной символ новое состояние действие основное *'*'*'*' после * нет основное x * x ' * 'основное печать х после * *'*'*'*'основное печать печать '^' после * x * x ' * 'основное печать *х печать ' * ' х

Задачи (анализ текста) Описать автомат, удаляющий из текста заданную подстроку. Описать автомат, удаляющий из текста заданную подстроку. Описать автомат, удаляющий из текста программы комментарии ( /* … */ ). Описать автомат, удаляющий из текста программы комментарии ( /* … */ ). Описать автомат, удаляющий из HTML-кода (или модифицирующий) заданные HTML-теги. Описать автомат, удаляющий из HTML-кода (или модифицирующий) заданные HTML-теги. Подумать над автоматом для определения в тексте фрагментов, представляющих собой, например, URL или . Подумать над автоматом для определения в тексте фрагментов, представляющих собой, например, URL или .

Автомат, удаляющий из текста программы комментарии 1 вариант 1 вариант Вне комм. Вне комм. после / Внутри комм. Внутри комм. после * / * * / * / * * / Вне комм. после /* Внутри комм. после */ * * / /

Автомат, удаляющий из текста программы комментарии 2 вариант 2 вариант Вне комм. Вне комм. после / Внутри комм. Внутри комм. после * / * * / * * / * / Конец анализируемого текста print('/'+s) print(s)

Автомат, удаляющий из текста программы комментарии Матрица стимулов (входных символов) Матрица стимулов (входных символов) состояния / / 1 ** 2 ** 3/ /

Автомат, удаляющий из текста программы комментарии Матрица действий Матрица действий состояния вывод очередного символа 1 вывод '/ ' и очередного символа 2 3

К.А.: модель банкомата Так работает банкомат Сбербанка (не слишком эффективно) Ожидание Запрос pin-кода Запрос операции Запрос суммы Выполнение операции Вставлена карта Неверный код Снятие наличных Остаток на счете Нет денег Завершение работы Выдача денег, чека, … Возврат карты Запрос на продолжение ОК нет да Такой банкомат умнее

Обобщение и развитие темы Бесконечное число состояний. Бесконечное число состояний. Описание вероятностных характеристик переходов. Описание вероятностных характеристик переходов. Акцент на описании процесса переходов Акцент на описании процесса переходов Расчет характеристик процесса. Расчет характеристик процесса. Попытка управления процессом с точки зрения некоторого функционала качества. Попытка управления процессом с точки зрения некоторого функционала качества.

Системы потоков Динамические системы S n = f(S n-1 ) Системы потоков регулярные нерегулярные Системы массового обслуживания (СМО) (системы с очередями) прибор запросы

ДС: Фракталы z n+1 = f(z n ) = a z n 2 + b z n + C

Регулярные системы потоков Одноканальные Одноканальные λ μ λ – интенсивность поступления запросов μ – интенсивность обслуживания (пропускная способность) μ > λ – условие стабильности

Другие возможные задачи Оптимизация по стоимости или времени протекания процесса. Оптимизация по стоимости или времени протекания процесса. Несколько начальных или конечных состояний. Несколько начальных или конечных состояний. Комбинированные потоки. Комбинированные потоки. … Стохастические модели. Стохастические модели.

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

Стохастическая одноканальная модель Время поступления запросов случайно. Время поступления запросов случайно. => случайно количество запросов. => случайно количество запросов. Время обслуживания также случайно. Время обслуживания также случайно. λ μ Теперь одноканальная модель уже не кажется тривиальной

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

Дискретные цепи Маркова Задача путешественника Задача путешественника p ij - вероятность перехода из состояния i в состояние j /4 1/4 3/4 1/2

Задача путешественника Матрица вероятностей перехода Матрица вероятностей перехода Вероятность попадания в состояние j из состояния i за m шагов p ij (m) = p ik (m-1) p kj Вероятность попадания в состояние j из состояния i за m шагов p ij (m) = p ik (m-1) p kj 03/41/4 1/403/4 1/41/41/2 P = k

Процессы размножения и гибели P ij = d j j = i b j - d j j = i b j j = i+1 0 в остальных случаях Состояния характеризуется объемом популяции. Состояния характеризуется объемом популяции. Возможны переходы только в «соседние» состояния. Возможны переходы только в «соседние» состояния. Вероятности переходов, вообще говоря, зависят от состояния. Вероятности переходов, вообще говоря, зависят от состояния.

Процессы размножения и гибели Матрица вероятностей перехода Матрица вероятностей перехода 1-b 0 b0b0b0b … d1d1d1d1 1-b 1 - d 1 b1b1b1b100000… 0 d2d2d2d2 1-b 2 - d 2 b2b2b2b20000… 00 d3d3d3d3 1-b 3 - d 3 b3b3b3b3000… 000 d4d4d4d4 1-b 4 - d 4 b4b4b4b400… 0000 d5d5d5d5 1-b 5 - d 5 b5b5b5b50… d6d6d6d6 1-b 6 - d 6 b6b6b6b6… ………

Процессы размножения и гибели Рассмотрев вместо вероятностей интенсивности переходов, получаем классический процесс общего вида. Вероятность ровно одного «рождения» в промежутке Δt : k Δt + o(Δt) Вероятность ровно одного «рождения» в промежутке Δt : k Δt + o(Δt) Вероятность ровно одной «гибели» в промежутке Δt : k Δt + o(Δt) Вероятность ровно одной «гибели» в промежутке Δt : k Δt + o(Δt) Основное применение модели: анализ потоков в системах с обслуживанием запросов. Основное применение модели: анализ потоков в системах с обслуживанием запросов. 012К-1К+1К … … 0 1 к-1 k 1 2 k k+1

Процессы размножения и гибели Для процесса общего вида: p k+1 = p 0 = p k Формула Литтла: N = λ T Среднее число запросов в системе равно произведению интенсивности их поступления на среднее время пребывания запроса в системе. i=0 K i

Системы массового обслуживания (Queueing systems) – «СМО» Совокупность «приборов» («каналов»). Совокупность «приборов» («каналов»). Потоки запросов (однородные или неоднородные). Потоки запросов (однородные или неоднородные). Характеристики входных потоков. Характеристики входных потоков. Характеристики «приборов». Характеристики «приборов». Стратегия обслуживания. Стратегия обслуживания.

Вопросы, представляющие интерес Среднее количество запросов в системе. Среднее количество запросов в системе. Ожидаемое время, проведенное запросом в системе (или в очереди). Ожидаемое время, проведенное запросом в системе (или в очереди). Ожидаемый промежуток времени непрерывной загрузки прибора. Ожидаемый промежуток времени непрерывной загрузки прибора. Ожидаемый пик нагрузки. Ожидаемый пик нагрузки. Дисциплина обслуживания, приоритеты. Распределение запросов по приборам (каналам). Дисциплина обслуживания, приоритеты. Распределение запросов по приборам (каналам).

Основные характеристики СМО ξ : коэффициент использования = произведение средней интенсивности поступления запросов на среднее время обслуживания ξ : коэффициент использования = произведение средней интенсивности поступления запросов на среднее время обслуживания N : среднее число запросов в системе N : среднее число запросов в системе T : Среднее время пребывания в системе T : Среднее время пребывания в системе 012К-1К+1К … … 0 1 к-1 k 1 2 k k+1

Простейшие классические СМО: 1 М / М / 1 k = ; k = М / М / 1 k = ; k = Проще не бывает: в любом состоянии интенсивности поступления запросов и интенсивности их обслуживания – константы. Оказывается, что в этом случае процессы поступления и обслуживания запросов обладают замечательным свойством – отсутствием последействия (прошлая история случайного процесса не влияет на предсказание будущего). То есть, эти процессы являются марковскими.

Простейшие классические СМО: 1 М / М / 1 k = ; k = М / М / 1 k = ; k = Вероятность прихода k запросов в промежутке t : Плотность распределения интервала между соседними запросами: a(t) = e - a(t) = e - t ( ( t) k e - t k! P k (t) = - распределение Пуассона - показательное распределение

Простейшие классические СМО: 1 М / М / 1 k = ; k = М / М / 1 k = ; k = ξ = /μ p k = p 0 ξ k ; p 0 = 1 - ξ N = k p k = ξ / (1-ξ) N = k p k = ξ / (1-ξ) T = 1 / ( (1- ξ) ) T = 1 / ( (1- ξ) )

Простейшие классические СМО: 1 М / М / 1 k = ; k = М / М / 1 k = ; k = Пуассоновский входящий поток Постоянная интенсивность поступления / обслуживания Показательное распределение промежутков Отсутствие последействия

Простейшие классические СМО: 2 М / М / 1 k = / (k+1); k = М / М / 1 k = / (k+1); k = p k = p 0 ( / ) k / k! ξ = 1 – e - / ξ = 1 – e - / N = / N = / T = 1 / ( (1- ξ) ) T = 1 / ( (1- ξ) )

Простейшие классические СМО: 3 М / М / - немедленное обслуживание k = k = k = k k = k N = N = / T = 1 / T = 1 /

Простейшие классические СМО: 4 М / М / m - несколько приборов k = k = k = min { k, m } k = min { k, m } ξ = / m ξ = / m

Простейшие классические СМО: 5 М / М / 1 / K - конечный накопитель (k=1 - система с удалением заблокированных запросов) заблокированных запросов), k=K k = k =

Простейшие классические СМО: 6 М / М / m - система с несколькими приборами и потерями, k=m k = k k = k

Внутри «прибора»: параллельные процессы Как управлять очередью? Как управлять очередью? Проблема взаимного исключения при совместном доступе к ресурсам (синхронизация процессов). Проблема взаимного исключения при совместном доступе к ресурсам (синхронизация процессов). процесс Критическая секция

Параллельные процессы. 1 flag1:= false flag2:= false Процесс 1 Критическая секция 1 flag1:= true flag2 flag1:= false Процесс 2 Критическая секция 2 flag2:= true flag1 flag2:= false yes no yes no

Параллельные процессы. 2 flag1:= false; flag2:= false Процесс 1 Критическая секция 1 flag1:= true flag2 & (letPass=2) flag1:= false letPass:= 2 Процесс 2 Критическая секция 2 flag2:= true flag1 & (letPass=1) flag2:= false letPass:= 1 yes no

Параллельные процессы: семафор Персоналиии «проблемы взаимного исключения»: Эдсгер Дейкстра (1965 г.) Эдсгер Дейкстра (1965 г.) Гарри Петерсен (1981 г.) Гарри Петерсен (1981 г.) Объекты класса «семафор» принимают целочисленные неотрицательные значения и имеют методы: V(s) s:= s + 1 P(s) s = 0 s:= s - 1 yes no

Параллельные процессы: семафор semaphore:= 1 Процесс 1 Критическая секция 1 semaphore.P() semaphore.V() Процесс 2 Критическая секция 2 semaphore.P() semaphore.V()

Параллельные процессы: писатели и читатели блокировка жесткаярекомендательная исключительнаяразделяемая

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

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

Исторические вехи SA – Structured Analysis ( 1960-е – середина 1970-х ) SA – Structured Analysis ( 1960-е – середина 1970-х ) системы автоматизированного проектирования,системы автоматизированного проектирования, структурный анализ при создании алгоритмических языков.структурный анализ при создании алгоритмических языков. SADT – Structural Analysis and Design Technique ( 1974 ) SADT – Structural Analysis and Design Technique ( 1974 ) методология структурного проектированияметодология структурного проектирования Программа ICAM - Integrated Computer-Aided Manufacturing ( конец 1970-х ) Программа ICAM - Integrated Computer-Aided Manufacturing ( конец 1970-х ) интегрированная компьютеризация производства СШАинтегрированная компьютеризация производства США начало разработки методологии IDEF (ICAM Definition)начало разработки методологии IDEF (ICAM Definition)

Исторические вехи Развитие объектно-ориентированных методов (1980-е) Развитие объектно-ориентированных методов (1980-е) «Война методов» «Война методов» Object-Oriented Software Engineering (OOSE)Object-Oriented Software Engineering (OOSE) Object Modeling Technique (OMT) …Object Modeling Technique (OMT) … Unified Modeling Language – UML (1994) Unified Modeling Language – UML (1994) объектно-ориентированное моделирование системы в целом, от концепции до исполняемых компонентов;объектно-ориентированное моделирование системы в целом, от концепции до исполняемых компонентов; решение проблемы масштабируемости;решение проблемы масштабируемости; создание языка моделированиясоздание языка моделирования наглядного и интуитивно понятного для разных категорий специалистов, работающих над проектом, наглядного и интуитивно понятного для разных категорий специалистов, работающих над проектом, легко конвертируемого в программный код. легко конвертируемого в программный код.

Исторические вехи XXI век. Дальнейшее развитие методологии, методологии, стандартов IDEF, UML …, стандартов IDEF, UML …, графических нотаций, графических нотаций, инструментальных средств моделирования. инструментальных средств моделирования. Использование инструментальных средств предполагает следование стандартам и соблюдение строгой формализации при разработке моделей; предполагает следование стандартам и соблюдение строгой формализации при разработке моделей; позволяет генерировать соответствующие программные модули. позволяет генерировать соответствующие программные модули.

Графические нотации Диаграммы функционального моделирования ( Structured Analysis and Design Technique, SADT) Диаграммы функционального моделирования ( Structured Analysis and Design Technique, SADT) Диаграммы "сущность-связь" ( Entity- Relationship Diagrams, ERD) Диаграммы "сущность-связь" ( Entity- Relationship Diagrams, ERD) Диаграммы потоков данных ( Data Flow Diagrams, DFD). Диаграммы потоков данных ( Data Flow Diagrams, DFD). …

Примеры диаграмм SADT (IDEF0)

Примеры диаграмм ERD

Пример диаграммы IDEF3

Стандарты IDEF IDEF0 (Integration Definition For Functional Modelling) - функциональные модели: IDEF0 (Integration Definition For Functional Modelling) - функциональные модели: функции информационной средыфункции информационной среды информация и объекты, связывающие эти функцииинформация и объекты, связывающие эти функции IDEF1X – информационные модели IDEF1X – информационные модели структура информации, необходимой для поддержки функций системыструктура информации, необходимой для поддержки функций системы IDEF2 – динамические модели IDEF2 – динамические модели изменение во времени функций, информационных потоков и ресурсов системыизменение во времени функций, информационных потоков и ресурсов системы IDEF3, IDEF4, …, IDEF14 IDEF3, IDEF4, …, IDEF14

Функциональные модели IDEF0 Цель: документирование информационных и производственных процессов и отображение информации об использовании ресурсов на каждом из этапов проектирования системы. Функциональная модель SADT отображает структуру процессов функционирования системы и ее отдельных подсистем, т. е. выполняемые ими действия и связи между этими действиями Основные сущности: функциональные блоки функциональные блоки объектные потоки объектные потоки Графическая нотация: функциональная диаграмма IDEF0

Основные концепции IDEF0 1. Модель Модель дает полное, точное и адекватное описание системы.Модель дает полное, точное и адекватное описание системы. Модель имеет конкретное назначение. Оно называется целью модели.Модель имеет конкретное назначение. Оно называется целью модели. Цель определяет возможный набор точек зрения (часто – единственную возможную точку зрения) и допустимые границы модели.Цель определяет возможный набор точек зрения (часто – единственную возможную точку зрения) и допустимые границы модели.

Основные концепции IDEF0 2. Блочное моделирование Система представляется в виде функциональных блоков Система представляется в виде функциональных блоков Связи и взаимодействия между блоками характеризуются объектными потоками.Связи и взаимодействия между блоками характеризуются объектными потоками. Модель представляет собой набор взаимосвязанных диаграмм.Модель представляет собой набор взаимосвязанных диаграмм.

Основные концепции IDEF0 3. Принцип декомпозиции (Decomposition) - разбиение сложного процесса на составляющие его функции. 4. Глоссарий (Glossary) - набор соответствующих определений, ключевых слов, и т.д., характеризующих каждый объект модели.

Основные элементы диаграммы IDEF0 функциональный блок (Activity Box) - изображается прямоугольником. функциональный блок (Activity Box) - изображается прямоугольником. интерфейсная дуга (Arrow) - изображается стрелкой. интерфейсная дуга (Arrow) - изображается стрелкой. Обслужить пользователя уровень доступа администратор монитор системы login password база данных запрос база данных протокол

Функции - основа IDEF0-модели Название функции – глагол. Функция описывает не то, что обязательно происходит, но то, что может произойти при определенных сочетаниях входов, управлений, механизмов. Функция в IDEF0 существует вне времени, сама по себе она атомарна. Функция изображается прямоугольником (блоком). Стрелки, касающиеся сторон блока, изображают условия выполнения функции и те условия для выполнения других функций, которые данная функция порождает.

Объектные потоки Условия выполнения функций при моделировании информационных и организационных систем чаще всего представляют собой наборы объектов (реальных или искусственных) – объектные потоки. Каждый объектный поток на диаграмме IDEF0 должен иметь название (имя существительное). Объектные потоки на диаграммах IDEF0 изображаются в виде стрелок. Имена и другие характеристики объектных потоков входят в словарь данных модели. Этот словарь может затем использоваться для создания моделей «сущность-связь».

Функциональный блок Функция управление (Control) механизм (Mechanism) вызов (Call) вход (Input) выход (Output) Обслужить пользователя уровень доступа администратор монитор системы login password база данных запрос база данных протокол

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

Фрагмент диаграммы IEDF0 учиться сдать сессию студент стандарты на специальность студент, сдавший сессию студент, переживший семестр отчисленный студент студент, сдавший все экзамены

Функциональный блок: примечания Итак, Диаграммы содержат блоки и дуги Диаграммы содержат блоки и дуги Блоки представляют функции Блоки представляют функции Блоки имеют доминирование Блоки имеют доминирование Дуги изображают Дуги изображают объектыобъекты взаимосвязи между блокамивзаимосвязи между блоками наборы объектовнаборы объектов

Синтаксис диаграмм Объектные потоки ICOM прямолинейный сегмент поворот под углом 90 0, скруглен расщепление слияние

UML Unified modelling language Унифицированный язык моделирования Unified modelling language Унифицированный язык моделирования Диаграммы Диаграммы взаимодействия Структурные Диаграммы поведения

Структурные диаграммы Диаграмма классов (Structure diagram) Диаграмма компонентов (Component diagram) Диаграмма объектов (Object diagram) Диаграмма композитной (составной структуры) (Composite structure diagram) Диаграмма развёртывания (Deployment diagram) Диаграмма профилей (Profile diagram) Диаграмма пакетов (Package diagram)

Диаграммы поведения Диаграмма деятельности (Activity diagram) Диаграмма прецедентов (Use case diagram) Диаграммы взаимодействия (Interaction Diagrams) Диаграмма состояний (State Machine diagram) Диаграмма последовательности (Sequence diagram) Диаграмма коммуникации (Communication diagram) Диаграмма обзора взаимодействия (Interaction overview diagram) Диаграмма синхронизации (Timing diagram)

Взаимосвязь между диаграммами (один из возможных взглядов)

Диаграмма классов Центральное место в объектно-ориентированном программировании занимает разработка логической модели системы в виде диаграммы классов. Диаграмма классов (class diagram) служит для представления статической структуры модели системы в терминологии классов объектно-ориентированного программирования. Центральное место в объектно-ориентированном программировании занимает разработка логической модели системы в виде диаграммы классов. Диаграмма классов (class diagram) служит для представления статической структуры модели системы в терминологии классов объектно-ориентированного программирования. Диаграмма классов представляет собой граф, вершинами которого являются элементы типа «классификатор», связанные различными типами структурных отношений. Диаграмма классов может также содержать интерфейсы, пакеты, отношения и даже отдельные экземпляры, такие как объекты и связи. Диаграмма классов представляет собой граф, вершинами которого являются элементы типа «классификатор», связанные различными типами структурных отношений. Диаграмма классов может также содержать интерфейсы, пакеты, отношения и даже отдельные экземпляры, такие как объекты и связи.

Диаграмма классов Класс (class) в языке UML служит для обозначения множества объектов, которые обладают одинаковой структурой, поведением и отношениями с объектами других классов. Класс (class) в языке UML служит для обозначения множества объектов, которые обладают одинаковой структурой, поведением и отношениями с объектами других классов. Имя класса (для абстрактного класса выводится курсивом) Атрибуты (свойства) класса Student::RegUser name: String(15) address: String(35) userID: String phoneNmbr: String logon() requestCatalogue() Методы (операции) класса Имя пакета Имена классов образуют словарь предметной области

Атрибуты класса [кратность]: [кратность]: = {строка-свойство} = {строка-свойство} квантор видимости квантор видимости «+» обозначает атрибут с областью видимости типа общедоступный (public). Атрибут с этой областью видимости доступен или виден из любого другого класса пакета, в котором определена диаграмма; «+» обозначает атрибут с областью видимости типа общедоступный (public). Атрибут с этой областью видимости доступен или виден из любого другого класса пакета, в котором определена диаграмма; «#» обозначает атрибут с областью видимости типа защищенный (protected). Атрибут с этой областью видимости недоступен или невиден для всех классов, за исключением подклассов данного класса; «#» обозначает атрибут с областью видимости типа защищенный (protected). Атрибут с этой областью видимости недоступен или невиден для всех классов, за исключением подклассов данного класса; «-» обозначает атрибут с областью видимости типа закрытый (private). Атрибут с этой областью видимости недоступен или невиден для всех классов без исключения. «-» обозначает атрибут с областью видимости типа закрытый (private). Атрибут с этой областью видимости недоступен или невиден для всех классов без исключения. квантор видимости

Атрибуты класса [кратность]: [кратность]: = {строка-свойство} = {строка-свойство} Имя атрибута студент regUser счет факультет visibility … Имя атрибута студент regUser счет факультет visibility … Кратность (границы – целые положительные числа) [1..2] [2..5,10..15] [2..*] [*] - любое положительное число или 0 [1] - ровно 1 Кратность (границы – целые положительные числа) [1..2] [2..5,10..15] [2..*] [*] - любое положительное число или 0 [1] - ровно 1 Тип атрибута String Integer Color Цвет Многоугольник Тип атрибута String Integer Color Цвет Многоугольник Строка-свойство служит для указания значений атрибута, которые не могут быть изменены при работе с данным типом объектов. Строка-свойство служит для указания значений атрибута, которые не могут быть изменены при работе с данным типом объектов. тип атрибута имя атрибута кратность {строка-свойство}

Атрибуты класса: примеры [кратность]: [кратность]: = {строка-свойство} = {строка-свойство} цвет: Соlоr имя_студента [1..2]: String видимость: Boolean форма: эллипс formType: ellipce цвет:Соlоr = (255, 0, 0) форма: Прямоугольник = квадрат занятие: Программирование стипендия : Currency = $30 стипендия: Currency = {$30} Подчеркивание означает, что атрибут может принимать подмножество значений из некоторой области. «Все объекты данного класса могут иметь несколько различных форм, каждая из которых является прямоугольником» абстрактный атрибут

Операции (методы) класса (список параметров): (список параметров): {строка-свойство} {строка-свойство} Квантор видимости Квантор видимости «+» - область видимости типа общедоступный (public) «+» - область видимости типа общедоступный (public) «#» - область видимости типа защищенный (protected) «#» - область видимости типа защищенный (protected) «-» - область видимости типа закрытый (private) «-» - область видимости типа закрытый (private) Список параметров набор разделенных запятой формальных параметров в формате: : = Список параметров набор разделенных запятой формальных параметров в формате: : = вид параметра - одно из ключевых слов «in» (по умолчанию), «out» или «inout» вид параметра - одно из ключевых слов «in» (по умолчанию), «out» или «inout» синтаксис зависит от конкретного языка программирования и подчиняется принятым в нем ограничениям синтаксис зависит от конкретного языка программирования и подчиняется принятым в нем ограничениям (список параметров) Квантор видимости

Операции (методы) класса (список параметров): (список параметров): {строка-свойство} {строка-свойство} Выражение типа возвращаемого значения является зависимой от языка реализации спецификацией типа или типов значений параметров, которые возвращаются объектом после выполнения соответствующей операции. Двоеточие и выражение типа возвращаемого значения могут быть опущены, если операция не возвращает никакого значения. Выражение типа возвращаемого значения является зависимой от языка реализации спецификацией типа или типов значений параметров, которые возвращаются объектом после выполнения соответствующей операции. Двоеточие и выражение типа возвращаемого значения могут быть опущены, если операция не возвращает никакого значения. Строка-свойство служит для указания значений свойств, которые могут быть применены к данному элементу. Строка-свойство не является обязательной, она может отсутствовать, если никакие свойства не специфицированы. Строка-свойство служит для указания значений свойств, которые могут быть применены к данному элементу. Строка-свойство не является обязательной, она может отсутствовать, если никакие свойства не специфицированы. Операция с областью действия на весь класс показывается подчеркиванием имени и строки выражения типа. По умолчанию под областью операции понимается объект класса. В этом случае имя и строка выражения типа операции не подчеркиваются. Операция с областью действия на весь класс показывается подчеркиванием имени и строки выражения типа. По умолчанию под областью операции понимается объект класса. В этом случае имя и строка выражения типа операции не подчеркиваются. Операция, которая не может изменять состояние системы и, соответственно, не имеет никакого побочного эффекта, обозначается строкой-свойством «{запрос}» («{query}»). Операция, которая не может изменять состояние системы и, соответственно, не имеет никакого побочного эффекта, обозначается строкой-свойством «{запрос}» («{query}»). выражение типа возвращаемого значения {строка-свойство}

Операции (методы) класса: примеры +создать() +create() может обозначать абстрактную операцию по созданию отдельного объекта класса, которая является общедоступной и не содержит формальных параметров. Эта операция не возвращает никакого значения после своего выполнения +создать() +create() может обозначать абстрактную операцию по созданию отдельного объекта класса, которая является общедоступной и не содержит формальных параметров. Эта операция не возвращает никакого значения после своего выполнения +нарисовать(форма: Многоугольник = прямоугольник, цвет_заливки: Color = (О, О, 255)) может обозначать операцию по отображению на экране монитора прямоугольной области синего цвета, если не указываются другие значения в качестве аргументов данной операции +нарисовать(форма: Многоугольник = прямоугольник, цвет_заливки: Color = (О, О, 255)) может обозначать операцию по отображению на экране монитора прямоугольной области синего цвета, если не указываются другие значения в качестве аргументов данной операции выдать_сообщение():{"Ошибка деления на ноль"} смысл данной операции не требует пояснения, поскольку содержится в строке- свойстве операции. Данное сообщение может появиться на экране монитора в случае попытки деления некоторого числа на ноль, что недопустимо выдать_сообщение():{"Ошибка деления на ноль"} смысл данной операции не требует пояснения, поскольку содержится в строке- свойстве операции. Данное сообщение может появиться на экране монитора в случае попытки деления некоторого числа на ноль, что недопустимо

Отношения между классами зависимость (dependency relationship) ассоциация (association relationship) aгрегация (aggregation relationship) композиция (composition relationship) обобщение (generalization relationship) Клиент зависимости Источник зависимости

Отношения ассоциации компания сотрудник работает 1 1..* Имя ассоциации Символ порядка классов в ассоциации Кратность ассоциации компания сотрудник имеет в штате

Отношения ассоциации Ассоциации могут быть бинарными (связывающими 2 класса), тернарными, N-арными… Ассоциации могут быть бинарными (связывающими 2 класса), тернарными, N-арными… Исключающая ассоциация Исключающая ассоциация годматч футбольная команда * * * Юридическое лицо Физическое лицо Счет в банке xor

Отношения агрегации настольный компьютер системный блокклавиатурамонитормышь целоечасть состоит из контейнер элемент включает в себя коллекция элемент представляет собой набор

Отношения композиции (частный случай агрегации) Составляющие элементы не могут существовать в отрыве от целого Составляющие элементы не могут существовать в отрыве от целого окно приложения заголовокрабочая область полоса прокрутки менюпанель инструментов

Отношения обобщения Наследуются атрибуты и методы Наследуются атрибуты и методы класс-предоккласс-потомокгеометрическая фигура квадратпрямоугольникокружностьэллипс … многоугольник … квадрат прямоугольник окружность эллипс … параллелограмм

Пример диаграммы классов Point PoligonCircle radius Style Color borderType isFilled stroke() fill() 3..*1 11 **

Примеры диаграмм классов

Диаграммы вариантов использования (диаграммы прецедентов) (use case diagram) Цели: Определить общие границы и контекст моделируемой предметной области на начальных этапах проектирования системы. Определить общие границы и контекст моделируемой предметной области на начальных этапах проектирования системы. Сформулировать общие требования к функциональному поведению проектируемой системы. Сформулировать общие требования к функциональному поведению проектируемой системы. Разработать исходную концептуальную модель системы для ее последующей детализации в форме логических и физических моделей. Разработать исходную концептуальную модель системы для ее последующей детализации в форме логических и физических моделей. Подготовить исходную документацию для взаимодействия разработчиков системы с ее заказчиками и пользователями. Подготовить исходную документацию для взаимодействия разработчиков системы с ее заказчиками и пользователями.

Диаграммы вариантов использования Отношения между акторами и прецедентами: Отношение ассоциации (association relationship) Отношение ассоциации (association relationship) Отношение расширения (extend relationship) Отношение расширения (extend relationship) Отношение обобщения (generalization relationship) потомок наследует все свойства и поведение родителя Отношение обобщения (generalization relationship) потомок наследует все свойства и поведение родителя Отношение включения (include relationship) Отношение включения (include relationship) 1 * «extend» «include»

Диаграммы вариантов использования Запросить каталог всех товаров Оформить заказ на покупку товара Оформить заказ на покупку ноутбука Выписать счет на покупку ноутбука Выдавать каталог только по запросу клиента Проверить условия на запрос каталога клиентом «extend» «include»

Диаграммы вариантов использования На диаграмме отражаются отношения между акторами (actors) и прецедентами – возможными вариантами использования системы. На диаграмме отражаются отношения между акторами (actors) и прецедентами – возможными вариантами использования системы. Каждый вариант использования Каждый вариант использования Связан хотя бы с одним актором Связан хотя бы с одним актором Кем-то инициирован Кем-то инициирован Имеет существенный для системы результат Имеет существенный для системы результат

Примеры диаграмм вариантов использования

Диаграмма состояний (State Chart/State Machine diagram) Цель - описать возможные последовательности состояний и переходов, которые в совокупности характеризуют поведение элемента модели в течение его жизненного цикла. Цель - описать возможные последовательности состояний и переходов, которые в совокупности характеризуют поведение элемента модели в течение его жизненного цикла. Диаграмма состояний представляет динамическое поведение сущностей Диаграмма состояний представляет динамическое поведение сущностей

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

Диаграмма деятельности Сущности и графические нотации Состояние действия (action state) Состояние действия (action state) Переход Переход Ветвление Ветвление Параллельные ветви (разделение и слияние) Параллельные ветви (разделение и слияние) Дорожка Дорожка

Примеры диаграмм деятельности

Диаграмма последовательности (sequence diagram) Цель - моделирование взаимодействия объектов во времени. Цель - моделирование взаимодействия объектов во времени. Представляет временные особенности передачи и приема сообщений между объектами. Представляет временные особенности передачи и приема сообщений между объектами. Сущности: Сущности: Объект Объект Линия жизни объекта Линия жизни объекта Фокус управления Фокус управления Сообщения (рекурсия, рефлексия) Сообщения (рекурсия, рефлексия)

Примеры диаграмм последовательности