Дослідження ефективності методів та алгоритмів розбиття схем на частини (оптимізація розбиття. Звіт з Інші. Робота № 110809

Перехід до торгівельного партнера Binance

Дослідження ефективності методів та алгоритмів розбиття схем на частини (оптимізація розбиття

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2010

Тип роботи:

Звіт

Предмет:

Інші

Група:

ПЗС-13м

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет “ Львівська політехніка ” Кафедра ПЗ Звіт до наукового проекту з дисципліни: Методи та засоби наукових досліджень в інноваційних комп'ютерних технологіях на тему: "Дослідження ефективності методів та алгоритмів розбиття схем на частини (оптимізація розбиття)" Львів 2010 Анотація Даний науковий проект присвячений питанню дослідження ефективності методів та алгоритмів розбиття схем на частини (оптимізація розбиття) В основі роботи лежить мета дослідити ефективність існуючих методів та алгоритмів розбиття схем на частини, визначити оптимальні методи до вирішення даної проблеми та якість отриманих з їх допомогою вирішень, а також застосувати отримані результати для створення програмної системи що моделює розбиття електричних схем Метою проекту є експериментальне та комерційне впровадження отриманих програмних засобів із дослідженням процесу їх функціонування з метою аналізу роботи розроблених методів в реальних умовах. Зміст Вступ - 4 - Тема проекту - 5 - Мета проекту - 5 - Об’єкт досліджень - 5 - Предмет досліджень - 5 - Актуальність - 5 - Новизна - 6 - УДК - 6 - Сфери застосування - 6- Розробка календарного плану проекту. Планування витрат - 7 - Логіко-структурна матриця проекту - 10 - Висновки - 11 - Список літератури - 12 - Додаток Вступ При конструкторському проектуванні РЕА (радіоелектронної апаратури) вирішуються завдання, пов'язані з пошуком найкращого варіанту конструкції, технічного завдання, що задовольняє вимогам, і що максимально враховує можливості технологічної бази виробництва. Тісна взаємозв'язаність завдань і велика розмірність кожної з них зазвичай не дозволяє запропонувати метод пошуку оптимального конструктивного рішення в єдиному циклі у зв'язку з труднощами створення загальної математичної моделі, особливості конструкторсько-технологічної бази виробництва, що комплексно враховується. Тому розробка і реалізація алгоритмів і методів вирішення окремих завдань етапу конструкторського проектування: компоновки, розміщення і трасування, - до цих пір залишаються актуальними проблемами, вирішення яких невід'ємно пов'язане з розвитком систем автоматизації проектування. Компоновкою електричної схеми РЕА на конструктивно закінчені частини називається процес розподілу елементів нижчого конструктивного рівня у вищий відповідно до вибраного критерію. Основним для компоновки є критерій електромагнітотеплової сумісності елементів нижчого рівня. Даний критерій визначає область допустимого розбиття схеми, на якій формулюються інші критерії. Такими критеріями можуть бути: мінімум типів конструктивно закінчених частин, щільність компоновки, мінімум з'єднань між пристроями, простота діагностування і ін. Вочевидь, що зовнішні з'єднання між частинами схем є одним з найважливіших чинників, що визначають надійність РЕА. Тому найбільш поширеним критерієм є критерій мінімуму числа зовнішніх зв'язків. Виконання цього критерію забезпечує мінімізацію взаємних наведень, спрощення конструкції, підвищення надійності і так далі Для побудови формальної математичної моделі компонувальних завдань зручно використовувати теорію графів. При цьому електричну схему інтерпретують ненапрямленим мультиграфом, в якому кожному конструктивному елементу (модулю) ставлять у відповідність вершину мультиграфа, а електричним зв'язкам схеми - його ребра. Вихідною інформацією при вирішенні завдань розміщення є: дані про конфігурацію і розміри комутаційного простору, визначувані вимогами установки і кріплення даної складальної одиниці в апаратурі; кількість і геометричні розміри конструктивних елементів, що підлягають розміщенню; схема з'єднань, а також ряд обмежень на взаємне розташування окремих елементів, що враховують особливості конструкції, що розробляється. Завдання зводиться до відшукання для кожного розміщуваного елементу таких позицій, при яких оптимізується вибраний показник якості і забезпечується найбільш сприятливі умови для подальшого електричного монтажу. Особливого значення це завдання набуває при проектуванні апаратури на друкарських платах. Трасування з'єднань є, як правило, завершальним етапом конструкторського проектування РЕА і полягає у визначенні ліній, що сполучають еквіпотенціальні контакти елементів, і компонентів, складових проектований пристрій. Завдання трасування - одна з найбільш трудомістких в загальній проблемі автоматизації проектування РЕА. Це пов'язано з декількома чинниками, зокрема з різноманіттям способів конструктивно-технологічної реалізації з'єднань, для кожного з яких при алгоритмічному рішенні задачі застосовуються специфічні критерії оптимізації і обмеження. З математичної точки зору трасування - складне завдання вибору з величезного числа варіантів оптимального рішення. Алгоритми компонування: Алгоритми, що застосовують методи цілочисельного програмування. Дозволяють отримати точний розв’язок, проте для пристроїв реальної складності важко реалізуються на ПК. Послідовні алгоритми. Легко реалізуються, мають високу швидкодію, проте недоліком є нездатність знаходити глобальний мінімум кількості зовнішніх зв’язків(не аналізуються можливі ситуації). Ітераційні алгоритми. Забезпечують високу якість розв’язку задачі, однак потребують більших затрат машинного часу ніж послідовні. Змішані алгоритми. Мають за мету поєднати переваги послідовних та ітераційних алгоритмів та виключити їх недоліки Алгоритми розміщення Силові алгоритми. Зводить пошук до обчислювальних процедур для яких розроблені чисельні методи, проте трудомісткий і складний для реалізації. Ітераційні алгоритми. Характеризуються високою швидкодією. Послідовні алгоритми. На теперішній час найбільш швидкодіючими, але за якістю результату поступаються ітераційним. Алгоритми трасування Хвильові алгоритми. Легко враховують технологічну специфіку, завжди гарантують побудову траси, якщо шлях для неї існує. Ортогональні алгоритми. Характериуються високою швидкодією, проте на 100% не гарантується прокладання траси, а також велика кількість паралельних провідників і переходів між шарами. Алгоритми евристичного типу. Засновані на прийомі пошуку найкоротшого шляху в лабіринті. Тема проекту Дослідження ефективності методів та алгоритмів розбиття схем на частини (оптимізація розбиття) Мета проекту Дослідити ефективність існуючих методів та алгоритмів розбиття схем на частини, визначити оптимальні методи до вирішення даної проблеми та якість отриманих з їх допомогою вирішень, а також застосувати отримані результати для створення програмної системи що моделює розбиття електричних схем Об’єкт досліджень Електричні схеми, елементи яких потрібно розбити на конструктивно завершені частини Предмет досліджень Особливості, переваги і недоліки алгоритмів розбиття схем, їх точність та обчислювальна складність, а також можливість створення оптимальних методів вирішення даної проблеми Актуальність При проектуванні схем РЕА вирішуються задачі пов’язані з пошуком найкращого варіанту конструкції. Тісний взаємозв’язок задач і їх велика розмірність не дозволяють застосувати метод пошуку оптимального конструктивного рішення в зв’язку зі складністю створення загальної математичної моделі, що комплексно враховує всі особливості. Тому розробка і реалізація алгоритмів і методів вирішення окремих завдань етапу конструкторського проектування: компоновки, розміщення і трасування, - до цих пір залишаються актуальними проблемами, вирішення яких невід'ємно пов'язане з розвитком систем автоматизації проектування. Так наразі не існує універсальних підходів, які дозволили б вирішувати задачі розбиття схем з високим ступенем оптимальності. Усі існуючі підходи мають як свої переваги так і значні недоліки. Проте з розвитком техніки схеми все більш ускладнюються і проблема оптимізації постає все більш жорстко. Тому необхідно проводити роботу по створенні нових підходів до вирішення таких задач, які становлять як науковий та і практичний інтерес. Новизна Наукова новизна даного проекту випливає із того, що ставиться за мету отримання оптимального вирішення даної проблеми при оптимальному компонуванні між собою алгоритмів компонування, розміщенні і трасування. УДК Для даного наукового проекту відповідно до теми дослідження УДК матиме наступний вигляд: УДК 621.3.062 : 004.94 Пояснення цифр УДК УДК 62 – Інженерна справа. Техніка в цілому. УДК 621 – Загальне машинобудування. Ядерна техніка. Електротехніка. Технологія машинобудування в цілому. УДК 621.3 – Електротехніка. УДК 621.3.06 – З’єднання та комутація електричних ланцюгів. Вмикання та вимикання. УДК 621.3.062 – Способи з’єднання і комутації електричних ланцюгів УДК 00 – Наука в цілому УДК 004 – Інформаційні технології. Комп’ютерні технології. Теорія обчислювальних машин і систем УДК 004.9 – Прикладні інформаційні (комп’ютерні) технології УДК 004.94 – Комп’ютерне моделювання УДК 004.942 – Дослідження поведінки об’єкта на основі його математичної моделі Сфери застосування Системи автоматизованого проектування схем РЕА (радіоелектронної апаратури) із високим степенем інтеграції, зокрема мікропроцесорів, друкованих плат Розробка календарного плану проекту. Планування витрат Проект розбивається на етапи, для кожного з яких визначаються під задачі і встановлюються терміни їх виконання. Основними етапами виконання проекту є : 1. Аналіз На даному етапі проводиться аналіз предметної області, проводяться дослідження даної теми, виконується ознайомлення з існуючими працями у даній області та здійснюється напрацювання теоретичного базису. Включає такі підзадачі: Аналіз предметної області Ознайомлення з існуючими напрацюваннями Напрацювання теоретичного базису 2. Проектування На цьому етапі формулюються задачі проекту, визначаються вимоги, методи вирішення задач, планується бюджет та розробляється календарний план робіт. Включає такі підзадачі: Формулювання задач проекту Визначення вимог Визначення методів вирішення задач Планування бюджету і виділених ресурсів Розробка календарного плану робіт Написання документації Затвердження 3. Реалізація На даному етапі розробляються алгоритми, створюється інтерфейс програми, визначаються структури даних та здійснюється програмна реалізація Включає такі підзадачі: Розробка комплексу алгоритмів Розробка структур даних Розробка інтерфейсу Програмування Написання робочої документації Альфа-версія 4. Тестування На даному етапі виконуються тестування версій програми та її доопрацювання Включає такі підзадачі: Альфа-тестування Розробка бета-версії Бета-тестування Розробка гамма-версії Гамма-версія 5. Впровадження На цьому завершальному етапі виконується експериментальне впровадження проекту, аналіз результатів цього впровадження та остаточна здача проекту. Включає такі підзадачі: Експериментальне впровадження Аналіз результатів Доопрацювання користувацького інтерфейсу Здача проекту Розробка документації Комерційне впровадження На Рис.1 показано календарний план проекту із зазначенням календарних дат робіт, їх виконавців та витрати на всі стадії проекту. Рис.1 Календарний план проекту На рис. 2 зображено діаграму Ганта проекту. Вона також відображає критичний шлях проекту. Критичний шлях формує такий ланцюжок підзадач: Усі під задачі етапу Аналіз Усі підзадачі етапу Проектування Усі підзадачі етапу Реалізація Розробка бета та гамма-версій етапу Тестування Усі підзадачі етапу Впровадження Розрахована наближена тривалість проекту становить 89 днів (1648 годин). Згідно календарного плану з урахуванням усіх вихідних днів часові рамки проекту матимуть вигляд : 24.09.2009 – 26.01.2010. Рис. 2 Діаграма Ганта На рис. 3 наведено таблицю погодинних ставок працівників проекту. Відповідно до календарного плану робіт і окладами закріплених за ними працівників загаль-на вартість проекту становитиме 42253 грн. Рис. 3 Погодинні ставки працівників Логіко-структурна матриця проекту Важливим інструментом планування проекту є логіко-структурна матриця. Вона дозволяє в наглядній і лаконічній формі відобразити усі важливі характеристики проекту, цілі проекту, показники досягнення цілей… В таблиці 1 наведено логіко-структурну матрицю даного наукового проекту. Таблиця1. Логіко-структурна матриця проекту Опис проекту Обєктивно вимірювані індикатори Джерела перевірки Припущення Загальні цілі Створення компютерної системи що моделює розбиття схем Розроблена програмна система здатна виконувати процес компонування, розміщення і трасування схеми з заданим рівнем оптимізації Відгуки з місця експериментального впровадження системи, звітність по супроводу системи Конкретні цілі 1. Провести аналіз конструктивно-технологічної бази виробництва Досліджено конструктивні особливості елементів та технологію їх виготовлення, сформовано звітну документацію по проведеній роботі Звіти по дослідженнях. Наявні кадри можуть виконати таке дослідження 2. Провести дослідження існуючих методів та алгоритмів Досліджено методи і алгоритми розбиття схем, визначено їх переваги і недоліки Звіти по дослідженням Наявні кадри можуть виконати таке дослідження 3. Розробити оптимальні методи розбиття схем на частини Розроблені методи дозволяють знаходити 100% розбиття схем з заданим рівнем оптимальності Звіти по проведеним обчисленням та експериментам. Експертиза результатів незалежними фахівцями. Наявні засоби досягнення мети, наявний організований персонал Результати 1. Отримано детальний науковий аналіз існуючих методів вирішення проблеми Здійснено огляд існуючих методів, виконано їх порівняння та описано отримані результати Звіти по дослідженням Наявний розвинений інформаційний базис. Наявний укомплектований професійний персонал для виконання робіт. Фінансування усіх статей витрат по проекту. Детально розроблено календарний план проекту, прораховано всі стадії. Розробка виконується за допомогою найсучасніших засобів. 2.1 Розроблено алгоритми компонування Алгоритм компонує елементи схеми в логічно-зв’язані блоки з заданою точністю Протоколи тестування алгоритму. 2.2 Розроблено алгоритми розміщення Алгоритм з достатнім рівнем швидкодії забезпечує розміщення елементів схеми Протоколи тестування алгоритму. 2.3 Розроблено алгоритми трасування Алгоритм 100% знаходить трасу, яка є якомога найкоротша Протоколи тестування алгоритму. 3. Розроблено алгоритми оптимізації схеми Алгоритм виконує оптимізацію розбиття схеми Протоколи тестування алгоритму. Дії що дозволяють досягти цілі 1.1 Провести аналіз предметної області 1.2 Сформувати базис для досліджень 1.3 Провести наукові дослідження 1.4 Систематизувати отримані результати Ресурс часу 23 робочі дні. Людський ресурс 3 працівників Фінансовий ресурс Затрати на заробітну плату Затрати на навчання Затрати на придбання засобів досліджень Матеріальні затрати 9481 грн Наявність висококваліфікованого персоналу. Відсутні непередбачувані ситуації у працівників. Достане фінансове забезпечення та забезпечення ресурсами Постійна взаємодія із потенційними користувачами програмною системою. Врахування максимального числа вимог існуючих стандартів до процесів розробки програмних систем. 2.1.1 Розробити алгоритми та структури даних для компонування схем 2.1.2 Виконати програмування 2.1.3 Виконати тестування та аналіз Ресурс часу 8 робочих днів. Людський ресурс 3 працівники Фінансовий ресурс Затрати на заробітну плату Затрати на засоби розробки програм Матеріальні затрати 5124 грн 2.2.1 Розробити алгоритми та структури даних для розміщення схем 2.2.2 Виконати програмування 2.2.3 Виконати тестування та аналіз Ресурс часу 8 робочих днів. Людський ресурс 3 працівники Фінансовий ресурс Затрати на заробітну плату Затрати на засоби розробки програм Матеріальні затрати 5245 грн 2.3.1 Розробити алгоритми та структури даних для трасування схем 2.3.2 Виконати програмування 2.3.3 Виконати тестування та аналіз Ресурс часу 8 робочих днів. Людський ресурс 3 працівники Фінансовий ресурс Затрати на заробітну плату Затрати на засоби розробки програм Матеріальні затрати 5450 грн 2.3.1 Розробити алгоритми та структури даних для оптимізації розбиття схем 2.3.2 Виконати програмування 2.3.3 Виконати тестування та аналіз Ресурс часу 24 робочих днів. Людський ресурс 3 працівники Фінансовий ресурс Затрати на заробітну плату Затрати на засоби розробки програм Матеріальні затрати 15840 грн Висновки Розглянуто існуючі методи та алгоритми розбиття схем на частини, досліджено їх ефективність, наявні переваги і недоліки, визначено оптимальні методи до вирішення даної проблеми та якість отриманих з їх допомогою рішень. Також побудовано календарний план проекту, визначені його цілі та очікувані результати. Отримані результати в подальшому можуть бути застосованими для створення програмної системи що моделює розбиття електричних схем Список літератури Б.Н. Деньдобренко, А.С. Малика «Автоматизация конструирования РЭА», Москва «Высшая школа» 1980. В.М. Курейчик «Математическое обеспечение конструкторского и технологического проектирования с применением САПР», Москва «Радио и связь» 1990. К.К. Морзов, В.Г. Одиноков, В.М. Курейчик «Автоматизированное проектирование конструкций радиоэлектронной аппаратуры», Москва «Радио и связь» 1983. В.Н. Ильин, В.Т. Фролкин, А.И. Бутко и др.; «Автоматизация схемотехнического проектирования: Учебное пособие для вузов», Москва «Радио и связь» 1987. К.К. Морозов “Метод розбиения схем РЕА на конструктивно законченние части”. В.А. Селютин “Машинное конструирование електронних устройств ”. Додаток Слайд №1 Слайд №2 Слайд №3 Слайд №4 Слайд №5 Слайд №6 Слайд №7 Слайд №8 Слайд №9 Слайд №10 Слайд №11 Слайд №12 Слайд №13 Слайд №14 Слайд №15

Звіт Інші

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись