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
2022/2023
Pré-requisitos / Pre-Requisites
Conhecimentos previstos na UC de Introdução à Programação
Objetivos Gerais / Objectives
A disciplina aprofunda técnicas de conceção e desenvolvimento de algoritmos e estruturas de dados e introduz a análise da complexidade de algoritmos. São apresentados algoritmos de pesquisa e ordenação baseados em estruturas de dados elementares concebidas para suportar operações eficientes e computacionalmente exequíveis. A disciplina segue diretamente a estrutura de curso apresentada em Sedgewick, R. and Wayne, K. (2011) e disponível em Coursera.org.
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
Concluída a disciplina o aluno deverá ser capaz de: OA1. Compreender algoritmos de ordenação e pesquisa apropriados a soluções computacionais; OA2. 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); OA3. Estimar a complexidade e desempenho de algoritmos sobre estruturas de dados alternativas, OA4. Esboçar novas formas de organização de dados e algoritmos associados adequadas a novos problemas computacionais.
Conteúdos Programáticos / Syllabus
CP1. O problema Union-Find CP2. Análise de Algoritmos CP3. Stacks, Filas, Listas e Sacos CP4. Filas Prioritárias CP5. Tabelas de Símbolos Elementares CP6. Árvores de Pesquisa Equilibradas CP7. Tabelas de Dispersão CP8. Ordenação Elementar: Selectionsort; Insertionsort; Shellsort CP9. Ordenação Avançada: Mergesort; Quicksort; Heapsort CP10. Complexidade dos problemas de ordenação
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
Objectivos de aprendizagem - Conteúdos programáticos OA1 - CP2 a CP10; OA2 - CP3 a CP7; OA3 - CP2 a CP10; OA4 - CP1 a CP10
Avaliação / Assessment
Avaliação Periódica: 10 avaliações semanais online (10%) + 10 exercícios semanais de programação (20%) + 2 avaliações intercalares individuais (70%) + 1 projeto individual de programação (classificações A,B,C,D). As notas do projeto são qualitativas e definem um limite para a nota final à UC: A - max. 20; B - max. 17; C - max. 13; D - reprovado. ou Exame Final individual (100%)
Metodologias de Ensino / Teaching methodologies
Aulas teóricas, práticas e aprendizagem independente através de cursos abertos online em Cousera.org
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
As aulas práticas e teóricas desenvolvem a capacidade de interpretação e programação de algoritmos. Nas aulas teóricas descrevem-se conceitos e casos de algoritmos e estruturas de dados, desenvolve-se a capacidade de análise de complexidade, caso a caso e apoia-se a exploração do curso OOC Coursera de referência com vista à autoaprendizagem. Nas aulas práticas são exercitados os conceitos expostos nas aulas teóricas através do desenvolvimento de novas formas de organização de dados e algoritmos associados.
Observações / Observations
.
Bibliografia Principal / Main Bibliography
(Algorithms, Part I - MOOC in www.coursera.org) R. Sedgewick and K. Wayne, Algorithms, 4th edition, Addison-Wesley, 2012
Bibliografia Secundária / Secondary Bibliography
D. Harel, Algorithmics: the Spirit of Computing, 3th edition, Addison-Wesley, 2004 F. Santos and C. Conti, Algoritmos e Estruturas de Dados - Exercícios, ISCTE-IUL, 2022.
Data da última atualização / Last Update Date
2024-02-16