Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
99 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
4.86 MB
Просмотров:
75
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Автоматизация](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img0.jpg)
Содержание слайда: Автоматизация конструкторско-технологического проектирования
Лекция 04
Декомпозиция,
Конструктивные алгоритмы,
алгоритм Кернигана-Лина, Фидуччи-Маттеуса
№2 слайд![Используется для разделения](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img1.jpg)
Содержание слайда: Используется для разделения системы на меньшие подсистемы
Обычно производится иерархически
Система бьется до тех пор, пока размер каждой подсистемы не будет удовлетворительным
Подсистемы могут проектироваться независимо
Минимизируется количество связей между частями
- меньше требования к интерфейсу
- сигнал между подсистемами имеет большую задержку
№3 слайд![Уровень системы множество](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img2.jpg)
Содержание слайда: Уровень системы:
множество печатных плат
№4 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img3.jpg)
№5 слайд![Быстродействие повышается при](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img4.jpg)
Содержание слайда: Быстродействие повышается при хорошем разбиении на верхних уровнях проектирования
№6 слайд![Стратегия разделяй и властвуй](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img5.jpg)
Содержание слайда: Стратегия «разделяй и властвуй»
Эффективна для решения очень сложных задач
Области применения: дихотомическое размещение, генерация тестовых последовательностей, …
На системном уровне разбивается на многочиповые схемы
Влияет на задержку сигнала и быстродействие системы
Применяется при параллельном моделировании схем
Разбиение больших схем на набор ПЛИС или микроконтроллеров
Разработка параллельных алгоритмов САПР
- разбиение задачи и распределение нагрузки
В современных схемах определяет локальные и глобальные межсоединеня прямо влияет на быстродействие
№7 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img6.jpg)
№8 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img7.jpg)
№9 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img8.jpg)
№10 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img9.jpg)
№11 слайд![Стоимость минимального](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img10.jpg)
Содержание слайда: Стоимость минимального сечения = 15
Стоимость минимальной бисекции = 45
Стоимость деления с мин. отношения = 18
Минимизация отношения помогает находить натуральные кластеры
№12 слайд![Критерии минимальная](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img11.jpg)
Содержание слайда: Критерии:
минимальная связанность блоков
максимальная связанность блоков
равномерная связанность блоков
функциональный признак
удовлетворение ограничениям
Ограничения:
количество блоков
размер блоков
число выводов блока
№13 слайд![Улучшают начальное разбиение](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img12.jpg)
Содержание слайда: Улучшают начальное разбиение
Наиболее распространены из-за эффективности
№14 слайд![Производят различные решения](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img13.jpg)
Содержание слайда: Производят различные решения при каждом запуске
№15 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img14.jpg)
№16 слайд![Входные данные Граф G V, E](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img15.jpg)
Содержание слайда: Входные данные:
Граф G=(V, E)
Матрица смежности С
Максимальный размер блока Bmax
Обозначения:
Bi – i-й блок
|Bi| - число элементов в блоке
№17 слайд![Алгоритм i Пока в Е есть](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img16.jpg)
Содержание слайда: Алгоритм:
i=1
Пока в Е есть элементы
Если |Bi|=0
Найти элемент с наибольшим количеством связей emax
Переместить emax из Е в Bi
Иначе
Если |Bi| < Bmax
Найти элемент emax, наиболее связанный с Bi
Переместить emax из Е в Bi
Иначе
i=i+1
№18 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img17.jpg)
Содержание слайда: Пример:
№19 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img18.jpg)
Содержание слайда: Пример:
№20 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img19.jpg)
Содержание слайда: Пример:
№21 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img20.jpg)
Содержание слайда: Пример:
№22 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img21.jpg)
Содержание слайда: Пример:
№23 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img22.jpg)
Содержание слайда: Пример:
№24 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img23.jpg)
Содержание слайда: Пример:
№25 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img24.jpg)
Содержание слайда: Пример:
№26 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img25.jpg)
Содержание слайда: Пример:
№27 слайд![Пример](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img26.jpg)
Содержание слайда: Пример:
№28 слайд![Способы повышения](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img27.jpg)
Содержание слайда: Способы повышения эффективности:
№29 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img28.jpg)
№30 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img29.jpg)
№31 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img30.jpg)
№32 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img31.jpg)
№33 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img32.jpg)
№34 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img33.jpg)
№35 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img34.jpg)
№36 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img35.jpg)
№37 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img36.jpg)
№38 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img37.jpg)
№39 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img38.jpg)
№40 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img39.jpg)
№41 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img40.jpg)
№42 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img41.jpg)
№43 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img42.jpg)
№44 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img43.jpg)
№45 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img44.jpg)
№46 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img45.jpg)
№47 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img46.jpg)
№48 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img47.jpg)
№49 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img48.jpg)
№50 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img49.jpg)
№51 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img50.jpg)
№52 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img51.jpg)
№53 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img52.jpg)
№54 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img53.jpg)
№55 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img54.jpg)
№56 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img55.jpg)
№57 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img56.jpg)
№58 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img57.jpg)
№59 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img58.jpg)
№60 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img59.jpg)
№61 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img60.jpg)
№62 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img61.jpg)
№63 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img62.jpg)
№64 слайд![Принадлежат к итерационным](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img63.jpg)
Содержание слайда: Принадлежат к итерационным алгоритмам
Эти алгоритмы начинают работы с некоторого начального разбиения, обычно случайного
В разбиении производятся локальные изменения (перестановки элементов) для уменьшения стоимости разреза
Процесс повторяется, пока больше не будет улучшений
№65 слайд![Входные данные Граф G V,E с n](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img64.jpg)
Содержание слайда: Входные данные:
Граф G=(V,E) с 2n вершинами, каждая вершина имеет одинаковый вес.
Задача:
Разделить граф на два непересекающихся подмножества A и B с минимальной стоимостью разреза,
|A| = |B| = n.
№66 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img65.jpg)
№67 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img66.jpg)
№68 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img67.jpg)
№69 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img68.jpg)
№70 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img69.jpg)
№71 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img70.jpg)
№72 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img71.jpg)
№73 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img72.jpg)
№74 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img73.jpg)
№75 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img74.jpg)
№76 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img75.jpg)
№77 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img76.jpg)
№78 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img77.jpg)
№79 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img78.jpg)
№80 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img79.jpg)
№81 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img80.jpg)
№82 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img81.jpg)
№83 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img82.jpg)
№84 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img83.jpg)
№85 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img84.jpg)
№86 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img85.jpg)
№87 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img86.jpg)
№88 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img87.jpg)
№89 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img88.jpg)
№90 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img89.jpg)
№91 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img90.jpg)
№92 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img91.jpg)
№93 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img92.jpg)
№94 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img93.jpg)
№95 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img94.jpg)
№96 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img95.jpg)
№97 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img96.jpg)
№98 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img97.jpg)
№99 слайд![](/documents_6/bd003230e85b34dfa2f8c2ff05120554/img98.jpg)