Notícias
Sessão de esclarecimento de dúvidas na próxima 2ª feira (dia 18) às 14:30 na sala DI 0.02.
-- MariaJoaoFrade - 12 Jul 2005
Os testes poderão ser consultados na Quarta-feira (13 de Julho) às 9:30 na sala DI 0.02 (junto à recepção).
-- MariaJoaoFrade - 12 Jul 2005
Os alunos que vão entregar o trabalho prático apenas a MP2, deverão faze-lo na próxima 2ªfeira, 30 de Maio, da parte da manhã.
Está na recepção do DI a folha com os horários disponíveis, para os alunos se inscreverem.
Quem entregar trabalhos a MP2 e a PP4, apenas tem que fazer a marcação de entrega de trabalhos a PP4 (a recepção de MP2 será feita na mesma altura).
-- MariaJoaoFrade - 24 May 2005
Disponíveis as notas práticas do ano lectivo 2004/2004.
-- JoseBacelarAlmeida - 09 Mar 2005
|
Métodos de Programação II 2004-2005
Sugestão de Leitura
Robert Floyd, um grande Cientista da Computação, recordado
aqui nas palavras de outro grande cientista, Donald Knuth.
Equipa Docente
Horários de Atendimento
Material Disponibilizado
(À medida que o semestre for avançando é actualizada a informação aqui apresentada com os diferentes temas abordados.)
Aulas Teóricas
Aulas Teórico-Práticas
- Revisões da linguagem C - faz-se uso de estruturas de dados já conhecidas (listas, stacks, queues) para recordar os seguintes conceitos:
- Tipos Abstractos de Dados (ADTs);
- Diferentes implementações de um ADT;
- Modularidade na implementação em C (header files, compilação separada);
- Ficha prática: Revisoes.pdf.
- Slides das aulas teórico-práticas (2003).
- Grafos: algoritmo "Shortest Path" (ficheiros em C, incompletos).
- Grafos: algoritmos "Shortest Path" e "Minimum Spanning Tree" (ficheiros em C, completos).
- Grafos: Slides sobre "PERT charts" e "Critical Path Method" (ficheiros em C, incompletos).
Trabalhos Práticos
FAQ da Disciplina
Disponível
aqui.
(faça login como TWikiGuest e coloque as suas questões)
Outro material
Testes deste ano lectivo
Testes de anos anteriores:
Notas e Avaliação
Critérios de Avaliação
- Nota final
- Componente Teórica (Exame): 60% (nota mínima de 8 valores)
- Componente Prática (Trabalhos Práticos): (nota mínima de 10 valores)
- 1 trabalho prático (a ser apresentado na última semana de aulas) (30%)
- TPCs das aulas teórico práticas (facultativo) (10%)
Pré-Requisitos
Não havendo pré-requisitos formais, assume-se que os alunos possuem o seguinte conjunto de conhecimentos:
- familiaridade com a linguagem C
- familiaridade com a utilização de ferramentas de desenvolvimento para a linguagem C, nomeadamente de compiladores.
- conhecimento das estruturas de dados estudadas na cadeira de PP2: listas, stacks, queues, árvores binárias, etc.
- conhecimento dos algoritmos de ordenao estudados na disciplina de MP1: insert sort, merge sort, quick sort, etc.
Aconselham-se todos os alunos a resolver a ficha de revisões proposta.
Notas Práticas (2004/2005)
Estas notas englobam o trabalho prático e a informação das aulas Teórico-Práticas.
Notas época normal (2004/2005)
Notas época recurso (2004/2005)
Notas época especial (2004/2005)
Notas Práticas do ano lectivo 2003/2004
Programas e Bibliografia
Programa Resumido
- Introdução à análise de algoritmos:
- análise de tempo de execução
- análise de correcção
- limites assimptóticos de complexidade
- notações O, Teta e Omega
- classes de complexidade
- relações de recorrência
- estratégias algorítmicas fundamentais:
- força bruta
- algoritmos gananciosos
- divisão e conquista
- ...
- algoritmos de ordenação
- ordenação em tempo linear.
- Algoritmos clássicos sobre grafos.
- Definição das classes de problemas P e NP
- Exemplos de problemas NP-completos
- Estruturas de dados fundamentais:
- questões de eficiência na pesquisa
- árvores AVL
- tabelas de hash
- realização na linguagem C
- Realização de grafos em 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.