Exercícios

11.6. Análise e Projeto de Algoritmos
Exercícios Fixação

O objetivo desta lista de exercícios é permitir a você revisar o conteúdo desta parte da disciplina de Análise e Projeto de Algoritmos e verificar os seus conhecimentos. O teste a ser realizado conterá exercícios semelhantes a estes e será do mesmo nível de dificuldade.

Alguns dos exercícios abaixo são de mera compreensão (você compreendeu a matéria ?), alguns são de resolução (você será capaz de aplicar diretamente uma técnica aprendida ?) e outros são de transferência (você é capaz de aplicar conhecimentos adquiridos em aula a um novo problema ?).

11.6.1. Parte I: Análise da Complexidade de Algoritmos

  1. Um dos pontos importantes a serem considerados ao se tomar a decisão de utilizar um algoritmo para a solução de um problema, é a sua correção. Um algoritmo incorreto não produzirá os resultados esperados e não pode ser utilizado. Outro ponto importante a ser considerado, quando temos mais de uma opção de algoritmos tradicionais para resolver um problema ou quando podemos projetar um algoritmo para um problema de diversas maneiras, é a questão de sua eficiência.
    Explique:
    a) O que significa a eficiência de tempo de um algoritmo.
    b) Quais as grandezas físicas que influenciam a eficiência de tempo de um algoritmo na prática.
    c) Quais dessas grandezas nós realmente utilizamos para expressar a eficência de tempo de um algoritmo, utilizando-as para o nosso modelo de computação ?
    d) De quais nós abstraímos e por quê ?
    e) Que notação utilizamos na prática para expressar a complexidade de tempo de um algoritmo ?
  2. Uma das possíveis formas de se descrever a complexidade de um algoritmos é a chamada Notação-Big-Oh, que é definida da seguinte forma: T(n) = O(f(n)) se existem constantes c e n0 tais que T(n) menor ou igual c.f(n) quando n maior ou igual n0. Explique o que você entendeu por esta definição.
  3. Para o cálculo da complexidade de algoritmos não recursivos, existe um conjunto de regras bastante simples de serem seguidas. Cite e descreva estas regras.
  4. Algoritmos recursivos são bem mais difíceis de se analisar com respeito ao seu comportamento assintótico (complexidade de tempo). Quando nós tentamos descrever a complexidade de tempo de um algoritmo recursivo utilizando as regras acima, acabamos obtendo uma fórmula também recursiva, que nós chamamos de relação de recorrência. Para resolver esta fórmula existe um conjunto de regras matemáticas que você ainda não viu. Mas você pode, para alguns problemas, "estimar" a complexidade de execução de um algoritmo recursivo com base em algumas de suas características sem a necessidade de resolver um problema matemático mais complexo.
    a) Explique que tipos de problemas ou algoritmos costumam ter complexidade da ordem de n log n e como os identificamos.
    b) Quais problemas que possuem geralmente complexidade da ordem de log n ?
    c) Quais os problemas que costumam ser exponenciais ?
  5. O que diferencia os problemas tratáveis dos não-tratáveis ? Explique o termo NP.
  6. O que são problemas não-decidíveis ? Explique porque eles são assim.
  7. Como eu identifico se um problema está em NP ? Exemplifique.
  8. Explique o que é a classe dos problemas NP-completos. Dê um exemplo de um problema aparentemente NP-completo e explique porquê.
  9. Explique porque, caso algum dia alguém encontre uma solução polinomial para um problema NP-completo, todos os problemas NP-completos estarão teoricamente resolvidos.

11.6.2. Parte II: Projeto de Algoritmos

  1. O que são as técnicas de projeto de algoritmos vistas em aula ? Como devem ser aplicadas ?
  2. Cite cada uma das técnicas de projeto de algoritmos vista em aula, explique quais são os seus princípios gerais e exemplifique com um problema concreto que pode que pode ser resolvido com cada uma, explicando de forma sucinta como a técnica é aplicada para resolver este problema.
  3. Todos conhecemos o problema do caixeiro viajante e vimos que é um problema de complexidade de tempo exponencial. Vimos também em aula, que uma solução bastante elegante para este problema é a de construirmos um algoritmo recursivo utilizando a técnica do backtracking para chegarmos a um conjutno solução de onde então extraímos a melhor. Esta solução tem a grande desvantagem, porém, de ficar tentando obter soluções evidentemente ruins ao descer por todos os ramos possíveis da árvore de chamadas recursivas.
    Uma outra solução é a descrita por Kurt Melhorn, na qual iterativamente vamos calculando o caminho de menor custo passando entre k cidades, com k crescendo de 2 até n e armazenando estes valores em uma tabela de melhores caminhos. Assim temos, iterativamente, para cada par de vértices vi, vj uma tabela contendo o caminho com k-1 arestas de menor custo entre os vértices deste par. Podemos inclusive calcular novos caminhos utilizando subcaminhos já calculados, o que nos poupa muito tempo de busca. Esta solução também é exponencial, possue porém, uma complexidade de tempo bastante inferior à do algoritmo recursivo.
    Identifique qual a técnica de projeto de algoritmos que foi utilizada na concepção deste algoritmo e justifique.
  4. Explique porque as técnicas de projeto de algoritmos nos permitem projetar algoritmos mais eficientes.