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
2 testes de igual valor (70%) com nota mínima de 7,5 valores na média dos 2 testes; 3 mini-projectos de igual valor (30%);
Tipo
Não Estruturante
Regime
Semestral
Carga Horária
1º Semestre
3.0 h/semana
1.5 h/semana
147.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; Fundamentos matemáticos para análise de algoritmos; Revisão de algoritmos de ordenação: Mergesort; Heapsort; Quicksort; algoritmos de ordenação não baseados em comparação; Revisão de estruturas de dados: Listas; Pilhas; Filas; Tabelas de dispersão; Árvores de procura binária; Árvores equilibradas; Análise amortizada. Exemplos de aplicação: Amontoados Binomiais; Introdução à Geometria Computacional. Algoritmos em grafos: Algoritmos elementares; Árvores abrangentes de menor custo; Caminhos mais curtos; Fluxos máximos; Introdução à Programação Linear: Algoritmo Simplex; Técnicas de síntese de algoritmos: Programação dinâmica; Algoritmos gananciosos; Algoritmos para emparelhamentos máximos; Introdução à complexidade: Classes P e NP; Problemas NP-completos; Teorema de Cook; Estudo de alguns problemas NP-completos; Algoritmos de aproximação para problemas NP-díficeis;
Metodologia de avaliação
2 testes de igual valor (70%) com nota mínima de 7,5 valores na média dos 2 testes; 3 mini-projectos de igual valor (30%);
Pré-requisitos
Componente Laboratorial
Princípios Éticos
Componente de Programação e Computação
Componente de Competências Transversais
Bibliografia
Principal
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford St
Introduction to Algorithms, Second Edition
Thomas H. Cormen, CharlesE. Leiserson, Ronald L. Rivest e Clifford Stein, 2001,
MIT Press - ISBN: 0-262-03293-7