Algoritmos e Estruturas de Dados II
Turma 128 - semestre 98/1
Prof. Eduardo Augusto Bezerra
Monitor: Luciana
Spagnoli
Congresso
de Algoritmos
Provas do semestre:
-
P1
(13/04), P2
(25/05), P3
(29/06), P4
(30/06), G2 (06/07), G3 (13/07)
Trabalhos:
-
Trabalho sobre matrizes esparsas (entrega: 30/03/98) - Implementação
em uma linguagem de programação de algoritmos para inclusão,
exclusão, alteração e listagem de matrizes esparsas
representadas por intermédio dos métodos: matriz de bits
e tabular.
-
Trabalho extra (valendo 1 ponto em qualquer um dos trabalhos, menos no
final) - Implementação de algoritmo para multiplicação
de matrizes (entrega: 16/03/98).
-
Trabalho 3: Desenvolver um programa para gerencia de pessoal em uma
organização militar. O programa deverá utilizar como
estrutura de dados uma árvore genérica (sugestão -
utilizar a transformação para árvore binária
conforme visto em aula). Nesta árvore as folhas representam
os militares de mais baixa patente (ex: marinheiros, soldados). Implementar
as operações de inclusão, remoção, alteração
e relatórios. Nos relatórios deverá existir opção
para: busca por um determinado nome; listar todos os sargentos pertencentes
a uma determinada divisão; fornecer o total de tenentes da organização;
informar quantos elementos são de responsabilidade de determinado
oficial ou sargento; o nome de todos os capitães. Adicionalmente
deverão existir mais três tipos de relatórios sugeridos
pelo desenvolvedor do programa.
O programador é o responsável por modelar o problema e
propor uma solução. Maiores informações sobre
o problema poderão ser obtidas em entrevistas com o professor da
disciplina (que irá representar o cliente), ou a partir de entrevistas
com militares que tenham conhecimento do sistema de funcionamento de uma
organização militar. O trabalho é individual e deverá
ser entregue em um disquete (contendo o fonte e o executável) no
dia 08/06/98. Desenvolver uma interface o mais clara possível para
evitar notas baixas devido a problemas durante a utilização
do software (dica: após o programa estar funcionando, solicitar
a um colega que utilize o programa, sem dar explicações sobre
o funcionamento).
-
Trabalho final (entrega: semana de 29/06/98 a 03/07/98). Implementar os
algoritmos para caminhamento em grafos (largura e profundidade). Os algoritmos
deverão processar grafos direcionados e não-direcionados,
com um número indeterminado de nodos e arcos. Os grafos a serem
processados deverão ser obtidos a partir de arquivos texto (exemplos
de arquivos: ex1.txt;
ex2.txt;
ex3.txt).
O programa deverá ser capaz de trabalhar com qualquer arquivo que
siga o formato dos arquivos exemplos (primeira linha contendo um comentário
sobre o conteúdo dos nodos do grafo; segunda linha contendo o tipo
do grafo direcionado ou não-direcionado; a partir da terceira linha
aparecem o nodo origem, seguido por um 0 e nas linhas seguintes nodos adjacentes
seguidos por um peso em relacao ao nodo origem). O trabalho é individual,
e a avaliacão será realizada em reuniões individuais
com os alunos que deverão apresentar os códigos fonte e executável
do programa. Para evitar falta de horários para apresentação
no final do semestre, marcar um horário para apresentação
o quanto antes. Maiores detalhes sobre o que deverá ser implementado
foram fornecidos na aula do dia 08/06/98 e serão fornecidos conforme
necessário nas próximas aulas até a data da entrega.
Listas de exercícios e sugestões de algoritmos:
Material sobre listas encadeadas:
Material sobre Grafos:
Páginas
das turmas dos semestres anteriores.