Currículo
Estruturas de Dados e Algoritmos 03587
Contextos
Groupo: Ciência de Dados - PL > 1º Ciclo > Unidades Curriculares Obrigatórias
ECTS
6.0 (para cálculo da média)
Objectivos
No final da UC os alunos deverão ser capazes de: OA1. Identificar, reescrever e examinar formas comuns de organização de dados e algoritmos associados (com e sem gestão dinâmica de memória, com algoritmos iterativos ou recursivos); OA2: Saber avaliar e comparar a ordem de desempenho e eficiência de uma dada estrutura de dados e/ou algoritmo para as operações de inserção, remoção e acesso; OA3: Identificar a estrutura de dados mais apropriada e eficiente para um determinado problema; OA4: Perceber as vantagens e desvantagens de algoritmos recursivos, iterativos e técnicas de programação dinâmica; OA5. Compreender diferentes algoritmos de pesquisa e ordenação apropriados a soluções computacionais.
Programa
CP1: Estruturas de Dados e Algoritmos: o que são e por que são importantes. Tipos Abstratos de Dados. CP2: Estruturas de dados lineares: pilhas, filas, listas e listas ligadas. CP3: Introdução à análise da complexidade (eficiência) de algoritmos. CP4: Algoritmos de pesquisa: linear e binária. CP5: Recursão, iteração e programação dinâmica. CP6: Algoritmos de ordenação elementar: Selectionsort, Insertionsort. CP7. Algoritmos de ordenação avançada: Mergesort, Quicksort. CP8: Estruturas de dados não lineares: árvores, árvores de pesquisa binária, árvores AVL e grafos. CP9: Algoritmos simples sobre estruturas de dados não lineares.
Método de Avaliação
A aprovação nesta unidade curricular (UC) só pode ser conseguida pela modalidade de avaliação ao longo do semestre ou pela época especial (para os alunos com algum estatuto conferido pelos Serviços de Gestão do Ensino que permita aceder a Época Especial). Não existe para esta UC a modalidade de avaliação por exame. Elementos de avaliação e respetivas ponderações na nota final: - teste 1, escrito individual -> 30%, nota mínima de 8 valores, previsto realizar no período de avaliações do 3º trimestre; - teste 2, escrito individual -> 30%, nota mínima de 8 valores, previsto realizar no período de avaliações da 1a época; - trabalho 1, individual, com discussão -> 15%; - trabalho 2, individual, com discussão (eventualmente em grupos de 2 alunos) -> 25%, nota mínima de 8 valores. Assim Nota_final = 30% x Nota_teste1 + 30% x Nota_teste2 + 15% x Nota_trabalho1 + 25% x Nota_trabalho2. Em Época Especial, os elementos de avaliação e respetivas ponderações na nota final são: - teste, escrito individual -> 60%, nota mínima de 8 valores, e - dois trabalhos, individuais -> 15% + 25%, nota mínima de 8 valores em cada um dos trabalhos. Assim Nota_final_época_especial = 60% x Nota_teste + 15% x Nota_trabalho1 + 25% x Nota_trabalho2. Para obter aprovação na UC a Nota_final ou a Nota_final_época_especial têm que ser 10 valores em 20 valores.
Carga Horária
Carga Horária de Contacto -
Trabalho Autónomo - 113.0
Carga Total -
Bibliografia
Principal
- - J. Wengrow, A Common-Sense Guide to Data Structures and Algorithms, Second Edition. The Pragmatic Bookshelf, 2020. - M. Goodrich, R. Tamassia, and M. Goldwasser, Data Structures & Algorithms in Python. Wiley, 2013.:
Secundária
- - B. Miller and D. Ranum, Problem Solving with Algorithms and Data Structures using Python, Second Edition, Release 3.0. 2013. - T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, Fourth Edition. MIT Press, 2022. - Referências adicionais a indicar durante as aulas.: