Lista de Exercicios Projeto e Analise de Algoritmos EEM002 - Questoes Resolvidas

EEM002 Projeto e Análise de Algoritmos Para um determinado problema foi provado que a cota inferior é Ωn3 Nesse caso para algoritmos que resolvem esse problema é possível afirmar que A um algoritmo que resolve o problema e executa em tempo On3 será dito assintoticamente ótimo B o melhor algoritmo conhecido para o problema deve ter um tempo de processamento igual a On3 C não é possível desenvolver um algoritmo que resolva o problema e que tenha tempo de processamento igual a On3 D a cota inferior poderá mudar se alguém conseguir implementar um outro algoritmo melhor E não é possível desenvolver um algoritmo que resolva o problema e que tenha tempo de processamento igual a Ωn3 EEM002 Projeto e Análise de Algoritmos Uma equação de recorrência é uma maneira de definir uma função por uma expressão em termos dela mesma um conceito muito usado para computar o consumo de tempo de algoritmos recursivos Seja a recorrência dada por T1 1 Tn 2Tn11 A esse respeito assinale a alternativa correta A Essa recorrência é comum em problemas de ordenação Por exemplo MergeSort consegue obter uma recorrência parecida B Essa recorrência gerará um resultado Tn On2 C Um algoritmo recursivo descrito por essa recorrência executará um número exponencial de passos sendo proibitivo para entradas muito grandes D Essa recorrência pode ter vindo do algoritmo de busca binária dado que o algoritmo particiona o array de entrada em dois E Essa recorrência é obtida se dividirmos o tamanho da entrada pela metade Por exemplo se a entrada for um array de tamanho n faremos uma chamada recursiva passando um array que tera tamanho n2 As etapas de divisão e combinação juntas executam em θn EEM002 Projeto e Análise de Algoritmos Grafos são uma maneira computacional de representar problemas do mundo real o que gera naturalmente representações usando grafos orientados e não orientados Além disso as várias propriedades dos grafos como o grau dos vértices ajudam a entender a dificuldade do problema a partir do quão conectados estão os vértices Sobre os grafos orientados e não orientados assinale a alternativa que apresenta uma afirmação correta A Em um grafo orientado o grau de um vértice v é definido como o número de nos conectados a v somado com o numero de nós conectados aos nós conectados a v B Na representação usando matrizes de adjacência grafos orientados formam uma matriz em que todos os elementos abaixo e à esquerda da diagonal principal são nulos C Na representação usando colecoes de listas encadeadas não e possivel representar pesos nas arestas Nesse caso grafos ponderados devem utilizar a representação por meio de matrizes de adjacencias D Em um grafo orientado o grau de um vértice e computado como a soma do número de arestas de entrada com o numero de arestas de saída E Em um grafo não orientado um selfloop é possivel e pode conectar um vértice a ele mesmo sendo contabilizado duas vezes na computação do grau do vértice Dado um algoritmo com a seguinte equação de recorrência Tn Tn 1 On considere as afirmações abaixo como verdadeiras V ou falsas F O algoritmo não possui chamadas recursivas As etapas de divisão e combinação possuem complexidade linear A etapa de conquista é Tn 1 O algoritmo possui complexidade linear A sequência correta de preenchimento dos parênteses de cima para baixo é A VVFF B FFVV C FVVV D VVVV E FVVF Sobre algoritmos de ordenação considere as seguintes sentenças 1 O melhor caso do quicksort acontece quando o vetor já está ordenado 2 O quicksort tem complexidade de espaço Θ1 3 O heapsort tem complexidade de tempo On2 no pior caso Assinale a alternativa que apresenta a sequência correta A F V F B F F V C F F F D V F V E V V V Observe as seguintes funções fn 2100 gn n2 250 log n hn 210 n Assinale a alternativa que indica a ordem das funções de acordo com o crescimento para valores de n grandes A hn fn gn B fn hn gn C fn gn hn D gn hn fn E gn fn hn Uma equação de recorrência é uma maneira de definir uma função por uma expressão em termos dela mesma um conceito muito usado para computar o consumo de tempo de algoritmos recursivos Seja a recorrência dada por T1 1 Tn 2Tn11 A esse respeito assinale a alternativa correta A Essa recorrência é obtida se dividirmos o tamanho da entrada pela metadePor exemplo se a entrada for um array de tamanho n faremos uma chamada recursiva passando um array que terá tamanho n2 As etapas de divisão e combinação juntas executam em θn B Essa recorrência é comum em problemas de ordenação Por exemplo MergeSort consegue obter uma recorrência parecida C Essa recorrência pode ter vindo do algoritmo de busca binária dado que o algoritmo particiona o array de entrada em dois D Um algoritmo recursivo descrito por essa recorrência executará um número exponencial de passos sendo proibitivo para entradas muito grandes E Essa recorrência gerará um resultado Tn On2 Observe as seguintes funções fn 2100 gn n2 250 log n hn 210 n Assinale a alternativa que indica a ordem das funções de acordo com o crescimento para valores de n grandes A hn fn gn B fn gn hn C fn hn gn D gn fn hn E gn hn fn