Nota: a bibliografia para cada aula é dada no formato [Número, Sec. ...; Número, Sec. ...; ...]. Cada número refere-se a um dos livros recomendados para a cadeira, de acordo com a numeração apresentada na página principal da cadeira. Os pontos-e-vírgula separam livros diferentes. A informação a seguir a um número, separada por uma vírgula, identifica as secções ou capítulos do livro que foram abordados na aula.
Em cada capítulo de [3] abordado nas aulas os alunos devem tentar resolver todos os exercícios.
1a aula teórica, 7/3/01. Apresentação dos
objectivos da cadeira, programa, bibliografia, avaliação
e informações gerais.
2a aula teórica, 12/3/01. Introdução genérica
à linguagem C. Programação em ambiente UNIX. Exemplos
preliminares: a função factorial, recursiva e
iterativa. Noção de estado. Quadros de emulação.
Variáveis, constantes, expressões, comandos, tipos de dados:
uma panorâmica. Funções e bibliotecas.
As funções main() e printf(). (Bibliografia: [2,
Cap. 1; 3, Caps. 0 e 1; 11]).
3a aula teórica, 13/3/01. Estrutura geral de um programa
em C. Descrição sumária de algumas bibliotecas: stdio.h,
string.h, math.h. Criação de bibliotecas (exemplo: biblioteca
factlib.h
com a função factorial iterativa da aula anterior). Programação
em C em ambiente UNIX: compilação separada de ficheiros.
Constantes. Tipos de dados básicos: inteiros (int, short int, long
int), reais (float, double), caracteres (char), enumerados e vazio (void).
(Bibliografia: [2, Caps. 1, 2, Ap. B; 3, Caps. 0-2; 11]).
4a aula teórica, 14/3/01. A função printf:
caracteres de conversão %d, %u, %c, %f, %e e %%; diversos exemplos
de formatação de output de reais. A função
scanf(): introdução. Expressões aritméticas
e lógicas. Expressões lógicas (continuação):
operadores lógicos. Operadores bit-a-bit. (Bibliografia:
[2,
Caps. 1, 2, 7; 3, Caps. 1-2, 6-7; 11]).
5a aula teórica, 19/3/01. A função scanf;
leitura e escrita de strings; tipo vector: formas de declaração
e inicialização, o caso das strings; tipos struct e typedef;
atribuições especiais e exemplo strlen.
6a aula teórica, 20/3/01. Passagem de parâmetros
para funções; exemplo: a função troca.
Tipo estruturado ponteiro; relacionamento entre vectores e ponteiros; aritmética
de ponteiros.
7a aula teórica, 21/3/01. Aritmética de ponteiros
e relacionamento entre vectores e ponteiros: a função strcpy.
Comandos de composicao iterativa: for e do-while; exemplificação
com a função strlen.
8a aula teórica, 26/3/01. A função itoa
e apresentação breve da tabela ASCII. Alternativas encadeadas
usando if-else-if. Exemplo: o algoritmo de pesquisa binária.
9a aula teórica, 27/3/01. Expressões condicionais
(exp1 ? exp2 : exp3), exemplos e comparação com o if-else.
O comando switch de alternativa generalizada e exemplo que lê caracteres
do teclado e conta algarismos, brancos e outros. Alguns comentários
complementares sobre estruturas, usando o exemplo da computação
gráfica (struct ponto).
--- 10a aula teórica, 28/3/01. Cancelada. ---
10a aula teórica, 2/4/01. "Macros": exemplos de operações
simples implementadas como macros em vez de funções; alguns
cuidados a ter com a definição de macros. Organização
de programas por camadas e centrada nos tipos de dados. Exemplo: calculadora
de expressões aritméticas em notação polaca,
utilizando uma pilha. Ficheiro pilha.h, com declaração do
nome do tipo de dados pilha (incompleta) e declaração dos
tipos das operações void nova(pilha *), void sobrepoe(pilha
*), void retira(pilha *) e double topo(pilha *). Ficheiro
polcalc.c,
com função main que implementa o algoritmo descrito na aula
anterior, que utiliza o ficheiro pilha.h, e que lê a expressão
a avaliar a partir da linha de comando, como a seguir:
> polcalc <expressão>
Implementação do tipo de dados pilha por meio de uma estrutura constituída por um vector de reais e de um inteiro, completando o ficheiro pilha.h com as definições seguintes:
#define MAXP 100
typedef struct {int t ; double v[MAXP]
; } pilha ;
Implementação das operações do tipo de dados pilha: o ficheiro pilha.c. Algumas considerações acerca de tratamento de erros da pilha: underflow e overflow. Fazer como exercício em casa: (1) nova versão deste programa, em que as operações da pilha são definidas por macros; (2) nova versão deste programa, em que as expressões podem ser constituídas por operandos com mais do que um dígito, sendo os operandos separados por ponto-e-vírgula; além disso os operandos podem ser escritos em notação de vírgula fixa, com ponto decimal, como no exemplo seguinte, que representa a expressão aritmética (12.3+5.4)*(5.1-65.9):
> polcalc 12.3;5.4;+5.1;65.9;-*
(3) nova versão deste programa (novamente com as expressões
simplificadas em que os operandos são constituídos por um
só dígito), em que se verifica se a sintaxe da expressão
está correcta (sugestão: utilize uma nova versão das
operações do tipo de dados pilha em que as operações
retornam códigos de erro que permitem saber no programa principal
se houve underflow ou overflow). (Bibliografia: [2,
Sec. 4.11; 5, Cap. 1]).
11a aula teórica, 3/4/01. Variáveis externas.
Variáveis "static": exemplo de gerador de números pseudo-aleatórios.
Declarações de variáveis constantes. Exemplos: size_t
strlen (const char *s); double topo (const pilha *p) (operação
que lê o topo de uma pilha, vista na aula anterior). Ficheiros: abertura
e fecho de ficheiros, escrita e leitura. Os ficheiros stdin, stdout e stderr.
Alguns comentários acerca de tratamento de erros em programas. O
comando exit(expr). (Bibliografia: [2, Caps. 4, 2, 7]).
12a aula teórica, 4/4/01. Análise de eficiência
do algoritmo de ordenação por inserção directa.
Pior e melhor caso. (Bibliografia:
[1, Secs. 1.1 e 1.2; 5, Cap.
1]).
13a aula teórica, 9/4/01. O algoritmo de pesquisa linear:
melhor e pior caso; análise detalhada do caso médio. (Bibliografia:
[1,
5]).
14a aula teórica, 10/4/01. Definição das
relações "assintoticamente menor ou igual" e "mesmo comportamento
assintótico; exemplos e propriedades. (Bibliografia:
[1,
5]).
--- FÉRIAS DA PÁSCOA ---
15a aula teórica, 17/4/01. Mais propriedades das relações
de comparação assintótica: reflexividade e transitividade
de menor-ou-igual; simetria da equivalência assintótica. De
volta ao algoritmo da pesquisa linear. Cálculo da divisão
da dimensão do vector a cada nova iteração, nos casos
em que o número de elementos a pesquisar é par e naqueles
em que é ímpar. Obtenção de expressão
de recorrência para o número de iterações e
sua resolução no caso em que a dimensão do vector
é uma potência de 2. Caso geral: expressões de recorrência
para um minorante e um majorante do número de iterações.
(Bibliografia:
[1, 5]).
16a aula teórica, 18/4/2001. Análise de eficiência
do algoritmo de pesquisa binária. Análise da divisão
do vector a pesquisar quando a dimensão é par. Cálculo
da eficiência no caso em que a dimensão é uma
potência de 2 (primeiro exemplo de uma sucessão definida por
recorrência). Análise da divisão do vector quando a
dimensão é ímpar. Propriedades algébricas das
operações de arredondamento. Cálculo da eficiência
do algoritmo no caso geral. (Bibliografia: [1, 5]).
17a aula teórica, 23/4/2001. O algoritmo recursivo de
ordenação por fusão binária (merge-sort). Descrição
geral do algoritmo. Análise assintótica abreviada da função
merge, em função da dimensão n do vector. Expressão
de recorrência para o tempo de execução do merge-sort.
Majorante (Tmax(n)) e minorante (Tmin(n)) do tempo de execução.
Obtenção de expressão exacta para o majorante, através
da expansão da definição por recorrência de
Tmax(n) e recorrendo às leis algébricas dos arredondamentos
(exercício: obtenha a expressão exacta para Tmin).
(Bibliografia: [1, 5]).
18a aula teórica, 24/4/2001. Cálculo do majorante
assintótico (n lg n) para a fusão binária a partir
da expressão exacta obtida na aula anterior (exercício: mostrar
que n ln n é também um minorante assintótico) e obtenção
do tempo assintótico exacto (n ln n). Dois outros exemplos de obtenção
de expressões exactas para sucessões definidas por recorrência:
T(n)=3T(n/2)*n, com n/2 arredondado para cima, e T(n)=3T(n/4)+n, com n/4
arredondado para baixo. (Bibliografia: [1,5]).
19a aula teórica, 30/4/01. Teorema fundamental ("Teorema
Master"); exemplos de aplicação de cada um dos três
casos do teorema: T(n) = 3T(n/2)+n (caso 1, com arredondamento para cima);
Tmin(n)=2Tmin(n/2)+an+b (caso 2 - tirado do merge-sort -
com arredondamento para baixo); e T(n)=3T(n/4)+n (caso 3, com arredondamento
para baixo). Verificação da condição de regularidade
de f(n) quando a=b=2 e f(n)=n^2, para aplicar o caso 3 do Teorema Fundamental,
com arredondamento de n/b respectivamente para baixo e para cima.
Teorema 1. Se a condição de regularidade se verifica então
a condição a seguir é verdadeira: Existe um número
real positivo epsilon tal que f(n) cresce assintoticamente pelo menos tão
depressa como n^((log_b a)+epsilon). (Bibliografia: [1, 5]).
20a aula teórica, 2/5/01. Contra-exemplo de que o recíproco
do Teorema 1 não se verifica. Exemplos aos quais o Teorema Fundamental
não se aplica: (i) a=b=2, com f(n)=n lg n; (ii) T(n)=n+(n-1) para
n maior do que 0, com T(0)=1 [resolução imediata por expansão
da recorrência]; T(n)=2T(n/2 + 17) + n, com n/2 arredondado para
baixo, para n maior do que 34, com T(34)=K [resolução por
substituição, fazendo S(n)=T(n+34), calculando uma expressão
de recorrência para S(n) e em seguida aplicando o Teorema Fundamental].
Discussão geral acerca de algoritmos de divisão-e-conquista
e da utilização do Teorema Fundamental para calcular os respectivos
tempos de execução. Breve discussão acerca do espaço
de memória ocupado pelo merge-sort. (Bibliografia: [1, 5]).
21a aula teórica, 7/5/2001. Ainda o espaço ocupado
pelo Mergesort: Obtenção da expressão de recorrência
supondo q a função Merge não ocupa espaço,
e solução pelo Teorema Fundamental (lg n). Observação
de que, ao contrário de um algoritmo iterativo,
um algoritmo recursivo ocupa sempre espaço. Árvores binárias.
Definição básica. Posição de um nó,
representação de vectores como árvores. Níveis
e profundidade. Relação entre o número de nós
de uma árvore e a sua profundidade. Árvores cheias e completas.
(Bibliografia: [5]).
22a aula teórica, 8/5/2001. Heaps, a função
fixheap(), o algoritmo de ordenação Heapsort. (Bibliografia:
[5]).
23a aula teórica, 9/5/2001. Análise da eficiência
do algoritmo Heapsort. O algoritmo de ordenação Quicksort,
com uma função split() que apenas utiliza uma variável
de progresso (versão do livro da Sara Baase). (Bibliografia:
[4,6]).
24a aula teórica, 14/5/2001. Análise de eficiência
do algoritmo de ordenação Quicksort: tempo e espaço
no pior caso e quando o vector é dividido por um factor constante.
Árvores de decisão e obtenção do minorante
assintóptico do número de comparações no pior
caso. (Bibliografia: [1, 5]).
25a aula teórica, 15/5/2001. Aula de apoio ao projecto:
descrição do enunciado e seus objectivos. Apresentação
informal do neurónio biológico e do artificial e de redes
neuronais. Cálculo da activação de neurónios.
26a aula teórica, 16/5/2001. Ordenação
por contagem e digito-a-digito: counting-sort e radix-sort. Análise
da sua eficiência. (Bibliografia: [1,5]). Gestão dinâmica
de memória em C: as funções malloc() e calloc(). Exemplo:
pilhas de inteiros. (Bibliografia: [2,3]).
27a aula teórica, 21/5/2001. Grafos: motivação
e definição de grafos orientados e não orientados.
Caminhos e circuitos e definição de grafos cíclicos
e acíclicos. Definição de matriz de adjacência
e sua utilização para determinar se um grafo é ciclico.
28a aula teórica, 22/5/2001. Implementações
de grafos: representação directa da matriz de adjacencia
(adequada apenas para grafos não esparsos) e por representação
apenas das arestas existentes: com um vector de ponteiros para listas encadeadas.
Funções sucessor e antecessor e implementação
dos grafos recorrendo as estas funções (Bibliografia:
[4]).
29a aula teórica, 23/5/2001. Filas de espera: motivação
e implementação vectorial (com ocupação circular
do vector) e dinâmica (Bibliografia: [4]).
30a aula teórica, 28/5/2001. Conclusão da implementação
dinâmica das filas de espera. Travessias de grafos: motivação
e exemplos de travessia em largura e em implementação
recursiva da travessia em profundidade e iterativa (com uma fila auxiliar)
da travessia em largura. Filas de prioridade: motivação (Bibliografia:
[4]).
32a aula teórica, 4/6/2001. Implementação
das funções insere e retira máximo em árvores
de pesquisa e análise da sua eficiência. Determinação
do minorante assintótico para o tempo de construção
de uma árvore de pesquisa. Definição de árvores
equilibradas e prova de que numa árvore equilibrada a profundidade
é assintoticamente proporcional ao logaritmo do número de
nós (Bibliografia: [4, 7]).
33a aula teórica, 05/6/2001. Explicação
do algoritmo de inserção em árvores equilibradas de
pesquisa: desiquilíbrios LL e LR e sua correcção.
Implementação do algoritmo (Bibliografia: [4, 7]).
FIM