Sumários Aulas Teóricas

17/9/2008, 11:00-12:00

Apresentação do docente e da disciplina. Método de Avaliação. Programa e bibliografia recomendada.

19/9/2008, 14:00-15:00

Motivação para o estudo dos algoritmos. Conceito de correcção de um algoritmo. Noção de invariante de ciclo. Exemplos.

24/9/2008, 11:00-12:00

Continuação da aula anterior: exemplos de invariantes de programas. Introdução ao estudo da análise de tempo de execução dos algoritmos.

26/9/2008, 14:00-15:00

Exemplos de análise do tempo de execução de algoritmos com ciclos. Análise de melhor caso, pior caso, e caso médio. Introdução à notação assimptótica para a variação do tempo de execução com a dimensão do input.

1/10/2008, 11:00-12:00

Conclusão do estudo da notação assimptótica. Caso de estudo: algoritmo "insertion sort". Análise de correcção. Análise temporal de melhor caso.

3/10/2008, 14:00-15:00

Conclusão do estudo do algoritmo "insertion sort": análise de pior caso. Caso de estudo: algoritmo "merge sort". Análise da função de fusão de sequências ordenadas. Introdução ao estudo das equações de recorrência.

8/10/2008, 11:00-12:00

Resolução de recorrências. Método da substituição. Análise da árvore de recursão do algoritmo "merge sort". Prova pelo método da substituição do tempo de execução N lg N. Caso de estudo: algoritmo "quick sort". Estudo do tempo de execução da função de partição.

10/10/2008, 14:00-15:00

Conclusão do estudo do algoritmo "quick sort": análise de pior caso e melhor caso. Breve referência à análise de caso médio. Algoritmo "quick sort" com alietoriedade.

15/10/2008, 11:00-12:00

Algoritmos de ordenação com base em comparações. Análise por contagem de comparações. Árvores de decisão e traços de execução. Teorema do limite inferior para o tempo de execução no pior caso de um algoritmo de ordenação com base em comparações.

17/10/2008, 14:00-15:00

Algoritmos de ordenação de tempo linear. Algoritmo "counting sort". Análise do tempo de execução. Propriedade de estabilidade de um algoritmo de ordenação. Algoritmo de ordenação "radix sort".

22/10/2008, 11:00-12:00

Breve referência à necessidade de utilização de técnicas amortizadas para a análise do tempo de execução de sequências de operações sobre estruturas de dados. Análise agregada de sequências de operações. Exemplos: "stack" com operação "multipop"; sequência de operações de inserção de elementos em árvores binárias de pesquisa.

Introdução do segundo capítulo do programa: conceitos básicos sobre grafos e tipos de grafos.

24/10/2008, 14:00-15:00

Representação de grafos em computador: matrizes de adjacências e listas de adjacências. Discussão. Travessia / pesquisa de grafos. Algoritmo de travessia em largura.

29/10/2008, 11:00-12:00

Continuação do estudo do algoritmo de travessia de grafos em largura. Propriedades da árvore de travessia construída; Cálculo da distância entre dois nós. Análise do tempo de execução.

31/10/2008, 14:00-15:00

Algoritmo de travessia de grafos em profundidade (versão recursiva). "Timestamps". Propriedades da árvore de travessia em profundidade. Análise do tempo de execução.

5/11/2008, 11:00-12:00

Árvores geradoras mínimas de um grafo. Algoritmo de Prim para a construção de AGMs. Prova de correcção.

7/11/2008, 14:00-15:00

Análise do tempo de execução do algoritmo de Prim. Problemas de caminhos mais curtos num grafo. Introdução ao algoritmo de Dijkstra.

12/11/2008, 11:00-12:00

Estudo do algoritmo de Dijkstra. Variantes do problema de caminhos mais curtos: "single pair", "single source", "single destination", "all pairs". A estratégia algorítmica "greedy". Problemas com sub-estrutura óptima.

14/11/2008, 14:00-15:00

Fecho transitivo de um grafo. Algoritmo de Warshall. Adpatação para a resolução do problema "all pairs shortest paths".

19/11/2008, 11:00-12:00

Introdução ao estudo dos problemas NP-completos. Problemas de decisão e problemas de optimização. Exemplos de problemas "difíceis".

21/11/2008, 14:00-15:00

A classe de problemas "P". Noção de algoritmo não-determinístico. A classe de problemas "NP".

26/11/2008, 11:00-12:00

Discussão da questão P=?NP.

28/11/2008, 14:00-15:00

Redução polinomial de um problema a outro.

3/12/2008, 11:00-12:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

