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
Artur Miguel de Andrade Vieira Dias, Carla Maria Gonçalves Ferreira
Horas
Semanais - 4
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 (1 pequeno projeto e 1 teste escrito), e a componente laboratorial por 1 prova em grupo (trabalho prático).
Todas as provas de avaliação (teste, projeto, trabalho prático e exame) são classificadas na escala de 0 a 20 com valores arredondados às décimas.
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 do mesmo turno prático.
A nota da componente laboratorial (NCL) será atribuída segundo a seguinte fórmula:
NCL = 0.40 * TP
Alguns alunos podem ter que fazer uma discussão oral do trabalho, com influência na nota final deste.
Frequência
Para obter frequência na cadeira a nota do trabalho (TP) deve ser superior ou igual a 9.5 valores em 20 valores. Poderá haver uma prova escrita individual de validação do contributo de cada aluno para o trabalho. A frequência também depende da aprovação nessa prova escrita.
Componente Teórico-Prática
Os alunos devem realizar 1 teste individual (T) e um pequeno projeto (P) no período de aulas, ou um exame (EX) na época de recurso.
Avaliação contínua: O projeto P terá um peso de 15%, e o teste T 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 * P + 0.45 * T
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
Aprovação
Para obter aprovação é necessário e suficiente:
NCL >= 0.40 * 9.5
e
NCT >= 0.60 * 9.5
Nota Final de Avaliação
Para os alunos aprovados, a nota final (NF) será atribuída segundo a seguinte fórmula, arredondada às unidades:
NF = NCL + NCT
Frequência e classificações obtidas nos anos anteriores
Os alunos que obtiveram frequência no ano passado estão dispensados de realizar o trabalho prático (TP), ficando esta componente da nota com o valor obtido nesse ano.
Os alunos que obtiveram frequência antes do ano passado têm que realizar o trabalho prático (TP) para obter frequência este semestre, sendo ignorada a nota obtida anteriormente.
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.