ЛЕКЦИИ 2-3. Курс: Проектирование систем: Структурный подход Каф. Коммуникационные сети и системы, Факультет радиотехники и кибернетики Московский физико-технический институт (университет) / Марк Ш. ЛЕВИН Институт проблем передачи информации, РАН Сент. 4, 2004 ПЛАН: 1.Декомпозиция (разбиение) систем *декомпозиция – разбиение; *иллюстративные примеры; *подходы 2.Вопросы модульности *описание и базовый лингвистический аналог *прикладные примеры (механика, космос и др. ) *цели и результаты 3. Структурные модели *графы (графы, ориентированные графы - орграфы, знаковые графы) *простые структуры (цепи, деревья, параллельно-последовательные графы и др.) *задачи на графахs (метрика/близость, оптимизация, перспективные модели)

1.Декомпозиция / разбиение систем Декомпозиция: последовательный процесс (например, динамическое программирование) Разбиение: параллельный процесс / разбиение (пример: комбинаторный синтез) Методы разбиения: *физическое разбиение *функциональное разбиение Примеры (для самолета, для человека) Примеры для программных систем: 1.Последовательный процесс обработки информации (вход, процесс решения, анализ, выход) 2.Архитектура: Подсистема поддержки данных, процесс решения, пользовательский интерфейс, подсистема обучения, коммуникации 3.Дополнительная часть: visualization (для данных, для процесса решения) 4. Дополнительная вспомогательная часть для управления моделями (model management) : *анализ исходной прикладной ситуации, *библиотека моделей / методов, *выбор / проектирование моделей / методов, *выбор / проектирование много-модельных стратегий решения

1.Декомпозиция / разбиение систем: Пример для много-функционального тестирования систем Функции системы Кластеры Функций системы F1 F2F3 Орграф на кластерах Кластерr F1 Кластер F2 Кластер F3

Главные подходы к разбиению систем A.Содержательный анализ и опыт: *по функциям (основные функции, дополнительные функции) *по системным частям (физическое разбиение) B.Кластер-анализ (кластеризация) Кластер F1 Кластер F2 Кластер F3 Кластер F4 Кластер F5 Кластер F6

2.Вопросы модульности ПРИНЦИПЫ УПРАВЛЕНИЯ СЛОЖНОСТЬЮ : *дискретные части (модули) *стандартные интерфейсы для коммуникации модулей Приложения: *проектирование новых технологий * организационное проектирование ТЕКСТЫ ФРАЗЫ СЛОВА АЛФАВИТ ЛИНГВИСТИЧЕСКАЯ СИСТЕМА

Прикладные примеры использования модульности 1.Генетика 2.Реконфигурируемое (Reconfigurable) производство 3.Программные библиотеки стандартных модулей 4.Комбинаторная химия: *молекулярное проектирование в химии и биологии *проектирование лекарств *технология проектирования материалов *др. 5.Проектирование в механических / космических систем 6.Электроника 7.Строительство

Основные цели модульности и резюме ОСНОВНЫЕ ЦЕЛИ: 1.Управление сложностью 2.Параллельная работа 3.Подготовка к будущей неопределенности 4.Разнообразие результирующих модульных систем 5.Гибкость, адаптивность, способность к изменению конфигурации результирующих модульных систем РЕЗЮМЕ: 1.Упрощение процесса проектирования & упрощение всех фаз жизненного цикла 2.Короткий жизненный цикл продукции, долгий жизненный цикл модулей 3.Способность к изменению конфигураций систем (Reconfigurable systems) (например, для производственных систем): продолжительный жизненный цикл поколений системы 4.Упрощенные проектирование и поддержка семейств продуктов (самолеты, автомобили и др.) 5.Упрощенное проектирование и поддержка различных продуктов (на основе библиотек модулей как повторное использование)

3.Структурные модели А.ГРАФЫ 1.Графы 2.Орграфы (направленные графы или ориентированные графы) 3.Графы / орграфы с весами (для вершин, для ребер / дуг) 4.Простые графы: цепи, деревья, параллельно-последовательные графы, иерархии 5.Знаковые графы Б.СЕТИ В.АВТОМАТЫ Г.БИНАРНЫЕ ОТНОШЕНИЯ

Иллюстрация для графов / орграфов Граф: G = (A,E) где множество узлов (вершин) A={1,…,n} и множество ребер E A×A (пары вершин) Пример: A={a, b, c}, E={(a, b), (b, c), (a, c)} a b c Орграф : G = (A,E) где множество узлов (вершин) A={1,…,n} и множество дуг E A×A (пары вершин) Пример: A={a, b, c}, E={(a, a), (a, b), (b, c), (a, c)} a b c a b c a 1 1 b 1 1 c 1 1 Матрица a b c a b 1 c Матрица

