Questões de Ciência da Computação do ano 2006

Julgue os seguintes itens, relativos à tarefa de classificação, a qual consiste em aprender uma função (construir um modelo) que mapeie um item de dado para uma entre várias classes pré-definidas. Algoritmos de árvore de decisão populares como o C4.5 e o CART examinam um atributo por vez, o que conduz a um particionamento dos dados em regiões de classificação retangulares, que sempre correspondem às distribuições reais das instâncias no espaço de decisão.

• C. Certo
• E. Errado

Julgue os seguintes itens quanto a tarefa de associação, a qual consiste na aprendizagem de regras de produção a partir de uma base de dados, considerando a análise de afinidade entre atributos. Algoritmos, como o apriori, para descoberta de regras de associação tendem a descobrir muitas regras. A significância de uma regra pode ser inferida por meio do suporte e da confiança. A confiança da regra corresponde ao percentual de exemplos da base de treinamento que levaram a determinada regra.

• C. Certo
• E. Errado

Quando uma função é definida em termos de si mesma fica caracterizado o uso

• A. da iteratividade.
• B. da recursividade.
• C. da interatividade.
• D. do acesso direto a Banco de Dados.
• E. de DLLs.

Levando-se em conta as cinco afirmações acima, identifique a única alternativa
válida:

• A.

  apenas I e III estão corretas.

• B.

  apenas I e IV estão corretas.

• C.

  apenas II e III estão corretas.

• D.

  apenas II e IV estão corretas.

• E.

  apenas V está correta.

Considere o algoritmo de busca seqüencial de um elemento em uma lista com n elementos. A expressão que representa o tempo médio de execução desse algoritmo para uma busca bem sucedida é:

• A.

  n2

• B. n * (n+1) / 2
• C. log2 n
• D.

  (n+1) / 2

• E.

  n log n

Uma função matemática unidirecional aplicada em uma quantidade de dados de entrada para produzir um resultado de tamanho fixo denomina-se algoritmo de

• A. hash.
• B. criptografia.
• C. certificação.
• D. autenticação.
• E. assinatura digital.

Seja a seguinte sub-rotina:

• A.

  21

• B.

  40

• C.

  56

• D.

  64

• E.

  70

Julgue as seguintes afirmações sobre análise de complexidade de algoritmos utilizando a notação O.

Escolha a alternativa que indica a(s) afirmação(ões) CORRETA(s).

• A.

  Apenas III

• B.

  Apenas I e II

• C.

  Apenas I e III.

• D.

  Apenas II e III.

• E.

  Todas as afirmações.

Julgue as seguintes afirmações sobre os principais algoritmos de ordenação. 2

I. O heapsort possui complexidade O(n ) no pior caso. Apesar disso, é o algoritmo mais eficiente para a grande maioria das situações. Ele é um algoritmo recursivo e demanda uma pequena quantidade de memória adicional em sua implementação.

II. O quicksort possui sempre em tempo proporcional a n logn, mesmo que o arquivo esteja completamente desordenado. Por esta razão, é recomendado para aplicações que não podem tolerar variações no tempo esperado de execução. Finalmente, o algoritmo não requer memória adicional para sua implementação.

III. O algoritmo de ordenação por inserção possui implementação simples e tem custo linear, quando se deseja adicionar elementos a um arquivo já ordenado e obter como resultado um outro arquivo ordenado.

Escolha a alternativa que indica a(s) afirmação(ões) CORRETA(s).

• A.

  Apenas II.

• B.

  Apenas III.

• C.

  Apenas I e II.

• D.

  Apenas II e III.

• E.

  Todas as afirmações.

Julgue as seguintes afirmações sobre compreensão de algoritmos. Apenas com a finalidade de auxiliar o candidato, ao lado da função é ofertada uma breve descrição de alguns símbolos utilizados, mas que são amplamente conhecidos e deve constar na base de conhecimentos do candidato.

Escolha a alternativa que indica a(s) afirmação(ões) CORRETA(s).

• A.

  Apenas I.

• B.

  Apenas II.

• C.

  Apenas III.

• D.

  Apenas I e II

• E.

  Todas as afirmações.