Понятно, что каждая строка табл. 2 – это двоичное S-разрядное число, являющееся кодом некоторой -ичной цифры, в которую «сжато» -разрядное двоичное число (реакция ЦУ на соответствующий входной набор, входящий в тест ). Поскольку упомянутые -ичные цифры (коды) есть решение системы (1), то все строки табл. 2 попарно различны. Но отсюда следует, что и два любых столбца той же таблицы также попарно различны.
Из последнего утверждения вытекает следующий вывод: если i-ый столбец табл.2 интерпретировать как столбец значений булевой функции , то комбинационная схема, реализующая совокупность этих функций, является искомой СС.
Альтернативой методу перебора при поиске решения СЛАУ вида (1) возможно использование генетического алгоритма (ГА).
Генетический алгоритм.
Генетический алгоритм – эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе.
В первую очередь интересен последний пункт. Многие, думаю, подметили, что технологии нередко черпают вдохновление у природы. Самолеты — это гигантские металические птицы. Водолазы используют ласты, подобные плавникам морских жителей. И этому есть вполне логическое объяснение: люди на Земле существуют порядка 150 тыс. лет, в то время, как эволюция идет уверенной поступью в будущее уже четвертый миллиард лет.
Что же об эвристике — она вступает в игру когда все математические формулы, все логические способы решения задачи не привели к ожидаемому результату, либо полученный результат не является оптимальным. Эвристический алгоритм подразумевает нахождение нетривиального, неочевидного решения. И в этом, собственно, вся суть генетического алгоритма. Если немного перефразировать определение эвристического алгоритма, то получится что-то вроде: «Алгоритм, который должен достичь поставленой цели, используя какие угодно способы и решения». То есть флажок финиша есть, невидимых стен, ограничивающих направление движения, нет.
