Michel Vale Ferreira
Monografia de MAC-499
1.
Introdução:
Esta é uma monografia provisória. Posteriormente (quando as tarefas forem completadas e os objetivos do projeto atingidos) esta monografia será completada. O Projeto consiste na Implementação de alguns (3 ou mais) algoritmos para o problema de Steiner em grafos, descritos na dissertação de mestrado de Eduardo Gondo.
2.
Objetivos:
A finalidade é comparar os resultados práticos com o resultado teórico esperado.
3.
Definição/especificação do problema
Devido à restrições de tempo ao escrever esta monografia não escreverei aqui as definições e especificações do problema. Porém elas podem ser encontradas na tese de mestrado de Eduardo Gondo.
4. Estimativa inicial de
atividades e prazos:
(a) (b)
(c) (d)
(e)
(f) (g)
tarefa maio junho julho
agosto setembro outubro novembro
1 x x
2
x x
x x
3
x x
x
4
x x
Tarefas:
1. estudo dos conceitos básicos.
2. implementação dos algoritmos.
3. testes e comparações dos algoritmos.
4. escrita do trabalho.
(a) Estudo da notação e do problema (cap 1) e implementação dos algoritmos de
Dijkstra e Kruskal.
(b) Estudo e implementação do algoritmo de Zelikovsky.
(c) Estudo e implementação dos algoritmos do ganho relativo e de Robin e
Zelikovsky.
(d) Término das implementações e testes comparativos com instâncias aleatórias.
(e) testes comparativos com instâncias da biblioteca ...
(f) término dos estudos comparativos e início da escrita do trabalho.
(g) finalização da escrita do trabalho.
5. Métricas
post-mortem do andamento do projeto:
Foi feita de forma completa a tarefa (a) até o fim do primeiro semestre e de forma incompleta a tarefa (b) durante o segundo semestre de 2002.
6.
Bibliografia:
- Tese de Eduardo Gondo
- Página do Professor Paulo Feofilof (algoritmos de enumeração)
-
Aproximation
Algorithms for NP-Hard Problems (editado por Dorit S. Hochbaum)
7. Ferramentas e técnicas utilizadas:
- Gnu C Compiler (gcc)
-
Stanford
Graph Base (SGB)
- Conceitos das seguintes disciplinas: Grafos, Autômatos, Sistemas Operacionais, Conceitos Fundamentais de Linguagens e Análise de Algoritmos.
8.
Resultados:
Espero obtê-los em breve.
1. Desafios e frustrações encontrados:
- A escassez de tempo foi o maior problema enfrentado devido ao elevado número de matérias cursadas no ano. O que mais surpreendeu foi o número de listas e EPs para nota apenas no segundo semestre (15 e 10, respectivamente).
- Dificuldade de compreensão inerente dos conceitos utilizados.
-
A maior frustração foi não ter podido entregar o
trabalho no prazo.
2. Lista
das disciplinas cursadas no BCC mais relevantes para o Projeto:
- Grafos
- Autômatos (conceitos)
- Sistemas Operacionais (Princípio da Localidade)
- Conceitos Fundamentais de Linguagens (Recursão de Cauda)
- Análise de Algoritmos (reconhecer as complexidades de tempo e dar mais atenção ao código das funções “gargalo” do projeto)
3. Observações sobre a aplicação de conceitos estudados nos cursos no contexto prático de aplicações reais:
Estão
listados ao lado de cada disciplina acima.
4. Se o aluno fosse continuar atuando na área em que exerceu o estágio, que passos tomaria para aprimorar os conhecimentos técnicos/metodológicos/comerciais/científicos/etc relevantes para esta atividade?
Acredito
que a única opção para aprimorar os conhecimentos seria continuar no mundo
acadêmico (Mestrado, Doutorado e etc)
5. Críticas e Sugestões ao curso o BCC
Na
Monografia final também pretendo incluir uma longa série de críticas e sugestões
aos professores e sobre as maneiras como muitas disciplinas são dadas no IME.