Aqui você encontra relatórios, códigos fonte e apresentações relacionados com trabalhos acadêmicos desenvolvidos durante graduação e pos-graduação. Alguns materiais estão em Português e outros em Inglês.
Desenvolvido na disciplina “Aprendizado de Máquina II” ministrada pelo Prof. Ruy L. Milidiú no Departamento de Informática da PUC-Rio.
Trabalho conjunto com Bernardo A. Pires.
Identificação de orações é um tipo de análise rasa e é importante para várias tarefas mais elaboradas de Processamento de Linguagem Natural como Semantic Role Labeling e Árvore de Dependência. Este projeto consiste no desenvolvimento de um sistema de apresendizado de máquina para este problema utilizando a técnica denominada Entropy Guided Transformation Learning (ETL).
Desenvolvido na disciplina “Combinatória Poliédrica” ministrada pelo Prof. Marcus V. S. Poggi de Aragão no Departamento de Informática da PUC-Rio.
O Orienteering Problem (OP) está relacionado ao Problema do Caixeiro Viajante com Coleta de Prêmios (PC-TSP). OP consiste em encontrar um ciclo em um grafo com peso nas arestas e prêmios nos vértices de modo a maximizar o total de prêmios coletados e respeitando uma restrição no tamanho máximo do ciclo. A diferença entre o OP e o PC-TSP é que no OP o objetivo é maximizar o total de prêmios coletados e existe uma restrição no tamanho máximo do ciclo. Já no PC-TSP, por outro lado, o objetivo é minimizar o tamanho do ciclo e existe uma restrição na quantidade mínima de prêmios coletados.
Este projeto consiste no desenvolvimento de um método de geração de restrições para eliminação de sub-ciclos em um algoritmo branch-and-cut para o OP. Este problema de separação pode ser formulado como um problema de corte mínimo (min-cut). O algoritmo para min-cut utilizado é fornecido na biblioteca Concorde. O pacote CPLEX é utilizado como framework branch-and-cut. A tecnologia Concert C++ é utilizada para interação com o CPLEX. Os cortes são gerados utilizando-se o esquema de callback do CPLEX.
Desenvolvido na disciplina “Aprendizado de Máquina I” ministrada pelo Prof. Ruy L. Milidiú no Departamento de Informática da PUC-Rio.
Trabalho conjunto com Carlos Crestana.
Semantic Role Labeling (SRL) é um importante problema na área de Processamento de Linguagem Natural. SRL consiste em identificar os modificadores e os argumentos dos verbos de uma sentença. Alguns exemplos deste argumentos são sujeito e objeto direto. Este problema foi proposto como tarefa conjunta em três edições da Conference on Computational Natural Language Learning (CoNLL 2004, 2005, and 2008). Este projeto consiste no desenvolvimento de um sistema de aprendizado de máquina para o SRL em textos de língua inglesa. O sistema é baseado na técnica de aprendizado de máquina denominada Entropy Guided Transformation Learning (ETL). Mais epcificamente, o sistema usa comitês de modelos ETL.
Esta é minha dissertação de mestrado concluída em 2005 na PUC-Rio. Meu orientador foi o Professor Celso C. Ribeiro.
Sequenciamento por Hibridação (SBH) é uma alternativa para o sequenciamento de DNA. Este método ainda está em desenvolvimento e pode se tornar mais barato e rápido do que as técnicas utilizadas atualmente. Um passo importante do SBH consiste em resolver um problema combinatorial. Este problema é formulado como um caso especial do Problema do Caixeiro Viajante com Coleta de Prêmios. Neste trabalho, nós propomos uma nova heurística construtiva multi-partida para este problema. Uma estratégia baseada em Memória Adaptativa e um procedimento de Construção de Vocabulário são utilizados para melhorar o desempenho da heurística multi-partida. A memória adaptativa é utilizada para intensificar a construção de novas soluções com elementos que aparecem frequentemente nas melhores soluções previamente construídas. O objetivo da construção de vocabulário é construir novas soluções através da combinação de partes de soluções boas. Experimentos computacionais são realizados e mostram que estes dois métodos melhoram substancialmente o desempenho da heurística multi-partida. Estes dois métodos são particularmente adequados para problema de escalonamento, nos quais as melhores soluções são construídas por blocos de elementos que aparecem juntos com alta frequência. A heurística proposta sistematicamente obtém melhores soluções que os melhores algoritmos encontrados na literatura. Além disso, a heurística proposta consome menos tempo computacional quando comparada com outros métodos.
Desenvolvido na disciplina “Projeto e Análise de Algoritmos” do Professor Ruy L. Milidiú no Departamento de Informática of PUC-Rio.
Este trabalho consiste na implementação de três algoritmos para cálculo da Árvore Geradora Mínima de um grafo. Os algoritmos desenvolvidos são: (i) o de Kruskal, (ii) o de Prim usando heaps binomiais e (iii) o de Prim usando heaps de Fibonacci.
Desenvolvido na disciplina “Geometria Computacional” do Professor Luiz Henrique de Figueiredo no Instituto de Matemática Pura e Aplicada (IMPA).
Trabalho conjunto com Michel Alain Quintana Truyenque.
Applet Java ilustrando a execução de dois algoritmos para o problema de encontrar o Círculo Envolvente Mínimo de um dado conjunto de pontos. O primeiro algoritmo tem complexidade O(n^2) e o segundo é o algoritmo aleatorizado de Welzl com complexidade O(n).
Desenvolvido na disciplina “Metaheurísticas” do Professor Celso C. Ribeiro no Departamento de Informática of PUC-Rio.
Neste relatório é apresentado uma revisão de dois trabalhos. O primeiro consiste em uma revisão bibliográfica (survey) da metaheurística Colônia de Formigas. No segundo artigo são apresentados algoritmos de Colônia de Formigas para o Problema Quadrático de Alocação. Neste artigo é apresentada uma detalhada comparação experimental entre estes algoritmos.
Desenvolvido na disciplina “Metaheurísticas” do Professor Celso C. Ribeiro no Departamento de Informática of PUC-Rio.
Este trabalho apresenta o Problema Quadrático de Alocação de duas perspectivas: teórica e prática. Em primeiro lugar, é discutida a complexidade computacional do problema. Então, são apresentadas heurísticas presentes na literatura para este importante problema. Particularmente, uma heurística construtiva aleatorizada e uma heurística de busca local baseada em diferentes vizinhanças são apresentadas. A partir destas duas heurísticas básicas, dois algoritmos são desenvolvidos, baseados nas metaheurísticas GRASP e ACO. O algoritmo ACO é baseado na versão MAX-MIN desta metaheurística. Todos estes algoritmos são avaliados experimentalmente.
Desenvolvido na disciplina “Programação Paralela e Concorrente” da Professora Noemi Rodriguez no Departamento de Informática of PUC-Rio.
Trabalho conjunto com Bruno Oliveira Silvestre.
Este projeto apresenta diferentes implementações de métodos paralelos para integração numérica. Um método estático e diferentes estratégias de um método adaptativo são apresentados. A implementação é baseada no pacote LAM-MPI – uma implementação da Message Passing Interface (MPI).
Desenvolvido na disciplina “Programação Concorrente e Paralela” da Professora Noemi Rodriguez no Departamento de Informática of PUC-Rio.
Trabalho conjunto com Alexandre Rocha Duarte.
Neste projeto é apresentada uma avaliação experimental de estratégias de paralelização da metaheurística Colônia de Formigas. O Problema Quadrático de Alocação é utilizado como caso de estudo. A implementação dos algoritmos é baseada no pacote LAM-MPI – uma implementação da Message Passing Interface (MPI).
Desenvolvido na disciplina “Laboratório de Hardware” do Professor Paulo A. Pagliosa no Departamento de Computação e Estatística of UFMS.
Trabalho conjunto com Delair O. Martinelli Jr.
Tutorial da API de comunicação serial Win32.
Desenvolvido na disciplina “Algoritmos Paralelos” dos Professores Henrique Mongelli e Édson Cáceres no Departamento de Computação e Estatística of UFMS.
Implementação do algoritmo paralelo de ordenação denominado Bitonic Sort. Este algoritmo segue o modelo BSP/CGM. O pacote LAM-MPI (uma implementação da Message Passing Interface) é utilizado.
Desenvolvido na disciplina “Algoritmos Paralelos” dos Professores Henrique Mongelli e Édson Cáceres no Departamento de Computação e Estatística of UFMS.
Este trabalho apresentado um relatório e uma implementação do algoritmo paralelo de Fox para multiplicação de matriz. Este algoritmo é baseado no modelo BSP/CGM. A implementação é baseada no pacote LAM-MPI (uma implementação da Message Passing Interface).
Desenvolvido na disciplina “Banco de Dados II” da Professora Kelly Adriana de Oliveira no Departamento de Computação e Estatística of UFMS.
Trabalho conjunto com Delair O. Martinelli Jr. e Marcos Leal Medeiros.
Neste trabalho é apresentado um tutorial sobre controle de recuperação do sistema de gerenciamento de banco de dados MySQL.
Desenvolvido na disciplina “Complexidade de Algoritmos” do Professor Celso C. Ribeiro no Departamento de Computação e Estatística of UFMS.
Trabalho em conjunto com Delair O. Martinelli Jr. e Marcos Leal Medeiros.
Neste trabalho são apresentados análise de complexidade, implementação e avaliação experimental de sete algoritmos de ordenação. Estes algoritmos são: bubble sort, insertion sort, selection sort, merge sorte, heap sorte, quick sort e box sort.
Desenvolvido na disciplina “Complexidade de Algoritmos” do Professor Celso C. Ribeiro no Departamento de Computação e Estatística of UFMS.
Trabalho conjunto com Delair O. Martinelli Jr. e Marcos Leal Medeiros.
Este trabalho apresenta análise de complexidade, implementação e avaliação experimental de dois algoritmos para o problema do par mais próximo. Os algoritmos são: força bruta e divisão-e-conquista.
Desenvolvido na disciplina “Complexidade de Algoritmos” do Professor Celso C. Ribeiro no Departamento de Computação e Estatística of UFMS.
Trabalho conjunto com Delair O. Martinelli Jr. e Marcos Leal Medeiros.
Neste trabalho são apresentados uma revisão da literatura e implementações de algoritmos para o Problema da Mochila. Dois algoritmos são implementados: o trivial baseado em força bruta e o clássico baseado em programação dinâmica.
Desenvolvido na disciplina “Complexidade de Algoritmos” do Professor Celso C. Ribeiro no Departamento de Computação e Estatística of UFMS.
Trabalho conjunto com Delair O. Martinelli Jr. e Marcos Leal Medeiros.
Neste trabalho são apresentados análise de complexidade, implementação e avaliação experimental de diversos algoritmos para o Problema do Caixeiro Viajante.
Except where otherwise noted, content on this wiki is licensed under the following license:Public Domain