Baixe o app para aproveitar ainda mais
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.
Compartilhar