MO417

This is a graduate course in Computer Science that aims to present strategies for the design and analysis of algorithms, as well as to study the main concepts and algorithms in graphs. Additionally, it introduces classes of computational complexity (P, NP, NP-complete) and proofs of NP-completeness. It is expected that, by the end of the semester, the student will be able to solve computational problems by designing algorithms, proving their correctness, and analyzing their complexity. Furthermore, the student should be capable of demonstrating the membership of problems in the NP-complete class.

Esta é uma disciplina de pós-graduação em Ciência da Computação que tem como objetivo apresentar estratégias de projeto e análise de algoritmos, além de estudar os principais conceitos e algoritmos em grafos. Também se propõe a introduzir classes de complexidade computacional (P, NP, NP-completo) e provas de NP-completude. Espera-se que, ao final do semestre, o aluno seja capaz de resolver problemas computacionais projetando algoritmos, provando sua corretude e analisando sua complexidade. Além disso, espera-se que o aluno seja capaz de demonstrar a pertinência de problemas à classe NP-completo.

Esta es una asignatura de posgrado en Ciencia de la Computación que tiene como objetivo presentar estrategias de análisis y diseño de algoritmos, así como estudiar los principales conceptos y algoritmos en grafos. Además, se introducen clases de complejidad computacional (P, NP, NP-completo) y demostraciones de NP-completitud. Se espera que, al final del semestre, el estudiante pueda resolver problemas computacionales diseñando algoritmos, demostrando su corrección y analizando su complejidad; además de ser capaz de demostrar la pertenencia de problemas a la clase NP-completo.