Estruturas de Dados e Algoritmos

Conhecimentos de Base Recomendados

Programação de Computadores.

Métodos de Ensino

Aulas teóricas do tipo magistral com recurso a meios audiovisuais para apresentação teórica dos tópicos do programa, incluindo a resolução de exercícios práticos elementares que concretizem o interesse prático dos tópicos ensinados e exemplifiquem a sua aplicação a situações reais.

Aulas práticas laboratoriais em que se pretende que os alunos, com a orientação do docente, resolvam exercícios de aplicação prática dos conceitos teóricos ensinados nas aulas teóricas, promovendo a criatividade e o raciocínio crítico perante problemas de programação de maior complexidade.

Resultados de Aprendizagem

Esta unidade curricular pretende aprofundar os conhecimentos de programação adquiridos na unidade curricular de Programação de Computadores. Para além da consolidação destes conhecimentos básicos, pretende-se que os alunos adquiram conhecimentos fundamentais de programação orientada a objetos, estruturas dinâmicas de dados e algoritmia. Pretende-se ainda que sejam capazes de utilizar uma linguagem de programação orientada a objetos para implementar; testar e depurar algoritmos e estruturas de dados, incluindo listas ligadas, pilhas, filas, e árvores binárias de pesquisa de suporte a esses algoritmos; conhecer aplicações típicas dessas estruturas de dados; analisar a complexidade de algoritmos; modelar problemas de programação e desenhar estruturas de dados e algoritmos que permitam obter uma solução eficiente, com base no conhecimento das principais técnicas de conceção de algoritmos.

Estágio(s)

Não

Programa

1. Consolidação de conceitos de programação em C

Variáveis

Controlo de fluxo

Tabelas e C-strings

Estruturas

Ponteiros

Funções

Recursividade

 

2. Programação procedimental em C++

Strings C++

Entrada e saída

Alocação dinâmica de memória

Ficheiros

Variáveis por referência

Funções que devolvem uma referência

Sobrecarga de funções

 

3. Conceitos fundamentais de algoritmia e algoritmos de ordenação e pesquisa

Noção de algoritmo

Conceção de algoritmos – da abstração do problema à proposta de solução

Eficiência de algoritmos – notação de O grande

Algoritmos de ordenação e pesquisa e análise de complexidade

Ordenação de estruturas de dados complexas usando tabelas indexadas

 

4. Programação orientada a objetos em C++

Classes, objetos, atributos e métodos

Sobrecarga de operadores

Membros estáticos

Funções e classes amigas

Composição de classes

Herança e polimorfismo

Templates de classes

 

5. Estruturas dinâmicas de dados

Listas ligadas

Pilhas e filas

Árvores binárias de pesquisa.

Docente(s) responsável(eis)

Rui Paulo Pinto da Rocha

Métodos de Avaliação

Avaliação
Trabalho laboratorial ou de campo: 5.0%
Mini Testes: 15.0%
Projecto: 15.0%
Exame: 25.0%
Frequência: 40.0%

Bibliografia

Langsam, Y., Augenstein, M.J., and Tenenbaum, A.M. (1996), “Data Structures Using C and C++”, 2nd edition, Pearson, ISBN: 978-0-13036-997-0.

Skiena, S.S. (2008), “The Algorithm Design Manual”, 2nd edition, Springer, ISBN: 978-1-84800-069-8.

Stroustrup, B. (2013), “The C++ Programming Language”, 4th edition, Addison-Wesley, ISBN: 978-0-32156-384-2.

Ellis, M., and Stroustrup, B. (1990), “The Annotated C++ Reference Manual”, Addison-Wesley, ISBN: 978-0-20151-459-9.