Planeamento
Aulas Teóricas
Apresentação e Motivação
Apresentação
- Objectivos e programa da disciplina
- Corpo docente e contactos
- Página da disciplina
- Funcionamento da disciplina
- Avaliação da disciplina
- Bibliografia
- Honestidade Académica
Motivação
- Introdução aos Algoritmos e Estruturas de Dados
- Estratégia de desenho e análise de algoritmos
- Relevância do estudo de algoritmos
- Exemplo de motivação
Problema da Conectividade
- Solução pouco eficiente
-
Algoritmo "quick find" - de procura rápida
- Descrição
- Implementação
- Exemplo de execução
- Análise de complexidade
-
Algoritmo "quick union" - de união rápida
- Descrição
- Implementação
- Exemplo de execução
- Análise de complexidade
-
Algoritmo "weighted union" - de união ponderada
- Descrição
- Implementação
- Exemplo de execução
- Análise de complexidade
-
Algoritmo "compressed weighted union" - de união ponderada com compressão de caminho
- Descrição
- Implementação
- Exemplo de execução
- Análise de complexidade
-
Algoritmos para o problema da conectividade
- Comparação global
- Aspectos fundamentais
Estruturas de Dados I
- Introdução aos Dados e Algoritmos
- Listagem de tipos de dados mais vulgares e critérios de escolha
- Tipos básicos, conversão de tipos
- Organização em C das definições de tipos
- Ponteiros
- Tabelas
- Unidimensionais
- Multidimensionais
- Alocação dinâmica e estática
- Cadeias de caracteres
Estruturas de Dados II
- Estruturas
- Conceito base e construção
- Definição de novos tipos
- Exemplos de manipulação dinâmica de memória
- Listas
- Listas simples
- Tabelas de listas
- Listas de listas
- Listas de tabelas
- Listas duplamente ligadas
- Interface para listas simples
- Implementação para listas simples
Estruturas de Dados - III
- Tipos abstractos
- Contentores
- Pilhas
- Implementação em tabela
- Implementação em lista
- Critérios para escolha da implementação
- Tipos abstractps de 1ª classe
- Exemplo para Complexos
Estruturas de Dados - IV
- Tipos abstractos de 1ª classe
- Exemplo para Filas
- Filas de Complexos
- Filas de Matrizes
- Listas Duplamente Ligadas
Análise de Algoritmos e Complexidade - I
Análise de Algoritmos
- Aspectos essenciais da análise
Crescimento de funções
Resolução de grandes problemas
Complexidade, funções rlevantes e sucessões
Notação Assimptótica
- Conceito
- Definições
- Propriedades
Operações sobre dados
- Determinação da complexidade
Análise de Algoritmos e Complexidade - II
etodologia para determinação de complexidade
Recorrências básicas
Exemplo: Procura
- Procura sequencial
- Procura binária
- Estudo empíricos de métodos de procura
- Conclusões do exemplo
Listagem da eficiência de operações sobre dados
- para tabelas e listas simples
Garantias, previsões e limitações
Algoritmos de Ordenação - I
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 - "Select sort"
- 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"
- Descrição do algoritmo e análise de funcionamento
- Exemplo de aplicação e análise de eficiência
Comparação dos três primeiros algoritmos elementares
- Em número de comparações e trocas
- Na evolução da tabela durante a execução - exemplo gráfico
"Shellsort"
- Variante de aceleração do "Insertion sort"
- Tabelas h-ordenadas
Algoritmos de Ordenação - II
"Shellsort"
- Continuação da aula anterior
- Exemplo de aplicação e discussão da eficiência do algoritmo
- Exemplo de execução e análise comparativa
Ordenação de outros tipo de dados
- Implementaçoes estudadas até aqui assumiam ordenação de inteiros
- Definição da interface adequada para outros tipos
Para evitar mover grandes quantidades de dados
- Ordenação por índices
- Ordenação por ponteiros
Ordenação em listas ligadas
"Quicksort"
- Ideia chave e motivação
- Código
- Exemplo de aplicação
- Descrição do mecanismo de partição
Algoritmos de Ordenação - III
"Quicksort"
- Continuação da aula anterior
- Análise de eficiência
Análise gráfica do algoritmo "quicksort"
- Descrição gráfica da evolução
- Memória utilizada na versão recursiva
- Implementação alternativa com pilha explícita
- Versão não recursiva do "quicksort"
- Melhoramentos na versão não recursiva
- Mecanimos de partição alternativos: aleatórios, mediana de três
- Algoritmo híbrido para tabelas de baixa dimensão
- Estudo empírico de complexidade
- Melhoramento em chaves duplicadas
O problema de Selecção e sua relação com o problema da Ordenação
Operação de junção - "merge"
- Junção de tabelas como alternativa à partição
- Código e exemplo de aplicação
Algoritmo "mergesort"
- Introdução
Recursividade e Árvores - I
Algoritmo "mergesort" - conclusão da aula anterior
- Exemplo de aplicação e implementação
- Análise de eficiência e outras propriedades
- Evolução gráfica
Recursividade e Árvores
- Recursividade
- recursividade e árvores
- algoritmos recursivos
- programas recursivos e não recursivos
- características básicas e demonstrações
- exemplos
- "Divide-and-conquer"
- decomposição em sub-problemas independentes
- Torres de Hanoi
- exemplos e variantes
- Programação dinâmica
- programação dinâmica ascedente
- programação dinâmica descendente
Recursividade e Árvores - II
Árvores
- Introdução às árvores
- Tipos de árvores
- Definições
- Árvores com raíz, árvores ordenadas, árvores M-árias, árvores binárias
- Definições de tipos e representações
- Árvores binárias
- Árvores M-árias
- Árvores ordenadas
- Árvores com raíz
- Árvores gerais
- Propriedades das árvores binárias
Recursividade e Árvores - III
Varrimento em árvores binárias
- Pré-fixado
- In-fixado
- Pós-fixado
- Exemplos
- Largura
Outros varrimentos e outras árvores
Algoritmos recursivos em árvores binárias
Construção de árvores binárias
- Torneios e parsing
- Exemplos
Recursividade e Árvores - IV
Árvores ordenadas
- Conceito e exemplos
- Inserção em árvores ordenadas
Árvores ordenadas balanceadas
- Mecanismo de rotação
- Exemplos
- Inserção com balanceamento
Combinação de árvores ordenadas
Remoção de vértices em árvores ordenadas
Tabelas de dispersão
- Introdução às tabelas de dispersão
- Componentes das tabelas de dispersão
- Funções de dispersão
- Resolução de colisões
- procura linear
- dupla dispersão
- inserção em lista
- comparação de eficiência
Filas com prioridade
- Introdução às filas com prioridade
- Operações abstractas
- Implementação por tabelas não ordenadas
- Introdução aos acervos
- Reposição nos acervos
- Ascendente
- Descendente
- Implementação de filas com prioridade por acervos
- Ordenação por acervo
Grafos - I
- Introdução
- Definição de grafo
- Motivação aplicacional
- Definições e notação
- Propriedades elementares em grafos
- Exemplos
- Definições e propriedades
- Grafos completos, complemento de um grafo, cliques, grafos bipartidos, grafos direccionados, ciclos em grafos direccionados, grafos ponderados, redes
- Estrutura abstracta de dados para grafos
- Interface elementar
- Representação de um grafo
- Matriz de adjacências
Grafos - II
- Representação de um grafo
- Listas de adjacências
- Implementação da estrutura abstracta de dados
- Comparação das representações alternativas
- Vantagens e inconvenientes das matrizes de adjacências
- Vantagens e inconvenientes das listas de adjacências
- Variantes e extensões
- Grafos direccionados, ponderados e redes
- Outras representações
- Comparação das representações alternativas
- Memória e tempo de execução
- Procura em grafos
- Analogia com a exploração de labirintos
- Estratégia de Tremaux
- Procura em profundidade - DFS
- Exemplo de execução
Grafos - III
- Procura em profundidade - DFS
- Exemplo de execução
- Implementação para matrizes de adjacências e listas de adjacências
- Comparação
- Propriedades
- Procura em largura - BFS
- Implementação para matrizes de adjacências
- Exemplo de execução
- Propriedades
- Implementação alternativas para matrizes de adjacências
- Procura generalizada em grafos
- Descrição
- Implementação
- Propriedades
- Árvores mínimas de suporte - MST
- Representação e implementação para grafos ponderados
- Propriedades das MST's - Exemplos
Grafos - IV
- Árvores mínimas de suporte - MST
- Propostas de solução para cálculo de MST's
- Algoritmo de Prim
- Descrição; Implementação; Exemplo de execução; Análise de eficiência
- Algoritmo de Kruskal
- Descrição; Implementação; Exemplo de execução; Análise de eficiência
- Algoritmo de Boruvka
- Breve referência ao algoritmo
- Comparação dos três métodos
- Caminhos em Grafos
- Caminhos Simples
- Implementação; Descrição da implementação; Exemplo de execução; Análise de complexidade
Grafos - V
- Caminhos de Hamilton
- Implementação; Exemplo de execução; Análise de complexidade
- Discussão comparativa dos problemas de caminhos simples e de Hamilton
- Caminhos e ciclos de Euler
- Caracterização dos grafos que possuem caminhos de Euler; Caracterização dos grafos que possuem ciclos de Euler; Discussão especulativa da complexidade do problema; Propriedades; Implementação #1; Exemplo de execução; Implementação #2; Exemplo de execução; Análise de complexidade
- Problemas em Grafos
- Síntese de complexidade
Grafos - VI
- Representação de Redes
- Caminhos mais curtos
- Caminho mais curto fonte-destino; Caminhos mais curtos de fonte única; Caminhos mais cutos entre todos
- Relaxação de aresta
- SPT - "Shortest Path Tree"
- Relaxação de caminho
- Princípio de optimalidade
- Algoritmo de Dijkstra
- Propriedades do algoritmo de Dijkstra; Análise do algoritmo de Dijkstra
- Breve referência a caminhos mais curtos entre todos e ao algoritmo de Floyd
Revisão de matéria
Aula dedicada a esclarecimento de dúvidas e revisão de conceitos com vista à preparação para exame.