AED 2004/2005

Aulas 1 a 3: Apresentação; Introdução ao C

Apresentação da disciplina. Apresentação do programa e do método de avaliação.

Conceitos básicos de C

Instrodução ao ANSI C. Exemplo de programa: hello world. Tipos básicos e aspectos relacionados. Declarações de constantes e variáveis.

Constantes e Operadores

Literais em C. Caracteres e cadeias de caracteres: organização em memória. Operadores aritméticos, lógicos e relacionais. Operadores de atribuição. Exemplos. Discussão de problemas.

Aulas 4 a 6: Controlo de Fluxo; Funções; Programas

Revisões sobre tipos básicos e matéria associada. Revisões sobre operadores. Operador condicional. Ordem de execução. Conversão de tipos implícita e explícita. Discussão de aspectos associados. Controlo de fluxo em programas: instruções e blocos. if e if/else.

Controlo de execução em C: ciclos while, for, do/while. Exemplos. Comparação entre ciclos while e ciclos for. Interrupção do desenrolar normal de um ciclo: break e continue. Análise de comportamento nos diferentes ciclos. Funções em C: estrutura geral de uma função. Argumentos e retorno. Exemplos simples: função pop para uma pilha de inteiros.

Funções e módulos. Compilação separada. Utilização do pré-processador de C. Visibilidade de variáveis e funções. O uso de static. Exemplos de funções e módulos. Exemplos de funções simples: leitura interactiva de caracteres. Aplicação de switch.

Aulas 7 a 11: Ponteiros e Gestão de Memória

Introdução ao uso de ponteiros em C: ponteiros e endereços; ponteiros e vectores/tabelas. Notação (introdução ao uso dos operadores * e &). Vectores de caracteres. Organização da memória. Apresentação e discussão de exemplos.

Ponteiros e vectores: semelhanças e diferenças. Aritmética de ponteiros. Conversão de ponteiros. Passagem de ponteiros e vectores como argumentos de funções. Apresentação e discussão de exemplos.

Matrizes em C. Acesso multidimensional. Diferenças entre matrizes, vectores e ponteiros: organização da memória. Passagem de argumentos por referência. Gestão de memória dinâmica utilizando malloc e free. Apresentação e discussão de exemplos.

Apresentação e discussão de exemplo prático de gestão de memória. Pilha de strings.

Ponteiros para funções. Apresentação e discussão de exemplo de utilização: algoritmo de procura binária parametrizado com comparador.

Aulas 12 a 15: Estruturas em C

Tipos estruturados em C. Acesso a campos de estruturas. Ponteiros para estruturas; sintaxes de acesso alternativas. Estruturas e vectores. Apresentação e discussão de exemplos.

Estruturas auto-referenciadas. Apresentação e discussão de exemplos: pilha de dimensão arbitrária (exemplo de cliente). Revisões sobre ponteiros para funções. Definição de tipos utilizando typedef.

Apresentação de exemplo de utilização de estruturas em C. Lista duplamente ligada; funções de iteração parametrizadas; funções de inserção e remoção nos extremos: "push" e "pop". Considerações sobre alguns problemas da solução. O uso de assert.

Apresentação e discussão de exemplo de aplicação de estruturas em C: construção de uma tabela de símbolos com recurso a função de dispersão; ênfase nos aspectos de organização e gestão de memória, assim como na simplicidade relativa dos acessos aos dados.

Aula 16: Argumentos Variáveis; Bibliotecas

Argumentos variáveis: stdarg. Apresentação de exemplo e discussão das condições de utilização. Bibliotecas em C. Funções para manipulação de ficheiros.

Aula 17: Problemas Comuns em C

Problemas comuns na programação em C. Apresentação e discussão de exemplos.

Aula 18: Aspectos de Desempenho

Aspectos de desempenho de programas em C: apresentação de programa ilustrativo dos problemas que afectam o desempenho. Apresentação e discussão de algumas alternativas de solução.

Aulas 19 a 24: Estruturas de Dados Elementares

Introdução às estruturas de dados. Estruturas de dados elementares: vectores, listas (simplesmente e duplamente ligadas). Uso de sentinelas. Apresentação e discussão de exemplos.

Vectores e listas. Algoritmos e dependência da estrutura de dados. Apresentação de ordenação por inserção (isort) com vector e lista ligada sem sentinela. Discussão de aspectos relacionados com as soluções.

Discussão de aspectos relacionados com o uso de sentinelas numa versão de ordenação por inserção (isort) numa lista ligada. Árvores binárias completas, equilibradas e completamente preenchidas: organização de elementos. Amontoados: propriedades e organização de dados. Algoritmos de fixUp e fixDown. Inserção e remoção de elementos em/de um amontoado. Discussão de aspectos de eficiência sem considerar implementações concretas.

