Модели и методы дискретной оптимизации презентация

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

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

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

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

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

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

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

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

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

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

списка цепей.
Цепь – совокупность выводов элементов, являющихся электрически общей точкой.
Вариант структуры предложения описания цепи:
ПЦ:=<имя цепи>
[<имя элемента><тип элемента> <номер или имя контакта>]
[<имя элемента><тип элемента> <номер или имя контакта>] …

2. Входной язык описания схемы в виде списка элементов.
Для каждого задействованного контакта элемента указывают номер подключенной к нему цепи или имя сигнала, передаваемого по данной цепи.
Вариант структуры предложения описания элемента:
ПЭ:=<имя элемента><тип элемента>
[<имя цепи><номер или имя контакта>]
[<имя цепи><номер или имя контакта>] …