Planeamento

Aulas Teóricas

T01 - Apresentação e Motivação

Aula 1

Apresentação
Motivação
Problema da Conectividade

T02 - Problema da Conectividade

Aula 2

Problema da Conectividade
  • Procura rápida
  • União rápida
  • União rápida ponderada
  • União rápida ponderada com compressão de caminho

T03 - Estruturas de Dados I

Aula 3

Estruturas de Dados
  • Introdução a dados e algoritmos
  • Tipologia de dados
  • Organização em C das definições de dados
  • Ponteiros
  • Listas simples

T04 - Estruturas de Dados II

Aula 4

Estruturas de Dados
  • Tipos abstractos
  • Contentores
  • Pilhas
  • Tipos abstractos de 1ª classe

T05 - Estruturas de Dados III

Aula 5

Estruturas de Dados
  • Tipos abstractos de 1ª classe
  • Filas
  • Listas duplamente ligadas

T06 - Análise de Algoritmos e Complexidade I

Aula 6

Análise de Algoritmos e Complexidade
  • Análise de algoritmos
  • Complexidade, funções relevantes e sucessões
  • Notação assimptótica
  • Operações sobre dados

T07 - Análise de Algoritmos e Complexidade II

Aula 7

Análise de Algoritmos e Complexidade
  • Metodologia para determinação de complexidade
  • Recorrências básicas e Master Theorem
  • Ilustração de aplicação em procura sequencial e binária

T08 - Algoritmos de Ordenação I

Aula 8

Algoritmos de Ordenação
  • Introdução ao problema da ordenação
  • Ordenação por selecção - "selection sort"
  • Ordenação por inserção - " insertion sort"
  • Ordenação por "bubble" - "bubble sort"
  • Análise comparativa

T09 - Algoritmos de Ordenação II

Aula 9

Algoritmos de Ordenação
  • Ordenação com "shellsort"
  • Generalização para ordenação de quaisquer dados
  • Ordenação indirecta
  • Ordenação em listas

T10 - Algoritmos de Ordenação III

Aula 10

Algoritmos de Ordenação
  • Ordenação por "quicksort"
  • Análise do algoritmo

T11 - Algoritmos de Ordenação IV

Aula 11

Algoritmos de Ordenação
  • Melhoramentos no "quicksort"
  • O problema de selecção
  • Ordenação por "mergesort"

T12 - Recursividade e Árvores I

Aula 12

Recursividade e Árvores
  • Recursividade
  • "Divide-and-conquer"
  • Programação dinâmica

T13 - Recursividade e Árvores II

Aula 13

Recursividade e Árvores
  • Introdução às árvores
  • Definições de tipos e representação
  • Propriedades das árvores binárias

T14 - Recursividade e Árvores III

Aula 14

Recursividade e Árvores
  • Varrimentos básicos
  • Árvores e algoritmos de procura
  • Algoritmos de procura
  • Construção de árvores binárias

T15 - Recursividade e Árvores IV

Aula 15

Recursividade e Árvores
  • Árvores ordenadas
  • Árvores ordenadas balanceadas
  • Junção de árvores e remoção de vértices

T16 - Acervos

Aula 16

Acervos
  • Introdução às filas prioritárias
  • Operações abstractas
  • Reposição em acervos
  • Filas prioritárias com acervo
  • Ordenação com acervo

T17 - Tabelas de dispersão

Aula 17

Tabelas de dispersão
  • Introdução às tabelas de dispersão
  • Componentes
  • Funções de dispersão
  • Resolução de colisões

T18 - Algoritmos em Grafos I

Aula 18

Algoritmos em Grafos
  • Introdução aos grafos
  • Propriedades elementares em grafos
  • Definições e propriedades
  • Estrutura abstracta de dados para representação de grafos
    • Matriz de adjacências

T19 - Algoritmos em Grafos II

Aula 19

Algoritmos em Grafos
  • Representação de grafos
    • Listas de Adjacências
  • Variantes e extensões
  • Procura em grafos
    • Procura em profundidade

T20 - Algoritmos em Grafos III

Aula 20

Algoritmos em Grafos
  • Procura em grafos
    • Procura em largura
    • Procura generalizada
  • Árvores mínimas de suporte

T21 - Algoritmos em Grafos IV

Aula 21

Algoritmos em Grafos
  • Árvores mínimas de suporte
    • Algoritmo de Prim
    • Algoritmo de Kruskal
    • Algoritmo de Boruvka
  • Caminhos em grafos
    • Caminhos simples
    • Caminhos de Hamilton
    • Caminhos de Euler

T22 - Algoritmos em Grafos V

Aula 22

Algoritmos em Grafos
  • Representação de redes
  • Problemas de caminhos mais curtos
  • Relaxação de aresta e de caminho
  • Algoritmo de Dijkstra
  • Algoritmo de Floyd