Кривцун О. В. Фрагментарні моделі задач трасування, пакування і логічного проектування

Дисертаційна робота присвячена вивченню властивостей фрагментарних структур та розробці моделей на основі цих структур, призначених для пошуку наближених оптимальних розв'язків задач трасування друкованих плат, множинного тривимірного пакування і логічного проектування. Встановлено необхідну та достатню умови відповідності нерозміченого орграфа деякому класу ізоморфних фрагментарних структур. Встановлено критерій відповідності розміченого орграфа деякій фрагментарній структурі. Побудовано фрагментарні моделі для задач трасування друкованих плат, множинного тривимірного пакування і логічного проектування. Для фрагментарних моделей задач трасування друкованих плат і логічного проектування показано, що фрагментарні алгоритми мають поліноміальну часову складність, і відповідні фрагментарні структури мають властивість досяжності. Для задачі пошуку мінімальної множини аксіом розроблено програмне забезпечення, що генерує тестові приклади з різними структурами. Проведено порівняльний аналіз оцінки якості запропонованих моделей і методів. У роботі запропоновано новий метод для розв'язку задачі тривимірного пакування у контейнери різних типів.