Lista Pratica AED1

DCC-ICEx-UFMG
TP0: Palavras Cruzadas
Thiago Costa Porto

10 de Março de 2008

1

Sumário
1 Introdução

3

2 Taxa de Interseção

3

3 Problema da Geração de Palavras Cruzadas

3

4 Solução Proposta

4

5 Tipos Abstratos de Dados
5.1 Matriz Esparsa . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Informações sobre palavras . . . . . . . . . . . . . . . . . . . . .

5
5
7

6 Entrada
6.1 Tipo da Entrada . . . . . . . . .
6.2 Tratamento da Entrada . . . . .
6.2.1 Pseudo-código . . . . . . .
6.2.2 Análise de Complexidade
6.3 Exemplo de Entrada . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

8
. 8
. 8
. 9
. 9
. 10

7 O Algoritmo
11
7.1 Descrição do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . 11
7.2 Pseudo-código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.3 Análise de Complexidade . . . . . . . . . . . . . . . . . . . . . . 14
8 Saída

15

9 Ambiente de Testes

15

10 Testes
10.1 Tempo de Usuário
10.2 Memória Utilizada
10.3 Tempo de Sistema
10.4 Tempo de Relógio .
10.5 Taxa de interseção

.
.
.
.
.

16
16
17
18
19
20

.
.
.
.

20
20
21
21
21

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

11 Análise dos Resultados
11.1 Por que o score não é uma
11.2 Taxa de Interseção . . . .
11.3 Memória . . . . . . . . . .
11.4 Tempo . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

boa escolha
. . . . . . .
. . . . . . .
. . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

de ordenação