Amontoados: estrutura de dados e representação em memória. Implementação com vector: algoritmos fixUp e fixDown. Algoritmo de ordenação de vectores com base em amontoados (heapsort). Discussão de aspectos de eficiência.

Filas de prioridades. Impacto da implementação na eficiência: implementação com amontoado e com vector. Discussão. Algoritmo de ordenação baseado em fila de prioridade (PQsort). Introdução aos tipos de dados abstractos (ADTs).

(na aula 21 foram feitas revisões para o primeiro teste)

Aula 25: Introdução à Análise de Algoritmos

Introdução à análise de algoritmos. Crescimento de funções. Notação assimptótica ("notação O"). Comportamentos em várias situações: média, pior caso e melhor caso. Recorrências. Apresentação e discussão de exemplos.

Aula 26: Tipos de Dados Abstractos (ADTs)

Tipos de dados abstractos: interface, implementação, cliente, item. Motivação para o uso de ADTs. Exemplos de ADTs: pilha; fila de prioridades; fila simples (FIFO) com base em vector e em lista ligada. Exemplos de clientes.

Aula 27: ADTs de 1ª ordem

Tipos de dados de primeira ordem: motivação. Exemplo de tipo de dados de 1ª ordem: números complexos. Reescrita como ADT de 1ª ordem. Justificação para o procedimento. Exemplos de ADTs de primeira ordem: FIFO; fila de prioridade com base em amontoado. Ordenação com base em fila de prioridade.

Aulas 28 a 32 Árvores Binárias

Anatomia de uma árvore: nós internos e externos; nós vs. folhas. "Rooted trees" vs. "free trees". Árvores genéricas: exemplos. Introdução às árvores binárias: definição de árvore binária; implementação vs. conceito. Estruturas de suporte à implementação de árvores binárias. Algoritmos básicos com árvores: contagem de nós e cálculo da altura de uma árvore. Travessias recursivas: "pre-order", "in-order", "post-order".

Travessias: algoritmos não recursivos: "pre-order" e "level-order". Discussão: algoritmos recursivos vs. iterativos. Árvores binárias de procura (BSTs - binary search trees). Métodos de construção, de procura e de inserção. Operações de rotação à esquerda e à direita. ADT para tabela de símbolos: implementação baseada em BSTs. Apresentação e discussão de implementações dos algoritmos de inserção e procura.

Algoritmos sobre árvores binárias de procura (BSTs): selecção da k-ésima menor chave; partição pela k-ésima menor chave; inserção na raiz; junção de árvores; remoção de um elemento. Discussão de aspectos de organização e eficiência; discussão de aspectos relacionados com os processos recursivos.

Árvores equilibradas. Problemas de eficiência das BSTs. Discussão de possíveis soluções: balanceamento explícito e recurso à aleatorização. Árvores 2-3-4 e árvores red-black. Método de construção. Exemplos. Algoritmo de inserção para árvores red-black. Apresentação de exemplo.

Aulas 33 a 34 Algoritmos de Ordenação

Noção de estabilidade.

Algoritmos elementares

Algoritmos apresentados (para vectores): selection sort, bubble sort, insert sort. Discussão de aspectos de eficiência. Exemplos. Shell sort. Noção de h-sortedness. Discussão da influência da sequência h na eficiência do algoritmo. Comparação do Shell sort com o insert sort simples. Apresentação e discussão de exemplos de aplicação. Avaliação experimental dos algoritmos de ordenação elementar: insert sort, selection sort e bubble sort. Avaliação experimental do algoritmo Shell sort. Estabilidade dos algoritmos.

Algoritmos baseados em propriedades das chaves

Ordenação por contagem: counting sort. Princípio de funcionamento; estabilidade. Apresentação de exemplo e discussão de aspectos de eficiência.

Algoritmos eficientes

Introdução aos algoritmos de ordenação eficientes: heapsort (revisões: princípio de funcionamento do algoritmo; aspectos de implementação; aspectos de eficiência); princípios básicos do funcionamento do quicksort. Função de partição: influência da escolha do pivot: discussão e exemplos de alternativas. Avaliação experimental comparativa do quicksort e do heapsort.

Ordenação por fusão: mergesort. Operação de fusão de vectores ordenados. Fusão abstracta in-place. Versões top-down e bottom-up do algoritmo mergesort. Requisitos para a estabilidade da ordenação. Apresentação de exemplos de aplicação. Discussão de aspectos de eficiência em espaço e tempo. Mergesort sem cópia. Avaliação experimental do mergesort.

Uso de cutoff: insert sort para vectores pequenos. Discussão.