Algoritmos e Complexidade
2019/2020 - 2. Semestre
Aulas Teóricas
SUMÁRIOS
1. Lição - 11/fevereiro/2020
Apresentação:
Objectivos
Programa
Bibliografia
Avaliação
Informações adicionais
Cap. 1 - Análise da Complexidade de Algoritmos
1 - Introdução
Análise do desempenho de algoritmos: conceitos fundamentais
Complexidade temporal e espacial
Eficiência relativa
Análise experimental vs. análise formal da complexidade
Exemplos simples
Ref. Principal
[McConnell] - Chapter 1
2. Lição - 13/fevereiro/2020
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
1 - Introdução (cont.)
Análise detalhada de alguns exemplos simples
Análise do Melhor Caso e do Pior Caso
Análise do Caso Médio: procura do maior elemento de um array não ordenado
Ordens de complexidade
Ref. Principal
[McConnell] - Chapter 1
3. Lição - 18/fevereiro/2020
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
1 - Introdução (cont.)
Ordens de complexidade (cont.)
Notações habituais
Exemplos
2 - Análise da Complexidade de Algoritmos de Pesquisa
O algoritmo de "Pesquisa Sequencial" para um array não ordenado
Análise do Pior Caso e do Caso Médio
Refs. Principais
[McConnell] - Chapter 1; Chapter 3
[Weiss] - Chapter 2
4. Lição - 20/fevereiro/2020
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
2 - Análise da Complexidade de Algoritmos de Pesquisa (cont.)
O algoritmo de "Pesquisa Sequencial" para um array ordenado
Análise do Pior Caso e do Caso Médio
O algoritmo de "Pesquisa Binária"
Análise do Pior Caso
Ref. Principal
[McConnell] - Chapter 3
5. Lição - 27/fevereiro/2020
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
2 - Análise da Complexidade de Algoritmos de Pesquisa (cont.)
O algoritmo de "Pesquisa Binária" (cont.)
Análise do Pior Caso (cont.)
Análise do Caso Médio
3 - Análise da Complexidade de Algoritmos de Ordenação
Introdução
O algoritmo de "Selecção Linear"
Refs. Principais
[McConnell] - Chapter 3; Chapter 4
[Weiss] - Chapter 7
[Sedgewick] - Chapter 6
6. Lição - 3/março/2020
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
3 - Análise da Complexidade de Algoritmos de Ordenação (cont.)
O algoritmo de "Selecção Linear" (cont.)
Análise do Melhor Caso, do Pior Caso e do Caso Médio
O algoritmo de "Troca Sequencial" ("Bubblesort")
Análise do Melhor Caso, do Pior Caso e do Caso Médio
O algoritmo de "Ordenação por Inserção"
Análise do Melhor Caso, do Pior Caso e do Caso Médio
Refs. Principais
[McConnell] - Chapter 4
[Weiss] - Chapter 7
[Sedgewick] - Chapter 6
7. Lição - 5/março/2020
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
3 - Análise da Complexidade de Algoritmos de Ordenação (cont.)
O algoritmo de "Ordenação por Inserção" (cont.)
Análise do Melhor Caso, do Pior Caso e do Caso Médio (cont.)
O algoritmo "Shellsort"
Análise do Melhor Caso e do Pior Caso
Possíveis sequências de incrementos
Refs. Principais
[McConnell] - Chapter 4
[Weiss] - Chapter 7
8. Lição - 10/março/2020
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
3 - Análise da Complexidade de Algoritmos de Ordenação (cont.)
O algoritmo "Heapsort"
O algoritmo "Heapsort" como exemplo da estratégia "Transform-and-Conquer"
Árvores binárias: algumas propriedades
A estrutura de dados "heap" binária: algumas propriedades
A estrutura de dados "heap" binária: principais operações
O algoritmo de ordenação
Análise da complexidade
Refs. Principais
[McConnell] - Chapter 4
[Weiss] - Chapter 7
[Adrego] - Cap. 9
9. Lição - 24/março/2020
Ensino a Distância
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
4 - Análise da Complexidade de Algoritmos Recorrentes
Introdução
Análise da complexidade de algoritmos simples:
- cálculo de potências
- inversão da ordem dos elementos de um array
Cálculo do valor de um determinante usando o Teorema de Laplace
"As Torres de Hanói"
Ref. Principal
[McConnell] - Chapter 2
10. Lição - 26/março/2020
Ensino a Distância
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
4 - Análise da Complexidade de Algoritmos Recorrentes (cont.)
Recapitulação dos tópicos principais da aula anterior
A estratégia "Decrease-and-Conquer"
A estratégia "Divide-and-Conquer"
Generalização: Algoritmos exponenciais
O algoritmo de Pesquisa Binária
"The Master Theorem"
"The Smoothness Rule"
Refs. Principais
[Levitin] - Appendix B
[Weiss] - Chapter 10
11. Lição - 31/março/2020
Ensino a Distância
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
4 - Análise da Complexidade de Algoritmos Recorrentes (cont.)
Multiplicação por Partição: O Algoritmo de Karatsuba
O Algoritmo de Ordenação por Fusão ("Mergesort")
Refs. Principais
[Weiss] - Chapter 10; Chapter 7
[McConnell] - Chapter 4
12. Lição - 2/abril/2020
Ensino a Distância
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
4 - Análise da Complexidade de Algoritmos Recorrentes (cont.)
O Algoritmo de Ordenação por Fusão ("Mergesort") (concl.)
O Algoritmo de Ordenação por Partição ("Quicksort")
Refs. Principais
[McConnell] - Chapter 4
[Weiss] - Chapter 7
13. Lição - 14/abril/2020
Ensino a Distância
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
4 - Análise da Complexidade de Algoritmos Recorrentes (cont.)
Análise detalhada do Guião Prático nº 5
O Algoritmo de Ordenação por Partição ("Quicksort") (concl.)
Selecção do K-ésimo elemento de um conjunto não ordenado
Introdução
Refs. Principais
[McConnell] - Chapter 4
[Weiss] - Chapter 7
14. Lição - 16/abril/2020
Ensino a Distância
Cap. 1 - Análise da Complexidade de Algoritmos (cont.)
4 - Análise da Complexidade de Algoritmos Recorrentes (cont.)
Selecção do K-ésimo elemento de um conjunto não ordenado
Possíveis estratégias
Algoritmo de selecção usando a estratégia de partição do "Quicksort"
Cálculo do valor de um polinómio P(x) usando o Método de Horner
Multiplicação de matrizes usando o Algoritmo de Strassen
Refs. Principais
[McConnell] - Chapter 3; Chapter 5
[Weiss] - Chapter 1; Chapter 7; Chapter 10
15. Lição - 21/abril/2020
Ensino a Distância
Cap. 2 - Árvores Binárias de Procura ("Binary Search Trees")
1 - Tipos Abstratos de Dados (TADs)
Introdução
Interface de um TAD vs Implementação de um TAD
Invariantes da representação
Análise de exemplos simples
Convenções e organização em ficheiros
16. Lição - 23/abril/2020
Ensino a Distância
Cap. 2 - Árvores Binárias de Procura ("Binary Search Trees") (cont.)
1 - Tipos Abstratos de Dados (TADs) (cont.)
O TAD STACK - funcionalidades; diferentes representações internas
O TAD QUEUE - funcionalidades; diferentes representações internas
O TAD DEQUE - breve referência
O TAD LISTA LIGADA - funcionalidades
17. Lição - 28/abril/2020
Ensino a Distância
Cap. 2 - Árvores Binárias de Procura ("Binary Search Trees")
1 - Introdução
Árvores: Definições; Terminologia
Algumas propriedades das árvores binárias
O TAD Árvore Binária
Possíveis estruturas de dados
Algoritmos recursivos para manipulação de árvores binárias:
- contar o número de nós de uma árvore
- determinar a altura de uma árvore
- destruir uma árvore
- verificar se duas árvores são iguais
Refs. Principais
[Weiss] - Chapter 4
[Sedgewick] - Chapter 5
18. Lição - 30/abril/2020
Ensino a Distância
Cap. 2 - Árvores Binárias de Procura ("Binary Search Trees")
2 - Travessias
Tipos de travessias
Algoritmos recursivos para as travessias em "Pré-Ordem", "Em-Ordem" e em "Pós-Ordem"
Algoritmo iterativo (usando uma FILA) para a travessia por níveis
Algoritmo iterativo (usando uma PILHA) para a travessia em "Pré-Ordem"
Algoritmos iterativos (usando uma PILHA) para as travessias "Em-Ordem" e em "Pós-Ordem" --- Breve referência
Uma aplicação da travessia em "Pré-Ordem": registar e recuperar a informação (e a estrutura) de uma árvore em / de ficheiro
Refs. Principais
[Weiss] - Chapter 4
[Sedgewick] - Chapter 5; Chapter 12
19. Lição - 5/maio/2020
Ensino a Distância
Cap. 2 - Árvores Binárias de Procura ("Binary Search Trees") (cont.)
3 - Árvores Binárias de Procura
O TAD ABP - Árvore Binária de Procura
Algoritmos recursivos e iterativos para procurar e para inserir informação numa Árvore Binária de Procura
Desenvolvimento de um algoritmo para procurar e remover um dado item de uma Árvore Binária de Procura
Análise simplificada da complexidade de algumas operações sobre Árvores Binárias de Procura
Refs. Principais
[Sedgewick] - Chapter 5; Chapter 12;
[Weiss] - Chapter 4
20. Lição - 7/maio/2020
Ensino a Distância
Cap. 2 - Árvores Binárias de Procura ("Binary Search Trees") (cont.)
3 - Árvores AVL
Introdução
Árvores de altura equilibrada
Árvores de Fibonacci
Exemplos de inserção de elementos numa árvore AVL
O algoritmo para inserção de um elemento numa árvore AVL
O algoritmo para remoção de um elemento de uma árvore AVL - Breve referência
Árvores ABP vs Árvores AVL - Comparação do desempenho
Ref. Principal
[Weiss] - Chapter 4
21. Lição - 14/maio/2020
Ensino a Distância
Cap. 3 - Dicionários
1 - Introdução
2 - "Digital Search Trees"
O algoritmo de pesquisa numa "Digital Search Tree"
Complexidade da pesquisa no pior caso
3 - "Prefix Trees"
O algoritmo de pesquisa numa "Prefix Tree"
4 - "Hash Tables"
Introdução
Funções de dispersão ("Hash Functions")
"Open Addressing"
Colisões: estratégias de resolução
Eficiência computacional
Refs. Principais
[Weiss] - Chapter 5
[Sedgewick] - Chapter 15; Chapter 14
22. Lição - 19/maio/2020
Ensino a Distância
Cap. 3 - Dicionários (cont.)
4 - "Hash Tables" (cont.)
Exemplo de aplicação: contagem das ocorrências de palavras num ficheiro de texto
"Separate Chaining"
Análise detalhada de algumas operações
Eficiência computacional
Refs. Principais
[Weiss] - Chapter 5
[Sedgewick] - Chapter 14
23. Lição - 21/maio/2020
Ensino a Distância
Cap. 4 - Grafos
1 - Introdução
Terminologia; Propriedades; Exemplos
2 - Os Tipos Abstratos de Dados Grafo e Digrafo
Possíveis estruturas de dados
Representação usando uma lista de arestas
Representação usando uma matriz de adjacência
Representação usando listas de adjacências
Operações básicas
Comparação do desempenho de várias estruturas de dados
Refs. Principais
[McConnell] - Chapter 8
[Weiss] - Chapter 9
24. Lição - 26/maio/2020
Ensino a Distância
Cap. 4 - Grafos (cont.)
3 - Travessias
Introdução
Travessia em profundidade ("Depth-First")
Travessia por níveis ("Breadth-First")
4 - Ordenação Topológica ("Topological Sorting")
Desenvolvimento e análise da complexidade de alguns algoritmos
Refs. Principais
[McConnell] - Chapter 8
[Weiss] - Chapter 9
25. Lição - 28/maio/2020
Ensino a Distância
Cap. 4 - Grafos (cont.)
5 - Determinação de Caminhos Mais Curtos
Introdução: terminologia; tipos de problemas
O algoritmo de Ford
Algoritmo, usando uma Pilha ou uma Fila, para referenciar os vértices recém-rotulados
O algoritmo de Dijkstra
Resolução detalhada de exemplos
Refs. Principais
[McConnell] - Chapter 8
[Weiss] - Chapter 9
26. Lição - 2/junho/2020
Ensino a Distância
Cap. 4 - Grafos (cont.)
6 - Determinação da Árvore Abrangente (ou Geradora) de Custo Mínimo ("Minimum Spanning Tree")
O algoritmo de Kruskal
O algoritmo de Prim
Análise de alguns exemplos
7 - Determinação de Circuitos Eulerianos
O algoritmo de Fleury
Refs. Principais
[McConnell] - Chapter 8
[Weiss] - Chapter 9
27. Lição - 4/junho/2020
Ensino a Distância
Cap. 4 - Grafos (cont.)
8 - Determinação de Ciclos Hamiltonianos
Introdução
Pesquisa exaustiva
9 - O Problema do Caixeiro Viajante ("The Traveling Salesperson Problem")
Resolução usando pesquisa exaustiva
10 - Pesquisa Exaustiva - Exemplos de Aplicação
O Problema da Mochila ("0-1 Knapsack")
O Problema da Soma de Subconjuntos ("The Subsetsum Problem")
Geração de "Quadrados Mágicos"
Refs. Principais
[Levitin] - Chapter 3
[Baase & Van Gelder] - Chapter 13
28. Lição - 9/junho/2020
Ensino a Distância
Cap. 5 - Problemas NP-Completo
1 - Introdução
Problemas tratáveis vs. não-tratáveis
Algoritmos deterministas vs. não-deterministas
2 - Tipos de Problemas
3 - As Classes P e NP
4 - A Classe NP-Completo
Exemplos de problemas
Reducibilidade
5 - Determinação de Soluções Aproximadas
Motivação
Heurística voraz ("greedy") para o Problema da Mochila ("0-1 Knapsack")
Heurísticas vorazes ("greedy") para o Problema do Caixeiro Viajante (TSP)
Refs. Principais
[Johnsonbaugh & Schaefer] - Chapter 10, 11
[Baase & Van Gelder] - Chapter 13
[Levitin] - Chapter 11, 12
Autor: Joaquim Madeira - jmadeira@ua.pt
Data: 9 de junho de 2020