Информационные технологии проектирования электронных средств

- 29 - 3. Какие задачи включает в себя первый класс. 4. Какие критерии используются для задач первого класса. 5. Какие задачи относятся ко второму классу. 6. Перечислите критерии, используемые в задачах второго класса. 7. Перечислите типовые задачи компоновки. 8. Какой критерий является основным в задаче компоновки. ЛЕКЦИЯ 7. Задачи типизации и покрытия Задача типизации Рассмотрим задачу типизации. Типизация – это разбиение схемы на части с минимизацией номенклатуры частей разбиения (количество разных типов). В зависимости от постановки задачи проектирования различается и по- становка задачи типизации. Будем называть однотипными такие ТЭК, которые имеют одинаковый состав элементов и одинаковую коммутационную схему. В этом случае задачу типизации можно сформулировать как задачу выделения в графе G ( Х,Е ) изоморфных подграфов, а именно : найти разбиение ϕ ( G ) графа G ( X,E ) на минимальное множество групп Г={Г 1 ,Г 2 ,...,Г s } изоморфных подгра- фов Г j , удовлетворяющих следующим условиям: 1) любые два подграфа Г i : G i j , G i h , принадлежащие произвольной груп- пе разбиения G i , должны быть изоморфны; 2) число вершин любого подграфа разбиения не должно превышать за- данного значения (это конструктивное ограничение, связанное с числом эле- ментов в ТЭК); 3) множество вершин любых двух подграфов разбиения не должны пе- ресекаться;