Computer Science › Especialização
Uma splay tree não guarda informação de balanceamento nenhuma, e ainda assim toda sequência de m operações custa O(m log n): cada acesso rotaciona o nó tocado até a raiz, e o método do potencial prova o limite cobrando as operações caras de uma \"energia\" armazenada que as operações baratas depositam.
O algoritmo de Karger encontra um corte mínimo contraindo arestas aleatórias até sobrarem dois vértices; uma execução acerta com probabilidade de pelo menos 2/(n(n-1)), então repeti-la O(n^2 log n) vezes torna a falha desprezível. Os limites de Markov, Chebyshev e Chernoff são as ferramentas que transformam \"costuma funcionar\" numa garantia quantificada.
A busca exata pelo vizinho mais próximo em alta dimensão degrada para varrer tudo. O hashing sensível à localidade inverte o objetivo de uma função hash comum: itens parecidos devem colidir. Agrupar assinaturas MinHash em bandas ou bits de hiperplanos aleatórios amplifica uma pequena diferença de probabilidade de colisão num limiar nítido, dando busca aproximada sublinear.
Quando um problema é NP-difícil, aceite uma razão comprovada em vez do ótimo. Relaxe o programa inteiro para um programa linear, resolva e arredonde: para cobertura de vértices, ficar com todo vértice com valor de PL de pelo menos 1/2 é uma 2-aproximação, e a cobertura de conjuntos gulosa fica dentro de um fator ln n, que é essencialmente o melhor possível a menos que P = NP.
Um algoritmo online precisa decidir antes de ver o futuro, então é comparado com um ótimo offline que sabe tudo. O aluguel de esquis mostra uma regra de empate 2-competitiva, a paginação mostra que o LRU é k-competitivo e que nenhum algoritmo determinístico faz melhor, e a aleatorização contra um adversário oblívio melhora a paginação para O(log k).
Um fluxo grande demais para ser guardado precisa ser resumido numa só passada com memória minúscula. O sketch Count-Min estima a frequência de qualquer item dentro de um erro aditivo usando algumas linhas de contadores com hash, e o HyperLogLog conta elementos distintos com cerca de 2% de erro em poucos kilobytes acompanhando a maior sequência de zeros iniciais nos valores com hash.
Medir memória em vez de tempo dá uma paisagem diferente: o espaço pode ser reutilizado, então o não determinismo custa só um quadrado (Savitch: NSPACE(s) está contido em SPACE(s^2)), PSPACE é igual a NPSPACE e o TQBF, decidir uma fórmula booleana totalmente quantificada, é PSPACE-completo, e é por isso que o jogo perfeito em muitos jogos generalizados é PSPACE-difícil.
BPP é a classe dos problemas resolvíveis em tempo polinomial com erro de no máximo 1/3 em toda entrada; repetição e um limite de Chernoff encolhem esse erro exponencialmente. O teste de identidade de polinômios está em BPP via Schwartz-Zippel, sem algoritmo determinístico conhecido, e a conjectura de que P = BPP liga a aleatoriedade a limites inferiores de circuitos.
Deixe o verificador fazer perguntas aleatórias em vez de ler um certificado estático, e muito mais passa a ser provável: a não isomorfia de grafos tem uma prova interativa simples, e IP é igual a PSPACE. Provas de conhecimento zero convencem o verificador de que uma afirmação é verdadeira sem revelar mais nada, definidas por um simulador que forja a transcrição sem o segredo.
A criptografia moderna troca \"parece difícil de quebrar\" por reduções: um esquema é seguro se quebrá-lo permitisse inverter uma função de mão única. A indistinguibilidade computacional define a pseudoaleatoriedade, um bit hard-core transforma uma permutação de mão única num gerador que estica uma semente curta, e um PRG faz um one-time pad com uma chave curta.
O algoritmo de Shor quebraria RSA e Diffie-Hellman num computador quântico grande, então os padrões estão migrando para reticulados. O Learning With Errors pede para resolver um sistema linear mod q em que cada equação carrega um pequeno ruído; Regev mostrou que ele é tão difícil quanto problemas de reticulado no pior caso, e ele sustenta o ML-KEM, padronizado pelo NIST como FIPS 203 em 2024.
A geometria computacional parte de uma primitiva exata, o teste de orientação (o sinal de um determinante 2x2). Com ela, a cadeia monótona de Andrew constrói um fecho convexo em O(n log n), o que uma redução a partir da ordenação mostra ser ótimo, e uma linha de varredura que só para em eventos encontra todas as k interseções de segmentos em O((n + k) log n).
O diagrama de Voronoi divide o plano em regiões mais próximas de cada sítio, e o seu dual, a triangulação de Delaunay, liga sítios cujos círculos circunscritos são vazios. A Delaunay maximiza o menor ângulo entre todas as triangulações, o teste do determinante incircle e as trocas de aresta a constroem, e as duas estruturas têm tamanho linear e construção em O(n log n).
Dados três problemas realistas (posicionar armazéns para que nenhuma cidade fique longe de um, contar visitantes únicos numa frota de servidores e escolher uma troca de chaves que precisa continuar segura por 20 anos), classifique a dificuldade de cada um, escolha a ferramenta certa desta trilha (aproximação, sketches, geometria ou criptografia pós-quântica) e diga exatamente qual garantia ela dá e do que ela abre mão.
Part of the Computer Science curriculum.
Uma splay tree não guarda informação de balanceamento nenhuma, e ainda assim toda sequência de m operações custa O(m log n): cada acesso rotaciona o nó tocado até a raiz, e o método do potencial prova o limite cobrando as operações caras de uma \"energia\" armazenada que as operações baratas depositam.
O algoritmo de Karger encontra um corte mínimo contraindo arestas aleatórias até sobrarem dois vértices; uma execução acerta com probabilidade de pelo menos 2/(n(n-1)), então repeti-la O(n^2 log n) vezes torna a falha desprezível. Os limites de Markov, Chebyshev e Chernoff são as ferramentas que transformam \"costuma funcionar\" numa garantia quantificada.
A busca exata pelo vizinho mais próximo em alta dimensão degrada para varrer tudo. O hashing sensível à localidade inverte o objetivo de uma função hash comum: itens parecidos devem colidir. Agrupar assinaturas MinHash em bandas ou bits de hiperplanos aleatórios amplifica uma pequena diferença de probabilidade de colisão num limiar nítido, dando busca aproximada sublinear.
Quando um problema é NP-difícil, aceite uma razão comprovada em vez do ótimo. Relaxe o programa inteiro para um programa linear, resolva e arredonde: para cobertura de vértices, ficar com todo vértice com valor de PL de pelo menos 1/2 é uma 2-aproximação, e a cobertura de conjuntos gulosa fica dentro de um fator ln n, que é essencialmente o melhor possível a menos que P = NP.
Um algoritmo online precisa decidir antes de ver o futuro, então é comparado com um ótimo offline que sabe tudo. O aluguel de esquis mostra uma regra de empate 2-competitiva, a paginação mostra que o LRU é k-competitivo e que nenhum algoritmo determinístico faz melhor, e a aleatorização contra um adversário oblívio melhora a paginação para O(log k).
Um fluxo grande demais para ser guardado precisa ser resumido numa só passada com memória minúscula. O sketch Count-Min estima a frequência de qualquer item dentro de um erro aditivo usando algumas linhas de contadores com hash, e o HyperLogLog conta elementos distintos com cerca de 2% de erro em poucos kilobytes acompanhando a maior sequência de zeros iniciais nos valores com hash.
Medir memória em vez de tempo dá uma paisagem diferente: o espaço pode ser reutilizado, então o não determinismo custa só um quadrado (Savitch: NSPACE(s) está contido em SPACE(s^2)), PSPACE é igual a NPSPACE e o TQBF, decidir uma fórmula booleana totalmente quantificada, é PSPACE-completo, e é por isso que o jogo perfeito em muitos jogos generalizados é PSPACE-difícil.
BPP é a classe dos problemas resolvíveis em tempo polinomial com erro de no máximo 1/3 em toda entrada; repetição e um limite de Chernoff encolhem esse erro exponencialmente. O teste de identidade de polinômios está em BPP via Schwartz-Zippel, sem algoritmo determinístico conhecido, e a conjectura de que P = BPP liga a aleatoriedade a limites inferiores de circuitos.
Deixe o verificador fazer perguntas aleatórias em vez de ler um certificado estático, e muito mais passa a ser provável: a não isomorfia de grafos tem uma prova interativa simples, e IP é igual a PSPACE. Provas de conhecimento zero convencem o verificador de que uma afirmação é verdadeira sem revelar mais nada, definidas por um simulador que forja a transcrição sem o segredo.
A criptografia moderna troca \"parece difícil de quebrar\" por reduções: um esquema é seguro se quebrá-lo permitisse inverter uma função de mão única. A indistinguibilidade computacional define a pseudoaleatoriedade, um bit hard-core transforma uma permutação de mão única num gerador que estica uma semente curta, e um PRG faz um one-time pad com uma chave curta.
O algoritmo de Shor quebraria RSA e Diffie-Hellman num computador quântico grande, então os padrões estão migrando para reticulados. O Learning With Errors pede para resolver um sistema linear mod q em que cada equação carrega um pequeno ruído; Regev mostrou que ele é tão difícil quanto problemas de reticulado no pior caso, e ele sustenta o ML-KEM, padronizado pelo NIST como FIPS 203 em 2024.
A geometria computacional parte de uma primitiva exata, o teste de orientação (o sinal de um determinante 2x2). Com ela, a cadeia monótona de Andrew constrói um fecho convexo em O(n log n), o que uma redução a partir da ordenação mostra ser ótimo, e uma linha de varredura que só para em eventos encontra todas as k interseções de segmentos em O((n + k) log n).
O diagrama de Voronoi divide o plano em regiões mais próximas de cada sítio, e o seu dual, a triangulação de Delaunay, liga sítios cujos círculos circunscritos são vazios. A Delaunay maximiza o menor ângulo entre todas as triangulações, o teste do determinante incircle e as trocas de aresta a constroem, e as duas estruturas têm tamanho linear e construção em O(n log n).
Dados três problemas realistas (posicionar armazéns para que nenhuma cidade fique longe de um, contar visitantes únicos numa frota de servidores e escolher uma troca de chaves que precisa continuar segura por 20 anos), classifique a dificuldade de cada um, escolha a ferramenta certa desta trilha (aproximação, sketches, geometria ou criptografia pós-quântica) e diga exatamente qual garantia ela dá e do que ela abre mão.