Estruturas de Dados e Algoritmos

Disciplina da Secção de Lógica e Computação.

Cursos:
LEBM (Licenciatura em Engenharia Biomédica). Ano: 1. Semestre: 2.
LCI (Licenciatura em Ciências Informáticas). Ano: 1. Semestre: 2.
LMAC (Licenciatura em Matemática e Computação). Ano: 3. Semestre: 2.

Professor Responsável: Francisco Miguel Dionísio.

Objectivos gerais

Complementar os conhecimentos de programação já adquiridos com vista ao desenvolvimento de aplicações interactivas de grande escala com recurso a bases de dados.

Objectivos operacionais

Programar em linguagem de programação imperativa de grande difusão, recorrendo a algoritmos e estruturas de dados comuns. Calcular o comportamento assimptótico dos algoritmos. Desenhar e utilizar bases de dados relacionais. Desenvolver aplicações na web com acesso a base de dados.

Programa

Programação imperativa em C. Introdução ao estudo da eficiência de algoritmos. Algoritmos de ordenação elementares e avançados: inserção directa, selecção directa, bubblesort, quicksort, fusão binária e heapsort. Tipos de dados abstractos: pilhas, filas de espera, filas de prioridade, árvores. Implementações vectoriais e dinâmicas em C. Árvores binárias de pesquisa. Árvores de pesquisa equilibradas. Tabelas de dispersão. Resolução de colisões por encadeamento e por endereçamento aberto. Endereçamento linear, quadrático e dispersão dupla. Mecanismos de modularidade em C. Elementos de bases de dados relacionais (PostgreSQL). Desenvolvimento de aplicações na web sobre bases de dados (PHP).

Bibliografia básica

• F. M. Dionísio. Estruturas de Dados e Algoritmos.
  AEIST, 2000. Versão revista e aumentada em preparação.
• R. Ramakrishnan, J. Gehrke. Database Management Systems (Third Edition).
  McGraw-Hill Higher Education, 2002.

Bibliografia complementar

• T. Cormen, C. Leiserson e R. Rivest. Introduction to Algorithms.
  MIT Press, 1994.
• L. Damas. Linguagem C (Segunda Edição).
  FCA - Editora de Informática, 1999.
• R. Lerdorf. PHP Pocket Reference.
  O'Reilly & Associates, 2000.
• T. Lockhart. PostgreSQL.
  PostgreSQL Inc, 2000.

Avaliação

Projecto (50%) e 3 testes (50%).

Carga horária semanal

Aulas teóricas: 3h. Aulas práticas: 2h. Estudo recomendado: 4h.

Última actualização: 27 de Janeiro de 2004.