Ementa de Disciplina

INF1721 | ANALISE DE ALGORITMOS

4 créditos

Ementa

Conceitos Básicos: motivação e solução de problemas, critérios de análise, correção e eficiência. Análise de Algoritmos: tempo de processamento e operações elementares, complexidade de pior caso, algoritmos polinomiais, comparação de algoritmos, algoritmos recursivos, algoritmos pseudo-polinomiais. Algoritmos e estruturas de dados para problemas em grafos: componentes conexas, planaridade, coloração, árvores geradoras de peso mínimo, caminhos mais curtos, caminhos críticos, fluxo máximo, aplicações. Teoria da Complexidade: problemas de decisão, transformações polinomiais, classe P, algoritmos não-determinísticos, classe NP e Co-NP, problemas NP-completos, classe P-space.

Bibliografia

CORMEN, T. H. ALGORITMOS: TEORIA E PRÁTICA; RIO DE JANEIRO: CAMPUS, 2002. KLEINBERG, JON; TARDOS, ÉVA. ALGORITHM DESIGN; BOSTON: PEARSON EDUCATION, 2005. DASGUPTA, SANJOY; PAPADIMITRIOU, CHRISTOS H.; VAZIRANI, UMESH. ALGORITHMS; BOSTON: MCGRAW HILL BOOK COMPANY, 2008.

Bibliografia Complementar

Nenhuma biliografia complementar encontrada para INF1721

Pré-requisitos

INF1006 e INF1631

ou

INF1007 e INF1631

ou

INF1010 e INF1308

ou

INF1010 e INF1631

ou

INF1037 e INF1631

ou

INF1308 e INF1389

ou

INF1389 e INF1631

ou

INF1620 e INF1631

Co-requisitos

Nenhum co-requisito encontrado para INF1721

Última atualização da ementa: 07/02/2014