PAA Aula 1

Prévia do material em texto

bruno.conceicao@ufop.edu.br
Prof. Bruno César Cota Conceição
Projeto e análise de Algoritmos
 Aula 1 
 Introdução a problemas e algoritmos
Introdução
Essa disciplina trata do conceito de algoritmos em dois aspectos principais:
Introdução
Essa disciplina trata do conceito de algoritmos em dois aspectos principais:
Análise
Introdução
Essa disciplina trata do conceito de algoritmos em dois aspectos principais:
Análise Projeto
Introdução
Essa disciplina trata do conceito de algoritmos em dois aspectos principais:
Análise Projeto
Observar o algoritmo e caracterizar
ele, comparando, identificando se o
algoritmo é bom ou ruim de acordo
com alguns critérios que a gente
definir.
Introdução
Essa disciplina trata do conceito de algoritmos em dois aspectos principais:
Análise Projeto
Observar o algoritmo e caracterizar
ele, comparando, identificando se o
algoritmo é bom ou ruim de acordo
com alguns critérios que a gente
definir.
Capaz de identificar técnicas
existentes de projetos de algoritmos e
aplicar estas técnicas para
desenvolvimento dos nossos próprios
algoritmos.
O que é um algoritmo?
O que é um algoritmo?
 Sequência de passos para resolver um problema
Consideramos problemas abstratos
O que é um algoritmo?
 Sequência de passos para resolver um problema
Consideramos problemas abstratos
Ex. Encontrar uma rota geográfica mais curta
O que é um algoritmo?
 Sequência de passos para resolver um problema
Consideramos problemas abstratos
Ex. Encontrar uma rota geográfica mais curta
 Encontrar um caminho mínimo 
