Algoritmos e Estrutura de Dados · CESPE / CEBRASPE · 2024 | Questão sqc-ce172772

Distância de Minkowski × Distância de Edição

❌ ERRADO. A afirmação incorre ao atribuir à distância de Minkowski a definição que cabe à distância de Levenshtein (ou distância de edição).

A distância de Minkowski é uma métrica generalizada para vetores numéricos, dada por:

d(\mathbf{x}, \mathbf{y}) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{1/p}

Ela engloba as distâncias de Manhattan ( $p=1$ ) e Euclidiana ( $p=2$ ). Já a distância de Levenshtein mede o número mínimo de operações de edição (inserção, remoção, substituição) para transformar uma cadeia de caracteres em outra.

Portanto, o item troca os conceitos e está errado.

Distância de Minkowski

1Métrica para vetores numéricos
- Fórmula: (Σ|xi - yi|^p)^(1/p)
- Casos particulares
  - Manhattan (p=1)
  - Euclidiana (p=2)
2Não se aplica a strings
3Distância de Levenshtein
- Métrica para cadeias de caracteres
  - Operações de edição
    - Inserção
    - Remoção
    - Substituição
- Mínimo de operações para transformar

LEVEL · soulevel.com.br

NÃO CAIA NESSA!

A banca confunde duas métricas distintas: a de Minkowski (numérica) e a de Levenshtein (para strings). Fique atento: sempre que a questão falar em "operações de edição" em cadeias de caracteres, pense em distância de edição, não em Minkowski.

Gabarito: E - Errado.

Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESPE / CEBRASPE 2024

Distância de Minkowski × Distância de Edição