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: 2010/2011 - 1S

Ativa?	Sim
Página Web:	http://moodle.fe.up.pt/1011/course/view.php?id=339
Página e-learning:	http://moodle.fe.up.pt/
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	37	Plano de estudos oficial	3	-	6	56	162

Língua de trabalho

Português

Objetivos

Esta unidade curricular tem os seguintes objectivos principais: 1) complementar os conhecimentos de programação adquiridos numa unidade curricular anterior, usando a linguagem C como ferramenta; 2) transmitir conceitos fundamentais sobre estruturas de dados, concepção e análise de algoritmos.
Os estudantes que concluam com sucesso esta unidade curricular deverão ser capazes de: descrever algumas aplicações típicas das estruturas de dados estudadas; criar/seleccionar estruturas de dados e algoritmos para resolver problemas de complexidade simples/média; comparar implementações alternativas de estruturas de dados e de algoritmos; aplicar os conhecimentos adquiridos no desenvolvimento de programas em C, de acordo com a especificação de um projecto, recorrendo às estruturas de dados e aos algoritmos mais adequados.

Programa

Introdução à programação em linguagem C
- estrutura de um programa em C;
- tipos de dados simples e sua representação; operadores e expressões;
- entrada e saída de dados;
- controlo do fluxo de execução: instruções condicionais e ciclos;
- arrays, strings e struct's e sua representação;
- apontadores e alocação dinâmica de memória;
- funções; passagem de parâmetros e retorno de resultados; funções recursivas;
- ficheiros;
- alguns tópicos avançados.

Estruturas de dados e Algoritmos
– Estruturas de dados fundamentais:
-- estruturas lineares: listas, filas e pilhas;
-- árvores;
-- grafos.
– Conceitos fundamentais de algoritmia
-- análise de algoritmos (eficiência e correcção).
- Técnicas de concepção de algoritmos:
-- divisão-e-conquista;
-- algoritmos gananciosos ("greedy");
-- programação dinâmica;
-- algoritmos de retrocesso ("backtracking").
- Exemplos de aplicação:
-- algoritmos de ordenação e pesquisa;
-- pesquisa de "strings";
-- árvores de decisão;
-- e outros.

Bibliografia Obrigatória

Paul J. Deitel, Harvey M. Deitel; C: How to Program, 6/E, Prentice-Hall, 2009. ISBN: 0136123562
Anany Levitin; Introduction to the design & analysis of algorithms. ISBN: 0-321-36413-9

Bibliografia Complementar

Brian W. Kernighan, Dennis M. Ritchie; C. ISBN: 85-7001-327-2
Luís Damas; Linguagem C. ISBN: 972-722-156-4
Marque de Sá; Fundamentos de programação usando C. ISBN: 972-722-475-X

Métodos de ensino e atividades de aprendizagem

Aulas teórico-práticas:
Exposição das matérias, acompanhada da resolução de problemas no quadro e sua discussão.

Aulas práticas:
Resolução de problemas de aplicação das matérias; desenvolvimento de soluções em linguagem C, em computador.

Trabalho práticos, a realizar fora das aulas:
Desenvolvimento de pequenos projectos de programação, envolvendo a aplicação das matérias estudadas.

Software

Microsoft Visual Studio

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	36,00
Resolução de problemas	Teste	36,00		2010-12-17
Projectos de programação	Trabalho escrito	36,00		2010-12-17
Exame	Exame	2,00		2011-02-11
	Total:	-	0,00

Componentes de Ocupação

Descrição	Tipo	Tempo (Horas)	Data Conclusão
Teoria	Estudo autónomo	36	2010-12-17
Preparação para exame	Estudo autónomo	16	2011-02-11
	Total:	52,00

Obtenção de frequência

Não exceder o limite de faltas estabelecido nas Normas e obter uma classificação mínima de 40% na classificação distribuída.
A classificação distribuída (cDist) é dada pela seguinte fórmula:
cDist = 0,4*cMT + 0,2*cTP1 + 0,4*cTP2
onde
cMT = classificação obtida no mini-teste a realizar próximo do meio do semestre, sobre programação em linguagem C
cTP1 e cTP2 = classificação de dois trabalhos práticos a realizar durante o semestre.

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

A classificação final é dada pela fórmula:
cFINAL = 0,5 * cDIST + 0.5 * cEXAME
onde cDIST e cEXAME representam, respectivamente, a classificação distribuída e a classificação do exame escrito.

É condição necessária para aprovação a obtenção de uma classificação mínima de 40% em qualquer uma das componentes.

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

Os alunos com estatuto especial, embora possam estar dispensados da frequência das aulas práticas, estão sujeitos às mesmas condições de avaliação dos alunos regulares, isto é, devem realizar o mini-teste e os trabalhos práticos nas datas e períodos estabelecidos para os restantes alunos.
É condição necessária para aprovação a obtenção de uma classificação mínima de 40% em qualquer uma das componentes.

Melhoria de classificação

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

A classificação do exame escrito pode ser melhorada nas épocas legalmente previstas.