Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

Última alteração: Dezembro 27, 2001

ENGENHARIA DE CONTROLE E AUTOMAÇÃO

ALGORITMOS E ESTRUTURAS DE DADOS II

Prof. Nivio Ziviani

Monitora: Claudine Santos Badue

Trabalho Prático 1

Data de Entrega: 15-Janeiro-2002

Comentários Gerais

1.

Comece a fazer este trabalho logo, enquanto o problema está fresco na memória e o prazo para terminá-lo está tão longe quanto jamais poderá estar.

2.

Penalização por atraso: vide texto apresentação da disciplina.

3.

Este trabalho exercita conceitos e estruturas de dados apresentados nos capítulos 1 e 2 do livro texto [Ziv93].

4.

Vão valer pontos clareza, indentação e comentários no programa.

O que deve ser apresentado:

1.

Listagem do programa em Pascal.

2.

Listagem dos testes executados.

3.

Descrição sucinta (por exemplo, desenho), das estruturas de dados e as decisões tomadas relativas aos casos e detalhes de especificação que porventura estejam omissos no enunciado.

4.

Estudo da complexidade do tempo de execução dos procedimentos implementados e do programa como um todo (notação O).

Avaliação:

1.

Execução

(a)

Execução correta: 20%

(b)

Saída legível: 10%

2.

Estilo de programação

(a)

Código bem estruturado: 10%

(b)

Código legível: 10%

3.

Documentação

(a)

Descrição das estruturas de dados e principais decisões: 25%

(b)

Estudo da complexidade do tempo: 25%

[Ziv93] Ziviani, Nivio, Projeto de Algoritmos Com Implementações em Pascal e C, Editora Pioneira, 1993.

Matrizes Esparsas

Utilização de Listas Através de Apontadores

Retirado de [Ziv93, página 59, exercício 3]

Matrizes esparsas  são matrizes nas quais a maioria das posições são preenchidas por zeros. Para estas matrizes, podemos economizar um espaço significativo de memória se apenas os termos diferentes de zero forem armazenados. As operações usuais sobre estas matrizes (somar, multiplicar, inverter, pivotar) também podem ser feitas em tempo muito menor se não armazenarmos as posições que contém zeros. Uma maneira eficiente de representar estruturas com tamanho variável e/ou desconhecido é através de alocação encadeada, utilizando listas. Vamos usar esta representação para armazenar as matrizes esparsas. Cada coluna da matriz será representada por uma lista linear circularListas!circulares com uma célula cabeça.  Da mesma maneira, cada linha da matriz também será representada por uma lista linear circular com uma célula cabeça. Cada célula da estrutura, além das células-cabeça, representará os termos diferentes de zero da matriz e devem ter o seguinte tipo:

type
		 Apontador  = ^ TipoCelula; 
 
		 TipoCelula = record
		 		 		 Direita,
		 		 		 Abaixo 		 : Apontador;
		 		 		 Linha,
		 		 		 Coluna 		  : integer;
		 		 		 Valor 		  : real;
		 		 end;

O campo Abaixo deve ser usado para apontar o próximo elemento diferente de zero na mesma coluna. O campo Direita deve ser usado para apontar o próximo elemento diferente de zero na mesma linha. Dada uma matriz A, para um valor A(i,j) diferente de zero, deverá haver uma célula com o campo Valor contendo A(i,j), o campo Linha contendo i e o campo Coluna contendo j. Esta célula deverá pertencer à lista circular da linha i e também deverá pertencer à lista circular da coluna j. Ou seja, cada célula pertencerá a duas listas ao mesmo tempo. Para diferenciar as células cabeça, coloque -1 nos campos Linha e Coluna destas células. Considere a matriz esparsa seguinte

$$A = \left( \begin{array} {rrrr} 50 & 0 & 0 & 0 \ 10 & 0 &... ... 0 \ 0 & 0 & 0 & 0 \ -30 & 0 & -60 & 5 \end{array} \right)$$

A representação da matriz A pode ser vista na Figura 1.

  

