Sumários
T09 - Algoritmos de Ordenação II
21 março 2019, 15:00 • Carlos Filipe Gomes Bispo
Algoritmos de Ordenação
- “Shellsort”
- Variante de aceleração do “Insertion sort”
- Descrição e implementação: sequências de ordenação
- Exemplo de aplicação e discussão da eficiência do algoritmo
- Exemplo de execução e análise comparativa
- Ordenação de outros tipos de dados
- Implementações estudadas até aqui assumiam ordenação de inteiros
- Definição da interface apropriada
- Protótipos de funções elementares e definição dos dados
- Para evitar mover grandes quantidades de dados
- Ordenação por índices
- Ordenação por ponteiros
- Ordenação em listas ligadas
- Referência às alterações a introduzir nos algoritmos analisados
- Ao nível dos dados de entrada
- Ao nível da interface
T08 - Algoritmos de Ordenação I
19 março 2019, 17:00 • Carlos Filipe Gomes Bispo
Algoritmos de Ordenação
- Introdução ao problema da ordenação de dados
- Definição das regras base e interface de utilização
- Macros e operações elementares relevantes
- Ordenação por Selecção – “Selectsort”
- Descrição,exemplo de aplicação e análise de eficiência
- Ordenação por inserção –“Insertion sort”
- Versão elementar e versão adaptativa
- Exemplo de aplicação e análise de eficiência
- “Bubble sort” – Breve referência
- Descrição do algoritmo e análise de funcionamento
- Exemplo de aplicação e análise de eficiência
- Comparação dos três algoritmos elementares
- Em número de comparações e trocas
- Na evolução da tabela durante a execução – exemplo gráfico
P03 - Análise de Complexidade
19 março 2019, 16:00 • Carlos Filipe Gomes Bispo
Análise de complexidade de código
- Contabilização de instruções básicas
- Exercícios com notação assimptótica
- Recorrências para complexidade temporal
- Recorrências para complexidade de memória
- Exercícios de aplicação do Master Theorem
P03 - Análise de Complexidade
18 março 2019, 09:30 • Carlos Filipe Gomes Bispo
Análise de complexidade de código
- Contabilização de instruções básicas
- Exercícios com notação assimptótica
- Recorrências para complexidade temporal
- Recorrências para complexidade de memória
- Exercícios de aplicação do Master Theorem
T07 - Análise de Algoritmos e Complexidade II
14 março 2019, 15:00 • Carlos Filipe Gomes Bispo
Análise de Algoritmos e Complexidade
- Operações sobre dados
- determinação da complexidade
- Metodologia para determinação de complexidade
- Recorrências básicas
- Master Theorem
- Exemplo: Procura
- Procura sequencial
- Procura binária
- Estudo empírico de métodos de procura
- Conclusões do exemplo
- Listagem da eficiência de operações sobre dados para as tabelas e listas
- Garantias, previsões e limitações