Ciência de Dados - Algoritmos de Dados Massivos II

Qual é a complexidade de espaço do Algoritmo 5.4 para escolher um elemento aleatório e uniforme em um fluxo de dados?

• O.n^2/

• O.n/

• O.`n/

• O.` C log n/

O que o Algoritmo 5.5 faz em relação aos elementos de um fluxo de dados?

• Conta o número de elementos ímpares

• Conta o número de elementos que são primos

• Conta o número de elementos pares

• Conta o número de elementos que satisfazem uma propriedade arbitrária

Qual é a probabilidade de um elemento ser escolhido pelo Algoritmo 5.4 em um fluxo de dados com n elementos?

• 1/2n

• 1/(n-1)

• 1/n

• 1/(n+1)

Qual é a estratégia utilizada pelo Algoritmo 5.4 para escolher um elemento aleatório e uniforme em um fluxo de dados?

• Sortear um número aleatório para cada elemento

• Manter um contador para cada elemento

• Trocar o valor do elemento com probabilidade 1/i

• Armazenar todos os elementos em memória

O que o Algoritmo 5.1 faz em relação à soma de elementos de um fluxo de dados?

• Conta a soma de todos os elementos

• Escolhe um elemento aleatório

• Ordena os elementos em ordem crescente

• Remove elementos repetidos

Qual é a função especial empregada no Algoritmo 5.1 para determinar o próximo elemento do fluxo?

• CONTA-ELEMENTO

• próximo.S

• SOMA-ELEMENTOS

• ESCOLHE-ELEMENTO

O que o Algoritmo 5.2 faz em relação à escolha de um elemento aleatório e uniforme em um fluxo de dados?

• Escolhe um elemento com base em um número aleatório

• Ordena os elementos em ordem decrescente

• Armazena todos os elementos em memória

• Remove elementos repetidos

Qual é a probabilidade de um elemento ser mantido como escolhido pelo Algoritmo 5.4 na iteração i de um fluxo de dados com n elementos?

• 1/(i+1)

• 1/i

• 1/(i-1)

• 1/2i

Qual é a estratégia utilizada pelo Algoritmo 5.4 para escolher um elemento aleatório e uniforme em um fluxo de dados?

• Armazenar todos os elementos em memória

• Trocar o valor do elemento com probabilidade 1/i

• Manter um contador para cada elemento

• Sortear um número aleatório para cada elemento

Qual é a complexidade de espaço do Algoritmo 5.5 para contar o número de elementos pares em um fluxo de dados?

• O.n^2/

• O.n/

• O.`n/

• O.` C log n/