Algoritmos e Estruturas de Dados

Código:

EIC0013

Sigla:

AEDA

Áreas Científicas
Classificação	Área Científica
OFICIAL	Programação

Ocorrência: 2010/2011 - 1S

Ativa?	Sim
Página Web:	http://arocha.liaccfeup.com/doku.php?id=shared:aeda2010
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado Integrado em Engenharia Informática e Computação

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MIEIC	123	Plano de estudos a partir de 2009/10	2	-	7	70	189

Língua de trabalho

Português

Objetivos

Na sequência das unidades curriculares de Introdução à Programação, é objectivo desta unidade curricular:
- recorrer às noções de programação já estabelecidas e sistematizar o uso de estruturas de informação e de algoritmos para resolver categorias de problemas
- usar, como paradigma de suporte ao desenvolvimento de programas, a orientação por objectos
- dar ênfase à organização dos programas em torno de tipos de dados abstractos.
Serão realizados pequenos projectos usando a linguagem C++.

No final da unidade curricular, os estudantes deverão ter competência para modelar problemas recorrendo ao paradigma da orientação por objectos ; resolver problemas fazendo uso de tipos de dados abstractos e estruturas de dados simples lineares e não lineares.

Programa

Programação orientada por objectos. Herança e Polimorfismo. Aspectos básicos de UML. Linguagem C++. Análise de algoritmos: classes e complexidade. Algoritmos de pesquisa e ordenação. Tipos abstractos de dados. Iteradores. Estruturas de dados lineares e sua implementação: pilhas, filas e listas. Árvores binárias e algoritmos associados. Tabelas de dispersão e algoritmos de manipulação. Filas de prioridade.
Árvores equilibradas. Árvores AVL e "Splay".

Bibliografia Obrigatória

Weiss, Mark Allen; Data structures and algorithm analysis in C++. ISBN: 0-201-36122-1
Sedgewick, Robert; Algorithms in C++. ISBN: 0-201-35088-2

Bibliografia Complementar

Deitel, H. M.; C++ how to program. ISBN: 0-13-185757-6
Stroustrup, Bjarne; The C++ programming language. ISBN: 0-201-88954-4
Koenig, Andrew; Accelerated C++. ISBN: 0-201-70353-X
Cormen, Thomas H.; Introduction to algorithms

Métodos de ensino e atividades de aprendizagem

As aulas teóricas são usadas para exposição formal da matéria, acompanhada da apresentação de exemplos e sua discussão. Nas aulas práticas são resolvidos exercícios de programação em C++. Avaliações práticas são aplicadas ao longo do curso, em datas previamente anunciadas, onde os alunos são continuamente avaliados a nível teórico e prático, com a realização de exercícios individuais em computador (Componente Individual). Os alunos efectuam trabalhos de grupo de pequena dimensão que são acompanhados fora das aulas e avaliados em dois momentos ao longo do curso (Componente de Grupo).

Software

Cute C++ Unit Testing Framework
Eclipse C++

Palavras Chave

Ciências Físicas > Ciência de computadores > Programação
Ciências Físicas > Matemática > Algoritmos

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	70,00
Implementação do trabalho prático	Trabalho escrito	60,00
Pntos de Avaliação (4x1,5h)	Exame	6,00
	Total:	-	0,00

Componentes de Ocupação

Descrição	Tipo	Tempo (Horas)	Data Conclusão
Estudo conteúdo teórico / resolução exercícios	Estudo autónomo	50
	Total:	50,00

Obtenção de frequência

O aluno não pode exceder o limite de faltas previsto.

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

A avaliação da disciplina contém duas componentes:
- componente individual (CI) (60%)
- componente de grupo (CG) (40%)

A Componente Individual é realizada individualmente, em quatro momentos distintos ao longo do curso:
- Incluirá duas componentes de igual peso, uma componente prática de programação (usando testes unitários) e uma componente teórica;
- Será realizada individualmente em computador, com consulta ao material fornecido, e duração não superior a 90 minutos;
- CI é a média aritmética das notas obtidas em cada um dos quatro momentos.

A avaliação da Componente de Grupo inclui 2 trabalhos a realizar em grupo (de 3 estudantes), de igual peso, sendo em cada um destes pontos de avaliação contabilizado o empenho e assiduidade do aluno no trabalho de grupo.

A Classificação Final (CF) é portanto computada da seguinte forma:
CF = CI*0,6 + CG*0,4

Onde:
CI = média das 4 notas obtidas nos momentos de avaliação individual
CG = avaliação correspondente à componente de grupo

Para aprovação na disciplina, o aluno deve obter uma classificação mínima de 35% (7 valores em 20) em qualquer das componentes: CI e CG.

Provas e trabalhos especiais

A Componente Individual será realizada em computador (a componente de programação envolve testes unitários), com recurso ao Sistema SIGEX.

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

Os alunos inscritos ao abrigo de regimes especiais sem frequência de aulas práticas:
- podem efectuar a Componente de Grupo (CG) de avaliação constituindo grupo com outro colegas ou sozinhos, devendo acordar com os docentes o trabalho a realizar e as datas de avaliação dos trabalhos.
- devem realizar a avaliação individual CI nas datas estipuladas.

Melhoria de classificação

A realizar na época seguinte da unidade curricular