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: Manuel M. Pita.
Projetos
-
Dados Complicados – Universidade do País Das Maravilhas
Projeto realizado com elevada interacção com o docente, tentando simular um ambiente real
Processar conteúdo para varias fontes de dados (bases de dados, ficheiros de texto)Identificar dados estranhos ou inválidosDescobrir quais os dados para considerar com ajuda do “data scientist”
Produzir data frames utilizando técnicas de data science
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).