Desenvolvimento e Análise de Algoritmos
2019/2020 - 1. Semestre
SUMÁRIOS
1. Lição - 27/setembro/2019
Apresentação:
Objectivos
Programa
Bibliografia
Avaliação
Informações adicionais
Cap. 1 - Estratégias de Desenvolvimento de Algoritmos
1 - Algoritmos Determinísticos vs Não-Determinísticos
2 - Tipos de Problemas
3 - Estratégias de Desenvolvimento de Algoritmos
Breve referência às principais estratégias abordadas ao longo da unidade curricular
4 - Análise da Complexidade
Revisão dos conceitos fundamentais
5 - Desenvolvimento de algoritmos iterativos e recursivos simples
Contagem do número de operações básicas realizadas
Análise empírica e análise formal da sua complexidade
Ref. Principal
[Levitin] - Chapter 1, Chapter 2
2. Lição - 4/outubro/2019
Cap. 2 - Algoritmos de Força-Bruta ("Brute-Force")
1 - Introdução
Características principais
Algoritmos directos
Pesquisa exaustiva
2 - Análise de alguns exemplos
Listar os sucessivos divisores de um número natural
Pesquisa num array
Ordenação de um array
"String Matching"
3 - Análise de exemplos da Geometria Computacional
Determinação do par de pontos mais próximos ("The Closest-Pair Problem")
Determinação do casco convexo de um conjunto de n pontos ("The Convex-Hull Problem")
4 - Pesquisa Exaustiva
Características principais
Análise de alguns exemplos:
O Problema da Mochila ("The 0-1 Knapsack Problem")
O Problema do Caixeiro Viajante ("The Traveling Salesman Problem")
O Problema da Afectação ("The Assignment Problem")
O Problema das 8 Damas ("The 8-Queens Problem")
Ref. Principal
[Levitin] - Chapter 3
3. Lição - 18/outubro/2019
Cap. 3 - As Estratégias "Dividir para Reinar" ("Divide and Conquer") e "Diminuir para Reinar" ("Decrease and Conquer")
1 - A estratégia "Dividir para Reinar"
Características principais
Análise da Complexidade: "The Master Theorem" e "The Smoothness Rule"
2 - Estudo de um caso
Cálculo de potências de expoente natural
3 - Algoritmos de ordenação
Mergesort
Quicksort
4 - Algoritmos numéricos --- Breve referência
Multiplicação de números inteiros: Algortimo de Karatsuba
Multiplicação de matrizes: Algoritmo de Strassen
5 - Estudo de casos
Um problema de cobertura usando triminós ("Tiling a defficient square board using triominoes")
Determinação do par de pontos mais próximos ("The Closest-Pair Problem")
Determinação do casco convexo de um conjunto de n pontos ("The Convex-Hull Problem")
6 - Estruturas de dados em árvore
Árvores quaternárias ("Quadtrees") --- Breve referência
Árvores octais ("Octrees") --- Breve referência
7 - A estratégia "Diminuir para Reinar"
Características principais
Variações possíveis:
Diminuição por um factor constante
Diminuição de um valor constante
Diminuição variável
8 - Estudo de um caso
Cálculo de potências de expoente natural
9 - Algoritmos de Pesquisa ("Array Searching") --- Breve referência
Pesquisa linear
Pesquisa binária
Pesquisa ternária
Pesquisa por interpolação
10 - Estudo de casos
O problema da moeda falsa ("The Fake-Coin Problem")
Multiplicação de números naturais usando o "Método Russo"
Refs. Principais
[Levitin] - Chapter 4, Chapter 5
[Johnsonbaugh and Schaefer] - Chapter 5
4. Lição - 25/outubro/2019
Cap. 4 - Programação Dinâmica
1 - Introdução
Características principais
Aplicações típicas
O "Princípio da Optimalidade" --- Breve referência
Passos principais para o desenvolvimento de algoritmos
"Memoization"
2 - Estudo de casos
Cálculo de termos da Sucessão de Fibonacci
Cálculo de combinações C(n,p)
Cálculo dos Números de Delannoy
"The Coin Row Problem"
O Problema da Mochila ("The 0-1 Knapsack Problem")
Refs. Principais
[Levitin] - Chapter 8
[Johnsonbaugh and Schaefer] - Chapter 8
5. Lição - 8/novembro/2019
Cap. 5 - Algoritmos Vorazes ("Greedy Algorithms")
1 - Introdução
Características principais
2 - Estudo de caso: o Problema da Mochila ("The Knapsack Problem")
Uma heurística para o problema não-fracionário da mochila ("The 0-1 knapsack problem")
Um algoritmo para o problema fracionário da mochila ("The continuous knapsack problem")
3 - Estudo de caso: "The Coin Changing Problem"
Uma heurística para determinar o menor número de moedas para um dado troco ("The Coin Changing Problem")
4 - Estudo de caso: "The Activity Selection Problem"
Análise do comportamento de diferentes heurísticas para a resolução do "Activity Selection Problem"
5 - Alguns problemas sobre grafos
O algoritmo de Kruskal para determinação da árvore abrangente de custo mínimo ("Minimum Spanning Tree")
O algoritmo de Prim para determinação da árvore abrangente de custo mínimo ("Minimum Spanning Tree")
O algoritmo de Dijkstra para determinação da árvore dos caminhos mais curtos
6 - Estudo de caso: O Problema do Caixeiro-Viajante ("TSP - The Traveling Salesperson Problem")
Análise do comportamento de diferentes heurísticas para a resolução do TSP
Refs. Principais
[Levitin] - Chapter 9
[Johnsonbaugh and Schaefer] - Chapter 7
6. Lição - 15/novembro/2019
Cap. 6 - Estratégias Avançadas
1 - Introdução
Limitações das estratégias algorítmicas tradicionais
Teoria da Complexidade: breve introdução
Problemas de decisão
As classes P e NP
Problemas NP-Completo
2 - Backtracking - Estudo de casos
Procura usando Backtracking: características principais
O Problema das Damas ("The N-Queens Problem")
Determinação de ciclos hamiltonianos ("The Hamiltonian Circuit Problem")
"The Subset-Sum Problem"
3 - Branch-and-Bound - Estudo de um caso
Procura usando Branch-and-Bound: características principais
O Problema da Mochila ("The 0-1 Knapsack Problem")
4 - Determinação de soluções aproximadas
Motivação
"Job Scheduling"
Algoritmos "on-line"
A heurística "Shortest-Queue"
"Bin Packing"
As heurísticas "First-Fit" e "Next-Fit"
Refs. Principais
[Levitin] - Chapter 11; Chapter 12
[Johnsonbaugh and Schaefer] - Chapter 4; Chapter 11
7. Lição - 22/novembro/2019
Cap. 7 - Introdução aos Algoritmos Probabilísticos
1 - Algoritmos Probabilísticos
Algoritmos determinísticos vs. não-determinísticos
Vantagens da sua aplicação
Exemplo de aplicação
2 - Probabilidades --- Revisão de Conceitos Fundamentais
Experiências estatísticas e eventos
Probabilidade
Variáveis aleatórias
Exemplos
3 - Simulação de Experiências Estatísticas
Análise de resultados de experiências simples (simulação e jogos)
O Paradoxo do Aniversário (“The Birthday Problem”) --- Breve referência
“The Coupon Collecter’s Problem” --- Breve referência
Refs. Principais
[Graham, Knuth and Patashnik] - Chapter 8
[Hromkovic] - Chapter 1; Chapter 2
[Langtangen] - Chapter 8
[Vrajitoru and Knight] - Chapter 6
8. Lição - 29/novembro/2019
Cap. 7 - Introdução aos Algoritmos Probabilísticos (cont.)
4 - Métodos de Monte Carlo
Cálculo aproximado do valor de Pi
Análise do Comportamento
5 - Amostragem probabilística
Algoritmo direto
O algoritmo R (Vitter, 1985)
6 - Algoritmos de Monte Carlo
O teste de primalidade de Fermat
Análise do comportamento de um algoritmo para deteção de números primos
7 - Algoritmos de Las Vegas
Randomized Search
Randomized Quicksort
8 - Algoritmos probabilísticos para resolução de problemas de otimização combinatória
Análise de um algoritmo para resolução do TSP
Refs. Principais
[Hromkovic] - Chapter 2
[Langtangen] - Chapter 8
[Vrajitoru and Knight] - Chapter 6
9. Lição - 6/dezembro/2019
Cap. 7 - Introdução aos Algoritmos Probabilísticos (cont.)
9 - Contagem Aproximada
Motivação
Contadores aproximados (estocásticos) com probabilidade fixa
Análise do comportamento para contagem com probabilidade 1/2 e 1/32
Contadores aproximados (estocásticos) com probabilidade decrescente logarítmica
Análise do comportamento
Contador aproximado de vírgula flutuante
Análise do comportamento
Refs. Principais
R. Morris, Counting Large Numbers of Events in Small Registers, Commun. ACM, Vol. 21, N. 10, October 1978
P. Flajolet, Approximate Counting: A Detailed Analysis, Bit, Vol. 25, 1985
M. Csurös, Approximate counting with a floating-point counter. In COCOON, LNCS vol. 6196, p. 358-367, Springer, 2010
10. Lição - 13/dezembro/2019
Cap. 7 - Introdução aos Algoritmos Probabilísticos (cont.)
10 - Filtros de Bloom
Motivação
Tabelas de Dispersão (Hash Tables) --- Breve revisão
Filtros de Bloom (Bloom Filters)
Principais características
Análise do comportamento
Seleção dos vários parâmetros característicos
Filtros de Contagem (Counting Bloom Filters)
Principais características e limitações
Filtros de Quociente (Quocient Filters)
Motivação e características principais
As operações de procura e de inserção de um item
Comparação com os Filtros de Bloom
Refs. Principais
B. H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, Commun. ACM, Vol. 13, N. 7, July 1970
J. Blustein and A. El-Maazaw, Bloom Filters – A Tutorial, Analysis, and Survey, Technical Report CS 2002-10, Dalhousie University, Halifax, NS, Canada, December 2002
A. Broder and M. Mitzenmacher, Network Applications of Bloom Filters: A Survey, Internet Mathematics, Vol. 1, N. 4, 2004
Michael A. Bender et al., Don't Thrash: How to Cache Your Hash on Flash. In Proceedings of the VLDB Endowment, Vol. 5, N. 11, 2012
11. Lição - 20/dezembro/2019
Apresentação, por cada aluno do programa doutoral, de um artigo científico escolhido de uma revista da área
Autor: Joaquim Madeira - jmadeira@ua.pt
Data: 12 de dezembro de 2019