Michel Vale Ferreira

Monografia de MAC-499

 

 

Parte I

 

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.

 

 

 

Parte II

 

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.