Graduação em 

Ciência da Computação

<Estrutura de Dados>

 

  

Atividades 

Durante o período o aluno deverá desenvolver 3 trabalhos que consistem basicamente de implementações dos algoritmos vistos em sala de aula e que complementam a sua formação em termos de prática de programação e de aprendizado de uma linguagem de programação. Os trabalhos colaboram com as 3 avaliações escritas para compor as notas do aluno.

 

  

Atividade 1a: Conversão e avaliação de expressões aritméticas

* Ler uma expressão em notação infixa.

Ex: (2,5+1,5)^(5.1-0,6)

* Converter para notação posfixa

* Avaliar a expressão posfixa

Linguagens permitidas 

Os trabalhos podem ser desenvolvidos apenas nas seguintes linguagens de programação: C, Pascal, C++ e Java  

 

Apresentação dos trabalhos

Os trabalhos devem ser entregues na data determinada em formato de documento e podem eventualmente, a critério do professor, serem apresentados em laboratório na mesma data ou data posterior à entrega.

Os documentos devem ser "zipados" contendo todos os arquivos solicitados pelo professor, tais como: fonte, executável e relatório de resultados. O arquivo zipado deve ser entregue ao professor  via email ou via mídia apropriada (CD, disquete). No nome do arquivo zipado deve constar o nome e o código do aluno.

A pedido do professor, o aluno poderá ainda entregar uma cópia impressa do relatório de resultados até a data determinada.

Relatório de resultados

O relatório de resultados documenta o trabalho de implementação, apresentando desde a justificativa para a solução algorítmica empregada pelo aluno até os resultados obtidos por ele e as principais dificuldades encontradas. Ele deve ser suficientemente completo para permitir ao professor o pleno entendimento e avaliação do trabalho realizado pelo aluno. Dentre outros recursos, o aluno deve lançar mão de trechos de código fonte que expliquem determinadas rotinas, imagem de telas de execução, gráficos, impressão de arquivos de resultados, etc.

O formato do relatório de resultados pode ser baixado aqui.

 

 

 

  

Atividade 1b: Labirinto

* Ler um arquivo texto com a descrição de um labirinto

Exemplo 1:

11 8
1 5
1 1 1 1 0 1 1 1
1 1 1 0 1 0 1 1
1 0 0 0 1 1 0 1
1 0 1 1 1 1 0 1
1 0 0 1 1 1 0 1
1 0 1 0 0 1 0 1
1 0 1 1 0 1 0 1
1 0 1 0 1 1 0 1
1 0 1 0 1 1 0 0
1 0 1 0 0 1 1 1
1 1 1 1 1 1 1 1

Linha1: tamanho do labirinto (11 linhas e 8 colunas)

Linha2: coordenada de entrada no labirinto

Exemplo 2

* Encontra pelo menos um caminho, caso exista, entre a entrada e saída (passando só por 0´s, considerando vizinhança com 8 direções)

* Exibe as coordenadas que fazem parte do caminho encontrado

Ex: 1,5,2,6,3,7,4,7,5,7,6,7,7,7,8,7,9,7,9,8

* Pode ser empregado qualquer método para resolução.

Sugestões: Implementar um backtracking com auxílio de recursividade ou pilha.

Links úteis:

http://pt.wikipedia.org/wiki/Backtracking

http://www.inf.ufsc.br/~awangenh/Analise/Backtracking.html

 

  

Atividade 2:  (total de pontos =  3,0)

PARTE A:  Comparar a operação de busca em listas encadeadas e árvores binárias

* Total de pontos: 1,0 (bem implementado e funcional)

* implementar uma lista encadeada ordenada e uma árvore binária de busca

* ler um arquivo de strings no seguinte formato

Antes
escrever
Duna
que
mente
algumas
diretivas
2007
sem
tempo
para
nada.
Rotina
dias
amores
paixões
Acordar
cedo
horas

* Cada palavra lida deve ser inserida na lista e na árvore (não é para transferir de lista para árvore posteriormente)

* O processo de inserção deve contabilizar o número de comparações entre strings em ambas as estruturas

* O programa deve entrar no módulo de consulta no qual o usuário deve digitar várias palavras para serem buscadas em ambas as estruturas

* o processo de busca deve contabilizar o número de comparações entre strings necessárias para encontrar a chave ou descobrir que ela não está

* Após várias consultas deve ser exibido as estatísticas das duas estruturas

1) Lista ordenada
**Inserção:
comparações necessárias para inserir todas as strings: 99
** busca:
menor número de comparações ocorridas em uma busca: 99
média do número de comparações ocorridas em uma busca: 99,99
maior número de comparações ocorridas em uma busca: 99

2) Árvore binária de busca
**Inserção:
comparações necessárias para inserir todas as strings: 99
** busca:
menor número de comparações ocorridas em uma busca: 99
média do número de comparações ocorridas em uma busca: 99,99
maior número de comparações ocorridas em uma busca: 99

Outras mais que o aluno achar interessante

 
   

PARTE B:  Implementação de percursos em árvores binárias com procedimento VISITA genérico

* Total de pontos: 1,0 (bem implementado e funcional)

A operação VISITA pode ser passada como parâmetro para o procedimento de percurso

Percursos a serem implementados:

* Por ordem de visita

* Por nível
   

PARTE C (Matriz Custo)

* Total de pontos: 1,0 (bem implementado e funcional)

A matriz adjacência pode conter também informações sobre o custo associado a uma aresta. A figura seguir mostra um grafo e a matriz custo inicial com a notação ¥, simbolizando ausência de arestas (custo infinito).

