Slide para Projeto e Análise de Algoritmos

Prévia do material em texto

INTRODUÇÃO 
Profa. Thaís Alves Burity Rocha 
Agenda 
 O que é um algoritmo? 
 Como escrever algoritmos 
 Exemplos de problemas que são resolvidos por 
algoritmos 
 Relação entre algoritmos e estruturas de dados 
 Análise de algoritmos 
 Projeto de algoritmos 
 Importância da disciplina 
O que é um algoritmo? 
 Procedimento computacional que recebe um valor 
ou um grupo de valores como entrada, e produz um 
valor ou um grupo de valores como saída 
 
Entrada Algoritmo Saída 
O que é um algoritmo? 
 Uma ferramenta para resolver problemas 
computacionais bem definidos 
 Exemplos: 
 
 
Ordenação 
Entrada: Uma sequência de n números <a1, a2, …, an > 
Saída: Uma reordenação da sequência de entrada <a1’, a2’, …, an’ >, 
onde a1’ ≤ a2’ ≤ … ≤ a3’ 
Número primo 
Entrada: Um número natural q 
Saída: Sim ou não, dependendo se q é primo 
Problemas computacionais 
 Uma instância de um problema é um possível valor 
(legal) de entrada, a partir do qual pode ser 
retornada uma saída 
 
 Exemplos: 
 Para o problema de ordenação 
 Entrada: <31, 41, 59, 26, 41, 58> 
 Saída: <26, 31, 41, 41, 58, 59> 
 
 Para o problema dos números primos 
 Entrada: 29 
 Saída: sim 
Problemas computacionais 
 Podem existir diversos algoritmos para um mesmo 
problema 
 Problema de ordenação 
 
 Seleção do algoritmo mais adequado depende de 
diversos fatores: 
 Número de itens a serem ordenados 
 Extensão em que os itens já estão ordenados de algum 
modo 
 
 
 
Algoritmos 
 Um algoritmo é dito correto se, para cada instância 
de entrada, ele pára com a saída correta 
 
 Um algoritmo correto resolve o problema 
computacional dado 
 
 Algoritmos incorretos também podem ser úteis 
Programa x Algoritmo 
 Programa pode ser visto como um algoritmo escrito 
em uma linguagem de computador 
 
 Algoritmo (abstrato) x Programa (concreto) 
Como escrever algoritmos 
Linguagem 
Natural 
Expressividade 
Flexibilidade 
Ambiguidade 
Prolixidade 
Estruturação 
+ 
- 
Código 
Controle 
Concisão 
Estrutura Formal 
Aprendizado 
+ 
- 
Como escrever algoritmos 
Linguagem 
Natural 
Código 
Pseudo-Código 
Expressividade 
Flexibilidade 
Controle 
Concisão 
Estrutura Formal 
Reduzir ambiguidade 
Abstrair detalhes não importantes 
Fácil de ser assimilado por humanos 
Como escrever algoritmos 
 A especificação deve fornecer uma descrição 
precisa do procedimento computacional a ser 
seguido 
Exemplos de problemas que são 
resolvidos por algoritmos 
 Busca de conteúdo na internet: 
Grande volume de informação 
 Necessidade de resposta rápida 
 
 Alguns problemas: 
 Localização de boas rotas pelas quais os dados viajarão 
 Uso de mecanismo de pesquisa para encontrar com rapidez 
páginas em que residem informações específicas 
Exemplos de problemas que são 
resolvidos por algoritmos 
 Comércio eletrônico: 
 Necessidade de proteger informações críticas, como 
número de cartão de crédito, senha e extratos 
bancários 
 
 Uso de criptografia de chave pública e assinaturas 
digitais 
Exemplos de problemas que são 
resolvidos por algoritmos 
 Alocação de recursos escassos de forma eficiente 
 Uma empresa petrolífera precisa saber onde localizar 
seus poços para tornar máximo o lucro esperado 
 
 Um candidato precisa definir onde gastar dinheiro em 
publicidade de campanha com a finalidade de 
ampliar as chances de vencer a eleição 
 
Exemplos de problemas que são 
resolvidos por algoritmos 
 Alocação de recursos escassos de forma eficiente 
 Alocação de equipes de desenvolvimento em projetos 
de software geograficamente distribuídos 
 Definir “tarefas” para serem realizadas de forma 
“independente”, com base na arquitetura do sistema 
 Definir ranking das equipes com base na qualificação 
técnica 
 Definir ranking das equipes considerando aspectos da 
distribuição geográfica 
 
Relação entre algoritmos e 
estruturas de dados 
 Estruturas de dados armazenam e organizam dados a 
fim de facilitar a recuperação e modificação destes 
 
 Algoritmos manipulam dados 
 
 O tipo de estrutura de dados a ser usada depende do 
problema em questão 
 
 Grafos 
1 2 
5 4 
3 
Análise de algoritmos 
 Significa prever os recursos de que o algoritmo 
necessitará 
 
 Principal recurso é o tempo de processamento 
(eficiência) 
 Suposição de modelo de computação genérico 
 As instruções são executadas seqüencialmente 
 Não se considera o uso de memória cash 
 
 Outros recursos: memória, largura de banda 
Análise de algoritmos 
 Abordagens para análise de eficiência 
 Análise assintótica 
 Análise empírica 
 
 Outros aspectos fundamentais 
 Corretude 
 Toda entrada (legal) produz uma saída correta 
 
 Simplicidade 
 Fácil de entender, implementar e manter 
Provar corretude de um algoritmo 
 Não é tarefa simples 
 
 Testes servem apenas para mostrar que o algoritmo 
não tem erros, ou que não há erros para aquelas 
entradas 
 
 Abordagens: 
 Invariantes de laço 
 Prova por indução 
 
Projeto de algoritmos 
 Estudo de métodos, técnicas, idéias, dicas para 
desenvolver algoritmos eficientes 
 Divisão-e-conquista 
 
 Algoritmos gulosos 
 
 Programação dinâmica 
 
 Backtracking 
 
 Branch-and-Bound 
 
 
Conclusão sobre algoritmos 
 Algoritmos constituem uma tecnologia, tal como o 
hardware de computadores 
 Desempenho total do sistema depende de ambos 
 
 Recursos atuais para dar suporte ao 
desenvolvimento de sistemas abstrai o uso de 
algoritmos (complexos) 
 
Importância da disciplina 
 Ajudar a entender ferramentas úteis 
 Exemplo: Compressão de dados 
 
Importância da disciplina 
 Evitar “reinventar a roda” 
 Existem bons algoritmos que solucionam problemas 
importantes 
 Prover meios para comparar diferentes soluções de um 
mesmo problema 
 
 Ajudar no desenvolvimento de novos algoritmos 
 Nem sempre existe um algoritmo de prateleira que sirva 
para resolver o seu problema 
 Muitos dos princípios de projetos de algoritmos são úteis em 
todos os problemas de programação 
 
Importância da disciplina 
 Permite definir o que é viável e o que é 
impossível 
 Problemas NP-Completos: problemas para os quais 
não se conhece nenhuma solução eficiente 
 
 Exemplo: Empresa de transporte por caminhão com um 
armazém central (problema do caixeiro viajante) 
 Definir ordem de parada das entregas 
 Distância total percorrida deve ser a menor possível 
 
Referência 
 Cormen, Leiserson, Riveste Clein. Algoritmos: Teoria 
e prática. Tradução da Segunda edição 
Americana. Editora Campus, 2002.