MO417 - Complexity of Algorithms I
MO417 - Complexidade de Algoritmos I
MO417 - Complejidad de Algoritmos I
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.
Offering: 1st semester of 2024Oferecimento: 1ro semestre de 2024Oferta: 1er semestre de 2024
Schedule: Tuesday and Thursday, from 4:00PM. to 6:00PM.Horário: Terça-feira e Quinta-feira, das 16:00 às 18:00Horario: Martes y Jueves, de las 4:00PM. a las 6:00PM.
Location: Local: Localización: CC51
Bibliography
Bibliografia
Bibliografía
Main references
Referências principais
Referencias principales
Complementary references
Referências complementares
Referencias complementares
Lectures
Aulas
Clases
The slides will be added after each lecture. These can be used as a guide to review the lessons. To study and practice, you should read the main bibliography and solve the suggested exercises.
Os slides serão disponilizados após cada aula. Estes podem ser usados como guia para revisar as aulas. Para estudar e praticar, devem ler a bibliografia principal e resolver os exercícios sugeridos.
Los slides serán disponibilizados después de cada clase. Estos pueden ser utilizados como guía para revisar las lecciones. Para estudiar y practicar, deben leer la bibliografía principal y resolver los ejercicios sugeridos
Acknowledgment: The slides are based on the material prepared by other professores. The list of professors that kindly provided the material is given below (in alphabetical order): Cândida Nunes da Silva, Cid Carvalho de Souza, Flávio Keidi Miyazawa, Lehilton Lelis Chaves Pedrosa e Orlando Lee. The slides that will be shared has been adapted and modified by me, with possible introduction of errors, which I request to be reported to me.
Agradecimentos: Os slides foram baseados em material didático preparado por outros professores. A lista dos professores que gentilmente cederam o material é dada a seguir (em ordem alfabética): Cândida Nunes da Silva, Cid Carvalho de Souza, Flávio Keidi Miyazawa, Lehilton Lelis Chaves Pedrosa e Orlando Lee. O material que será disponibilizado foi adaptado e modificado por mim, com possível introdução de erros, que solicito sejam reportados a mim.
Agradecimientos: Los slides se basearon en material didáctico preparado por otros profesores. La lista de los profesores que amablemente proporcionaron el material es la siguiente (en orden alfabética): Cândida Nunes da Silva, Cid Carvalho de Souza, Flávio Keidi Miyazawa, Lehilton Lelis Chaves Pedrosa e Orlando Lee. El material que se proporcionará fue adaptado y modificado por mí, con posible introducción de errores, que solicito sean reportados a mí.
Exercises lists
Listas de exercícios
Listas de ejercicios
The files will be added during the course.
Os arquivos serão adicionados durante o curso.
Los archivos serán adicionados durante el curso.
Grades
Notas
Notas
Evaluation method
Método de avaliação
Método de evaluación
Three tests: P1, P2 and P3. Two exercises lists: E1 and E2. One report: R. The average grade will be given by M=0.2P1+0.2P2+0.3P3+0.1E1+0.1E2+0.1R. The final grades will be: A if M in [8.5,10], B if M in [7,8.5), C if M in [5,7), and D if M in [0,5).
Três provas: P1, P2 e P3. Duas entregas: E1 and E2. Um relatório: R. A média será dada por M=0.2P1+0.2P2+0.3P3+0.1E1+0.1E2+0.1R. O conceito final será: A se M está em [8.5,10], B se M está em [7,8.5), C se M está em [5,7) e D se M está em [0,5).
Tres pruebas: P1, P2 y P3. Dos entregas: E1 and E2. Un relatorio: R. La media será dada por M=0.2P1+0.2P2+0.3P3+0.1E1+0.1E2+0.1R. La nota final será: A si M está en [8.5,10], B si M está en [7,8.5), C si M está en [5,7), y D si M está en [0,5).
Dates: P1 - 30/04/2024. P2 - 30/05/2024. P3 - 27/06/2024.
Datas: P1 -30/04/2024. P2 - 30/05/2024. P3 - 27/06/2024.
Fechas: P1 - 30/04/2024. P2 - 30/05/2024. P3 - 27/06/2024.
Any detection of fraud will result in a grade of D.
Qualquer detecção de fraude implicará em finalizar com conceito D.
Cualquier detección de fraude implicará terminar con nota D.
Files
Arquivos
Archivos
Attendance and grade files will be uploaded here.
Arquivos com as notas e a frequência serão disponibilizados aqui.
Archivos con las notas y la asiduez serán disponibilizados aquí.