Algoritmos e Outras Tecnologias

Os algoritmos eficientes em termos de tempo ou espaço ajudam a diminuir o custo dos computadores, dada à quantidade finita de velocidade e memória dos computadores. É por esse motivo que o estudo dessa tecnologia é tão importante quanto qualquer outra, devido a sua usabilidade em quase todos os tipos de sistemas existentes.

Exercícios (Livro Algoritmos Teoria e Prática – Thomas Cormen 2012):

1-     Forneça um exemplo de aplicação que exige conteúdo algorítmico no nível da aplicação e discuta a função dos algoritmos envolvidos.

Uma página de busca de hotéis utiliza algoritmos de busca, comparação e ordenação para apresentar as melhores opções para seus clientes no topo da página.

2-     Vamos supor que estamos comparando implementações de ordenação por inserção e ordenação por intercalação na mesma máquina. Para entradas de tamanho n, a ordenação por inserção é executada em 8n² etapas, enquanto a ordenação por intercalação é executada em 64n Ig n etapas. Para que valores de n a ordenação por inserção supera a ordenação por intercalação?

Tabela contendo os possíveis valores de n até que se encontre o ponto onde a ordenação por inserção supera a ordenação por intercalação:

Valor de n	Inserção (8n2)	Intercalação (64n Ig n)
1	8,00	-
2	32,00	128,00
3	72,00	304,31
4	128,00	512,00
5	200,00	743,02
6	288,00	992,63
7	392,00	1.257,70
8	512,00	1.536,00
9	648,00	1.825,88
10	800,00	2.126,03
11	968,00	2.435,44
12	1.152,00	2.753,25
13	1.352,00	3.078,77
14	1.568,00	3.411,39
15	1.800,00	3.750,61
16	2.048,00	4.096,00
17	2.312,00	4.447,16
18	2.592,00	4.803,75
19	2.888,00	5.165,48
20	3.200,00	5.532,07
21	3.528,00	5.903,27
22	3.872,00	6.278,88
23	4.232,00	6.658,68
24	4.608,00	7.042,50
25	5.000,00	7.430,17
26	5.408,00	7.821,53
27	5.832,00	8.216,45
28	6.272,00	8.614,78
29	6.728,00	9.016,41
30	7.200,00	9.421,23
31	7.688,00	9.829,13
32	8.192,00	10.240,00
33	8.712,00	10.653,76
34	9.248,00	11.070,32
35	9.800,00	11.489,59
36	10.368,00	11.911,51
37	10.952,00	12.335,99
38	11.552,00	12.762,96
39	12.168,00	13.192,36
40	12.800,00	13.624,14
41	13.448,00	14.058,22
42	14.112,00	14.494,55
43	14.792,00	14.933,08

3-     Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n² funciona mais rápido que um algoritmo cujo tempo de execução é 2ⁿ na mesma máquina?

Tabela contendo os possíveis valores de n até que se encontre o ponto onde o algoritmo A supera (ou seja, possui menor velocidade) que o algoritmo B.

Valor de n	Algoritmo A (100n2)	Algoritmo B (2n)
1	100,00	2,00
2	400,00	4,00
3	900,00	8,00
4	1.600,00	16,00
5	2.500,00	32,00
6	3.600,00	64,00
7	4.900,00	128,00
8	6.400,00	256,00
9	8.100,00	512,00
10	10.000,00	1.024,00
11	12.100,00	2.048,00
12	14.400,00	4.096,00
13	16.900,00	8.192,00
14	19.600,00	16.384,00
15	22.500,00	32.768,00

Problemas (Livro Algoritmos Teoria e Prática – Thomas Cormen 2012):

1-     Comparação entre tempos de execução: Para cada função f(n) e cada tempo t na tabela a seguir, determine o maior tamanho n de um problema que pode ser resolvido no tempo t, supondo-se que o algoritmo para resolver o problema demore f(n) microssegundos.

Tabela contendo os possíveis valores de n.

	1 segundo	1 minuto	1 hora	1 dia	1 mês	1 ano	1 século
lg n	9,97	15,87	21,78	26,36	31,27	34,86	41,50
√n	31,62	244,95	1.897,37	9.295,16	50.911,69	176.363,26	1.763.632,61
n	1.000	60.000	3.600.000	86.400.000	2.592.000.000	31.104.000.000	3.110.400.000.000

.