Estruturas de Dados e Algoritmos

Código:

EBE0116

Sigla:

EDA

Áreas Científicas
Classificação	Área Científica
OFICIAL	Engenharia Biomédica

Ocorrência: 2015/2016 - 1S

Ativa?	Sim
Página Web:	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	31	Plano de estudos oficial	3	-	6	70	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Esta unidade curricular tem os seguintes objectivos principais:
1) complementar os conhecimentos de programação adquiridos na unidade curricular de Introdução à Programação Científica, introduzindo o paradigma de programação orientada a objetos, usando a linguagem C/C++ como ferramenta;
2) transmitir conceitos fundamentais sobre estruturas de dados, análise e conceção de algoritmos, dotando os estudantes com a capacidade de aplicar o referido paradigma de programação para desenvolver programas em que sejam usadas as estruturas de dados e algoritmos disponíveis na Standard Template Library de C++, bem como abstrações desenvolvidas pelos próprios.

 

 

Resultados de aprendizagem e competências

Os estudantes que concluam com sucesso esta unidade curricular deverão ser capazes de:
- identificar os conceitos fundamentais da programação procedimental e da programação orientada por objectos;
- descrever algumas aplicações típicas das estruturas de dados e algoritmos estudados e seleccionar/criar estruturas de dados e algoritmos para resolver problemas de complexidade simples/média;
- aplicar os conhecimentos adquiridos no desenvolvimento de programas em C/C++, de acordo com a especificação de um projeto, recorrendo a estruturas de dados e  algoritmos criados pelo próprio ou disponíveis na biblioteca standard de C++ (STL).

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Recomenda-se a frequência com aproveitamento da unidade curricular de Introdução à Programação Científica ou equivalente.

Programa

INTRODUÇÃO À LINGUAGEM C/C++
Tipos de dados simples e E/S básica.
Operadores. Expressões aritméticas e booleanas.
Estruturas de controlo: estruturas de selecção e de repetição.
Tipos de dados estruturados: "arrays","strings" de C e "structs"; "vectors" e "strings" de C++.
Apontadores e alocação dinâmica de memória.
Funções: definição e declaração de funções; variáveis locais e variáveis globais; mecanismos de passagem de parâmetros e retorno de valores (passagem de parâmetros por valor e por referência); "overloading" de funções; “templates”. Funções recursivas.
"Streams": entrada e saída usando ficheiros de texto; "stringstreams".
INTRODUÇÃO ÀS CLASSES E ABSTRAÇÃO DE DADOS
Conceitos fundamentais. Classes e "structs".
Membros-dado e membros-função de uma classe; visibilidade dos membros; conceito de encapsulamento.
Construtores; construtores com parâmetros.
“Templates”.
Introdução à conceção de programas OO.
Relações entre classes; implementação de associações. Introdução à notação UML.
STANDARD TEMPLATE LIBRARY
Contentores: "vector", "list", "queue", "stack", "map", "multimap", "set", "multiset".
Iteradores e algoritmos.
CLASSES – CONCEITOS ADICIONAIS
Uso de qualificativos especiais: "const", "static", "friend".
Construtores de cópia.
Destrutores.
"Overloading" de operadores.
HERANÇA E POLIMORFISMO
Conceitos de herança e de polimorfismo.
Classes derivadas. Acesso aos membros da classe base.
Formas de polimorfismo: "overloading" de funções; "overriding" (funções virtuais); "templates".
Classes abstratas.
TRATAMENTO DE EXCEÇÕES (introdução)
EXEMPLOS DE APLICAÇÃO (ao longo do programa)
Conceção de programas usando programação OO.

Bibliografia Obrigatória

Cay Horstmann, Timothy Budd; Big C++, Wiley, 2009. ISBN: ISBN 978-0-470-38328-5

Bibliografia Complementar

Walter Savitch; Problem Solving with C++, Addison-Wesley, 2009. ISBN: ISBN-13: 9780321531346
H. M. Deitel, P. J. DeitelDeitel; C++ how to program. ISBN: 0-13-185757-6
Mark Allen Weiss; Data structures and algorithm analysis in C++. ISBN: 0-201-36122-1

Métodos de ensino e atividades de aprendizagem

 - Aulas teóricas: exposição das matérias do programa, recorrendo à apresentação e discussão código que ilustra o uso da linguagem e dos conceitos introduzidos, e à resolução de pequenos exercícios.
- Aulas teórico-práticas: resolução de exercícios de programação em C/C++ e desenvolvimento parcial de dois projetos.
- Auto-aprendizagem: estudo das matérias, recorrendo à bibliografia e ao material disponibilizado na página Web da unidade curricular, resolução de exercícios e realização dos projetos iniciados nas aulas teórico-práticas.

Software

Ambiente de desenvolvimento em C/C++ (Windows ou Linux)

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	50,00
Trabalho laboratorial	50,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	35,00
Frequência das aulas	70,00
Trabalho laboratorial	57,00
Total:	162,00

Obtenção de frequência

Não exceder o limite de faltas estabelecido nos regulamentos 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,5*cTP1 + 0,5*cTP2 em que 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. O exame escrito será realizado "com consulta". É condição necessária para aprovação a obtenção de uma classificação mínima de 40% em qualquer uma das componentes, cDIST e cEXAME.

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

As condições de avaliação são idênticas às dos estudantes regulares, isto é, os trabalhos práticos são obrigatórios, devendo ser executados e apresentados nos períodos estabelecidos para os restantes estudantes. O exame é também obrigatório, seguindo as normas estabelecidas.

Melhoria de classificação

A classificação da componente distribuída só pode ser melhorada frequentando de novo a disciplina num ano letivo posterior. A classificação do exame escrito pode ser melhorada nas épocas legalmente previstas. A melhoria de apenas uma das componentes implicará a manutenção da classificação obtida previamente na outra componente, aplicando-se a fórmula de cálculo da classificação anteriormente apresentada.