1. Início
  2. Faculdade de Ciências e Tecnologia
  3. Matemática e Aplicações
  4. Atuariado, Estatística e Investigação Operacional
  5. Algoritmos e Estruturas de Dados

Algoritmos e Estruturas de Dados

Objetivos

Saber: Técnicas básicas para a resolução de problemas: tipos abstractos de dados fundamentais (lista, conjunto, pilha, fila, dicionário, dicionário ordenado) e do domínio do problema; técnicas básicas de desenho de algoritmos: estruturas de dados fundamentais (vector, lista ligada simples e dupla, tabela de dispersão, árvores binárias); técnicas básicas para análise de algoritmos: complexidade espacial e temporal.

Saber Fazer: modelar programas usando tipos abstractos de dados; definir e implementar tipos abstractos de dados no domínio do problema; calcular a complexidade espacial e temporal de algoritmos; implementar os tipos abstractos de dados fundamentais, utilizando as estruturas de dados mais adequadas; conceber e implementar soluções eficientes para problemas concretos.

Soft-skills: Capacidade para avaliar soluções, capacidade para seleccionar as técnicas apropriadas a um problema; capacidade de comunicação escrita: relatórios de projetos da disciplina.

Caracterização geral

Código

3742

Créditos

6.0

Professor responsável

Carmen Pires Morgado, Luís Manuel Marques da Costa Caires

Horas

Semanais - 5

Totais - 84

Idioma de ensino

Português

Pré-requisitos

Precedência obrigatória:

- Programação de Microprocessadores (MIEEC)

Bibliografia

Mark Allen Weiss.
Data Structures and Algorithm Analysis in C (second edition).
Addison-Wesley, 1997.
ISBN 0-201-49840-5 (Hard cover)

Linguagem de Programação C

Brian Kernighan and Dennis Ritchie
The C Programming Language (second edition).
Prentice-Hall, 1988.
ISBN 0-13-110362-8 (Paperback)

Pedro Guerreiro.
Elementos de Programação com C (3ª edição).
FCA - Editora de Informática, 2005.

Luis Damas.
Linguagem C (12ª edição).
FCA - Editora de Informática, 2005.

Método de ensino

O ensino consiste na exposição da matéria em aulas teóricas e na resolução de problemas em aulas práticas de laboratório.

Nas aulas teóricas, todos os conteúdos programáticos são apresentados utilizando exemplos práticos concretos.

Para a maturação dos conteúdos, é realizado um conjunto de exercícios nas aulas práticas onde os alunos desenham, analisam e implementam programas para problemas concretos,  aplicando os conhecimentos adquiridos.

Os alunos vão sendo avaliados ao longo do semestre através do desenvolvimento de trabalhos práticos de pequena dimensão e de testes.

Método de avaliação

A avaliação do aluno é composta por uma componente teórico-prática e uma componente laboratorial realizadas ao longo do semestre.

A componente teórico-prática é composta por 2 provas individuais (2 testes escritos), e a componente laboratorial por 1 prova em grupo (trabalho prático).

Todas as provas de avaliação (testes, trabalhos e exame) são classificadas na escala de 0 a 20 valores.

Componente Laboratorial

Durante o período de aulas, os alunos devem realizar 1 trabalho prático (tp) com peso de  40% na nota final. O trabalho prático tp será realizado em grupo de 2 alunos. Este trabalho é composto por 2 fases (F1 e F2), com peso de 25% e 15%, respetivamente, na nota final da cadeira.

A nota da componente laboratorial (NCL) será atribuída segundo a seguinte fórmula:

NCL = 0.25 * F1 + 0.15 * F2.

Frequência

Para obter frequência na cadeira a nota da 1ª fase do trabalho deve ser superior ou igual a 9.5 valores em 20 valores.

Componente Teórico-Prática

Os alunos devem realizar 2 testes individuais (t1 e t2) no período de aulas, ou um exame (ex) na época de recurso.

Avaliação contínua: O teste t1 terá um peso de 15%, e o teste t2 terá um peso de 45% na nota final. A nota da componente teórico-prática (NCT) será atribuída segundo a seguinte fórmula:

NCT = 0.15 * t1 + 0.45 * t2.

Recurso: O exame ex terá um peso de 60% na nota final. Para realizar o exame de recurso, o aluno deve ter obtido frequência na cadeira. A nota da componente teórico-prática (NCT) será atribuída segundo a seguinte fórmula:

NCT = 0.6 * ex.

Nota Final de Avaliação

- A nota final (NF) será atribuída segundo a seguinte fórmula, arredondando à unidade:

NF =NCL + NCT.

Conteúdo

  1. Estruturação dum programa em tipos abstractos de dados.
    • Método para análise e concepção da solução
    • Definição e implementação de tipos abstractos de dados no domínio do problema
  2. Introdução à análise de algoritmos.
  3. Especificação formal de tipos de dados abstractos:
    • Fila
    • Pilha
    • Sequência (Lista)
    • Conjunto
    • Dicionário
    • Dicionário Ordenado
  4. Estudo das principais estruturas de dados, sempre acompanhado da análise da complexidade das primitivas suportadas, no melhor caso, no pior caso e no caso esperado.
    • Vectores circulares.
    • Listas simplesmente e duplamente ligadas.
    • Tabelas de dispersão. Funções de dispersão. Dispersão aberta. Dispersão fechada.
    • Árvores binárias. Árvores de pesquisa.