Análise e Desenho de Algoritmos

Sumários das aulas teóricas:

1. 15/2 - Apresentação da Disciplina, Método de avaliação e Datas das avaliações
2. 22/2 - Análise de Complexidade temporal e Espacial. Tipo Abstracto de Dados Fila
3. 1/3 - Tad árvores pretas e vermelhas (RBT), propriedades das rbts, operações: criar, pesquisa,inserir.
4. 8/3 - Tad árvores pretas e vermelhas (RBT): estrutura de dados em C para representar uma rbt, implementação da operação de inserção. Remoção na rbt.
   
5. 15/3 - Remoção na Rbt. Tad Trie: pesquisa, inserção e remoçãoç estrutura de dados para representar uma trie em C.
6. 29/3 - Tad Trie. Tad Btree: propriedades da Btree operação de pesquisa e inserção, representação de uma btree em C.
   

Exercício 1

• Desenvolva, em C, um programa 'HelloWorld'.
• Crie uma função int impar(int x), que verifica se o número inteiro dado como parâmentro é ímpar. Utilize a seguinte função main() para testar:

       int main()
       {
         int i = 3;

         if (impar(i)) {
           printf("%d é um número ímpar.\n", i);
         }
         else {
           printf("%d não é um número ímpar.\n", i);
         }
       }

• Crie um procedimento void primos(int x), que mostra todos os números primos de 1 a x.

1. Altere a disciplina da fila, que é fifo (primeiro a entrar é o primeiro a sair) para lifo (o primeiro a entrar é o último a sair).
2. Implemente a operação remove(int valor), que deve remover o valor indicado da fila.
3. Implemente a operação insere_apos(int valor1, int valor2), que deve inserir o valor1 após o valor2 na fila.
4. Reimplemente o TAD fila usando os seguintes tipos para lista, fila:

   struct lista{int val[34];}
   struct fila {int cabeca, cauda; struct lista l;};
   

   Implementando a nova operação int fila_cheia(fila f) que retorna True (?o que é True em C?) quando a fila tem 34 valores.

5. Reimplemente o TAD fila com as operações remove(int valor) e insere_apos(int valor1, int valor2), usando o seguinte tipo para lista:

   struct lista{ int val;
     lista *prox;
     lista *ant;};
   

6. Para cada implementação do tipo fila indique a complexidade (função do número de elementos na fila) da sua implementação das operações sobre o tipo fila.
   

Exercício 3

Exercício 3.2

1. (para fazer numa folha de papel)
   Numa rbt vazia, insira os valores 4, 8, 2, 14, 11, 23, 30, 1 e 10.
   


2. Na rbt anterior, remova os valores 11, 4 e 23.


3. Implemente a função struct rbt *pesquisa(struct rbt *arv, int val), que devolve o nó da rbt cujo valor é val.


4. Implemente a função struct rbt *sucessor(struct rbt *arv, int val), que devolve o nó sucessor do nó cujo valor é val.

Exercício 4

1. Desenhe (em papel) a B-Tree de grau minimo 3 que se obtem após a inserção de cada elemento da seguinte sequência de chaves:
   8, 16, 24, 32, 64, 1, 4, 7, 3, 25, 28, 31, 27, 40, 41, 42, 43, 44, 45, 47, 49, 46, 50.
2. Defina a operação pesquisa que dada uma Btree e uma chave devolve true sse a chave está na Btree.
3. Defina a operação máximo que dada uma Btree devolve a maior chave na Btree.
4. Defina a operação num_chaves que dada uma Btree devolve o número de chaves na Btree.
5.  Defina a operação num_nos que dada uma Btree devolve o número de nos na Btree.
6. Altere o tipo Btree e a implementação das operações de forma a que as chaves sejam strings em vez de inteiros.

Exercício 5

Considere o TAD trie e a implementação dada na teórica (ficheiro .tgz com a base):

1. Usando papel e lápis, insira os seguintes valores numa trie: "abc", "abcde", "efg", "efgaa" e "bfg", pela ordem indicada. Indique para cada inserção qual a trie obtida.
   
2. Usando o papel da alínea anterior, remova os seguintes valores da trie: "abc" e "efgaa", pela ordem indicada. indique para cada remoção qual a trie obtida.
   
3. Implemente a operação remove que dada uma chave e uma trie remove a chave da trie.

   Teste a sua função com as remoções da alínea 2.

4. Implemente a função mínima que devolve a menor chave na trie.

   Teste a sua função com as tries da alínea 1.

5. Implemente a operação pesquisa, que dada uma chave devolve true se ela está na trie, false senão.

   Teste a sua função para as diferentes tries da alínea 1.

6. Implemente a operação próxima, que dada uma chave devolve a próxima chave na trie (ordem alfabética).
   
7. Suponha que além de palavras gostaria de guardar num dicionário as linhas onde as palavras ocorrem.
   
   1. Altere o tipo trie, e a função insere para inserir uma chave e a linha onde ocorre (note que uma palavra pode ocorrer em várias linhas).
   2. Altere a função lista_ord para listar as palavras por ordem alfabética e as linhas onde a palavra ocorre.
   3. Defina a operação palavrasNaLinha que dada uma linha lista todas as palavras que ocorrem na linha.

    

1. Defina um função em C que implemente o algoritmo ingénuo para verificação de coincidência de padrões (naive search).
2. Faça um programa que indique quantas vezes e em que shifts ocorre um padrão p na string t.
   

   ex:

   p=''123123''

   t=''123456712123123123124123123''

   p ocorre 3 vezes em t em: 9,12 e 21.
   
   

3. Defina uma função em C que implemente o algoritmo Rabin-Karp.
   
   
4. Desenhe os autómatos finitos que reconhecem os seguintes padrões (e construa as funções de transição), para o vocabulário {a,b,c,d}:
1. p=''aaaaa''
2. p=''ababa''
3. p=''abcddcba''
   
   
5. Defina uma função em C que dado um padrão (uma string), e um vocabulário constrói a função de transição do autómato finito que reconhece o padrão.
   
   
6. Defina em C uma função que dado um padrão e um texto (duas strings) usa um autómato finito para encontrar o shift do padrão no texto.

Exercício 7

1. Para o grafo G1 indique qual é o resultado da pesquisa em largura (bfs), iniciada no vértice 1. i.e quais as anotações em cada nó do grafo após a pesquisa. Desenhe a árvore em largura.
2. Para o grafo G2 indique quais as anotações nos nós feitas pela pesquisa em profundidade (dfs). Desenhe as árvores em profundidade.
3. Usando a implementação do tad grafos dada na teórica (ficheiros grafo.c, grafo.h e grafosmain.c - grafos.tgz) e pesquisa em largura (bfs)
1. Defina a função caminho2 que dados um grafo e dois vertices lista o menor caminho entre os dois vertices (os vertices do caminho) e a distância minima entre os dois vertices.
2. Defina a função caminho3 que dados um grafo e três vertices (u, v, e x) lista o menor caminho entre u e v que passa por x.
   
   
4. Usando as estruturas de dados e as funções definidas para representar grafos dadas na teorica:
   1. Implemente a função pesquisa em profundidade (dfs) dada nas aulas (acrescente int ti e int tf a struct vertice para poder anotar os tempos de visita de cada nó).
   2. Defina a função ordena vertices que dado um grafo directo sem ciclos, usando a sua função (dfs), lista uma linearização do grafo (ordenação topologica).