Иллюстрация для графов с весами Граф (веса ребер): G = (A,E) где множество узлов (вершин) A={1,…,n} и множество ребер E A×A (пары вершин) Пример: A={a, b, c}, E={(a, b), (b, c), (a, c)} a b c a b c a 2 5 b 2 3 c 5 3 Матрица Граф (веса ребер & вершин): G = (A,E) где множество ребер (узлов) A={1,…,n} и множество ребер E A×A (пары вершин) Пример: A={a, b, c}, E={(a, b), (b, c), (a, c)} (веса вершин указаны в скобках) a(1)b(2) c(4) a b c a 2 5 b 2 3 c 5 3 Матрица

Простые структуры (цепи, деревья, параллельно-последовательные графы) ЦЕПЬ ДЕРЕВО ПАРАЛЛЕЛЬНО- ПОСЛЕДОВАТЕЛЬНЫЙ ГРАФ

Простые структуры (иерархия) Уровень 4 Уровень 3 Уровень 1 Уровень 2

Знаковый граф: иллюстративный пример Экологическая система ЛИСЫ КРОЛИКИ Группа (бригада) a0a0 Руководитель a1a1 a2a2 a3a3 Ученый ИнженерТехник a0a0 a1a1 a2a2 a3a

Некоторые перспективные структурные модели 1.Мультиграфы 2.Графы с версиями вершин (узлов) 3.Графы с весами в виде векторов 4.Графы с «размытыми» весами

Задачи на графах А.Метрика / близость (в графе между вершинами, между графам) Близость между графами: 1.метрики, 2.расстояние редактирования (минимальная цена трансформации), 3.общая часть Б.Оптимизация на графах: 1.Кратчайший путь 2.Покрывающее дерево (& близкие аппроксимационные задачи: Покрытие другими простыми структурами) 3.Задача о коммивояжере 4.Минимальное дерево Штейнера 5.Упорядочение вершин 6.Размещение на графах 7.Задачи о покрытиях В.Задачи балансов для знаковых графов Г.Кластеризация (разбиение на группы взаимосвязанных / близких элементов)

Оптимизация на графах: иллюстрации a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 БАЗОВЫЙ ГРАФ (ОРГРАФ): Веса для дуг (или ребер) a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a Кратчайший путь : L = = 8

Оптимизационные задачи на графах: иллюстрации a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 Покрывающее дерево (длина = 19): Задача коммивояжера : L = a4a4 a3a3 a7a7 a1a1 a0a0 a2a2 a5a5 a6a6 a9a9 a8a8 a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a

Оптимизационные задачи на графах: иллюстрации a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 Дерево Штейнера (пример): Задача Упорядочения (близкие задачи: задача календарного планирования): a4a4 a3a3 a7a7 a1a1 a0a0 a2a2 a5a5 a6a6 a9a9 a8a8 a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a a0a0 a 1,a 2,a 3 a 4, a 5,a 6,a 7 a 8,a 9 2

Оптимизационные задачи на графах: иллюстрации Размещение (назначение, сопоставление, отображение):Позиции... Множество элементов РАЗМЕЩЕНИЕ (отображение, назначение)

Пример: кластеры функций системы и их покрытие цепями (покрытие дуг) F5 F6 F1 F2 F3 F4 F1 F2 F3 F4 F5F6 F3 F1F3 F5 F3 Орграф кластеров функций системы

Иллюстрация кластеризации a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a9 Базовый граф Кластеры (вариант решения): C 1 = { a 0, a 1 } C 2 = { a 3, a 5 } C 3 = { a 8, a 9 } C 4 = { a 2, a 4, a 6, a 7 } a0a0 a1a1 a2a2 a3a3 a4a4 a6a6 a5a5 a7a7 a8a8 a9a

Бинарные отношения Исходное множество A = {1, 2, …, n}, B = A × A ( (x, y), x, y A) Определение. Бинарное отношение R это подмножество B ПРИМЕР: A={a, b, c, d} B = {(a, a), (a, b), (a, c), (a, d), (b, a), (b, a), (b, c), (b, d), (c, a), (c, b), (c, c), (c, d), (d, a), (d, b), (d, c), (d, d)} R 1 = { (a, b), (b, c), (c, b), (d, c) } R 2 = { (a, d), (b, d), (a, c) } R 3 = R 1 & R 2 a b c d R1R1 ab c d R2R2 ab c d R3=R1&R2R3=R1&R2

Бинарные отношения НЕКОТОРЫЕ СВОЙСТВА: 1.Симметрия: (x, y) R => (y, x) R ( x R, y R) 2.Рефлексивность: (x, x) R x R 3.Транзитивность: (x, y) R, (y, z) R => (x, z) R ( x R, y R, z R) ПРИЛОЖЕНИЯ *Дружба, *Партнерство, *Похожесть и др. Смысловой пример: 1.Лучше (доминирование) 2.Лучше & Равно (доминирование & эквивалентность ) 3.Равно (эквивалентность) Расширенные модели: 1.Взвешенные бинарные отношения (например, сила доминирования) 2.K-отношения Перспективное использование : Задача комбинаторной оптимизации на графах с дополнительными бинарными отношениями (на вершинах / узлах, на ребрах / дугах, на элементах / позициях)