Plano de Ensino
Projeto e Análise de Algoritmos - 2020/2

Compreender os fundamentos teóricos para a análise de algoritmos por meio de ferramentas matemáticas que permitam a construção 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 a análise assintótica;
2. Provar a correção de algoritmos;
3. Conhecer os paradigmas de projeto por indução, divisão e conquista, algoritmos gulosos e programação dinâmica para projetos 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:

1. Leituras dirigidas que serão disponibilizadas na página web da disciplina¹ e/ou na plataforma Microsoft Teams institucional;
2. Atividades 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. Atividades 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 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 é cite: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: cite:baaseComputerAlgorithmsIntroduction1999,levitinIntroductionDesignAnalysis2012,manberIntroductionAlgorithmsCreative1989,roughgardenAlgorithmsIlluminatedPart2017,roughgardenAlgorithmsIlluminatedPart2018,roughgardenAlgorithmsIlluminatedPart2019.

bibliographystyle:unsrt bibliography:/Users/flaviomoura/beorg/org/zotLib.bib