Figura 1: Exemplo de Matriz Esparsa

Com esta representação, uma matrix esparsa $m \times n$ com r elementos diferentes de zero gastará (m + n + r) células. É bem verdade que cada célula ocupa vários bytes na memória; no entanto, o total de memória usado será menor do que as $m \times n$posições necessárias para representar a matriz toda, desde que r seja suficientemente pequeno. Dada a representação acima, o trabalho consiste em desenvolver cinco procedimentos em Pascal, conforme especificação abaixo:

• procedure LeMatriz (var A: Matriz); Este procedimento lê de algum arquivo de entrada os elementos diferentes de zero de uma matriz e monta a estrutura especificada acima. Considere que a entrada consiste dos valores de m e n (número de linhas e de colunas da matriz) seguidos de triplas (i, j, valor) para os elementos diferentes de zero da matriz. Por exemplo, para a matriz acima, a entrada seria:

  $$\begin{array} {rrr} 4, & 4 & \ 1, & 1, & 50.0 \ 2, & 1,... ..., & 1, & -30.0 \ 4, & 3, & -60.0 \ 4, & 4, & 5.0\end{array}$$

• procedure ApagaMatriz (var A: Matriz); Este procedimento devolve todas as células da matriz A para a área de memória disponível (use a procedure dispose).
• procedure SomaMatriz (var A, B, C: Matriz); Este procedimento recebe como parâmetros as matrizes A e B, devolvendo em C a soma de A com B.
• procedure MultiplicaMatriz (var A, B, C: Matriz); Este procedimento recebe como parâmetros as matrizes A e B, devolvendo em C o produto de A por B.
• procedure ImprimeMatriz (var A: Matriz); Este procedimento imprime (uma linha da matriz por linha da saída) a matriz A, inclusive os elementos iguais a zero.

Para inserir e retirar células das listas que formam a matriz, crie procedimentos especiais para este fim. Por exemplo, um procedimento

		 procedure Insere (i, j: integer; v: real; var A: Matriz);

para inserir o valor v na linha i, coluna j da matriz A será útil tanto na procedure LeMatriz quanto na procedure SomaMatriz. As matrizes a serem lidas para testar os procedimentos são:

• A mesma da Figura 1 deste enunciado;

  
  

• $\left( \begin{array} {rrrr} 50 & 30 & 0 & 0 \ 10 & 0 & -20 & 0 \ 0 & 0 & 0 & 0 \ 0 & 0 & 0 & -5 \end{array} \right)$

  
  

• $\left( \begin{array} {rrr} 3 & 0 & 0 \ 0 & -1 & 0 \end{array} \right)$

Os procedimentos deverão ser testados com o seguinte programa:

program TestaMatrizesEsparsas; 
$\cdots$ 
$\cdots$ 
begin
		  $\cdots$ 
		 LeMatriz (A); ImprimeMatriz (A);
		 LeMatriz (B); ImprimeMatriz (B);
		 SomaMatriz (A, B, C); ImprimeMatriz (C); ApagaMatriz (C);
		 MultiplicaMatriz (A, B, C); ImprimeMatriz (C);
		 ApagaMatriz (B); ApagaMatriz (C);
		 LeMatriz (B);
		 ImprimeMatriz (A); ImprimeMatriz (B);
		 SomaMatriz (A, B, C); ImprimeMatriz (C);
		 MultiplicaMatriz (A, B, C); ImprimeMatriz (C);
		 MultiplicaMatriz (B, B, C);
		 ImprimeMatriz (B); ImprimeMatriz (B); ImprimeMatriz (C);
		 ApagaMatriz (A); ApagaMatriz (B); ApagaMatriz (C);
		  $\cdots$  
end. { TestaMatrizesEsparsas }

É obrigatório o uso de alocação dinâmica de memória para implementar as listas de adjacência que representam as matrizes. A análise de complexidade deve ser feita em função de m, n (dimensões da matriz) e r (número de elementos diferente de zero).