Disciplina
Análise e Síntese de Algoritmos
Área
Área Científica de Metodologia e Tecnologias da Programação > Algoritmia
Activa nos planos curriculares
LEIC-T 2021 > LEIC-T 2021 > 1º Ciclo > Área Principal > Análise e Síntese de Algoritmos
LEIC-A 2021 > LEIC-A 2021 > 1º Ciclo > Área Principal > Análise e Síntese de Algoritmos
MEGE > MEGE > 2º Ciclo > Formação Livre > Análise e Síntese de Algoritmos
MEIC-T 2006 > MEIC-T 2006 > 2º Ciclo > Áreas de Especialização Complementares > Fundamentos de Engenharia Informática > Análise e Síntese de Algoritmos
MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Fundamentos de Engenharia Informática > Análise e Síntese de Algoritmos
MERC 2006 > MERC 2006 > 2º Ciclo > Opções > Análise e Síntese de Algoritmos
LEIC-A 2006 > LEIC-A 2006 > 1º Ciclo > Ciências da Engenharia Informática > Análise e Síntese de Algoritmos
LEIC-T 2006 > LEIC-T 2006 > 1º Ciclo > Ciências da Engenharia Informática > Análise e Síntese de Algoritmos
Nível
Exame e componente prática. O exame contribui com 60% para a nota final (FM) e o aluno tem de obter pelo menos 7.5 valores num dos exames. A componente prática contribui 40% para a nota final (FM).
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
2.5 h/semana
1.5 h/semana
112.0 h/semestre
Objectivos
Formação de nível intermédio em algoritmia e complexidade, familiarizando os alunos com técnicas de análise e síntese de algoritmos e estruturas de dados. Conhecimento dos fundamentos da análise e síntese de algoritmos. Análise da realização prática de algoritmos e estruturas de dados. Perspectiva abrangente das aplicações dos algoritmos em Engenharia Informática.
Programa
Introdução à análise e síntese de algoritmos. Revisão de algoritmos de ordenação. Revisão de estruturas de dados: listas; pilhas; filas; filas com prioridade; tabelas de dispersão; árvores de procura binária; árvores equilibradas. Análise amortizada, e exemplos de aplicação. Algoritmos em grafos: algoritmos elementares, árvores abrangentes de menor custo, caminhos mais curtos, fluxos máximos. Introdução à Programação Linear e o algoritmo Simplex. Técnicas de síntese de algoritmos: programação dinâmica e algoritmos gananciosos. Algoritmos para emparelhamento de cadeias de caracteres. Complexidade computacional e caracterização de problemas. Classes de problemas P, NP, NP-completos e NP-díficeis.
Metodologia de avaliação
Exame e componente prática. O exame contribui com 60% para a nota final (FM) e o aluno tem de obter pelo menos 7.5 valores num dos exames. A componente prática contribui 40% para a nota final (FM).
Pré-requisitos
Introdução aos Algoritmos e Estruturas de Dados
Componente Laboratorial
Exercícios e problemas a resolver em todas as aulas no seguimento das matérias aprendidas nas aulas teóricas.
Princípios Éticos
Todos os membros de um grupo são responsáveis pelo trabalho do grupo. Em qualquer avaliação, todo aluno deve divulgar honestamente qualquer ajuda recebida e fontes usadas. Numa avaliação oral, todo aluno deverá ser capaz de apresentar e responder a perguntas sobre toda a avaliação.
Componente de Programação e Computação
No curso onde esta UC é oferecida estão asseguradas as componentes de Computação e Programação de acordo com o MEPP 2122.
Componente de Competências Transversais
Não existindo uma componente explícita de Competências Transversais a desenvolver no âmbito desta UC, o desenvolvimento da componente prática levará ao desenvolvimento de Pensamento Crítico e Inovador e Competências Intrapessoais.
Bibliografia
Principal
Introduction to Algorithms, Third Edition
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
ISBN-10: 0-262-53305-7; ISBN-13: 978-0-262-53305-8