Algoritmos e Ciência da Computação Nivio Ziviani Professor Titular do DCC/UFMG Introdução à Ciência da Computação DCC/UFMG, 19 de Outubro de 2007 LATIN – Laboratório para Tratamento da Informação 1 O que é um algoritmo? Pode ser visto como uma seqüência de ações executáveis para a obtenção de uma solução para um determinado tipo de problema É um procedimento (um conjunto finito de instruções bem definidas) para executar alguma tarefa, a qual, dado um estado inicial, termina em um estado final (Wikipedia) Corresponde a uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações (Dijkstra, 1971) LATIN – Laboratório para Tratamento da Informação 2 Por que estudar algoritmos? Algoritmos e estruturas de dados formam o núcleo da ciência da computação Formam os componentes básicos de qualquer software Aprender como programar está intimamente ligado a algoritmos Um algoritmo é a abstração de um programa Logo, aprender algoritmos é crucial para quem deseja desenvolver software de qualidade LATIN – Laboratório para Tratamento da Informação 3 Qual a origem da palavra algoritmo? Muhammad ibn Musa abu Djafar Al-Khorezmi Algoritmo: vem de Al-Khorezmi Al-Khorezmi: originário de Khorezmi (hoje Khiva, Uzbekistan) Nascido por volta do ano 780, escreveu vários livros Criou o conceito de zero Aritmetica: introduz sistema numérico da India Kitab al-jabr wa’l-muqabala: deu origem a palavra álgebra Grande poder de abstração, se preocupava em reduzir o número de operações necessárias em cada cálculo Não foi o inventor do primeiro algoritmo, mas merece que o conceito de algoritmo seja ligado ao seu nome Foi sem dúvida o primeiro pensador algoritmico! LATIN – Laboratório para Tratamento da Informação 4 Maneiras de ensinar algoritmos Por tópicos ou tipos de problemas Estruturas de dados básicas; ordenação; pesquisa em memória principal; pesquisa em memória secundária; grafos; processamento de cadeias de caracteres; problemas NP-completo; algoritmos aproximados Paradigmas ou técnicas de projeto Indução; recursividade; tentativa e erro; divisão e conquista; balanceamento; programação dinâmica; algoritmos gulosos; algoritmos aproximados LATIN – Laboratório para Tratamento da Informação 5 Algoritmos: eficiência Buscar um registro: Registros não ordenados Registros ordenados Registros ordenados com info sobre a distribuição LATIN – Laboratório para Tratamento da Informação 6 Algoritmos: eficiência Descobrir quais cheques foram descontados a partir do saldo Problema do caixeiro viajante LATIN – Laboratório para Tratamento da Informação 7 Problema dos cheques No primeiro dia de cada mês o Sr. Joaquim recebe o saldo bancário de sua conta corrente. Baseado apenas no saldo bancário o Sr. Joaquim quer descobrir quais os cheques dados por ele foram descontados até a data de emissão do saldo. O Sr. Joaquim sabe que o valor dos n cheques dados por ele são todos diferentes. 1 Cheques: 20 bits: 0 2 3 60 30 1 0 4 10 1 Total = 120 Saldo = 50 Descontados = 70 (quais cheques?) Solução: tentar todas as combinações (24 = 16 para o exemplo) Quantas são: 2n possibilidades 20 cheques: 220 ? 30 cheques: 230 ? 2n LATIN – Laboratório para Tratamento da Informação 8 Problema do Caixeiro Viajante <C1,C3,C4,C2,C1> = 24 Como encontrar a menor rota? Resp.: tentar todas as rotas! Quantas são? (n-1)! 20! = 2432902008176640000 40! = 815915283247897734345611269596115894272000000000 LATIN – Laboratório para Tratamento da Informação 9 P vs NP: prêmio de 1 milhão de dólares Clay Mathematics Institute (CMI), Cambridge, Massachusetts Comitê do CMI selecionou sete problemas (prêmio de US$1 milhão para cada um) Foco em problemas clássicos importantes sem solução por muitos anos P vs NP é um deles Teoria fornece um mecanismo que permite descobrir se um problema é “fácil” ou “difícil” Existem milhares de problemas na natureza que são “difíceis” Se alguém encontrar um algoritmo eficiente para qualquer um deles estará resolvendo todos os outros Ninguém conseguiu provar que tal algoritmo não existe LATIN – Laboratório para Tratamento da Informação 10 Engenharia de software? Programação: coração da Ciência da Computação Algoritmos e estruturas de dados + paradigmas de programação Mais arte do que ciência ou engenharia (trilogia sobre algoritmos e estruturas de dados de Knuth se chama The Art of Computer Programming) A tarefa de programar é nobre? Importante distinguir: Pessoas capazes de tornar uma solução em um programa Pessoas capazes de projetar a solução de um problema e então transformá-la em um programa Um programador completo, chamado de engenheiro, é capaz de conduzir todo o processo, da análise à implementação Programar deveria trazer satisfação pessoal Nós engenheiros produzimos os melhores programas LATIN – Laboratório para Tratamento da Informação 11 A Computação como Ciência Que problemas podemos resolver? Modelos e complexidade dos problemas Como podemos resolver um problema? Projeto de algoritmos Com que rapidez podemos resolvê-lo? Análise de algoritmos LATIN – Laboratório para Tratamento da Informação 12 Computação: Ciência e Engenharia Matemática Computação Biologia Engenharia Eletrônica Física LATIN – Laboratório para Tratamento da Informação 13 Algoritmos Matemática Análise Projeto de Algoritmos Realidade Abstração Implementação Software Aplicação Recuperação de Informação LATIN – Laboratório para Tratamento da Informação 14 Exemplo Análise Software Projeto Abstração Busca em texto Aplicação Recuperação de Informação LATIN – Laboratório para Tratamento da Informação 15 Algoritmos e Ciência da Computação Para aprender algoritmos é necessário ter a combinação correta de conhecimentos matemáticos e bom senso O balanceamento entre teoria e prática é sempre uma tarefa difícil A melhor teoria é inspirada na prática e a melhor prática é inspirada na teoria. Donald Knuth, 1989 LATIN – Laboratório para Tratamento da Informação 16 ? LATIN – Laboratório para Tratamento da Informação 17