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
84
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
- 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
- Introdução à análise de algoritmos.
- Especificação formal de tipos de dados abstractos:
- Fila
- Pilha
- Sequência (Lista)
- Conjunto
- Dicionário
- Dicionário Ordenado
- 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 2 provas individuais (1 teste prático e um teste escrito), e a componente laboratorial por 1 prova individual e 1 prova em grupo (trabalhos práticos).
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 2 trabalhos práticos (tp1e tp2) com pesos de 15% e 25% na nota final, respectivamente. O trabalho prático tp1 será realizado e entregue individualmente em aulas práticas. O trabalho prático tp2 será realizado em grupo de 2 alunos.
A nota da componente laboratorial (NCL) será atribuída segundo a seguinte fórmula:
NCL = 0.15 * tp1 + 0.25 * tp2.
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 prático t1 terá um peso de 25%, e o teste escrito t2 terá um peso de 35% na nota final. A nota da componente teórico-prática (NCT) será atribuída segundo a seguinte fórmula:
NCT = 0.25 * t1 + 0.35 * t2.
Recurso: O exame ex terá um peso de 60% na nota final. 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.