Apresentação
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.
Docentes: Lucio Studer.
Programa
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).
Objetivos
OA1: Analisar e comparar a complexidade de algoritmos;
OA2: Aplicar a recursividade na resolução de problemas;
OA3: Explicar e usar alguns dos principais algoritmos de pesquisa, seleção e ordenação;
OA4: programar algoritmos de ordenação [aplicar o conhecimento (AC)];
OA5: Explicar e usar os tipos abstratos de dados: Pilha e Fila;
OA6: Programar uma Pilha e / ou Fila utilizando arrays ou listas (AC);
OA7: Explicar as funções de dispersão;
OA8: Usar as estruturas de dados Dicionários e Conjuntos na resolução de problemas (AC);
OA9: Explicar e usar as estruturas de dados: árvore binária, AVL e preta e vermelha;
OA10: Programar uma árvore binária (AC);
OA11: Explicar e dar exemplos da utilização de grafos na resolução de problemas;
OA12: Programar o algoritmo de Dijkstra (AC).