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.