Análise de Algoritmos – TIN0118 – BSI

Obrigatória – 60 horas – 4 créditos
Pré-requisitos: Estruturas de Dados II
Professor Responsável: Vânia Maria Félix Dias

Objetivos da Disciplina

Capacitar o aluno a analisar, avaliar e comparar a eficiência computacional de algoritmos. Qualificar o aluno no conhecimento de técnicas de projeto de algoritmos eficientes, quando possível, e na identificação da estratégia mais indicada em cada caso. Habilitar o aluno na identificação e reconhecimento de classificação da complexidade de problemas computacionais.

Ementa

Critérios de análise, correção e eficiência. Análise de algoritmos: tempo de processamento e número de operações elementares, complexidade de pior caso. Algoritmos e estruturas de dados para problemas em grafos. Teoria da Complexidade: problemas de decisão, transformações polinomiais, classe P, algoritmos não determinísticos, classes NP e NP-completa.

Conteúdo Programático

Ordem de Grandeza das Funções
- Classes e Notação Assintótica
- Complexidades de Caso Médio e Pior Caso
Análises de Corretude e de Complexidade de Tempo em Algoritmos de Ordenação por comparações
- Merge Sort
- Insertion Sort
- Bubble Sort
- Quick Sort
- Heap Sort
Divisão e Conquista
- Definição e Aplicabilidade
- Recursão e Recorrência
- Algoritmos:
  - MergeSort
  - Mediana
  - Multiplicação de Matrizes
- Técnicas de solução de Equações de Recorrência
- Teorema Mestre
Algoritmos Gulosos: definição e aplicabilidade
- Problema da Árvore Geradora
- Mínima
- Problema da Mochila Fracionário
- Códigos de Huffman
Programação Dinâmica: definição e aplicabilidade
- Algoritmos:
  - Problema da Subsequência Crescente Máxima
  - Problema da Subsequência Comum mais Longa
  - Problema da Multiplicação de Cadeias de Matrizes
Representação de Grafos e Digrafos
- Modelagem de Problemas em Grafos
- Algoritmos: Problema do Caminho Mais Curto em grafos a partir de vértice único ou para todos os pares
  - Algoritmo de Dijikstra
  - Algoritmo de Bellman-Ford
  - Algoritmo de Floyd-Warshall
Classes de Problemas Computacionais
- Problemas de Decisão
- Problemas de Localização e Otimização
- A classe P
- As classes NP e Co-NP
- A classe NP-Completo
- Transformações Polinominais
- Demonstrações de alguns Problemas NP-Completos:
  - Clique
  - Cobertura de Vértices
  - Conjunto Independente
  - Ciclo Hamiltoniano
- Algoritmos Pseudo-Polinomiais

Metodologia

Exposição de conteúdo: nas aulas presenciais serão apresentados o conteúdo teórico e as diversas técnicas de projeto de algoritmos, através do uso intensivo de exemplos de solução de problemas utilizando cada uma das técnicas estudadas.
Aprendizagem colaborativa: para o entendimento do conteúdo serão apresentados problemas cujas soluções serão propostas e discutidas pelos alunos.
Aprendizagem baseada em projeto: a partir dos exemplos de problemas computacionais e técnicas de solução apresentados em sala, o aluno deverá desenvolver projetos de algoritmos para a solução de problemas propostos.

Avaliação

Avaliação contínua: ao longo da disciplina, o estudante apresentará em grupo aproximadamente 5 projetos de algoritmos, um para cada problema proposto, sendo cada um dos problemas correspondente a uma técnica específica de projeto de algoritmos estudada.
Avaliação somativa: ao longo da disciplina haverão duas avaliações com o objetivo de avaliar pontos específicos do conteúdo programático de forma individual.
Cálculo da nota final: (média dos trabalhos intermediários) / 2 + (média das provas) / 2.
Para ser aprovado na disciplina, o aluno precisa obter nota final acima de 5.

Bibliografia

CORMEN, Thomas H., LEISERSON, Charles E., RIVEST, Ronald L., STEIN, Clifford. Algoritmos: Teoria e Prática. Rio de Janeiro: Editora Campus, 2002.
CORMEN, T.H.; LEISERSON, C.E.; & RIVEST, R.L.; STEIN, C. Introduction to Algorithms 3rd Ed.. The MIT Press, 2009.
DASGUPTA , S.; PAPADIMITRIOU , C.H.; VAZIRANI , U.V. Algorithms, McGraw-Hill, 2006.
KLEINBERG, Jon; TARDOS, Éva. Algorithm Design, Addison-Wesley, 2005.
CORMEN, T.H. Algorithms Demystified, MIT Press, 2012.