Disciplina

Á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

September 2009

ISBN-10: 0-262-53305-7; ISBN-13: 978-0-262-53305-8