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 por 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 strings
Ponteiros
Ficheiros
Funções e passagem de parâmetros
Recursividade

2. Programação orientada a objetos em C++
Classes, objetos, atributos e métodos
Construtores e destrutor
Ponteiros para objetos
Sobrecarga de operadores
Entrada/Saída e Strings em C++
Membros estáticos
Funções e classes amigas
Composição de classes
Herança e polimorfismo
Templates de classes

3. Estruturas dinâmicas de dados
Listas ligadas
Pilhas e filas
Árvores binárias de pesquisa – inserção, procura, remoção e árvores equilibradas

4. Conceitos fundamentais de algoritmia
Eficiência de algoritmos – notação de O grande
Análise de complexidade de algoritmos de ordenação e pesquisa
Ordenação de estruturas de dados complexas usando tabelas indexadas
Técnicas para conceção de algoritmos
Exemplos práticos de conceção – da abstração do problema à proposta de solução

Docente(s) responsável(eis)

António Paulo Mendes Breda Dias Coimbra

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