Sumários das aulas práticas de ADA

1ª Aula

Introdução ao Linux

Estrutura de directorias. Sintaxe dos nomes de directorias e ficheiros. Os caracteres * e ?.
O interpretador de comandos (shell) bash.
Comandos para navegar e manipular a estrutura de directorias: cd, ls [-l], cp, mv, rm, mkdir, rmdir e pwd.
Comandos para trabalhar com disquetes MS-DOS: a suite mtools.
Comandos de documentação: man, info e help.
Gestão de processos: C-c, C-\, C-z e %.
Introdução ao editor GNU emacs.
Arranque dos PC's dos laboratórios em Linux, início e fim de uma sessão de trabalho, parar o Linux.

Introdução à linguagem C

Tipos simples. Declarações de variáveis. Introdução aos arrays em C. A pseudo-função sizeof.
Instruções: afectação, condicional, ciclos for e while, break, continue. Valores lógicos em C. Sequências de instruções. Blocos.
Definição de funçoes. O tipo void. As instruções return e chamada de função.

2ª Aula

Continuação da introdução à linguagem C

Strings, a sua representação em memória e sequências especiais de caracteres.
A função printf. Sequências de formatação.
Os arrays como parâmetros de funções.
O pré-processador. O comando #include.
Como compilar e executar programas em C.

Exercícios

Criar a directoria ada, mudar para lá, criar uma directoria lnº-aluno e mudar para lá.
Elaborar em C programas que escrevem no terminal:
1. Olá mundo.
2. 1 2 . . . 20
3. 1 2 ... 20
4. 10! e 20! (overflow)
  - versão recursiva e
  - versão iterativa
5. os primeiros 20 elementos da sucessão 0 1 1 2 3 5 8 13 ..., sem recorrer à recursividade e usando somente 2+1 variáveis (mais uma variável temporária)
6. ```
  1   2  ...   9  10
  2   4  ...  18  20
  .   .        .   .
  .   .        .   .
  .   .        .   .
  9  18  ...  81  90
 10  20  ...  90 100
```
7. ```
  1
  2   4
  .   .  .
  .   .    .
  .   .      .
  9  18  ...  81
 10  20  ...  90 100
```

3ª Aula

Tópicos de C

Estruturas, ou registos (struct): definição, declaração e inicialização, acesso aos campos.
Tipos enumerados (enum): definição, declaração e uso.
Definição de novos tipos com typedef.
Introdução aos apontadores: declaração, os operadores & e *. Acesso aos campos de uma estrutura através de um apontador para ela.
O qualificativo static em declarações globais e para funções.
Gestão de memória dinâmica. As funções malloc e free.
Compilação de programas com o código repartido por vários ficheiros.

Tópicos de Linux

Os comandos wget e lynx.
Redirecção da saída (output).

Exercícios

Exercícios sobre Árvores Pretas e Vermelhas, feitos no ficheiro apv-a3.c, no sítios assinalados por ... fazer .... (O código que completa o programa está nos ficheiros main-a3.c e apv.h, que não é necessário alterar.)

Implementar a rotação direita.
Completar a inserção de um elemento numa árvore preta e vermelha.
Fazer a função apv_mostra que mostra a estrutura de uma árvore preta e vermelha no écran da seguinte forma
<valor-na-raiz><p-ou-v> (<subárvore-esquerda>, <subárvore-direita>)
Se um nó não tem filhos, aparece só <valor-na-raiz><p-ou-v>.
Para a árvore cuja raiz tem chave 27 e é preta, cuja subárvore esquerda tem um único nó, preto, com chave 15, e cuja subárvore direita tem raiz preta, com chave 36, e um filho esquerdo vermelho com chave 29 a função escreve no écran
27p (15p, 36p (29v, ))
Fazer a função e_apv que devolve 1 se o argumento é uma árvore que satisfaz todas as propriedades das árvore pretas e vermelhas, e 0 no caso contrário. (Uma solução.)

4ª Aula

Finalização dos exercícios da aula anterior.

5ª Aula

Tópicos de C

Aritmética de apontadores.

Exercícios

Implementar as primitivas seguintes sobre tries cujas chaves são sequências não vazias de letras minúsculas

trie cria(void) - cria e devolve uma nova trie;
int procura(trie, char *) - devolve 1 ou 0 consoante a palavra existe ou não na trie;
trie insere(trie, char *) - insere uma palavra numa trie e devolve-a;
trie remove(trie, char *) - remove uma palavra de uma trie e devolve-a;
void destroi(trie) - liberta a memória ocupada por uma trie.

