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 100% da nota da primeira unidade
Segunda unidade
Prova escrita, valendo 70% da nota da segunda unidade
Atividades (Classroom), valendo 30% da nota da segunda unidade
Terceira unidade
Prova escrita, valendo 50% da nota da terceira unidade
Projetos (Classroom), valendo 50% 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.