Questões de Complexidade de Algoritmos (Algoritmos e Estrutura de Dados)

Limpar Busca

O analista Raimundo sabe que a indução de árvores de decisão é uma das formas mais simples, e ainda assim mais bem sucedidas, de aprendizagem de máquina. No entanto, ao aplicá-la em alguns problemas da empresa em que atua, o algoritmo de aprendizagem-em-árvore-de-decisão gera uma grande árvore quando realmente não há padrão a ser encontrado nos dados.
O nome do problema encontrado por Raimundo é

  • A suposição de estacionaridade.
  • B poda de árvore de decisão.
  • C superadaptação.
  • D hipótese nula.
  • E hiperárvore.

Na análise de complexidade de algoritmo, uma função f(n) é Ω (t(n)) se, e somente se, a seguintecondição for satisfeita, onde c e k são constantes positivas:

  • A 0 ≤ c .t(n) ≤ f(n) ∀ nk
  • B 0 ≤ c .t(n) < f(n) ∀ cn
  • C 0 < c . f(n) ≤ t(n) ∀ cn
  • D 0 < f(n) < c .t(n) ∀ ck
  • E 0 ≤ f(n) ≤ c .t(n) ∀ nk

O analista José precisa escolher entre dois algoritmos, Abusca e Cbusca. José sabe que, sendo N o tamanho da entrada do algoritmo, Abusca requer 2N + log2(N) operações para ser executado. Já o Cbusca requer N4 + N operações para ser executado. José determinou, na notação O-grande, a complexidade de tempo no pior caso para cada algoritmo e, por fim, deve escolher o algoritmo que apresenta a menor ordem de complexidade no pior caso.

José deve escolher o algoritmo:

  • A Cbusca, que possui complexidade O(N);
  • B Abusca, que possui complexidade O(2N);
  • C Cbusca, que possui complexidade O(N4 );
  • D Cbusca, que possui complexidade O(3N);
  • E Abusca, que possui complexidade O(log(N)).

O cálculo da complexidade computacional é essencial para verificar a viabilidade do algoritmo. Observe o código a seguir, em Python, para o problema da torre de Hanoi.

def hanoi(n, o, d, a):
if n==1:
print("D1 de "+o+" p/ "+d)
else:
hanoi(n-1, o, a, d)
print("D"+str(n)+" de "+o+" p/ "+d)
hanoi(n-1, a, d, o)

A complexidade desse algoritmo no pior caso é:

  • A O(2n );
  • B O(n);
  • C O(n log n);
  • D O(n2 );
  • E O(log n).

Filtros de Partículas são implementações não paramétricas de filtros Bayesianos em que as distribuições de probabilidade não são explicitamente definidas, sendo, portanto, representadas por um conjunto de amostras provenientes delas próprias (denominadas partículas).

Com relação aos filtros de partículas, analise as afirmativas a seguir e assinale (V) para a verdadeira e (F) para a falsa.

( ) As partículas representam observações (ou medidas) obtidas por sensores aplicados ao sistema em análise, e a elas são associados pesos proporcionais às suas probabilidades de coincidirem com medidas correspondentes ao estado verdadeiro do sistema.
( ) Quando aplicados à assimilação de dados, a cada passo de assimilação, novos pesos são atribuídos às partículas. Caso não seja realizado nenhum processo de reamostragem, o conjunto de partículas costuma degenerar-se, com uma das partículas recebendo peso normalizado próximo de 1 e as outras partículas recebendo pesos normalizados próximos de 0.
( ) São capazes de representar distribuições de probabilidade multimodais, isto é, cujas densidades de probabilidade possuem mais de um máximo local.

As afirmativas são, respectivamente,

  • A F – F – V.
  • B V – V – F.
  • C V – V – V.
  • D F – V – V.
  • E F – V – F.