PAA+ +2019 01+ +Apresentacao

Prévia do material em texto

Projeto e Análise de Algoritmos
Apresentação do Curso
Jobson Massollar
jobson.silva@uva.br
Projeto e Análise de Algoritmos2
Objetivo do Curso
Capacitar os alunos a analisar o desempenho de
algoritmos, através da análise dos algoritmos
clássicos.
Capacitar os alunos a aplicar estratégias para o
projeto de algoritmos.
Projeto e Análise de Algoritmos3
Estrutura do Curso
➢ Introdução
✓ Motivação
✓ Contagem dos passos de um algoritmo
✓ Funções de tempo
➢ Complexidade de Algoritmos
✓ Comportamento Assintótico
✓ Notações O e 
✓ Cota superior, inferior e algoritmo ótimo
✓ Classes de Comportamento Assintótico
➢ Cálculo da Complexidade de Algoritmos
✓ Contagem de estruturas de controle
✓ Contagem de algoritmos recursivos
✓ Complexidade de melhor caso, pior caso e caso médio
➢ Análise de Algoritmos de Ordenação
Projeto e Análise de Algoritmos4
Estrutura do Curso
➢ Complexidade de um Problema
✓ Problemas tratáveis, intratáveis e indecidíveis
✓ Classes de problemas: P, NP e NP-Completos
➢ Estratégias para o Projeto de Algoritmos
✓ Força Bruta (Brute Force)
✓ Dividir e Conquistar (Divide and Conquer)
✓ Diminuir e Conquistar (Decrease and Conquer)
✓ Transformar e Conquistar (Transform and Conquer)
✓ Compromisso Tempo–Espaço (Space and Time Tradeoffs)
✓ Algoritmo Guloso (Greedy)
✓ Backtracking
✓ Programação Dinâmica (Dynamic Programming)
✓ Ramificar e Limitar (Branch and Bound)
Projeto e Análise de Algoritmos5
Bibliografia
➢ TOSCANI, L. V. e VELOSO, Paulo, A. S. Complexidade de Algoritmos. 3ª
ed., Bookman, 2012.
➢ CORMEN, T. H., LEISERSON, C. E. e RIVEST, R. L. Algoritmos – Teoria e
Prática. 3ª ed., Campus, 2012
➢ ZIVIANI, N. Projeto de Algoritmos com Implementações em Pascal
e C. 3ª ed., Cengage Learning, 2010.
➢ SZWARCFITER, J. L. Estruturas de Dados e seus Algoritmos. 3ª ed.,
LTC, 2010.
➢ GOODRICH, M. T. e TAMASSIA, R. Projeto de Algoritmos –
Fundamentos, análise e exemplos da Internet. Bookman, 2002.
➢ ZIVIANI, N. Projeto de Algoritmos com implementação em Java e
C++. 1ª ed., Thomson Learning, 2006.
Projeto e Análise de Algoritmos6
Calendário
➢ Dias sem aula:
Datas Aulas
06/02 a 03/04 8 aulas (24 tempos)
10/04 A1
17/04 a 05/06 7 aulas (21 tempos)
12/06 A2
26/06 A3
Dia Motivo
06/03 Carnaval
01/05 Dia do Trabalho
Projeto e Análise de Algoritmos7
Material Didático 
➢ Todos o material apresentado em sala de aula e os programas
desenvolvidos no laboratório serão postados no sistema do aluno.
Os alunos deverão acessar o sistema e fazer o download do
material.
➢ Não será enviado nenhum tipo de material didático via email.
Projeto e Análise de Algoritmos8
Frequência
➢ O curso é presencial e, portanto, não há abono de faltas.
➢ Use os 25% de faltas (30 tempos) a que você tem direito para os
casos realmente necessários (doença, viagem, trabalho, etc.).
➢ Acompanhe o lançamento das frequências no sistema do aluno.