1 Курс: Модели и методы дискретной оптимизации Лектор: д.т.н., профессор Овчинников Владимир Анатольевич Структура курса: 17 лекций – 17 семинаров – экзамен. Разделы 2.12, 2.13, 5 и 6 курса должны быть проработаны самостоятельно. Литература: Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. – М.: МЦНМО, – 960 с. Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», – 288 с. В.А. Овчинников. Графы в задачах анализа и синтеза структур сложных систем: – М.: МГТУ им. Н.Э. Баумана, – 423 с. В.А. Овчинников. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов. – М.: МГТУ им. Н.Э. Баумана, – 288 с. Посещение всех семинаров обязательно! Студенты не выполнившие семинары к экзамену не допускаются. Отчет по семинарам выполняется в рабочей тетради и предоставляется на проверку до экзамена.

2 1 Некоторые задачи дискретной оптимизации Область применения задач дискретной оптимизации Задачи дискретной оптимизации возникают как при проектировании, так и при организации функционирования различного рода информационных систем. Основой информационной системы являются средства ЭВТ. Информационная система и средства ЭВТ относятся к классу сложных систем. «Сложная система – составной объект, части которого можно рассматривать как отдельные системы, объединённые в единое целое в соответствии с определёнными принципами или связанные между собой заданными отношениями. Части сложной системы (подсистемы) можно расчленить (часто лишь условно) на более мелкие подсистемы и т. д., вплоть до выделения компонентов сложной системы, которые либо объективно не подлежат дальнейшему расчленению, либо относительно их неделимости имеется договорённость.

3 Задачи структурного синтеза Свойства сложной системы в целом определяются как свойствами составляющих её элементов, так и характером взаимодействия между ними». Подсистемы нередко являются разнородными объектами, связи между которыми могут иметь разную физическую природу. Структура системы задается количеством и номенклатурой составляющих его компонентов и видом отношений между ними. В технических системах отношения между объектами реализуются различного рода соединениями (линиями связи, цепями и т. д.). Для таких систем задача структурного синтеза заключается в поиске некоторого варианта состава компонентов и порядка их соединения, а задача анализа – в определении свойств и/или характеристик системы.

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

5 Группы задач дискретной оптимизации В соответствии с преследуемыми целями многие комбинаторно-оптимизационные задачи можно отнести к одной из следующих групп. Это задачи: позиционирования; коммутации; декомпозиции / композиции; установления идентичности; выделения подмножества компонентов, обладающих заданными свойствами;

6 Группы задач дискретной оптимизации определения максимального потока в сети; назначение исполнителей на работы; анализа и преобразования алгоритмов (программ); синтеза многоуровневых и комбинированных структур данных; анализа и синтеза топологии многопроцессорных вычислительных систем, сетей ЭВМ и баз данных и др.

7 Исходные данные для задач дискретной оптимизации Задачи синтеза и анализа сложных систем различной природы отличаются широким разнообразием. В курсе будет рассмотрен ограниченный круг комбинаторно-оптимизационных задач структурного синтеза. Исходными данными для решения задач структурного синтеза средств ЭВТ являются: функциональное назначение объекта проектирования; наборы элементов и связей, применяемых для построения структуры объекта; функциональное назначение, метрические параметры и топологические свойства элементов и их связей; возможные правила и/или способы соединения элементов, обеспечивающие с учетом их назначения функционирование объекта; правило, служащее для сравнительной оценки качества структуры.

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

9 Методология формализованного проектирования Оценка возможности решения задачи. Выбор или разработка метода решения. Разработка алгоритма. Реализация алгоритма выбранными средствами программирования, тестирование и отладка программы. Собственно решение задачи.

10 Методология формализованного проектирования Разботка алгоритма выделена на самостоятельную проработку, написание, тестирование, отладка программы и собственно решение задачи выходят за рамки дисциплины. При формализации и решении прикладных задач дискретной оптимизации основными являются следующие проблемы: получение математической модели объекта проектирования и определение вида модели результата, конструирование целевой функции и формирование ограничений, оценка возможности решения задачи, разработка математической модели задачи, выбор или разработка метода решения.

11 Языки описания данных о схеме 1. Входной язык описания схемы в виде списка цепей. Цепь – совокупность выводов элементов, являющихся электрически общей точкой. Вариант структуры предложения описания цепи: ПЦ:= [ ] [ ] … 2. Входной язык описания схемы в виде списка элементов. Для каждого задействованного контакта элемента указывают номер подключенной к нему цепи или имя сигнала, передаваемого по данной цепи. Вариант структуры предложения описания элемента: ПЭ:= [ ] [ ] …