...collaborate on
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

Docente Horário
JoseBarros 4ª, das 10:00 às 12:00, 5ª das 10:00 às 11:00
MariaJoaoFrade 2ª das 16:00 às 18:00; 3ª 12:00 às 13:00
JoseBacelarAlmeida 2ª das 14:00 às 19:00


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.

r91 - 18 Oct 2005 - 16:55:03 - JoseBarros
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback
Syndicate this site RSSATOM