A matriz custo mínimo de um grafo G considera, de todos os caminhos (de qualquer comprimento) possíveis entre dois vértices, aqueles que possuem menor custo associado.

É equivalente ao fechamento transitivo, mas não mostra apenas a presença ou não de caminho entre i e j (vértices de G), mas também o menor custo entre i e j.

Se entre dois vértices não existir caminho de comprimento algum (PATH[i][j]=0), a matriz custo mínimo deverá apresentar ¥ para aquela aresta (i,j).

Portanto a matriz custo mínimo é a matriz dos caminhos de menor custo, obtida a partir da matriz de custo inicial. (algoritmo a ser validado)

MatrizCustoMínimo (Cm) := min { Ci , Ci2, Ci3, ... Cin }

Cm := Ci // O(n2)
Para i=1,n
     Para j=1,n
          Se i <> j
               Para k=1, n
                    Cm(i,j) := min ( Cm(i,j) , Cm(i,k) + Cm( k, j ) // O(n3)
               Fim
          Fim
      Fim
Fim
 
   

PARTE ÚNICA (Árvore de Jogos)

* Total de pontos: 3,0 (apresentado em laboratório)

Implementar um jogo qualquer utilizando a estratégia MIN-MAX com cortes alfa e beta.

Quem optar por esta opção estará automaticamente selecionado para apresentar em laboratório e não precisará ter feito as partes A, B, C
   

PARTE EXTRA (Opcional)

Caso as implementações não sejam bem sucedidas, o aluno estará isento de apresentar e poderá compensar as perdas de pontos através de um relatório único (1,0 ponto) e dos exercícios que são passados em sala de aula (1,0 ponto)

 
   

Atividade 3:

3a) Escolher dois métodos de ordenação para comparação.

  • Bolha x Seleção direta
  • Rápida x Heap
  • Inserção Simples x Seleção Direta
  • Rápida x Shell
  • Shell x Heap

Método:

  1. Criar um arquivo de dados com bastante registros ou digitando dados através de um programa P1 ou ainda aproveitando arquivos previamente digitados. Exemplo: http://www.journals.uchicago.edu/AAS/cdrom/volume4/volume4/aj/v109/p1269/table.dat
  2. Criar um arquivo de índices a partir do arquivo de dados. Nesse passo deverá ser escrito um programa P2 que lê apenas os campos que são chaves do arquivo de dados e gera um novo arquivo (de índice) que tem o seguinte formato:

CCCCCCCCCC000001BBBBBBBBBB000002DDDDDDDDDD000003AAAAAAAAAA000004EEEEEEEEEE000005...

Onde CCC...C, BBB...B, etc são os valores das chaves na ordem original em que foram lidos do arquivo de dados. O número sequencial que vem a seguir é o índice do registro de dados no arquivo de dados. Diz-se que o sequencial "aponta" para o registro no arquivo de dados que contém os dados relativos à chave CCC...C, por exemplo.

No exemplo do link:

WW And    1989-Oct-17  06:15  47816.77159  .82267  0.78   +38.
é o terceiro registro do arquivo de dados.
Um registro de índice (armazenado no arquivo de índice) que aponta para esse registro de dados seria:
1989-Oct-17000003
tomando o segundo campo como chave. O 000003 se refere à posição do registro de dados apontado por esse registro de índice.
O arquivo de índice vai ser ordenado e indiretamente o arquivo de dados. 
O arquivo de dados não é alterado.
  1. Ordenar o arquivo de índices usando 2 métodos, extraindo as seguintes medidas:

Número de comparações realizadas

Número de trocas

Tempo de execução

Percorrendo-se os índices no arquivo de índices ordenado podemos "enxergar" o arquivo de dados ordenados pelo campo chave escolhido.

FATOR_10: Os métodos podem ser implementados na versão original ou melhorados. Assim a comparação pode considerar até 2 implementações diferentes de cada método.

FATOR_10: As ordenações devem ser feitas diretamente nos índices em disco. Ou seja, devem ser lidos para a memória apenas aqueles sendo comparados para posteriormente serem re-escritos.

Para isso, estude as funções em C: fseek, fwrite, fread: I-ésimo registro: fseek(fd, i*TAM_DE_REGISTRO, 0) // vide documentação C/C++
 

  1. Comparar os métodos entre si, considerando a complexidade conhecida na literatura:

Utilize gráficos de desempenho (Exemplo: http://www.lcc.ufrn.br/~danield/dim0303/atividade1/graf.htm) . Para isso, é necessário ir aumentando o tamanho do arquivo de índice gradativamente e medindo o desempenho.

3b) Escolher um método de busca para implementação

  • Árvore AVL
  • Tabela de dispersão
  • Árvores rubro-negras

Usar a metodologia descrita anteriormente. Só não é preciso comparar com um segundo método. Apenas implementar e verificar o número de comparações para um número gradativamente maior de dados.

FATOR_10: Os métodos podem ser implementados na versão original ou melhorados. Assim a comparação pode considerar até 2 implementações diferentes.

FATOR_10: As buscas devem ser feitas diretamente nos índices em disco. Ou seja, devem ser lidos para a memória apenas aqueles sendo comparados.

Para isso, estude as funções em C: fseek, fread. I-ésimo registro: fseek(fd, i*TAM_DE_REGISTRO, 0) // vide documentação C/C++
 

3c) Escolher um jogo para implementação do algoritmo min-max com poda

  • Captura
  • ????

FATOR_10: Algoritmo com poda.