Prova de correção do algoritmo para determinar se os elementos de uma matriz são repetidos um número igual de vezes

7

Peço desculpas pelo título longo, mas realmente não sabia como escrevê-lo de maneira diferente, sem a falta de informações sobre o conteúdo.

Recentemente, fiz um exame universitário sobre algoritmos paralelos. Um exercício me pediu para escrever um algoritmo para determinar se os elementos de uma matriz, vamos chamá-lo A, foram repetidos um número igual de vezes.

Por exemplo:

1) A = 1 8 8 1 8 1 1 8: a resposta é sim, todo número é repetido 2 vezes.

2) A = 7 8 8 5 5 4 7 8: a resposta é não.

Eu tive que escrever o algoritmo para um modelo específico de computação paralela, uma PRAM: o modelo exigia que eu usasse algumas técnicas para evitar conflitos de leitura / gravação e outros problemas, mas isso não é relevante. O que acabei com foi uma nova matriz, vamos chamá-la B, que eu posso definir da seguinte maneira:Given the array A, B[i] contains the number of repetitions of the element A[i] within A.

Por exemplo:

1) A = 1 8 8 1 8 1 1 8

B = 4 4 4 4 4 4 4 4

2)A = 7 8 8 5 5 4 7 8

B = 2 3 3 2 2 1 2 3

Como você pode pensar e esperar, a única coisa que resta a fazer é verificar se cada elemento de Bé igual ao outro, mas ... acontece que eu sou masoquista e a pressão do exame (mais eu tive um pouco temperatura) me levou a seguir outro caminho. Além disso, a comparação de elementos de uma matriz não é imediata usando este modelo de computação.

Portanto, para verificar se todos os elementos de Bsão iguais, somai todos eles e dividi o resultado pelo número de elementos de B: se o resultado foi igual a um elemento de B (por exemplo, o primeiro B[0]), o algoritmo retornou true( falsecaso contrário).

Tomando o exemplo acima:

1) sum = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 32-> 32 / 8 = 4 = B[0]-> Sim.

2) sum = 2 + 3 + 3 + 2 + 2 + 1 + 2 + 3 = 18-> 18 / 8 ≠ 2 = B[0]-> Não.

Eu sei que é um absurdo, mas foi o que eu vim.

Eu verifiquei essa abordagem com várias combinações diferentes de matrizes / números, e parece funcionar. O problema é que estou tendo dificuldade em encontrar uma prova (matemática) de que o algoritmo está correto. Além do resultado do exame, que ainda não conheço, estou muito interessado em saber se há alguma prova / explicação matemática que indique que essa abordagem está correta ou não, e é por isso que preciso de ajuda.

Espero ter postado a pergunta no site StackExchange certo. Caso contrário, redirecione-me para o site certo.

Agradeço antecipadamente.

Alessandro
fonte
2
Que tal (3 + 2 + 4) / 3 = 3?
Yuval Filmus
@YuvalFilmus Não entendi o que você quer dizer. Eu acho que você de alguma maneira entendeu mal a minha pergunta.
Alessandro

Respostas:

11

Não, seu algoritmo não funciona. Considere se a matriz A é

A = [1 1 1 1 1 2 2 3 3 3 3 3 3].

Então a matriz B será

B = [5 5 5 5 5 2 2 6 6 6 6 6 6].

A soma de B será 65 e o comprimento de B será 13; portanto, após a divisão, obteremos o número 5. Isso é igual ao primeiro elemento de B, portanto seu algoritmo emitirá "Sim". No entanto, nem todos os elementos de B são iguais e a resposta correta é "Não". Portanto, seu algoritmo fornece a saída errada neste caso.

Boa tentativa, no entanto! Descobrir como construir B foi provavelmente a parte mais difícil desse problema.


Como eu encontrei isso: não consegui encontrar um contra-exemplo com dois números distintos, então tentei com três números distintos. Indique que frequência cada um desses números aparece. Então a matriz terá o comprimento , e B conterá o valor repetido vezes, o valor repetido vezes, e repetido vezes, então a soma dos elementos de B é . Podemos encontrar um contra-exemplo se encontrarmos uma solução sobre os números inteiros positivos para a equação diofantinau,v,wu+v+wuuvvwwu2+v2+w2

u2+v2+w2u+v+w=u

de modo que ou . Isso é equivalente avuwu

u2+v2+w2=u(u+v+w),

onde são inteiros positivos e ou . Escolhi alguns valores pequenos de e tentei resolver esta equação diofantina usando Wolfram Alpha. A primeira solução que encontrei foi , , , mas também existem muitas outras. Em retrospecto, acho que poderia ter simplificado ainda maisu,v,wvuwuuu=5v=2w=6

v2+w2=uv+uw

mas eu não percebi e acabou não importando.

DW
fonte
Obrigado pela explicação! Eu entendi tudo. (Sad :()
Alessandro
5

[2,2,5,5,5,5,5,6,6,6,6,6,6] é um contra-exemplo.

como descobri isso: (O último passo disso foi um script Python.) Para que nem todos sejam iguais, é necessário que haja pelo menos dois números distintos que apareçam. No entanto, as médias são estritamente entre o mínimo e o máximo, portanto, para passar pelo seu critério, deve haver pelo menos três números distintos. Eu simplesmente imaginei que deveria haver um contra-exemplo com apenas três números distintos. Pelo motivo que dei duas frases atrás, com apenas três números distintos, é preciso apenas verificar se a média é o número do meio. Com essa observação, escrevi um script Python para tentar triplos em relação à ordem lexicográfica de [sum, maior, médio, menor], e a matriz que dei corresponde ao menor contra-exemplo que o script encontrou.


fonte
Agradável! Parece correto e útil. Eu gosto da explicação de como você a encontrou; isso parece realmente útil. Espero que a exclusão seja apenas temporária - se você optar por cancelar a exclusão, eu ficaria feliz em aprová-la.
DW
(Eu tinha eliminado meu porque isso não parece acrescentar nada ao seu.)