Институт математики СО РАН.
Настоящая работа посвящена построению математических моделей и разработке методов оптимизации структур ИС. Анализ моделей теории ИС приводит к необходимости решения сложных задач дискретной оптимизации. Накопленный же теоретический и практический опыт, связанный с реализацией алгоритмов решения задач дискретной оптимизации, показал, что встречающиеся трудности имеют принципиальный характер. Долгое время единственным способом анализа эффективности методов решения таких задач было численное экспериментирование. На рубеже 70-х годов возникла необходимость объективного сравнения задач дискретной оптимизации и алгоритмов их решения. В связи с этим стала бурно развиваться теория сложности алгоритмов. В последнее время общепринято измерять сложность алгоритма по количеству арифметических операций и ячеек памяти, необходимых для его реализации. Количество ячеек в запоминающем устройстве ЭВМ, требуемое для хранения необходимой информации при реализации алгоритма, называют его памятью. Количество же арифметических операций, выполняемых алгоритмом, называют его трудоемкостью или временной сложностью. Очевидно, что разные алгоритмы имеют разную трудоемкость и выяснение того, какие алгоритмы эффективны, а какие нет, всегда будет зависеть от конкретной задачи. Однако, специалисты-разработчики алгоритмов считают эффективными полиномиальные алгоритмы, т.е. алгоритмы, трудоемкость и память которых ограничены сверху некоторым полиномом от длины записи исходной информации.
