Algoritmos e Estruturas de Dados

Objetivos

• A. Analisar problemas computacionais e selecionar as estruturas de dados, as estratégias de conceção e os algoritmos mais adequados à sua resolução, fundamentando as opções tomadas.
• B. Implementar tipos de dados abstratos e algoritmos utilizando representações e técnicas de conceção adequadas.
• C. Analisar, testar e comparar algoritmos quanto à sua correção, complexidade temporal e espacial e adequação aos requisitos do problema.
• D. Conceber, implementar, testar e documentar soluções computacionais que integrem estruturas de dados e algoritmos, adotando boas práticas de desenvolvimento de software.

Programa

1. Análise de algoritmos
   1.1. Correção, medidas de desempenho e casos de análise
   1.2 Complexidade temporal e espacial
   1.3 Notação assintótica
   1.4 Recorrências simples e introdução ao Teorema Mestre
2. Estratégias de conceção de algoritmos
   2.1 Divisão e conquista
   2.2 Algoritmos gulosos
   2.3 Backtracking
   2.4 Introdução à programação dinâmica
3. Tipos de Dados Abstratos
   3.1 Conceito, especificação, interfaces (API) e implementações estáticas e dinâmicas
   3.2 Estruturas lineares: listas, pilhas e filas
   3.3 Conjuntos, multiconjuntos, dicionários e tabelas de dispersão
   3.4 Árvores binárias de pesquisa, amontados e grafos
4. Algoritmos de pesquisa e ordenação
   4.1 Pesquisa sequencial, binária, em árvores de pesquisa e em tabelas de dispersão
   4.2 Algoritmos elementares e eficientes de ordenação
5. Algoritmos em grafos
   5.1 Representações de grafos
   5.2 Travessias em profundidade e em largura
   5.3 Caminhos mínimos
   5.4 Árvores geradoras mínimas

Métodos de Ensino

Ao longo da unidade curricular são utilizadas metodologias de ensino-aprendizagem diversificadas, articulando a apresentação dos fundamentos com a resolução de problemas e a experimentação prática.

Nas aulas teórico-práticas são apresentados e discutidos os conceitos fundamentais de algoritmos e estruturas de dados, recorrendo à análise comparativa de soluções, à resolução orientada de problemas e à demonstração de algoritmos com complexidade crescente. Estas atividades promovem a participação ativa, o raciocínio crítico e o feedback formativo.

Nas aulas práticas laboratoriais, os estudantes implementam, testam e avaliam algoritmos e estruturas de dados, seguindo uma abordagem de aprendizagem baseada em problemas (Problem-Based Learning). As atividades evoluem de exercícios de aplicação imediata para problemas de maior complexidade, promovendo o pensamento computacional, a abstração, a experimentação e a análise da eficiência das soluções.

No último terço do semestre é desenvolvido um projeto de aplicação, em pequenos grupos, que permite mobilizar de forma articulada os conhecimentos adquiridos na resolução de um problema computacional de pequena ou média dimensão. O projeto é acompanhado através de entregas faseadas, momentos de discussão e feedback, promovendo a melhoria progressiva da solução.

As horas de contacto assíncronas decorrem através do Moodle e incluem atividades orientadas de preparação e consolidação das aulas presenciais, designadamente leitura e exploração de recursos multimédia, quizzes com feedback automático, resolução de problemas, desafios de programação e atividades de apoio ao projeto. Estas atividades promovem a prática continuada, a autorregulação e a consolidação progressiva das aprendizagens.

São ainda promovidos momentos de trabalho colaborativo e discussão em grande grupo, incentivando a comunicação, a cooperação, a argumentação técnica e a reflexão crítica. O Moodle suporta a disponibilização de recursos, fóruns, submissões, acompanhamento do progresso e feedback formativo.

Bibliografia

Essencial:
- Lambert, K. A. (2019). Fundamentals of Python: Data structures (2nd ed.). Cengage. ISBN: 978-0-357-12275-4.
- Canning, J., Broder, A., & Lafore, R. (2023). Data structures & algorithms in Python. Pearson. ISBN: 978-0-13-485589-9.

Complementar:
- Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2013). Data structures and algorithms in Python. Wiley. ISBN: 978-1-118-29027-9.
- Costa, E. (2024). Programação em Python: Fundamentos e resolução de problemas (2.ª ed. atualizada). FCA. ISBN: 978-972-722-940-6.
- Miller, B. N., Ranum, D. L., & Yasinovskyy, R. (2014). Problem solving with algorithms and data structures using Python: The interactive edition. Runestone Academy.

Método de Avaliação