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

Os conteúdos programáticos CP2 a CP10 referem os principais algoritmos de ordenação e pesquisa, suas vantagens e limitações, contribuindo assim para a compreensão das condições da sua aplicação na resolução de problemas computacionais propostas no objetivo de aprendizagem OA1; Os conteúdos programáticos CP3 a CP7 apresentam os principais algoritmos de ordenação e pesquisa implementados de formas diferentes, contribuindo assim para o entendimento completo de várias formas diferentes de os implementar, referido no objetivo de aprendizagem O2; No seu conjunto, os conteúdos programáticos propostos permitem ganhar experiência para propor e analizar estruturas de dados alternativas e resolver eficientemente novos problemas, os objetivos de aprendizagem propostos OA3 e OA4.

Avaliação / Assessment

Avaliação ao longo do semestre: 10 exercícios individuais de programação (25%), sem nota mínima e entregues semanalmente e dois testes escritos (75 %), o primeiro a meio do semestre e o segundo coincidindo com o exame de 1ª época. Cada um dos testes escritos tem nota mínima de 7,5 valores. A presença nas aulas não é obrigatória. ou Exame final individual(100%) – 1ª época, 2ª época e Época Especial

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-07-25