Algoritmos e Estruturas de Dados

Objetivos

1. Saber escolher, criar e utilizar estruturas de dados.
2. Saber escrever algoritmos iterativos e recursivos sobre estruturas de dados.
3. Adquirir conhecimentos sobre algoritmos de ordenação e de pesquisa em estruturas de dados.
4. Saber analisar a complexidade dos algoritmos de ordenação e de pesquisa em estruturas de dados
5. Saber resolver problemas de pequena e média escala, usando as estruturas de dados e as estratégias mais adequadas e os algoritmos mais eficientes.

Programa

1. Introdução ao estudo da eficiência de algoritmos: critérios para avaliar a eficiência de um algoritmo; a notação do O maiúsculo.
2. Tipos de Dados Abstratos (TDA): pilhas, filas, listas, árvores binárias, grafos e dicionários.
3. Implementações vetoriais e dinâmicas de TDAs.
4. Algoritmos de pesquisa: sequencial, binária, com árvores binárias, com tabelas de dispersão, caminho mais curto e de menor custo em grafos.
5. Algoritmos de ordenação: inserção direta, seleção direta, bubble sort, shellsort, mergesort, quicksort, radix sort, heapsort.

Métodos de ensino

As aulas teóricas são expositivas em que se apresentam os conceitos elementares de programação com recurso a exemplos e demonstrações, usando a linguagem Python.

As aulas práticas laboratoriais funcionam articuladas com as aulas teóricas e são preenchidas pela exposição e resolução de problemas, de pequena e média escala, com soluções algorítmicas, usando a linguagem Python.

Os estudantes desenvolvem um projeto que é o elemento aglutinador dos conteúdos aprendidos ao longo da unidade curricular, que permite analisar, desenhar e implementar pequenos programas numa situação mais próxima da realidade e adquirir competências de trabalho autónomo e em equipa.

A plataforma de e-Learning Moodle da UAc (em http://moodle.uac.pt) é utilizada como repositório de material pedagógico e didático de apoio à aprendizagem, bem como de plataforma de agendamento, divulgação e promoção de atividades complementares e de gestão dos elementos de avaliação.

Bibliografia

Essencial

• Lambert, K. A. (2013). Fundamentals of Python: Data Structures (Second Edition). Boston, USA: Cengage.
• Costa, E. (2015). Programação em Python : Fundamentos e Resolução de Problemas. FCA

Complementar

• Goodrich M. T., Tamassia R., Goldwasser M. H. (2013), Data Structures and Algorithms in Python, Wiley
• Bradley N. Miller, David L. Ranum Milner (2013). Problem solving with algorithms and data structures using Python (disponível em https://runestone.academy/runestone/books/published/pythonds/index.html)