T06 Dualidade forte no Teorema de Hammersley (TH)
Por conta de minha vontade de simplificar, a explicação de por que vale a dualidade forte no contexto do teorema de Hammersley (TH) ficou errada/incompleta nas aulas. Este exercício retifica/completa o argumento.
Recordando: discutimos o jogo de paciência (simplificado) nas aulas de 14/9/2021 e 16/9/2021. Temos inicialmente uma sequência de cartas. Ao jogarmos paciência, podemos chegar em várias configurações finais (CFs). Seja \(p^*\) o número mínimo de pilhas a que conseguimos chegar (o objetivo do jogo é chegar no número mínimo de pilhas, isto é, em uma configuração final (CF) com $p^*$ pilhas).
Seja $q^*$ o número máximo de elementos em uma subsequência crescente (SSC) da sequência de cartas. O TH diz que $q^*=p^*$.
Observação. No jogo de paciência, estamos interessados em encontrar $p^*$. No Problema da SSC Mais Longa (LIS, Longest Increasing Subsequence), estamos interessados em encontrar $q^*$.
Prova do Teorema de Hammersley. Para provar o teorema, primeiro vimos uma relação entre o número de elementos em uma SSC e o número de pilhas em uma CF. Vimos que, se $q$ é o número de elementos em uma SSC e $p$ é o número de pilhas em uma CF, então $q\leq p$. Chamamos essa desigualdade de dualidade fraca.
Abaixo, para simplificar o texto, $p$ sempre denota o número de pilhas em uma CF e $q$ denota o número de elementos em uma SSC. Assim, a dualidade fraca diz que sempre temos $q\leq p$. A prova da dualidade fraca é simples, e vimos nas aulas (como aquecimento, prove a dualidade fraca agora mesmo).
Observação crucial. Se encontramos uma SSC com $x$ elementos e uma CF com $x$ pilhas, então $x=q^*$ e $x=p^*$. Em particular, $q^*=p^*$ e o provamos o TH.
Em palavras, a observação crucial acima diz que $x$ é o número máximo de elementos em uma SSC e $x$ é o número mínimo de pilhas em uma CF. A observação crucial é imediata: sempre temos $q\leq p$ (dualidade fraca) e assim um $x$ como no enunciado é claramente o máximo dos $q$ e o mínimo dos $p$.
Conclusão. Para provar o TH, basta encontramos um $x$ como na observação crucial. Para tanto, usamos um algoritmo guloso para jogar paciência. Ao decidirmos onda a próxima carta vai, escolhemos a pilha mais à esquerda possível. Seja $x$ o número de pilhas na CF resultante. Basta agora encontrarmos uma subsequência crescente com $x$ elementos.
Na aula de 16/9/2021, aos 47:00, falei que basta olharmos para a sequência dos topos das pilhas na CF resultante (no exemplo da aula, essa sequência é $2,4,7,8,9$). Essas cartas sempre formam uma sequência crescente: isso segue do algoritmo guloso. Entretanto, essa sequência não é necessariamente uma subsequência da sequência original de cartas (de fato, no exemplo, $2,4,7,8,9$ não é uma subsequência da sequência original). Assim, esse argumento não vale :-(
Exercício. Neste exercício, você deve argumentar como encontrar uma SSC com $x$ elementos com base no algoritmo guloso, completando assim a prova do TH.
Dica. O que indicam as flechas vermelhas na figura da página 6 da apresentação?
Observação. No E09 (enunciado em preparação), você deverá implementar um algoritmo $O(N\log N)$ para resolver o LIS, baseado em sua solução deste exercício.