Análise
de Algoritmos
Exercícios de Fixação 1
O objetivo desta lista
de exercícios é permitir a você revisar o conteúdo
desta parte de Análise de Algoritmos e verificar os seus conhecimentos.
O teste a ser realizado conterá exercícos semelhantes a estes
e será do mesmo nível de dificuldade.
-
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 ?
-
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) <= c.f(n) quando n > n0. Explique o que você entendeu
por esta definição.
-
Vimos que existem duas
formas de se implementar listas: como conjuntos de dados fisicamente
adjacentes, atraves da utilização de vetores e como conjuntos
de dados apenas logicamente interligados, mas sem adjacência física,
através da utilização de listas encadeadas. As listas
encadeadas possuem vantagens de economia de memória bastante óbvias,
uma vez que é somente utilizada a memória realmente necessária
para armazenar um determinado conjunto de dados. Do ponto de vista de complexidade,
discutimos em sala de aula também vantagens e desvantagens dos dois
modelos. Explique qual dos dois modelos é melhor em
termos de complexidade de tempo de acesso e explique por que isto
ocorre, exemplificando atrav'es de um desenho. Diga qual é
a complexidade média de tempo de acesso a um dado em uma lista com
vetor de n dados e uma lista encadeada com n dados. Justifique.
-
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.
-
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 ? Cite
dois exemplos (vistos em sala de aula).
c) Quais os problemas
que costumam ser exponenciais ? Cite um exemplo (visto em sala de aula).
-
O que diferencia os
problemas tratáveis dos não-tratáveis ? Explique o
termo NP (isto não foi visto em aula. Pesquise na literatura).
-
Calcule a complexidade
do algoritmo abaixo.
Algoritmo Prova
Variáveis
inteiro i,j,k,n,x(n)
Início
para I de 1 até
n faça:
leia x(i);
fim para
para i de 1 até n - 2 faça:
para j de 1 até 2*n faça:
se i for ímpar
então
para
k de 1 até n2 faça:
x(k) <- x(i) * x(j);
fim para
senão
para
k de 1 até n faça
x(k) <- j;
fim para
x(j)
<- 1;
x(i) <- j;
fim se
fim para
fim para
Fim
