PGCC006 > Plano de Ensino

PGCC 006 – Análise e Projeto de Algoritmos

Professor

João B. Rocha-Junior

Carga Horária 

60 horas 

Ementa

Análise da eficiência de algoritmos: uso da notação assintótica, relações de recorrência. Técnicas de projeto de algoritmos: força bruta, indução, divisão e conquista, programação dinâmica, método guloso. Algoritmos fundamentais para busca, ordenação e seleção. Limite inferior para ordenação com comparações. Algoritmos fundamentais para problemas em grafos: percursos em largura e em profundidade e suas aplicações, árvores mínimas, caminhos mínimos. 

Objetivos, Habilidades e Competências

• Saber analisar a eficiência de algoritmos;

• Conhecer as principais técnicas de projeto de algoritmos;

• Conhecer os principais algoritmos para busca e ordenação;

• Conhecer os algoritmos fundamentais para problemas em grafos.

Conteúdo Programático

• Introdução à algoritmos (algoritmos vs. programa)

• Pseudocódigo

• Análise de algoritmos

  • Notação assintótica

  • Relações de recorrência

  • Teorema mestre

• Algoritmos de busca

  • Busca linear

  • Busca binária

• Estruturas de dados avançadas

  • Fila com prioridade

  • Heap

• Métodos de ordenação

  • SelectionSort

  • BubbleSort

  • InsertionSort

  • MergeSort

  • HeapSort

  • QuickSort

• Limite inferior para ordenação com comparações

• Grafos

  • Terminologia e implementação

  • Grafos orientados e não orientados

  • Percurso em largura e profundidade

  • Árvores mínimas

  • Caminhos mínimos

• Técnicas de projeto de algoritmos

  • Força bruta

  • Indução

  • Dividir para conquistar

  • Programação dinâmica

  • Método guloso

Metodologia

A metodologia deste módulo será através de aulas expositivas e exercícios em sala de aula.

Material Utilizado

Salas de aula com quadro branco, kit para escrever nos quadros, computador e projetor multimídia.

Avaliação

O módulo será dividido em três unidades, para que o estudante possa refletir sobre sua situação em diferentes momentos do curso e, caso necessário, realizar correções de rumo no processo de aprendizagem.

Três avaliações, uma para cada unidade. 

• Primeira unidade

  • Prova escrita, valendo 90% da nota da primeira unidade

  • Atividades, valendo 10% da nota

• Segunda unidade

  • Prova escrita, valendo 80% da nota da segunda unidade

  • Atividades, valendo 20% da nota da segunda unidade

• Terceira unidade

  • Prova escrita, valendo 70% da nota da terceira unidade

  • Atividades, valendo 30% da nota da terceira unidade

Média final

A média final será a média aritmética das medidas de cada unidade. Obtendo média igual ou superior a 7,0 (sete), o estudante pode ser aprovado, caso cumpra os requisitos de frequência. Média inferior a 7,0, o estudante é reprovado.  

Aprovação no módulo

Para ser aprovado no módulo, o estudante precisa cumprir os seguintes requisitos: ter frequência igual ou superior a 75% da carga horária efetiva ministrada no módulo, caso contrário haverá reprovação por frequência; ser aprovado na avaliação do módulo, caso contrário haverá reprovação por nota.

Referências

• CORMEN, T.H., LEISERSON, C.E., RIVEST, R.L. e STEIN, C. Algoritmos, terceira edição, Elsevier, 2012.

• GOODRICH, M.T. e TAMASSIA, R. Estruturas de Dados e Algoritmos em Java, segunda edição, Bookman, 2002.

• MANBER, U., Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.

• PREISS, B. R. Estruturas de Dados e Algoritmos, Campus, 2001.

• SEDGEWICK, Robert. Algorithms. Pearson Education, 1988.