Disciplina Algoritmia e Estrutura de Dados

Muitos projetos na área da programação envolvem a resolução de problemas computacionais complexos, para os quais soluções rápidas e simplistas podem não ser suficientemente eficientes. Esta UC foca-se na problemática da conceção de bons algoritmos e de como analisar a sua correção e a sua eficiência. Estas são questões particularmente importantes, numa altura a qualidade do software se vem tornado, progressivamente, numa questão central. Trata-se portanto de uma UC particularmente relevante para o ciclo de estudos.

Não aplicável

CP1: Complexidade, classes, funções típicas e análise de algoritmos; CP2: Complexidade e recursividade (conjunto de problemas recursivos); CP3: Algoritmos de pesquisa e seleção; CP4: Algoritmos de ordenação: Insertion Sort, Heap Sort, Merge Sort e Quicksort; CP5: Comparação dos algoritmos de ordenação quanto à sua complexidade (programação do Quicksort); CP6: Tipos abstratos de dados: Pilha e Fila; CP7: array circular, listas simples e duplamente ligadas; CP8: Implementação de Pilha e Fila (programação em array e / ou listas); CP9: Funções de dispersão: aberta e fechada; CP10: Tabelas de hash (prática de utilização de Dicionários e Conjuntos); CP11: Árvore binária, árvores AVL e árvore preta e vermelha; CP12: Árvore binária (programação de árvore binária); CP13: Noções básicas de grafos: grafo orientado, não orientado e etiquetado, caminho e comprimento; CP14: Caminho mais curto entre dois vértices - Algoritmo de Dijkstra; CP15: Algoritmo de Dijkstra (programação).

M1: Ensino expositivo: A apresentação de conceitos teóricos é feita de forma expositiva através de slides. Disponibilizam-se num canal Educast da FCCN video-tutoriais curtos desenvolvidos sobre os conceitos chave da disciplina. M2: Ensino ativo: os conceitos teóricos são demonstrados recorrendo a "live coding" pelo docente. M3: Aprendizagem experimental: São usadas fichas em Jupyter Notebook que permitem a experimentação imediata dos conceitos lecionados. M4: Aprendizagem participativa: Durante as aulas é estimulada a discussão em grupo dos exercícios e projetos semanais. M5: Auto-avaliação: foi desenvolvida uma plataforma que permite realizar quizzes para avaliação de todos os conhecimentos, cuja solução submetida é validada de forma automática. M6: Aprendizagem orientada a projeto: são realizados de forma autónoma exercícios e projetos semanais com desafios exploratórios de aspectos complementares. M7: Avaliação contínua: fichas semanais, quizzes, projetos, minitestes e frequencias.

Tamassia, Roberto, Goldwasser, Michael H., Goodrich, Michael  T. - Data Structures and Algorithms in Python. First Edition. USA: Wiley, 2013 Cormen, Leiserson, Rivest e Stein - Algoritmos, Teoria e Prática, tradução da 3ª edição EUA, Elsevier Editora Ltd., 2012 Cormen, Thomas H. - Algorithms Unlocked. Cambridge, Massachusetts: MIT Press, 2013.