O tipo usado é dado por

  #define ALF_MIN 'a'                  /* menor elemento do alfabeto */
  #define ALF_MAX 'z'                  /* maior elemento do alfabeto */
  #define ALF_DIM (ALF_MAX - ALF_MIN + 1)    /* cardinal do alfabeto */

  typedef struct trie_dados *trie;

  struct trie_dados {
    int contem;
    trie filhos[ALF_DIM];
  };

6ª Aula

1. Calcular o grau mínimo de ramificação t para uma B-tree, num sistema em que o tamanho de um bloco de disco é 4KB. A informação contida na árvore diz respeito a modelos de automóveis e consiste em registos com os seguintes elementos: marca (20 caracteres no máximo), modelo (também 20 caracteres), cilindrada (em cm³), ano de introdução no mercado e ano de retirada do mercado.

2. Calcular o número máximo de elementos de uma B-tree de altura h, em função de t.

3. Calcular a complexidade do pior caso da pesquisa de um elemento numa B-tree, usando como medida o número de comparações efectuadas.

4. Desenhar a B-tree resultante de inserir, numa árvore inicialmente vazia,

os primeiros 11 múltiplos de 3, por ordem crescente, seguidos de
os restantes inteiros positivos menores que 33, por ordem decrescente.

5. Elaborar um algoritmo para encontrar o elemento de uma B-tree com a menor chave superior a uma chave dada.

7ª Aula

Tópicos de C

Entrada/saída (input/output)

de/para o terminal (stdin, stdout e stderr); e
sobre ficheiros.

Exercício

Implementar o TAD lista simplesmente ligada, em ficheiro, com primitivas para inserção, remoção e listagem de elementos (que podem ser inteiros).

8ª Aula

Continuação do exercício da aula anterior.

9ª Aula

1. Fazer um programa que lê duas strings (do stdin) e indica as posições de todas as ocorrências da segunda na primeira

usando pesquisa ingénua (naive string-matching);
usando o algoritmo de Rabin-Karp.

2. Alterar os programas do exercício anterior de modo a lerem o nome de um ficheiro e uma string, e copiarem, para o terminal, todas as linhas do ficheiro em que a string ocorre.

10ª Aula

Fazer um programa que conta as ocorrências de um padrão num ficheiro, e que copia, para o terminal, todas as linhas em que aparece, usando pesquisa com autómatos finitos, construídos recorrendo à função prefixo pi do algoritmo de Knuth-Morris-Pratt, e determinar a complexidade do algoritmo implementado.

Na construção do autómato, tem-se em conta a seguinte propriedade

delta(q, a) = delta(pi(q), a), se q = m ou P[q] <> a

onde delta representa a função de transição do autómato, m o comprimento do padrão P[0..m-1], q é um estado em {1, ..., m} e a um símbolo do alfabeto.

11ª Aula

Criar um programa que, dados um conjunto de localidades, as estradas que as unem e uma localidade origem, lista

as localidades que se alcançam directamente a partir da localidade origem;
seguidas das localidades que, para serem alcançadas a partir da localidade origem, obrigam à passagem por uma outra localidade;
seguidas daquelas que obrigam à passagem por duas outras localidades;
etc.

O programa lê os dados a partir da entrada padrão no seguinte formato:

número de localidades (V)
localidade₁
localidade₂
   .
   .
   .
localidade_V
número de estradas (E)
localidade₁₁ localidade₁₂
localidade₂₁ localidade₂₂
   .
   .
   .
localidade_E1 localidade_E2
localidade origem

12ª Aula

1. Concluir o programa da aula anterior.

2. Determinar a complexidade temporal do percurso em profundidade de um grafo representado através de listas de adjacências.

13ª Aula

1. Determinar os códigos de Huffman para o texto seguinte (e responder à pergunta):

Qual será o tamanho deste texto depois de comprimido?

2. Determinar o texto que, comprimido pelo algoritmo LZ77 (usando uma janela maior que o texto), deu origem a:

0 0 A 1 1 B 0 0 C 3 1 B 2 2 C.

3. Determinar o texto que, comprimido pelo algoritmo LZ78, deu origem a:

0a1a0r3r0g0h6h7

(o que é equivalente a "a1ar3rgh6h7").

4. Dúvidas.