16.2. Размещение
16.2.1. Алгоритмы решения математических задач, являющихся моделями задач размещения. Этапы:
16.2.1.1. Составление математической модели
16.2.1.2. Решение системы уравнений математической модели
16.2.2. Алгоритмы начального размещения: на каждом этапе размещают ещё один элемент.
16.2.3. Итерационные алгоритмы улучшения начального размещения: этапы те же, что и у алгоритмов компоновки.
16.2.4. Непрерывно-дискретные алгоритмы размещения
16.2.4.1. Составление системы дифференциальных уравнений
16.2.4.2. Решение системы дифференциальных уравнений
16.3. Трассировка межсоединений
16.3.1. Построение списка соединений (нахождение минимального связывающего дерева: алгоритм Прима, алгоритм Каскала)
16.3.2. Определение слоя (выявление конфликтов и их разрешение). Для определения количества слоев строится граф пересечений и раскрашивается. Количество красок определяет число слоев.
16.3.3. Определение порядка трассировки (порядка проведения соединений): метод прямоугольников
16.3.4. Собственно трассировка с учетом ограничений: волновые алгоритмы, лучевые алгоритмы, канальный алгоритм.
17. Виды обеспечения САПР
САПР – организационно-техническая система, состоящая из комплекса средств автоматизации проектирования, взаимосвязанного с необходимыми подразделениями или специалистами, и выполняющая автоматизированное проектирование (АП).
17.1. Техническое обеспечение – совокупность взаимосвязанных и взаимодействующих технических средств, предназначенных для выполнения АП.
17.2. Математическое обеспечение – совокупность математических методов, математических моделей и алгоритмов проектирования, необходимых для выполнения АП.
17.2.1. теории и методы (теория графов, теория подобия, теория множеств, численные методы)
17.2.2. математические модели
Математическая модель технического объекта – это совокупность математических объектов (числа, переменные, матрицы, множества) и соотношений между ними, которая адекватно отображает свойства технического объекта, интересующие разработчика. Требования к математическим моделям:
17.2.2.1. адекватность – отражение заданных свойств объекта с приемлемой точностью, т.е. степенью совпадения выходных параметров модели и объекта
17.2.2.2. универсальность – число и состав учитываемых в модели входных и выходных параметров
17.2.2.3. экономичность – затраты вычислительных ресурсов для её реализации (объем памяти и время работы)
17.2.3. алгоритмы (решения общих задач вычислительной математики, упорядочивания и поиска информации, проблемной ориентации, предметной ориентации, решения системных задач)
17.3. Информационное обеспечение – совокупность необходимых сведений для выполнения АП, представленных в заданной форме.
17.4. Программное обеспечение – совокупность необходимых для АП программ, представленная в заданной форме.
17.5. Лингвистическое обеспечение – совокупность языков проектирования, включая термины и определения, правила формализации естественного языка и методы сжатия и развертывания текста.
17.6. Организационное обеспечение – совокупность документов, устанавливающая состав проектной организации и её подразделений, связи между ними, их функции и форму представления результатов АП.
17.7. Методическое обеспечение – совокупность документов, устанавливающих состав и правила отбора для эксплуатации средств АП.
18. Классы математических задач. Эффективность алгоритмов
18.1. Алгоритмы
18.1.1. Алгоритмически нерешаемые
18.1.2. Алгоритмически решаемые
18.1.2.1. P – задачи, решаемые за полиномиальное время (kn2, ln n, n3)
18.1.2.2. NP – задачи, для которых существуют только экспоненциальные алгоритмы (2n, nn, n!)
18.2. Эффективность алгоритма – максимальное количество элементарных операций, выполняемых при его работе O(f(n))
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.