Disciplina

Área

Área Científica de Metodologia e Tecnologia 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

105.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%);

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