Computação e IA · o experimento
Ordenar sem comparar tudo
Candidatos, referências, um grafo de comparações permitidas e um limite que se mantinha desde 2011. Quatro perguntas, de iniciante a avançado, sobre como ordenar quando alguns pares não podem ser comparados.
1 · Identifique o que muda
Iniciante
O que torna a ordenação generalizada diferente da ordenação comum?
2 · Conte as fases
Cada fase do algoritmo define um palpite para pelo menos metade das ligações ainda pendentes e adia o resto. Um grafo tem cerca de um milhão de ligações, aproximadamente 2²⁰.
Intermediário
Cerca de quantas fases são necessárias, no máximo, até que toda ligação tenha um palpite?
3 · Encontre o que quebra o QuickSort
Avançado
Por que um método no estilo do QuickSort não pode simplesmente ser aplicado à ordenação generalizada?
4 · Identifique o que o artigo científico não traz
Avançado
Qual destes o artigo científico não fornece?
Ordem recuperada
—