Мне удалось найти алгоритм точного решения NP-полных задач за полиномиальное время. Результаты описаны⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
Как именно Вы видите применение такого решения в проектировании электронных устройств? Ну и в качестве продукции - тоже интересно как.Удешевить и повысить эффективность проектирования
электроники, как и улучить качество самой продукции.
Как именно Вы видите применение такого решения в проектировании электронных устройств?
Например имея решатель задачи точного покрытия множествами можно отключать минимальное количество строк и столбцов сбойных ячеек памяти обнаруженных в результате диагностики при производстве.
Что касается проектирования, то решая различные задачи на графах можно сделать схемы (имею ввиду прежде всего внутри микросхем) более эффективными.
Ага, понял о чем речь.# В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов.
# В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой.
Самое близкое, что приходит в голову это задача выполнимости булевых формул (ВЫП). Только в отличии карт карно задача более универсальная и NP-полная. т.е. решение получится известными но не мне способами не возможно в актуальное время.На счет оптимизации внутренней архитектуры алгоритма - с картами карно как-то можно сравнить?
Самое близкое, что приходит в голову это задача выполнимости булевых формул (ВЫП). Только в отличии карт карно задача более универсальная и NP-полная. т.е. решение получится известными но не мне способами не возможно в актуальное время.