Questões

Para aplicar uma cifra de bloco em diferentes situações, o National Institute of Standards and Technology (NIST) define alguns modos de operações usados para aprimorar o efeito do algoritmo criptográfico ou para adaptar o algoritmo para uma aplicação em particular. Em um desses modos de operação, a primeira entrada do algoritmo criptográfico é o resultado do XOR entre os primeiros 64 bits de texto claro e um vetor de inicialização (IV), e as demais entradas do algoritmo criptográfico são o resultado do XOR entre os próximos 64 bits de texto claro e os 64 bits anteriores de texto cifrado.

Esse modo de operação é o

Usando a notação Big-O para representar o custo computacional, é correto afirmar que o tempo de execução da busca binária nunca é pior que

No contexto de estruturas de dados, considere uma lista encadeada L, não ordenada, contendo N elementos.

A complexidade do algoritmo de inserção nessa lista é:

Considere o conceito de complexidade polinomial, definido como O(p(n)), onde p(n) é um polinômio e O representa o limite superior da complexidade de um algoritmo. Algoritmos que pertencem à classe P são aqueles que possuem soluções algorítmicas cuja complexidade é limitada por um polinômio de grau k, ou seja, O(nk) para alguma constante k.

Esse tipo de problema é considerado solucionável em tempo "razoável" ou eficiente. Dado esse contexto, analise as afirmativas a abaixo sobre a classe P e a complexidade polinomial.

I. Algoritmos de ordenação como a ordenação por inserção têm uma complexidade polinomial de O(n 2 ), o que os coloca na classe P.

II. A classe P engloba todos os problemas que podem ser resolvidos por algoritmos em tempo polinomial, independente de hardware.

III. Algoritmos de pesquisa binária, embora eficientes, não são classificados como pertencentes à classe P, pois sua complexidade é logarítmica, e não polinomial.

IV. Um algoritmo que possui uma complexidade de tempo O(n k ), onde k é constante, resolve o problema no pior caso em tempo polinomial e, portanto, pertence à classe P.

Estão corretas as afirmativas:

Para classificar os processos tramitados no TJ-AC em duas categorias (deferidos e indeferidos), um analista escolheu um algoritmo que divide os dados de entrada em duas regiões separadas por uma linha e resulta em uma simetria na classificação, de forma que o ponto mais próximo de cada classe está a uma distância d do ponto médio entre os dois grupos de classe (hiperplano). O algoritmo descrito é denominado:

PARA i ←1 ATÉ n FAÇA      

           INÍCIO           

                      PARA j ←1 ATÉ i FAÇA               

                                 INÍCIO 

rotina com complexidade Ο(n);                

                         FIM;           

             FIM PARA;      

      FIM; 

FIM PARA;