Теоремы

ТЕОРЕМА О КОРРЕКТНОСТИ ПО ИНВАРИАНТУ ЦИКЛА

Если инвариант верен до цикла, сохраняется каждой итерацией и вместе с условием завершения дает постусловие, то цикл частично корректен.

ТЕОРЕМА О РАВЕНСТВЕ МНОЖЕСТВК статье

Два множества равны тогда и только тогда, когда каждое из них является подмножеством другого.

ТЕОРЕМА О РАЗЛОЖЕНИИ ОБЪЕДИНЕНИЯ МНОЖЕСТВК статье

Объединение двух множеств можно разложить на элементы, принадлежащие только первому множеству, только второму множеству, и элементы, принадлежащие обоим множествам.

MASTER THEOREM

Для рекуррентностей вида T(n) = aT(n/b) + f(n) асимптотика определяется сравнением f(n) с n^(log_b a) при выполнении условий теоремы.