Plano de Ensino
Projeto e Análise de Algoritmos (2021/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 a análise de algoritmos;
  • Indução finita;
  • Crescimento de funções;
  • Notação assintótica;
  • Relações de recorrência.
• Análise assintótica de algoritmos;
• Paradigmas de projeto de algoritmos;
  • Projeto por indução;
  • Divisão e conquista;
  • Programação dinâmica;
  • Algoritmos gulosos.
• Algoritmos eficientes para:
  • ordenação;
    • insertion-sort;
    • bubble-sort;
    • merge-sort;
    • heap-sort;
    • quick-sort.
  • problemas em grafos.
    • busca em largura e profundidade;
    • caminho mínimo e algoritmos de Dijkstra e Bellman-Ford;
    • árvore espalhada mínima e algoritmos e Prim e Kruskal;
    • todos os caminhos mínimos e algoritmo de Floyd-Warshall.
• Fundamentos de complexidade computacional.
  • Redução entre problemas;
  • As classes P e NP;
  • Problemas NP-completos.

O conteúdo será abordado por meio de:

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

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

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

1. Atividades a serem enviadas em prazo determinado, perfazendo um total de 70 pontos.
   1. Estas atividades serão propostas ao longo do semestre;
   2. A característica de cada atividade (pontuação, se é individual ou em grupo) será detalhada no momento em que a atividade for disponibilizada.
2. Um projeto, a ser feito em grupos de até 4 alunos, perfazendo um total de 30 pontos.

A frequência será contabilizada por meio de atividades disponibilizadas em cada aula. Cada atividade entregue no prazo contabiliza a frequência para a aula correspondente. Atividades entregues fora do prazo, ou não entregues contabilizam falta para a aula correspondente.

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

• Frequência maior ou igual a 75%;
• Obter pelo menos 50 pontos considerando as duas partes da avaliação do curso como descrito acima.

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

A referência principal é cite:cormenIntroductionAlgorithmsThird2009. Bibliografia complementar: cite:baaseComputerAlgorithmsIntroduction1999, cite:levitinIntroductionDesignAnalysis2012, cite:manberIntroductionAlgorithmsCreative1989, cite:roughgardenAlgorithmsIlluminatedPart2017, cite:roughgardenAlgorithmsIlluminatedPart2018, cite:roughgardenAlgorithmsIlluminatedPart2019.

bibliographystyle:plain bibliography:~/workspace/org/zotLib.bib