Estruturas de Dados e Algoritmos

Código:

MEB0030

Sigla:

EDA

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

Ocorrência: 2022/2023 - 1S

Ativa?	Sim
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado em Engenharia Biomédica

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MEB	17	Plano de estudos oficial	1	-	6	52	162
			2

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Esta unidade curricular tem os seguintes objetivos 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 por objetos, usando a linguagem C/C++ como ferramenta;
2)transmitir conceitos fundamentais sobre estruturas de dados, conceção e análise 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 (STL) 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 objetos;
- 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.
Uso de qualificativos especiais: "const", "static", "friend". 
Construtores de cópia. 
Destruidores. 
"Overloading" de operadores.
“Templates”.
INTRODUÇÃO À CONCEÇÃO DE PROGRAMAS USANDO O PARADIGMA DE PROGRAMAÇÃO ORIENTADA POR OBJETOS (OO)
Relações entre classes; implementação de associações. 
STANDARD TEMPLATE LIBRARY
Contentores: "vector", "list", "queue", "stack", "map", "multimap", "set", "multiset".
Iteradores e algoritmos.
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. Algoritmos de pesquisa e de ordenação; análise da complexidade de algoritmos. Estruturas de dados lineares e sua implementação.

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órico-práticas: 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 práticas: resolução de exercícios de programação em C/C++ e desenvolvimento parcial de pequenos projetos de programação.
- 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 laboratoriais.

Software

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

Palavras Chave

Ciências Físicas > Ciência de computadores > Programação

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	60,00
Trabalho prático ou de projeto	40,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Estudo autónomo	80,00
Frequência das aulas	52,00
Elaboração de projeto	30,00
Total:	162,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 avaliação distribuída. Os estudantes que obtiveram frequência no ano letivo anterior podem manter a nota de frequência que obtiveram nesse ano; devem, neste caso, informar o docente responsável pela u.c., durante a primeira semana de aulas, e não devem inscrever-se nas turmas práticas.

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

A classificação final é dada pela fórmula: cFINAL = 0,4 * cDIST + 0.6 * cEXAME onde cDIST e cEXAME representam, respetivamente, a classificação da componente distribuída e a classificação do exame escrito. O resultado da avaliação distribuída será calculado com base na classificação obtida num trabalho prático, a realizar durante o semestre e a entregar próximo do final do semestre. 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.
A classificação final não pode exceder em mais de 4 valores a classificação do exame arredondada para o inteiro mais próximo.

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.