ANÁLISE DE ALGORITMOS QUESTIONÁRIO UNIDADE I

Prévia do material em texto

10/03/2025. 20:05 Revisar envio do teste: QUESTIONÁRIO UNIDADE - ANÁLISE.. UNIP EAD CONTEÚDOS ACADÊMICOS BIBLIOTECAS MURAL DO ALUNO TUTORIAIS LABORATÓRIOS ANÁLISE DE ALGORITMOS 7948-30_43701_R_E1_20251 CONTEÚDO Revisar envio do teste: QUESTIONÁRIO UNIDADE Usuário vitor.araujo23@aluno.unip.br Curso ANÁLISE DE ALGORITMOS Teste QUESTIONÁRIO UNIDADE Iniciado 10/03/25 19:50 Enviado 10/03/25 20:04 Status Completada Resultado da tentativa 5 em 5 pontos Tempo decorrido 14 minutos Resultados exibidos Todas as respostas, Respostas enviadas, Respostas corretas, Comentários, Perguntas respondidas incorretamente Pergunta 1 0,5 em 0,5 pontos Provavelmente este é o caso de complexidade, seja de tempo ou de espaço. Muitos problemas de descobrir trajetos em grafos se enquadram neste caso, como por exemplo o caso da implementação de um algoritmo para resolver o Problema do Caixeiro Viajante. Esta complexidade é: Resposta Selecionada: C. O(n!) Respostas: a. b. C. (n!) d. O(n log n) e. O(n) Comentário da Resposta: C resposta: Comentário: cenário ocorre quando o consumo de tempo ou de memória cresce em função do fatorial do número de entradas: por exemplo, para apenas 10 entradas, um algoritmo que tenha essa complexidade irá executar milhões de operações. o ideal é sempre que possível buscar um algoritmo com uma complexidade melhor do que essa. Pergunta 2 0,5 em 0,5 pontos A redução assintótica da função de complexidade de um algoritmo, seja de tempo ou de espaço, consiste resumidamente em: Resposta b. Selecionada: Reduzir a função do algoritmo para o coeficiente maior, desprezando os valores que ficam muito pequenos em relação a este quando o número de entradas é muito grande. Respostas: a. Encontrar um valor exato para o tempo de execução em função da memória que o algoritmo consome para sua execução. b. Reduzir a função do algoritmo para o coeficiente maior, desprezando os valores que ficam muito pequenos em relação a este quando o número de entradas é muito grande. 1/510/03/2025, 20:05 Revisar envio do teste: QUESTIONÁRIO UNIDADE ANÁLISE... C. Encontrar o número ideal de entradas para o qual o algoritmo consome menor tempo de execução e menos d. Obter uma função que apresente o ponto ótimo em termos de consumo de tempo e espaço em relação ao número de entradas. e. Comparar a memória consumida (complexidade de espaço) com o número de operações (complexidade de tempo) que um mesmo algoritmo consome para sua execução. Comentário Resposta: B da resposta: Comentário: A redução assintótica pode ser considerada como "redução no infinito": quando uma função tiver um número de entradas muito grande (tendendo a infinito), podemos desprezar os coeficientes menores da função, pois seu resultado será muito próximo do valor obtido pelo coeficiente maior da função. É importante lembrar que a finalidade da função de complexidade é fornecer uma estimativa da ordem de grandeza e não do valor exato. Pergunta 3 0,5 em 0,5 pontos Considere as seguintes afirmações acerca de algoritmos recursivos: I. Todo algoritmo recursivo pode ser substituído por um algoritmo iterativo. II. Para um algoritmo cuja complexidade de tempo seja O(n), uma função recursiva equivalente que chame a si mesma apenas uma vez terá a mesma complexidade de tempo para executar as operações equivalente à função iterativa. III. Um algoritmo recursivo consumirá mais memória que uma versão iterativa equivalente, devido à construção de uma fila de dados devido à recursão. Estão corretas as afirmações: Resposta Selecionada: e II, apenas. C. Respostas: I, apenas. a. b. II, apenas. e II, apenas. C. d. e III, apenas. e. I, e III. Comentário Resposta: C da resposta: Comentário: A primeira afirmação está correta, pois todo algoritmo recursivo possui uma versão iterativa equivalente, sendo, assim, possível sempre substituir uma versão recursiva por uma iterativa; a segunda afirmação também está correta, pois faz a ressalva de que uma função recursiva pode ser mais lenta devido à construção de uma pilha de dados; por fim, a última alternativa está incorreta porque um algoritmo recursivo constrói uma pilha de dados, e não uma fila, para depois remover os elementos dessa estrutura e calcular a resposta. Pergunta 4 0,5 em 0,5 pontos Um algoritmo iterativo que possua duas estruturas de repetição encadeadas, e que estas sejam executadas cada uma delas N vezes, terá complexidade de tempo para este trecho: Resposta Selecionada: a. Respostas: a. b. 2/510/03/2025, 20:05 Revisar envio do teste: QUESTIONÁRIO UNIDADE ANÁLISE... C. O(2n) d. O(2 log n) e. O(n) Comentário da Resposta: A resposta: Comentário: A primeira estrutura de repetição irá ser executada N vezes. A cada execução desta, N outras execuções da estrutura de repetição que está dentro dela serão executadas. Assim, a complexidade de tempo desse trecho do algoritmo será = Pergunta 5 0,5 em 0,5 pontos "Nesta abordagem de programação dinâmica, vamos calculando os subproblemas menores e aumentando a dificuldade a cada iteração. Observe que, neste caso nós sabemos que cada iteração anterior já foi resolvida, logo não precisamos verificar toda vez como em outra abordagem." O trecho acima se refere à abordagem: Resposta Selecionada: Bottom-Up. a. Respostas: Bottom-Up. a. b. Top-Down. C. First-In-First-Out Last-In-First-Out. d. Greedy Search. e. Comentário Resposta: A da resposta: Comentário: A programação dinâmica possui duas abordagens principais: Bottom-Up e Top- Down. A primeira consiste em resolver primeiro os problemas menores, e in encadeando as respostas em direção à resposta final do problema. A segunda abordagem consiste em dividir o problema e resolvendo retroativamente, da última "divisão" em direção à primeira. Assim, o trecho apresentado descreve de forma resumida a abordagem Bottom-Up. Pergunta 6 0,5 em 0,5 pontos Considere o vetor H = [99, 68, 57, 45, 12, 7, 51], organizado com um heap. Após a remoção do elemento de maior prioridade e subsequente rearranjo dos elementos, o vetor ficará: Resposta Selecionada: H = [68, 51, 57, 45, 12, 7] e. Respostas: a. H = [68, 51, 45, 57, 12, 7] b. H = [68, 57, 51, 45, 12, 7] H = [68, 51, 57, 45, 7, 12] C. d. H = [68, 51, 57, 12, 45, 7] 7] e. Comentário da Resposta: E resposta: Comentário: Para remoção do elemento de maior prioridade, o primeiro elemento é trocado de posição com o último, ficando, assim, o valor 51 na primeira posição. Em seguida, este é comparado com seus dois filhos (68 e 57, sendo que o maior troca de posição com ele. Comparamos o elemento que desceu (51) com seus dois filhos (45 e 12) e não há mais troca de posição. 1&retu... 3/510/03/2025, 20:05 Revisar envio do teste: QUESTIONÁRIO UNIDADE - ANÁLISE... Pergunta 7 0,5 em 0,5 pontos Considere as três árvores binárias apresentadas na imagem. Satisfazem os requisitos para serem um heap: 8 8 9 7 2 7 9 7 8 1 5 1 5 2 1 5 2 III Resposta Selecionada: e III, apenas. C. Respostas: a. I, apenas. b. II, apenas. e III, apenas. C. d. e III, apenas. I, e III. e. Comentário da Resposta: C resposta: Comentário: Um heap precisa ser uma árvore binária quase-completa, balanceada, da esquerda para a direita. Todas as três imagens satisfazem essas condições. Além disso, cada nó precisa ser maior ou igual aos seus filhos, sendo que a figura II não satisfaz essa condição. Pergunta 8 0,5 em 0,5 pontos Um algoritmo de ordenação é dito estável quando: Resposta Preserva a ordem original dos valores que forem iguais após a ordenação. C. Selecionada: Respostas: Não é influenciado pelo estado original dos dados a serem ordenados. a. b. Não apresenta risco de entrar em um loop de repetição infinito quando em execução. Preserva a ordem original dos valores que forem iguais após a ordenação. C. d. pion e o melhor caso de execução possuem a mesma complexidade de tempo. e. pion e o melhor caso de execução possuem a mesma complexidade de espaço. Comentário da Resposta: C resposta: Comentário: Um algoritmo de ordenação estável não altera a posição relativa de valores iguais que estejam presentes na estrutura de dados que está sendo ordenada. Pergunta 9 0,5 em 0,5 pontos algoritmo de Knuth-Morris-Prat, também chamado de algoritmo KMP, apresentou uma forma mais elaborada e com menor complexidade de tempo para resolver um problema de busca que era resolvido por uma abordagem 4/510/03/2025, 20:05 Revisar envio do teste: QUESTIONÁRIO UNIDADE ANÁLISE... de força bruta. Esse algoritmo é utilizado para: Resposta b. Selecionada: Verificar a ocorrência de uma dada cadeia de caracteres em um conjunto maior de caracteres. Respostas: a. Calcular o menor caminho entre dois pontos entre um grafo ponderado. b. Verificar a ocorrência de uma dada cadeia de caracteres em um conjunto maior de caracteres. Ordenar um conjunto de dados com uma complexidade de espaço O(1). C. d. Reduzir o tamanho de um conjunto de dados por meio de uma codificação mais eficiente. Inferir a computabilidade de um algoritmo de busca. e. Comentário da Resposta: B resposta: Comentário: algoritmo KMP é uma variação do Algoritmo de Boyer-Moore para realizar de forma mais eficiente a busca por uma dada cadeia de caracteres dentro de um conjunto maior de caracteres sequenciais. Pergunta 10 0,5 em 0,5 pontos Muitos algoritmos de ordenação possuem complexidades de tempo diferentes para o caso" e o "pion caso". Por exemplo, o algoritmo Quick Sort tem complexidade (n log n) para o melhor caso e complexidade para o pior caso. que significam esses diferentes casos para esse tipo de algoritmo? Resposta b. Selecionada: Algoritmos de ordenação sofrem influência no seu tempo de ordenação em função do estado de ordenação inicial dos dados. Respostas: a. Algoritmos de ordenação não podem ser aplicados a qualquer tipo de estrutura de dados. b. Algoritmos de ordenação sofrem influência no seu tempo de ordenação em função do estado de ordenação inicial dos dados. Muitos algoritmos de ordenação não são estáveis. d. Algoritmos de ordenação possuem complexidade de espaço diferentes entre si, e podem ser mais lentos caso não ocorra disponibilidade de memória. e. uso ou não de recursão no código do algoritmo quando implementado pode afetar seu tempo de execução. Comentário da Resposta: B resposta: Comentário: O estado original dos dados e o quão diferente ele está do estado ordenado que se deseja pode influenciar o tempo de execução de um algoritmo de ordenação. Quick Sort é um dos algoritmos de ordenação que mais sofre influência do estado original dos dados que estão sendo ordenados. OK Segunda-feira 10 de Março de 2025 20h04min56s GMT-03:00