Estruturas de Dados e Algoritmos

Código:

EBE0116

Sigla:

EDA

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciências de Base

Ocorrência: 2008/2009 - 1S

Ativa?	Sim
Página Web:	http://www.fe.up.pt/~rcamacho/cadeiras/eda/
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado Integrado em Bioengenharia

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MIB	8	Plano de estudos oficial	3	-	5	60	135

Língua de trabalho

Português

Objetivos

A disciplina tem três objectivos fundamentais: i) dar a conhecer aos alunos conceitos fundamentais sobre estruturas de dados; ii) dar-lhes conhecimentos básicos sobre algoritmia e sobre técnicas de concepção de algoritmos; e iii) estudar em detalhe algoritmos relevantes em áreas como a Bioengenharia e a Bioinformática.

Programa

Estruturas de dados: estruturas lineares; árvores; e grafos.

Conceitos fundamentais de algoritmia.

Técnicas concepção de algoritmos:
divisão e conquista;
algoritmos gananciosos ("greedy");
programação dinâmica;
algoritmos de retrocesso ("backtracking");
algoritmos probabilísticos.

Algoritmos eficientes em grafos:
visita em largura e em profundidade;
ordenação topológica;
caminho mais curto;
árvore de expansão mínima;
fluxo máximo;
circuito de Euler.

Algoritmos em "strings":
pesquisa exacta ("string matching");
pesquisa aproximada;
"substring" comum mais comprida.

Algoritmos de Análise de Dados (Data Mining)
Árvores de Decisão
Indução de Regras
Clustering

Problemas Computacionais em Biologia Molecular
Alinhamento de Pares de Sequências

Métodos de ensino e atividades de aprendizagem

As aulas te\'oricas são usadas para exposição formal da matéria, acompanhada da apresentação de exemplos e sua
discussão. Nas aulas de Laboratório será realizado um trabalho que envolva Estruturas de Dados e Algoritmos e que insida sobre um problema de Biologia ou Medicina

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	42,00
	Total:	-	0,00

Obtenção de frequência

Nota mínima de 50% na avaliação de frequência.

Fórmula de cálculo da classificação final

A classificação de frequência tem um peso de 50% na nota final repartida da seguinte forma:
90\% para o trabalho pr\'atico e 10\% para a impressão do professor sobre o (des)empenho do aluno nas aulas práticas.

A classificação do exame tem um peso de 50% na nota final
(é exigida uma nota mínima de 30% no exame para obtenção de aprovação na disciplina)

Avaliação especial (TE, DA, ...)

Os alunos que frequentam ao abrigo de estatutos especiais têm os mesmos requisitos de avaliação de frequência dos alunos regulares, devendo realizar os trabalhos práticos propostos e fazer a sua demonstração nas épocas estabelecidas.

Melhoria de classificação

A classificação distribuída só pode ser melhorada frequentando de novo a disciplina num ano lectivo posterior.