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.

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.