5/12/2008, 14:00-15:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

10/12/2008, 11:00-12:00

Definição de problema NP-completo. Restrições sobre problemas; problemas aparentemente semelhantes.

12/12/2008, 14:00-15:00

Os problemas NP-completos SAT e k-SAT. Redução de 3-SAT ao problema da existência de uma "clique" num grafo. Redução de problemas NP-completos: algoritmos aproximados.

Sumários Aulas Teórico-Práticas

TP2

25/9/2008, 14:00-16:00

Exercícios de revisão: programação com listas ligadas em C. Implementação de uma biblioteca de filas de espera.

2/10/2008, 14:00-16:00

Análise do tempo de execução das funções de pesquisa e inserção em árvores binárias de pesquisa. Análise de melhor e pior caso. Importância da profundidade de uma árvore. Motivação da utilização de árvores AVL.

9/10/2008, 14:00-16:00

Árvores AVL: desenvolvimento da função de inserção.

16/10/2008, 14:00-16:00

Árvores AVL: conclusão do desenvolvimento da função de inserção. Tabelas de "hash": introdução e princípios básicos. Resolução de colisões por "linear probing" (endereçamento aberto). Algoritmos de inserção, pesquisa, e remoção.

23/10/2008, 14:00-16:00

Tabelas de "hash" encadeadas: implementação das funções de inserção, remoção, pesquisa, e actualização. Discussão comparativa com a implementação por "linear probing".

30/10/2008, 14:00-16:00

Resolução de exercícios sobre análise de algoritmos iterativos: Avaliação de polinómios e pesquisa linear. Invariantes e análise do tempo de execução.

6/11/2008, 14:00-16:00

Resolução de exercícios sobre análise de algoritmos iterativos e recursivos: Algoritmos de ordenação incrementais ("bubble sort", "max sort", "insertion sort"). Análise do tempo de execução. Equações de recorrência e árvores de recursão.

13/11/2008, 14:00-16:00

Resolução de exercícios sobre "heaps". Implementação dinâmica.

20/11/2008, 14:00-16:00

Resolução de exercícios sobre "heaps". Implementação Estática.

27/11/2008, 14:00-16:00

Resolução de exercícios sobre grafos. Conversão de representações. Ordenações topológicas. Resolução do problema por travessias em profundidade e em largura.

4/12/2008, 14:00-16:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

11/12/2008, 14:00-16:00

Algoritmos "greedy": Implementação em C dos algoritmos de Prim e de Dijkstra.

TP3

25/9/2008, 16:00-18:00

Exercícios de revisão: programação com listas ligadas em C. Implementação de uma biblioteca de filas de espera.

2/10/2008, 16:00-18:00

Análise do tempo de execução das funções de pesquisa e inserção em árvores binárias de pesquisa. Análise de melhor e pior caso. Importância da profundidade de uma árvore. Motivação da utilização de árvores AVL.

9/10/2008, 16:00-18:00

Árvores AVL: desenvolvimento da função de inserção.

16/10/2008, 16:00-18:00

Árvores AVL: simulação de uma sequência de inserções. Tabelas de "hash": introdução e princípios básicos. Resolução de colisões por "linear probing" (endereçamento aberto). Algoritmos de inserção, pesquisa, e remoção.

23/10/2008, 16:00-18:00

Tabelas de "hash" encadeadas: implementação das funções de inserção, remoção, pesquisa, e actualização. Discussão comparativa com a implementação por "linear probing".

30/10/2008, 16:00-18:00

Resolução de exercícios sobre análise de algoritmos iterativos: Avaliação de polinómios e pesquisa linear. Invariantes e análise do tempo de execução.

6/11/2008, 16:00-18:00

Resolução de exercícios sobre análise de algoritmos iterativos e recursivos: Algoritmos de ordenação incrementais ("bubble sort", "max sort", "insertion sort"). Análise do tempo de execução. Equações de recorrência e árvores de recursão.

13/11/2008, 16:00-18:00

Resolução de exercícios sobre "heaps". Implementação dinâmica.

20/11/2008, 16:00-18:00

Resolução de exercícios sobre "heaps". Implementação estática.

27/11/2008, 16:00-18:00

Resolução de exercícios sobre grafos. Conversão de representações. Ordenações topológicas. Resolução do problema por travessias em profundidade e em largura.

4/12/2008, 16:00-18:00

Não houve aula. Motivo: interrupção para avaliação, por decisão do director de curso.

11/12/2008, 16:00-18:00

Algoritmos "greedy": Implementação em C dos algoritmos de Prim e de Dijkstra.