Что такое рокировка?

Рокировка — это преобразование алгоритма, при котором левое и правое плечо развилки меняются местами. Простейшие примеры рокировки показаны на рис. 8 и 21.

Два алгоритма называются равносильными, если для каждого маршрута первого алгоритма можно найти парный маршрут второго алгоритма, причем для каждой пары маршрутов их формулы совпадают. Обратимся к рис. 22. Легко убедиться, что схемы на рис. 22 а и б имеют одинаковый набор маршрутов:

Следовательно, указанные дракон-схемы равносильны.

Формальное преобразование алгоритма А1 в алгоритм А2 назы­вается равносильным, если алгоритмы А1 и А2 равносильны. Сказанное означает, что рокировка является равносильным преобразованием алгоритмов. При рокировке слова “да” и “нет” обязательно меняются местами.

Дата добавления: 2015-08-21