MC558 - Design and Analysis of Algorithms II
MC558 - Projeto e Análise de Algoritmos II
MC558 - Proyecto y Análisis de Algoritmos II
This is an undergraduate course in Computer Science that aims to present the main concepts and algorithms in graphs, introduce classes of computational complexity (P, NP, NP-complete), and proofs of NP-completeness, as well as discuss basic notions of linear programming. It is expected that, by the end of the semester, the student will be able to solve computational problems by designing algorithms on graphs, proving their correctness, and analyzing their complexity. Additionally, the student should be capable of demonstrating the membership of problems in the NP-complete class and proposing linear programming models for some problems.
Esta é uma disciplina de graduação em Ciência da Computação que objetiva apresentar os principais conceitos e algoritmos em grafos, introduzir classes de complexidade computacional (P, NP, NP-completo) e provas de NP-completude, assim como discutir noções básicas de programação linear. Se espera que, no final do semestre, o aluno consiga resolver problemas computacionais projetando algoritmos em grafos, provando que são corretos e analisando sua complexidade; ademais de ser capaz de provar pertença de problemas à classe NP-completo e propor modelos de programação linear para alguns problemas.
Esta es una asignatura de pregrado en Ciencia de la Computación que tiene como objetivo presentar los conceptos y algoritmos principales en grafos, introducir clases de complejidad computacional (P, NP, NP-completo) y demostraciones de NP-completitud, así como discutir nociones básicas de programación lineal. Se espera que, al final del semestre, el estudiante pueda resolver problemas computacionales diseñando algoritmos en grafos, demostrando su corrección y analizando su complejidad; además de ser capaz de demostrar la pertenencia de problemas a la clase NP-completo y proponer modelos de programación lineal para algunos problemas.
Offering: Summer of 2024, from 08/01/2024 to 09/02/2024Oferecimento: Verão de 2024, do 08/01/2024 ao 09/02/2024Oferta: Vernao de 2024, del 08/01/2024 al 09/02/2024
Schedule: From Monday to Friday, from 2:00PM. to 5:20PM.Horário: De segunda-feira a sexta-feira, das 14:00 às 17:20Horario: De lunes a viernes, de las 2:00PM. a las 5:20PM.
Location: Auditorium 85, IC2Local: Auditório 85, IC2Localización: Sala 85, IC2
Test 1: 23/01/2024 from 2:00PM. to 4:00PM. at Lab.305 - IC3
Prova 1: 23/01/2024 das 14:00 às 16:00 no Lab.305 - IC3
Prueba 1: 23/01/2024 de las 2:00PM. a las 4:00PM. en el Lab.305 - IC3
Beecrowd exercise: 29/01/2024 at Room 06 - IC1
Exercício do beecrowd: 29/01/2024 na Sala 06 - IC1
Ejercício del beecrowd: 29/01/2024 en la Sala 06 - IC1
Seminars: 07/02/2024 at Room 85 - IC2
Seminários: 07/02/2024 na Sala 85 - IC2
Seminarios: 07/02/2024 en la Sala 85 - IC2
Test 2: 09/02/2024 from 2:00PM. to 4:00PM. at Lab.300 - IC3
Prova 2: 09/02/2024 das 14:00 às 16:00 no Lab.300 - IC3
Prueba 2: 09/02/2024 de las 2:00PM. a las 4:00PM. en el Lab.300 - IC3
Final test: 15/02/2024 from 2:00PM. to 4:00PM. at Lab.300 - IC3
Exame: 15/02/2024 das 14:00 às 16:00 no Lab.300 - IC3
Exámen: 15/02/2024 de las 2:00PM. a las 4:00PM. en el Lab.300 - IC3
Bibliography
Bibliografia
Bibliografía
Main reference
Referência principal
Referencia principal
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
Two tests: P1 and P2. The final grade will be given by M=0.4P1+0.6P2. Students with M in [2.5,5) may take a final test (E); for those students the new final grade will be M=min{5,0.5M+0.5E}. Students with M greater than or equal to 5 will be approved.
Duas provas: P1 e P2. A média final será M=0.4P1+0.6P2. Alunos com M no intervalo [2.5,5) poderão fazer o exame (E) e, para eles, a nova média final será M=min{5,0.5M+0.5E}. Alunos com M maior ou igual que 5 estarão aprovados.
Dos pruebas: P1 y P2. La media final será M=0.4P1+0.6P2. Alumnos con M en el intervalo [2.5,5) podrán realizar el exámen (E) y, para ellos, la nueva media final será M=min{5,0.5M+0.5E}. Alumnos con M mayor o igual que 5 estarán aprobados.
Dates and location: P1 - 23/01/2024 - Lab.305 - IC3. P2 - 09/02/2024 - Lab.300 - IC3. E - 15/02/2024 - Lab.300 - IC3.
Datas e local: P1 - 23/01/2024 - Lab.305 - IC3. P2 - 09/02/2024 - Lab.300 - IC3. E - 15/02/2024 - Lab.300 - IC3.
Fechas y lugar: P1 - 23/01/2024 - Lab.305 - IC3. P2 - 09/02/2024 - Lab.300 - IC3. E - 15/02/2024 - Lab.300 - IC3.
The submission of exercise lists before the resolution and active participation in solving exercises during class may be considered to improve the grade.
A entrega de listas de exercícios antes da resolução e a participação da resolução de exercícios em aula, poderão ser coniseradas para melhorar a nota.
La entrega de listas de ejercicios antes da resolución y la participación de la resolución de ejercicios en clase, podrán ser coniserados para mejorar la nota.
Exercises solved in exams or submitted in the lists must be done individually. Any detection of fraud will result in a grade of zero.
Exercícios resolvidos nas provas ou entregues nas listas, devem ser feitos individualmente. Qualquer detecção de fraude implicará em zerar a nota.
Los ejercicios resueltos en las pruebas o entregados en las listas deben realizarse de forma individual. Cualquier detección de fraude implicará la anulación de la nota.
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í.