Полуинвариант (комбинаторика)
Полуинвариант — характеристика объекта которая изменяется монотонно в некотором определённом смысле при заданных преобразованиях. Например, числовой полуинвариант обычно не убывает или не возрастает. Обычно полуинвариант используется при доказательстве того, что применение данного алгоритма приводит к определённому состоянию.
Примеры
- Солдаты Конвея — одна из классических задач на полуинвариант.
Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.