Universidade Nova de Lisboa

Universidade Nova de Lisboa

Faculdade de Ciências e Tecnologia

Algoritmos e Estruturas de Dados

Código

3742

Unidade Orgânica

Faculdade de Ciências e Tecnologia

Departamento

Departamento de Informática

Créditos

6.0

Professor responsável

Fernanda Maria Barquinha Tavares Vieira Barbosa, Luís Manuel Marques da Costa Caires

Horas semanais

5

Total de horas

70

Língua de ensino

Português

Objectivos

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.

Pré-requisitos

Precedência obrigatória:

- Programação de Microprocessadores (MIEEC)

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.

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 1 prova individual (teste ou exame), e a componente laboratorial por 2 provas individuais e 1 prova em grupo (trabalhos práticos).

Todas as provas de avaliação (teste, 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 3 trabalhos práticos (tp1, tp2 e tp3) com pesos de  15%, 20% e 25% na nota final, respectivamente. Os trabalhos práticos tp1 e tp2 serão realizados e entregues individualmente em aulas práticas. O trabalho prático tp3 será realizado em grupo de 2 alunos.

Componente Teórico-Prática

Os alunos devem realizar um teste individual (t1) no período de aulas, ou um exame (ex) na época de recurso. Qualquer uma destas provas terá um peso de 40% na nota final.

Nota Final de Avaliação Contínua

- Para os alunos com nota de teste igual ou superior a 9.0 valores, a nota final (NF) será atribuída segundo a seguinte fórmula, arredondando à unidade:

NF = 0.15 * tp1 + 0.2 * tp2 + 0.25 * tp3 + 0.4 * t1.

- Para os alunos com nota de teste inferior a 9.0 valores, a nota final será a nota do teste, arredondando à unidade:

NF = t1.

Nota Final em Época de Recurso

- Para os alunos com nota de exame (ex) igual ou superior a 9.0 valores, a nota final (NF) será atribuída segundo a seguinte fórmula, arredondando à unidade:

NF = 0.15 * tp1 + 0.2 * tp2 + 0.25 * tp3 + 0.4 * ex.

- Para os alunos com nota de exame (ex) inferior a 9.0 valores, a nota final será a nota de exame, arredondando à unidade:

NF = ex.

Cursos