Composições fracas, invariantes de laço e rastreamento de fluxogramas
Introduzido| English | Significado |
|---|---|
| stars and bars/stɑːz ænd bɑːz/ | estrelas e barras |
| complement/ˈkɒmplɪmənt/ | complementar |
| invariant/ɪnˈveərɪənt/ | invariante |
Tokens idênticos, caixas nomeadas
- Onze tokens de recompensa idênticos são colocados em quatro caixas nomeadas, sem limites de capacidade e permitindo caixas vazias. O registro de resultado contém apenas as quatro contagens. Não é $4^{11}$: isso distinguiria os tokens.
- Usaremos estrelas e barras, complementos e contagens exatas de caixas vazias, depois traçaremos um algoritmo de soma de quadrados. Invariantes de laço conectam os valores em um rastro a uma prova sobre cada passagem.
Estabeleça o modelo de alocação primeiro
- Sejam $n\ge0$ e $k\ge1$ inteiros. Objetos idênticos em caixas nomeadas $k$ correspondem a contagens de inteiros não negativos $x_1+\cdots+x_k=n$. Não há ordem dentro de uma caixa e, para a fórmula básica, não há capacidade máxima.
- Se os objetos forem distintos, alterar qual objeto entra em uma caixa pode mudar o resultado. Se as caixas forem anônimas ou capacidades forem impostas, a contagem básica também muda. Decida o que torna dois resultados diferentes antes de escolher uma fórmula.
Por que estrelas e barras é uma bijeção
- Coloque $n$ estrelas e $k-1$ barras em uma única linha. Lendo da esquerda para a direita, as barras separam as contagens das caixas 1 até $k$. Barras adjacentes são permitidas: elas registram caixas vazias.
- Para seis tokens em quatro caixas,
***||**|*representa $(3,0,2,1)$. Inversamente, cada tupla de contagens permitida constrói exatamente uma tal linha. Escolher as posições das barras entre $n+k-1$ lugares, portanto, conta as alocações sem duplicação.
Contar soluções não negativas
- O número de composições fracas é $\binom{n+k-1}{k-1}$. Para o $x_1+x_2+x_3=8$ original, escolha duas posições de barra entre dez: $\binom{10}{2}=45$. Para onze tokens em quatro caixas, a contagem é $\binom{14}{3}=364$.
- Casos limites importam. Sem tokens, há uma alocação, todas as contagens zero. Com uma caixa, há uma alocação, todos os tokens nela. A fórmula concorda em ambos os casos; ela não exige que toda caixa seja usada.
How many non-negative integer solutions does $x_1 + x_2 + x_3 = 8$ have?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Stars and bars: 8 stars and 2 bars, so C(8 + 2, 2) = C(10, 2) = 45 non-negative solutions.
How many allocations put zero identical tokens into four named boxes, with empty boxes allowed?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
There is exactly one tuple: (0,0,0,0). The stars-and-bars count is C(3,3)=1.
Remova limites inferiores por substituição
- Se cada $x_i\ge1$, defina $z_i=x_i-1\ge0$. Quando $n\ge k$, o total residual é $n-k$ e a contagem é $\binom{n-1}{k-1}$. Se $n<k$, não há tais alocações. As quatro contagens positivas originais somando-se a 9 resultam em $\binom83=56$.
- Mais geralmente, para limites inferiores inteiros $x_i\ge\ell_i\ge0$, subtraia todos os limites inferiores primeiro. Para $x_1+x_2+x_3=8$ com limites 2, 1 e 0, o total residual é 5, resultando em $\binom72=21$. Um residual negativo significa nenhuma solução.
How many positive integer solutions does $x_1+x_2+x_3+x_4=9$ have?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Set yᵢ = xᵢ − 1 ≥ 0, so y₁ + … + y₄ = 5. Stars and bars: C(5 + 3, 3) = C(8, 3) = 56.
Count integer solutions of $x_1+x_2+x_3=8$ with $x_1\ge2$, $x_2\ge1$, $x_3\ge0$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Subtract lower bounds 2,1,0, leaving three nonnegative counts totaling 5. The count is C(7,2)=21.
Use um complemento para pelo menos uma caixa vazia
- Dentro do conjunto completo de alocações, o complemento de "pelo menos uma caixa está vazia" é "todas as caixas são não vazias." Para onze tokens e quatro caixas nomeadas, alocações totalmente positivas contam $\binom{10}{3}=120$.
- Assim, $364-120=244$ alocações deixam pelo menos uma caixa vazia. Subtraia o complemento uma vez; subtrair quatro eventos de caixa vazia separadamente would malhandle alocações com várias caixas vazias.
Exatamente r caixas vazias é um evento diferente
- Para $n>0$ e exatamente $r$ caixas vazias, primeiro escolha essas caixas de $\binom kr$ maneiras. Coloque contagens positivas nas outras $k-r$ caixas. Se $1\le k-r\le n$, a contagem é $\binom kr\binom{n-1}{k-r-1}$; caso contrário, é zero.
- Com onze tokens e quatro caixas, exatamente duas vazias resulta em $\binom42\binom{10}{1}=60$. As contagens para zero, uma, duas e três vazias são 120, 180, 60 e 4, somando-se a 364. Para $n=0$, todas $k$ caixas estão vazias na única alocação.
Eleven identical tokens go into four named boxes. How many allocations have exactly two empty boxes?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Choose the two empty boxes in C(4,2)=6 ways. Split 11 positively between the remaining two in C(10,1)=10 ways. Multiply to obtain 60.
Twelve identical tokens go into four named boxes, each receiving at least two. Count all such allocations, then count those with at least one box receiving exactly two.
Verifique as condições de alocação ou o ponto exato de verificação do laço antes de comparar sua resposta.
Limites superiores exigem correções de sobreposição
- Contar $x_1+x_2+x_3=8$ com $0\le x_i\le3$. Começar com 45 alocações sem restrições. Para uma violação especificada $x_i\ge4$, subtrair 4 dessa coordenada: existem $\binom62=15$ dessas alocações.
- Subtrair $3\cdot15$ remove violações pares duas vezes. Para cada um dos três pares, dois contadores pelo menos 4 deixam resíduo zero, dando uma alocação para adicionar de volta. Nenhuma violação tripla se encaixa, então a resposta é $45-45+3=3$: as três permutações de $(3,3,2)$.
How many integer solutions of $x_1+x_2+x_3=8$ satisfy $0\le x_i\le3$ for every i?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Only the three permutations of (3,3,2) fit. Inclusion-exclusion gives C(10,2)-3C(6,2)+3C(2,2)=45-45+3=3.
Count integer solutions of $x_1+x_2+x_3=7$ with $0\le x_i\le3$. Use overlap counting and check by listing the possible count patterns.
Verifique as condições de alocação ou o ponto exato de verificação do laço antes de comparar sua resposta.
Objetos distintos usam escolhas independentes
- Para $n$ objetos distintos e $k$ destinatários nomeados, sem capacidades e sem ordem dentro da coleção de um destinatário, cada objeto escolhe um destinatário. A contagem é $k^n$. Cinco livros diferentes dados a três estudantes têm portanto $3^5=243$ alocações.
- Isso conta quais livros cada estudante recebe, não a ordem de entrega. Se todo estudante deve receber um livro, excluir eventos de estudante vazio e adicionar de volta suas interseções de par: $3^5-3\cdot2^5+3=150$. Barras e estrelas positivas não se aplicariam a esses livros distintos.
Qual modelo de contagem corresponde às condições declaradas?
Use identidade de objeto e restrições de alocação, não apenas uma fórmula familiar.
Five different books are given to 3 students (a student may get none). How many ways?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Each distinct book picks a student.
Especificar o laço de soma ímpar
- Seja a entrada $N$ um inteiro não negativo. Usar aritmética inteira exata e um laço pré-teste: testar a guarda antes da primeira passagem e antes de cada passagem subsequente. Aqui $m$ conta adições completadas, e $B$ armazena o próximo somando ímpar.
S ← 0
m ← 0
B ← 1
WHILE S < N
S ← S + B
m ← m + 1
B ← B + 2
ENDWHILE
- As atribuições executam na ordem escrita. Cada lado direito usa os valores disponíveis quando essa declaração executa; são atualizações sequenciais, não uma substituição simultânea de todas as três variáveis.
Rastrear uma declaração por vez
- Para $N=10$, o estado inicial é $(S,m,B)=(0,0,1)$ e a guarda é verdadeira. A primeira passagem altera o estado da seguinte forma; um valor permanece inalterado até que uma declaração o atribua.
| Declaração executada | S | m | B |
|---|---|---|---|
S ← S + B |
1 | 0 | 1 |
m ← m + 1 |
1 | 1 | 1 |
B ← B + 2 |
1 | 1 | 3 |
- A relação $S=m^2$ falha temporariamente após a primeira atribuição, quando $S=1$ e $m=0$. Vamos claimá-la no cabeçalho do laço, após a inicialização ou uma passagem completa, em vez de após cada declaração individual.
Resumir passagens completadas
- A tabela original mostra estados da cabeça do laço, com a guarda prestes a ser testada. Para $N=10$, as somas são 0, 1, 4, 9, 16; apenas os primeiros quatro estados entram em outra passagem. Na saída, $S=16$, $m=4$ e $B=9$.
- Para o limiar original $N=30$, o laço atinge 25 após cinco adições, depois adiciona 11 para atingir 36. Ele sai com $S=36$, $m=6$ e $B=13$. Manter o próximo somando separado do último somando usado.
Use the stated pre-test odd-sum loop with $S=0$, $m=0$, $B=1$ and threshold $N=30$. What is $S$ at exit?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
The loop-head sums are 0,1,4,9,16,25,36. Since 25<30≤36, it exits after six additions with S=36, m=6 and next addend B=13.
Estabelecer e preservar o invariante
- Em todo cabeçalho de laço, o invariante é $S=m^2$ e $B=2m+1$, com $m\ge0$ sendo um inteiro. A inicialização dá $S=0=0^2$ e $B=1$. Esses fatos não dependem do limiar.
- Suponha que a contagem antiga seja $m$. Uma passagem completa define a soma como $m^2+(2m+1)=(m+1)^2$, a contagem como $m+1$ e o próximo somando como $2m+3$. Assim, ambas as relações seguem válidas novamente no próximo cabeçalho. Isso é preservação, ainda não uma prova de terminação.
Provar que o laço para
- Seja $q=\lceil\sqrt N\rceil$, usado apenas para a prova. Em uma cabeça de laço com um guardião verdadeiro, $m^2<N$, logo $m<q$. Cada passagem aumenta $m$ exatamente em uma unidade, fazendo o inteiro não negativo $q-m$ diminuir em uma unidade. Após $q$ passagens, o guardião é falso.
- Isso prova a terminação e a contagem exata de passagens $q$, incluindo zero passagens para $N=0$. Dizer meramente que uma quantidade aumenta é insuficiente: uma sequência crescente pode permanecer abaixo de um limiar. Aqui, o invariante fornece o crescimento quadrático específico.
Use o invariante na saída
- Para $N>0$, o último guardião verdadeiro e o primeiro guardião falso fornecem $(m-1)^2<N\le m^2$. Portanto, $S$ é o menor quadrado maior ou igual a N. Se $S=N$, a entrada é um quadrado; se $S>N$, não é. Para $N=0$, o estado inicial já fornece o quadrado correto 0.
- O teste de saída fornece $S\ge N$; o invariante fornece $S=m^2$. Nenhum fato isoladamente prova a afirmação completa. Substituir
<por≤retornaria o menor quadrado estritamente maior que $N$, logo o guardião faz parte da especificação.
Qual parte da prova de soma ímpar é esta?
Separe inicialização, preservação, terminação e raciocínio na saída.
A loop invariant shows what is true when a loop ends, but termination needs a separate argument.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
An established and preserved invariant, combined with a false guard, proves the exit claim if the loop stops. A separate argument, such as the decreasing nonnegative integer ceil(sqrt(N))-m here, proves that it does stop.
Use the stated pre-test odd-sum loop with threshold $N=0$. What is $S$ at exit?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
The initial guard 0<0 is false, so the body runs zero times and S stays zero.
For the stated pre-test odd-sum loop, give S, m and B at exit for N=50 and for N=49. Justify both the pass count and the square test.
Verifique as condições de alocação ou o ponto exato de verificação do laço antes de comparar sua resposta.
Alterar a ordem das atualizações muda a sequência
- Se
B ← B + 2mover antes deS ← S + B, o primeiro somando torna-se 3. Com os mesmos valores iniciais, as somas tornam-se 3, 8, 15, …, e após $m$ passagens, a nova relação é $S=m(m+2)$. - Essa relação decorre da soma de $3+5+\cdots+(2m+1)$, mas não é o invariante original. Rastreie as atribuições reais antes de aplicar uma fórmula conhecida; uma prova válida para um laço não prova a correção de um laço reordenado.
Moving B ← B+2 before S ← S+B preserves the original loop-head invariant $S=m^2$ with the same initialization.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The first complete pass then gives S=3, m=1, B=3. The original equation S=m² already fails; the new sum is m(m+2).
Reinitialize todo o estado usado por uma nova execução
- Para processar limiares 2 e 5 independentemente, coloque todas as três inicializações dentro do laço externo, antes de cada laço de soma ímpar. As execuções retornam 4 e 9. Reinicializar apenas $S$ deixa o próximo somando antigo e a contagem no lugar.
- Com $m=0,B=1$ inicializado apenas uma vez, a primeira execução termina em $(S,m,B)=(4,2,5)$. Reinicie apenas $S$ para o limiar 5, e a próxima adição será 5: a segunda execução retorna 5, não 9. O invariante original não corresponde mais ao estado reinicializado.
Reset S=0, m=0 and B=1 before each run of the stated odd-sum loop. Which outputs correspond to thresholds 2 and 5?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The first squares at least 2 and 5 are 4 and 9. The output 5 on the second run would result from retaining B=5 after resetting only S.
Process thresholds 2, 5 and 10 in order. Compare outputs when all three state variables reset before each run with outputs when m=0 and B=1 are initialized once and only S resets between runs. Explain the difference.
Verifique as condições de alocação ou o ponto exato de verificação do laço antes de comparar sua resposta.
Resumo: modelo e ponto de verificação
- Conte os resultados pretendidos: verifique a identidade do objeto, rótulos das caixas, limites inferiores e capacidades. Para um laço, especifique inicialização, guardião e ordem de atualização, depois prove inicialização, preservação, terminação e a afirmação de saída em um ponto de verificação declarado.
- estrelas e barras: Um método bijetivo para contar alocações de inteiros não negativos de objetos idênticos entre caixas nomeadas sem capacidades superiores.
- complemento: Os resultados em um conjunto total especificado que não estão no evento sendo considerado.
- invariante: Uma propriedade que se mantém em um ponto de verificação especificado antes do laço e após cada passagem completa.