MO640 - Questão para a prova oral

Número: 049

Enunciado:
Dadas duas permutações, α e β, e considerando que ρ1, ρ2,...,ρt é uma série mínima de reversões sinalizadas que transformam α em β, ou seja

αρ1ρ2...ρt = β
A distânica 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

Autor(a): Douglas José Soares Rodrigues