Compreender os fundamentos matemáticos para a análise de algoritmos por meio de ferramentas matemáticas e de implementações de soluções eficientes para problemas usuais nas aplicações computacionais. Ao final do curso o aluno dever ser capaz de:

1. Analisar a complexidade quanto aos recursos de tempo e espaço de algoritmos utilizando análise assintótica;
2. Provar a correção de algoritmos elementares;
3. Conhecer aos paradigmas de projeto por indução, divisão e conquista, algoritmos gulosos e programação dinâmica para o projeto de algoritmos;
4. Compreender os fundamentos da teoria de NP-completude.

• Fundamentos matemáticos para análise de algoritmos;
• Análise assintótica de algoritmos;
• Paradigmas de projeto de algoritmos;
• Algoritmos eficientes;
• Fundamentos de complexidade computacional.

O conteúdo será abordado por meio de atividades:

1. Leituras dirigidas que serão disponibilizadas na página web da disciplina¹ e/ou na plataforma Microsoft Teams institucional;
2. Assíncronas (videoaulas) que ficarão disponíveis na plataforma Youtube, e cujos links serão disponibilizados na página web da disciplina¹ e/ou na plataforma Microsoft Teams institucional;
3. Síncronas (aulas virtuais) via a plataforma Microsoft Teams institucional.

A plataforma institucional Microsoft Teams será utilizada para troca de mensagens e discussão de dúvidas.

A avaliação será composta das seguintes partes:

1. Atividades individuais a serem enviadas em prazo determinado.
   1. Serão 30 atividades, cada uma valendo 2 pontos, perfazendo um total de 60 pontos.
   2. Cada atividade individual será contabilizada como uma frequência, se enviada no prazo determinado; e contabilizada como falta da aula correspondente, se enviada com atraso ou se não for enviada.
   3. A pontuação de cada uma das 30 atividades será contabilizada como a seguir:
      • até 2 pontos, se enviada no prazo determinado;
      • até 1 ponto, se enviada em até 24 horas depois do prazo determinado;
      • 0, nas outras situações.
   4. As atividades individuais que não tenham sido realizadas por alguma razão amparada por lei poderão ser repostas no final do semestre por meio de uma avaliação envolvendo todo o conteúdo do semestre.
2. Uma avaliação escrita individual a ser enviada em formato pdf em prazo determinado, perfazendo um total de 10 pontos.
3. Uma formalização (a ser feita individualmente ou em dupla) a ser feita no assistente de provas Coq, e enviada pela plataforma GitHub em prazo determinado, perfazendo um total de 30 pontos.

Para ser aprovado o aluno deve cumprir simultaneamente os seguintes itens:

• Frequência maior ou igual a 75% nas aulas;
• Obter pelo menos 50 pontos considerando as duas etapas de avaliação do curso.

A menção final é definida como a seguir:

A referência principal é cormenIntroductionAlgorithmsThird2009. Materiais de leitura complementar serão disponibilizados no ambiente virtual, assim como links para outras referências que estiverem disponíveis na internet.

Bibliografia complementar: baaseComputerAlgorithmsIntroduction1999,levitinIntroductionDesignAnalysis2012,manberIntroductionAlgorithmsCreative1989,roughgardenAlgorithmsIlluminatedPart2017,roughgardenAlgorithmsIlluminatedPart2018,roughgardenAlgorithmsIlluminatedPart2019.

Bibliography

• [cormenIntroductionAlgorithmsThird2009] Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Third Edition, The MIT Press (2009).
• [baaseComputerAlgorithmsIntroduction1999] Baase & Gelder, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley Longman Publishing Co., Inc. (1999).
• [levitinIntroductionDesignAnalysis2012] Levitin, Introduction to the Design and Analysis of Algorithms, Third Edition, Addison-Wesley Longman Publishing Co., Inc. (2012).
• [manberIntroductionAlgorithmsCreative1989] Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA (1989).
• [roughgardenAlgorithmsIlluminatedPart2017] Roughgarden, Algorithms Illuminated (Part 1): The Basics, Soundlikeyourself Publishing, LLC (2017).
• [roughgardenAlgorithmsIlluminatedPart2018] Roughgarden, Algorithms Illuminated (Part 2): Graph Algorithms and Data Structures (Volume 2), Soundlikeyourself Publishing, LLC (2018).
• [roughgardenAlgorithmsIlluminatedPart2019] Roughgarden, Algorithms Illuminated (Part 3): Greedy Algorithms and Dynamic Programming, Soundlikeyourself Publishing, LLC (2019).