Período: 2008.1
15 de abril de 2008
Horário: 2as-feiras e 4as-feiras de 9 às 11 horas
ANÁLISE DE ALGORITMOS (INF 1721)

1o Trabalho de Implementação (T1) (Parte a)

Data de Entrega: 7 de maio de 2008

Descrição

Este trabalho prático consiste em desenvolver códigos para diferentes buscas em matrizes de inteiros ordenadas nas linhas e nas colunas (ver descrição abaixo).

Considere uma matriz quadrada M contendo n números inteiros (para efeito de cáculo de complexidade teórica, você pode assumir que n = (2k)2 para algum k inteiro). Esta matriz é dada ordenada tanto nas linhas como nas colunas (veja o exemplo abaixo, para n=64, k seria 3).

é
ê
ê
ê
ê
ê
ê
ê
ê
ë
4 10 21 34 39 40 57 62
9 17 28 35 41 42 58 72
19 20 30 47 49 49 65 73
27 39 40 48 52 60 66 79
33 43 44 58 59 61 77 81
46 46 60 63 69 71 79 88
56 61 62 68 72 76 87 88
64 67 69 73 83 89 90 91
ù
ú
ú
ú
ú
ú
ú
ú
ú
û

Table 1:

Considere agora o seguinte problema: Dado um número inteiro i, deseja-se saber se este se encontra na matriz M. Analise a complexidade (de pior caso) dos algoritmos abaixo para resolver este problema. A complexidade deve ser em função de n.
  1. Algoritmo I
  2. Algoritmo II
  3. Algoritmo III
  4. Algoritmo IV
Os algoritmos acima devem ser desenvolvidos e seu desempenho experimental deve ser analisado com respeito ao tempo de CPU. O desenvolvimento destes códigos e a análise devem seguir o seguinte roteiro: A corretude código será testada sobre instâncias de tamanho 64, 256, 1024, 2304, 4096, 9216, 12544 e 16384, que correspondem à matrizes quadradas de dimensão 8X8, 16X16, 32X32, 48X48, 64X64, 96X96, 112X112 e 128X128, respectivamente. O conteúdo das matrizes com n elementos serão os primeiros n inteiros ímpares. As buscas serão sempre por números pares, ou seja, será sempre um ``pior caso''. O elemento a ser buscado em cada caso teste será n/64, n/32, n/16, n/8, n/4 e n/2. Ou seja, deverão ser testadas 6 buscas para cada valor de n (um total de 48 testes).

Incentiva-se mais testes com valores ainda maiores de n (256X256, 512X512, ...).

O trabalho entregue deve conter: Observação:

No algoritmos II, III e IV, pode acontecer de a matriz entrada do algoritmo não seja quadrada. Isso NÃO é restritivo. Nesse caso, a posição central é dada pela média do índice inicial e final em cada dimensão. Considere também que a diagonal possui um elemento em cada uma das linhas ou colunas, aquele que acontecer em menor número. Os elementos da diagonal estarão espaçados homogeneamente na outra dimensão. Exemplo: Matriz retangular com posição inicial (1,1) e final (5,10). A diagonal será: (1,1), (2,4), (3,6), (4,8) e (5,10).

As implementações dos algoritmos TÊM que tratar esse caso.


This document was translated from LATEX by HEVEA.