[LMCC]

Algoritmos e Complexidade 2005-2006

Notas

• Notas Época Normal
• Notas Época Recurso

Programa Resumido

1. Grafos: Conceitos e Algoritmos Fundamentais
2. Introdução à Análise de Algoritmos
   Casos de Estudo:
   • Algoritmos de Ordenação
   • Algoritmos de Grafos
3. Problemas NP-completos
4. [P] Estruturas de Dados Fundamentais: Questões de Eficiência na Pesquisa;
   Árvores AVL e Tabelas de “Hash”; sua Realização na Linguagem C;

Programa Detalhado

1. Grafos: Conceitos e Algoritmos Fundamentais
   • Grafos: conceitos básicos e representação em memória de computador
   • Algoritmos elementares: pesquisas (em largura e em profundidade)
   • Algoritmos para determinação de árvores geradoras mínimas
   • Algoritmos para determinação de caminhos mais curtos
   • Estratégias algorítmicas: algoritmos "greedy''
   • Algoritmos para determinação do fecho transitivo de um grafo
2. Introdução à Análise de Algoritmos
   Casos de Estudo:
   • Algoritmos de Ordenação
   • Algoritmos de Grafos
3. Problemas NP-completos
4. [P] Estruturas de Dados Fundamentais: Questões de Eficiência na Pesquisa;
   Árvores AVL e Tabelas de “Hash”; sua Realização na Linguagem C;

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge,Mass., second edition, 2001.

• Robert L. Kruse, Bruce P. Leung, and Clovis L. Tondo. Data Structures and Program Design in C. Prentice Hall, second edition, 1997.

• Donald E. Knuth. The Art of Computer Programming : (1) Fundamental Algorithms, (2) Seminumerical Algorithms, (3) Sorting and Searching. Addison/Wesley, third edition, 1997/98. 3 volumes.

Equipa Docente

• JorgeSousaPinto (responsável pela disciplina)
• JoseBarros
• JoseBacelarAlmeida

Critérios de Avaliação

• Componente Teórica (Exame): 60% (nota mínima de 8.5 valores)
• Componente Prática (Trabalhos Práticos): 40% (nota mínima de 10 valores)
  • Trabalho prático (a ser apresentado na semana de 21 a 25 de Novembro)
  • Informação das aulas práticas

Exames

• Primeira Chamada
• Segunda Chamada

Material Disponibilizado

• Slides aulas teóricas: cap.1 (Grafos)
• Slides aulas teóricas: cap.2 (Análise de Algoritmos)
• Slides aulas teóricas: cap.3 (Problemas NP-completos)
• Exercícios sobre Análise de Algoritmos: Exercicios.pdf

Aulas Práticas:

1. Árvores Binárias - BinTree.h
2. Árvores AVL (inserção balanceada) - avl-part.c
3. Tabelas de Hash (chaining address) - hashCh.h; hashCh-part.c
4. Representação de Grafos - graph.h; graph-part.c; test.c
5. Uma implementação de Queues de inteiros - QueueInt.h; QueueInt.c
6. Codificação do algoritmo Prim para cálculo da árvore geradora de custo mínimo - mst.c

Trabalho Prático

Observação: Os alunos com nota prática de 9 valores serão admitidos a exame.

• Notas Práticas obtidas no ano lectivo de 2004/2005

• Enunciado
• Entrega e apresentação: semana de 21 a 25 de Novembro