Matrizes Esparsas

thiaguitolima
(usa Kurumin)

Enviado em 16/10/2007 - 20:14h

Galera preciso fazer um trabalho para faculdade sobre matrizes esparsas e nem sei por onde começar. Segue enunciado do trabalho, se alguém poder me ajudar dando dicas, mostrando como começar ficarei muito grato !

Projeto 01: matrizes esparsas
Nesse projeto o objetivo ´e implementar um conjunto de opera¸c˜oes para a
manipula¸c˜ao de matrizes esparsas [Ziviani, 2004, p´ag: 59-64].
Uma matriz esparsa ´e uma matrizes na qual a maioria das posi¸c˜oes ´e preenchida
por zeros. Para este tipo de matriz, podemos economizar espa¸co de mem´oria
se forem armazenados apenas os termos diferentes de zero. As opera¸c˜oes usuais
sobre estas matrizes (ler matriz, imprimir matriz, apagar matriz, somar duas
matrizes, multiplicar duas matrizes, e inverter uma matriz) tamb´em podem
ser feitas em tempo muito menor se n˜ao forem armazenadas as posi¸c˜oes
que cont´em zeros. Uma modo eficiente de representar estruturas com tamanho
vari´avel e/ou desconhecido ´e atrav´es de aloca¸c˜ao dinˆamica, utilizando listas.
Exemplo:
Abaixo temos um exemplo de arquivo texto que permite construir uma
matriz esparsa.

4 4
1 1 50.0
2 1 10.0
2 3 20.0
4 1 -30.0
4 3 -60.0
4 4 5.0

Tabela 1: Exemplo de Arquivo de Entrada

A primeira linha do arquivo texto informa o n´umero de linhas e colunas da
matriz a ser constru´ýda. Cada uma das linhas cont´em tres informa¸c˜oes: as
coordenadas (linha e coluna) e o conte´udo da respectiva coordenada. Desse
modo, a matriz esparsa correspondente ´e (a Figura 1 representa a matriz esparsa
via lista ligada):

M =
50.0 0 0 0
10.0 0 20.0 0
0 0 0 0
−30.0 0 −60.0 5.0


1.1 Exigˆencias na Implementa¸c˜ao
As estruturas de dados devem ser alocadas dinamicamente com malloc() e
as matrizes s˜ao constru´ýdas por informa¸c˜oes obtidas a partir de arquivos texto
que devem ser lidos pelo programa. Os arquivos de entrada e sa´ýda devem ser
informados na linha de comando. A modulariza¸c˜ao (e o encapsulamento) ´e parte
fundamental na confec¸c˜ao desse projeto. Escreva as rotinas em arquivos separados,
por exemplo, as rotinas de tratamento de arquivo devem estar num arquivo
separado das rotinas que fazem a manipula¸c˜ao das matrizes. Desse modo, ir´a
necessitar de um terceiro arquivo contendo a rotina principal (com o main).
todas as defini¸c˜oes de tipos e prot´otipos de fun¸c˜oes devem constar em header
files (arquivos do tipo .h).

paoloo
(usa Slackware)

Enviado em 16/10/2007 - 20:55h

rapaz, no numerical recipes in c(o mais classico dos livros de computacao cientifica), tem tudo isso implementadinho no 3o capitulo, q fala de matrizes e sistemas lineares... se na tua universidade nao tem, baixa o 3o capitulo do site q eh gratis... www.nr.com

LVX

f_Candido
(usa Ubuntu)

Enviado em 28/11/2007 - 14:11h

Não sei se será de grande ajuda, mas no Livro C Completo e Total, tem um capítulo falando sobre Matrizes Esparsas.
Espero ter Ajudado,
Abraços