Análise e Projeto de Algoritmos

Disciplina Análise e Projeto de Algoritmos do Mestrado em Ciência da Computação.

Objetivos do curso

O curso tem dois objetivos básicos. O primeiro é ensinar o aluno a compreender e analisar algoritmos, em relação a aspectos como finitude, corretude, tempo de execução e outros parâmetros de execução. O segundo é proporcionar intuição a respeito de como projetar algoritmos eficientes, apresentando as principais estratégias para a construção de algoritmos. Conforme o perfil da turma e a disponibilidade de tempo, são apresentadas aplicações e tópicos contemporâneos em algoritmos, combinatória e complexidade computacional.

Ementa do curso

  • Análise de algoritmos
    • Conceito de Problema e Algoritmo
    • Tempo de execução e operações críticas
    • Complexidade assintótica – notações O, Theta e Omega
    • Recursão, indução, relações de recorrência
  • Paradigmas/Estratégias para projeto de Algoritmos
    • Divisão e conquista
    • Programação dinâmica
    • Algoritmos gulosos
    • Algoritmos aproximativos
    • Grafos e fluxo em redes
    • Algoritmos Randomizados
  • Classes de complexidade
    • Problemas de decisão
    • Classes P e NP
    • Problemas NP-Completos
    • Superclasses de NP
  • Tópicos em Algoritmos, Combinatória e Complexidade Computacional
    • Criptografia e Segurança da Informação
    • Geometria Computacional
    • Bioinformática e Biologia Computacional
    • Computação Quântica

Para maiores informações, acesse a página do curso no Moodle: