Multiplicação de Cadeia de Matrizes
Este repositório foi criado com o intuito de disponibilizar as implementações dos algoritmos Recursive-Matrix-Chain e Matrix-Chain-Order em JAVA.
Encontram-se aqui todos os arquivos referentes a implementação de Matrix-Chain-Order que utiliza a programação dinâmica para fornecer o custo mínimo de multiplicação de cadeias de matrizes, e posteriormente a melhor parentização para a multiplicação.E a implementação de Recursive-Matrix-Chain que por ser recursivo demananda maior custo para obtenção dos resultados.
A finalidade é demonstrar através dessas implementações que a programação dinâmica é capaz de reduzir um processo exponencial em n para O(n3).
Requisitos para execução
A execução dos programas em Java e feita através da JVM, que precisa estar previamente instalada. Para que o programa possa ser compilado é necessário a instalação do JDK. A forma mais prática é a instalação de um IDE. Recomendamos o Netbeans IDE que já é instalado juntamente com o JDK.
- [Java 6 ou versões posteriores] (http://java.com/pt_BR/)
- [Netbenas IDE versão 7.3.1] (http://netbean.org)
Arquivos
- No pacote Classes: Matriz. java;
- No pacote Janelas: JPrincipal.java e JPrincipal.form
Onde, Matriz.java é a classe que contém os atributos e métodos necessários para obter os custos para a multiplicação de cadeia de matrizes; JPrincipal.java é a classe que cria a interface gráfica para entrada e saida de dados; JPrincipal.form e um arquivo auxilar .xml para o Netbeans IDE.
Instruções de compilação e execução
Primeiramente, caso não tenha a JVM instalada, baixe e instale. Baixe e instale o Netbeans IDE. No Netbeans, vá no menu Arquivos/Novo Projeto. Selecione a opção Java/Aplicação Java. Vai ser criado um projeto padrão JSE. Na estrutura de diretórios, procure a pasta src. Copie pra dentro desta pasta os pacotes que estão nesse repositório. Para compilar o projeto, vá no menu Executar/Limpar e Construir Projeto. O Netbeans IDE vai gerar os bytecodes a partir dos arquivos .java que estão nos pacotes. Para executar o projeto, na estrutura de diretóios, procure a pasta dist. Nesta pasta está o arquivo executável .jar.
As implementações foram desenvolvidas por Maria Filomena de Souza Alves, Luciano Pereira Varanis e Carlos Alberto de Assis alunos da disciplina Estrutura de Dados e Algoritmos, do curso de Mestrado em Modelagem Matemática da Informação da FGV- RJ no ano de 2013.