Ciência e Dados - Algoritmos de Contagem Probabilística

Qual é a principal função do algoritmo da contagem probabilística?

• Remover duplicatas de um fluxo

• Ordenar elementos em um fluxo

• Estimar o número de elementos distintos em um fluxo

• Calcular a média de elementos em um fluxo

O que representa a notação z(x) no contexto do algoritmo da contagem probabilística?

• O número de dígitos 1 à direita da representação binária de x

• O número de dígitos 0 à esquerda da representação binária de x

• O número total de dígitos na representação binária de x

• O número de dígitos 1 à esquerda da representação binária de x

Como é calculado o valor de zmax no algoritmo da contagem probabilística?

• Somando todos os valores de z.h(ai)

• Calculando a média de todos os valores de z.h(ai)

• Encontrando o valor mínimo de z.h(ai)

• Encontrando o valor máximo de z.h(ai)

Qual é a relação entre zmax e o número de elementos distintos D?

• Quanto maior o valor de zmax, maior a chance de que D seja grande

• Quanto maior o valor de zmax, menor a chance de que D seja grande

• zmax é sempre igual a D

• zmax não tem relação com D

Qual é a principal melhoria do algoritmo LogLog em relação ao algoritmo da contagem probabilística?

• Aumentar a variância do estimador

• Diminuir a variância do estimador

• Reduzir o número de elementos no fluxo

• Aumentar o número de elementos no fluxo

Como o algoritmo LogLog reduz a variância do estimador?

• Usando a moda de múltiplos estimadores

• Usando a mediana de múltiplos estimadores

• Usando a média aritmética de múltiplos estimadores

• Usando apenas um estimador

Qual é a desvantagem de usar múltiplos estimadores no algoritmo LogLog?

• Reduz o número de elementos distintos

• Aumenta o número de elementos distintos

• Reduz a eficiência computacional

• Aumenta a variância

O que representa a variável aleatória Yz no contexto do Teorema 5.5?

• O maior número de elementos distintos de S

• O número total de elementos em S

• O menor número de elementos distintos de S

• O número de zeros à esquerda na representação binária

Qual é a probabilidade de que um elemento a ∈ S comece por no mínimo z zeros?

• 1/2^(2z)

• 1/2^(z-1)

• 1/2^(z+1)

• 1/2^z

Qual é a fórmula para o valor esperado de Yz?

• E[Yz] = 2^(z-1)

• E[Yz] = 2^(2z)

• E[Yz] = 2^(z+1)

• E[Yz] = 2^z