Ficha Unidade Curricular (FUC)

Informação Geral / General Information

Carga Horária / Course Load

Área científica / Scientific area

Ciências e Tecnologias da Programação

Departamento / Department

Departamento de Ciências e Tecnologias da Informação

Ano letivo / Execution Year

2024/2025

Pré-requisitos / Pre-Requisites

Conhecimentos básicos de programação em Python.

Objetivos Gerais / Objectives

Esta disciplina introduz conceitos importantes de estruturas de dados, de algoritmos e de eficiência algorítmica. Estes conceitos são introduzidos numa perspetiva de desenvolver e encorajar, nos estudantes, o pensamento crítico. Do ponto de vista do desenvolvimento de software, pretende-se uma consolidação do desenvolvimento de software de uma forma estruturada e segundo o paradigma de orientação a objetos. Serão apresentadas e utilizadas estruturas clássicas de organização de dados (lineares e não-lineares) e algoritmos associados, bem como algoritmos clássicos de procura e estruturação, numa perspetiva de resolver problemas de uma forma eficiente. Caso o tempo o permita, tópicos adicionais poderão ser abordados. A componente prática de programação, com recurso à linguagem de programação Python, é essencial. Serão introduzidas práticas de trabalho centrados na gestão de dados.

Objetivos de Aprendizagem e a sua compatibilidade com o método de ensino (conhecimentos, aptidões e competências a desenvolver pelos estudantes) / Learning outcomes

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.

Conteúdos Programáticos / Syllabus

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.

Demonstração da coerência dos conteúdos programáticos com os objetivos de aprendizagem da UC / Evidence that the curricular units content dovetails with the specified learning outcomes

No seu conjunto, os conteúdos programáticos propostos (CP1 a CP9) permitem ganhar conhecimento e experiência para identificar, reescrever e examinar formas comuns de organização de dados e algoritmos, propor e analisar estruturas de dados alternativas e resolver eficientemente novos problemas, os objetivos de aprendizagem propostos em OA1, OA2 e OA3. Especificamente o conteúdo programático CP5, mas também CP6 e CP7, permitem ganhar conhecimentos e experimentar o que são, e as diferenças entre algoritmos iterativos e recursivos, contribuindo para o objetivo de aprendizagem OA4. Os conteúdos programáticos CP4, CP6 a CP7 apresentam os principais algoritmos de pesquisa e ordenação implementados de formas diferentes, contribuindo para objetivo de aprendizagem OA5.

Avaliação / Assessment

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.

Metodologias de Ensino / Teaching methodologies

Serão utilizadas as seguintes metodologias de ensino-aprendizagem (MEA): MEA1: Expositivas, para apresentação do enquadramento teórico MEA2: Ilustrativas, para exemplificação dos conceitos teóricos em contextos reais MEA3: Argumentativas, com apresentação e discussão de trabalhos individuais ou de grupo. MEA4: Ativas, com resolução prática pelos estudantes de exercícios de aplicação, quer em trabalho autónomo dos estudantes, quer acompanhados pelos professores.

Demonstração da coerência das metodologias de ensino e avaliação com os objetivos de aprendizagem da UC / Evidence that the teaching and assessment methodologies are appropriate for the learning outcomes

Esta UC requer conceitos teóricos, fundamentais para a compreensão dos diferentes conteúdos programáticos, pelo que a parte teórica das aulas teóricao-práticas é fundamental para explorar e consolidar os conceitos base necessários para todos os objetivos de aprendizagem. As aulas prático-laboratoriais permitem a experimentação prática (em particular usando programação em Python) e a aplicação de conhecimentos, o que também implica trabalho autónomo por parte do estudante. As metodologias de ensino usadas prioritizam a aquisição de conhecimentos de um modo ativo e através da resolução de problemas/projetos, de modo a consolidar o conhecimento e adquirir competências.

Observações / Observations

Bibliografia Principal / Main Bibliography

- 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.

Bibliografia Secundária / Secondary Bibliography

- 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.

Data da última atualização / Last Update Date

2024-08-09