049-2006

MO640 - Questão para a prova oral

Número: 049
Enunciado:
Dadas duas permutações, α e β, e considerando que ρ₁, ρ₂,...,ρ_t é uma série mínima de reversões sinalizadas que transformam α em β, ou seja

αρ₁ρ₂...ρ_t = β

A distância entre as permutações é definida como d_β(α) = t.
Sendo assim, uma reversão segura (safe reversal) ρ, de acordo com as notas de aula de Mneimneh, tem a seguinte propriedade:

1. d_β(αρ) = 1.
2. d_β(αρ) < 1.
3. d_β(αρ) < d_β(α).
4. d_β(α) < d_β(αρ).
5. NDA

Ideia original de: Douglas José Soares Rodrigues