entre dois vértices de um grafo
O que é um algoritmo?
Formalizando problemas
Formalizando problemas
Formalizando problemas
Formalizando problemas
Formalizando problemas
Formalizando problemas
Formalizando problemas
Formalizando problemas
Formalizando problemas
Formalizando problemas
Sequência de passos
Sequência de passos
1 - Pegar o problema
Sequência de passos
1 - Pegar o problema
2 - Formalizar o problema
Sequência de passos
1 - Pegar o problema
2 - Formalizar o problema
3 - Entender o problema bem entendido
Sequência de passos
1 - Pegar o problema
2 - Formalizar o problema
3 - Entender o problema bem entendido
4 - Desenvolvimento de algoritmos que possam solucionar o problema
Exemplo: Problema do Caixeiro Viajante (PCV)
Exemplo: Problema do Caixeiro Viajante (PCV)
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Distancia: 19
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Distancia: 19
É a distância mínima?
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Distancia: 19
É a distância mínima?
Não
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Distancia: 19
Uma outra resposta:
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Distancia: 19
Uma outra resposta:
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Distancia: 19
Uma outra resposta:
Distancia: 15
Exemplo: Problema do Caixeiro Viajante (PCV)
Uma possível resposta:
Distancia: 19
Uma outra resposta:
Distancia: 15
Logo essa resposta satisfaz o problema e vocês vão perceber que 15 é o caminho
mínimo nesse caso.
Exemplo: Problema do Caixeiro Viajante (PCV)
Agora que entendemos o problema, vamos defini-lo formalmente:
Exemplo: Problema do Caixeiro Viajante (PCV)
Agora que entendemos o problema, vamos defini-lo formalmente:
Ou seja, especificar o que é a entrada do problema e o que seria a saída.
Exemplo: Problema do Caixeiro Viajante (PCV)
Agora que entendemos o problema, vamos defini-lo formalmente:
Ou seja, especificar o que é a entrada do problema e o que seria a saída.
Exemplo: Problema do Caixeiro Viajante (PCV)
Exemplo: Problema do Caixeiro Viajante (PCV)
Exemplo: Problema do Caixeiro Viajante (PCV)
Exemplo: Problema do Caixeiro Viajante (PCV)
Vamos ver se temos uma ideia melhor para uma possível solução para este
problema
Exemplo: Problema do Caixeiro Viajante (PCV)
Vamos ver se temos uma ideia melhor para uma possível solução para este
problema
Primeira coisa: 
Exemplo: Problema do Caixeiro Viajante (PCV)
Vamos ver se temos uma ideia melhor para uma possível solução para este
problema
Primeira coisa: Pensar nas restrições deste problema
Exemplo: Problema do Caixeiro Viajante (PCV)
Vamos ver se temos uma ideia melhor para uma possível solução para este
problema
Primeira coisa: Pensar nas restrições deste problema
Passar por todos os pontos
E a distância tem que ser mínima
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Partindo do ponto (0,0) e assumindo que todos tem a mesma distância, eu posso ir para a
cidade mais próxima.
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Partindo do ponto (0,0) e assumindo que todos tem a mesma distância, eu posso ir para a
cidade mais próxima.
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Partindo do ponto (0,0) e assumindo que todos tem a mesma distância, eu posso ir para a
cidade mais próxima.
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Partindo do ponto (0,0) e assumindo que todos tem a mesma distância, eu posso ir para a
cidade mais próxima.
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Partindo do ponto (0,0) e assumindo que todos tem a mesma distância, eu posso ir para a
cidade mais próxima.
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Exemplo: Problema do Caixeiro Viajante (PCV)
Passar por todos os pontos
E a distância tem que ser mínima
Realmente a melhor solução neste caso
Exemplo: Problema do Caixeiro Viajante (PCV)
A questão que nos devemos perguntar: Eu encontrei a instância de um problema e um
algoritmo que resolve esta instância. 
Exemplo: Problema do Caixeiro Viajante (PCV)
A questão que nos devemos perguntar: Eu encontrei a instância de um problema e um
algoritmo que resolve esta instância. 
Meu algoritmo funciona para toda instância? 
Exemplo: Problema do Caixeiro Viajante (PCV)
A questão que nos devemos perguntar: Eu encontrei a instância de um problema e um
algoritmo que resolve esta instância. 
Meu algoritmo funciona para toda instância? 
Senão, vamos achar um contra exemplo onde o algoritmo falhe.
Consideremos um Segundo exemplo
Usando o algoritmo do cenário anterior:
Consideremos um Segundo exemplo
Consideremos um Segundo exemplo
Consideremos um Segundo exemplo
É a melhor solução?
Consideremos um Segundo exemplo
É a melhor solução?
Não
Consideremos um Segundo exemplo
Consideremos um Segundo exemplo
Consideremos um Segundo exemplo
Encontramos um contra exemplo que mostra que nem sempre ir para a cidade mais
próxima é a melhor solução possível. Desse modo achamos um algoritmo que não
funciona.
Consideremos um Segundo exemplo
Encontramos um contra exemplo que mostra que nem sempre ir para a cidade mais
próxima é a melhor solução possível. Desse modo achamos um algoritmo que não
funciona.
Jáque esse não , qual poderia funcionar?
Consideremos um Segundo exemplo
Consideremos um Segundo exemplo
Aqui entramos em um
paradigma que
chamamos de força
bruta.
Consideremos um Segundo exemplo
Vimos uma coisa importante, uma característica que o
algoritmo precisa ter que é funcionar para todas as
instâncias....
Então esse último algoritmo é o correto.
Propriedades de um algoritmo
provar que funciona para todos os casos.
Propriedades de um algoritmo
provar que funciona para todos os casos.
Propriedades de um algoritmo
Propriedades de um algoritmo
Representamos o custo através de uma função que tem algumas características, algumas
notações específicas que vão nos ajudar a comparar alguns algoritmos.
Propriedades de um algoritmo
Representamos o custo através de uma função que tem algumas características, algumas
notações específicas que vão nos ajudar a comparar alguns algoritmos.
Referências:
Créditos ao professor Vinícius Dias pelo material disponibilizado.
 LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3a edition. Editora
Addison Wesley;
2. CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford.
Introduction to Algorithms. 3a edition. Editora The MIT Press;
3. ERICKSON, Jeffe. Algorithms. 1st edition. June 2019.
Disponível em: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
4. KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Editora Addison Wesley.
5. DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algorithms. Editora
McGraw-Hill.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788563308535/pageid/0
6. MANBER, Udi. Introduction to Algorithms: A Creative Approach. 1st edition. Editora
AddisonWesley