Аннотация:
В статье рассмотрена одна из важных задач конструкторского проектирования – задача синтеза комбинационных логических схем. Она относится к классу NP-сложных и
трудных задач. В работе описана постановка задачи, предложен эволюционный подход ее
решения. Описаны задачи анализа и синтеза при проектировании комбинационных логических схем. Разработан эволюционный алгоритм на основе моделирования эволюции Гуго де
Фриза, позволяющий получать наборы квазиоптимальных решений за полиномиальное время. Реализована программная среда на языке С# и проведен вычислительный эксперимент.
Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки
временной сложности алгоритмов проектирования комбинационных логических схем и их
поведение. В лучшем случае временная сложность алгоритмов $\approx O(n\log n)$, в худшем случае — $O(n^2)$.
Полный текст:
PDF файл (160 kB)