E o algoritmo, hein? Afinal, que “bicho” é esse que domina o mundo?

sexta-feira, 25 novembro, 2016 at 7:18 pm Deixe um comentário

Como o diminuto GPS consegue, tão rápido, em míseros segundos, achar uma rota para nós? Como o número do nosso cartão de crédito é protegido em uma transação virtual? Como as próprias transações virtuais são realizadas? Como conseguimos ouvir música e assistir a um vídeo, em nossos dispositivos eletrônicos de um local a quilômetros de distância de nós?

A resposta para essas e muitíssimas outras perguntas reside em uma palavra: algoritmo.

Mas, afinal, o que é um algoritmo?

algoritmo

Uma resposta genérica, rápida e de âmbito geral seria: “uma sequência de instruções que executadas ordenadamente e passo a passo, resolve um problema”. Aí você responde: com essa definição, então tudo é um algoritmo? Bom, …, quase tudo, mas, nem tudo! rsrsrs

Mas, sim, você executa algoritmos diariamente. Ao acordar, por exemplo, você escova os dentes. O procedimento de escovar os dentes é quase sempre o mesmo: abrir o tubo de creme dental, pegar a escova, apertar o tubo sobre a escova aplicando uma pequena quantidade de creme sobre a mesma, fechar o tubo, colocar a escova na boca e movimentá-la para a cima e para baixo em pequenos círculos por um determinado tempo, etc. Se você pega um ônibus para ir ao trabalho ou à escola também tem um algoritmo para isso e assim sucessivamente.

Mas, “peraí”, calma lá! Não são esses os algoritmos que executam as tarefas descritas no início do texto. Não, não são mesmo. Mas, eles partem do mesmo princípio.

Eu ensino sobre algoritmos há mais de dez anos e os alunos, invariavelmente acham difícil ou tem uma curva de aprendizado pouco suave (ao menos no início). Tratamos, neste blog, e no início do texto, dos algoritmos que podem ser executados em computadores, ou dispositivos de computação. E estes, simplesmente dominam o mundo…

Mas, vamos por partes (como nosso conhecido Jack). Os matemáticos conhecem o conceito de algoritmo (e de computação em geral) há muitos anos. É famoso, por exemplo, o método babilônico (ou algoritmo) para extração da raiz quadrada aproximada de um número (cerca de 2 mil anos antes de Cristo) e o muitíssimo conhecido Algoritmo de Euclides (300 a.C.) para a extração do MDC entre dois números.

Em suma, um algoritmo, de fato, representa um método para realizar uma tarefa. Os algoritmos de computador tem duas características principais (dentre tantas) que o distinguem de serem “métodos computacionais“: 1) Ele é não ambíguo e 2) tem que ter fim! (Um método para calcular o número π, por exemplo, grosso modo, não pode ser considerado um “algoritmo” formal, pois o número pi não tem fim! É um método. É computacional. Mas não tem fim!)

A consequência destas características é o que define, formalmente, algoritmo. O fato das instruções serem não ambíguas leva à corretude (entradas iguais geram saídas iguais), à previsão da saída e a finitude é o que leva uma máquina como o computador a executá-lo.

Normalmente, se exemplifica o conceito de algoritmo relacionando-o a uma receita culinária onde segue-se passos e usa-se ingredientes (dados de entrada) para gerar um prato (saída). É um exemplo comum e sua força reside na simplicidade da comparação.

cakeisalie

Tecnicamente, pode-se repetir operações, efetuar cálculos e tomar decisões até que a tarefa seja completada. Diferentes algoritmos podem realizar a mesma tarefa usando instruções diferenciadas que levam mais ou menos tempo, espaço ou esforço computacional. Isso chama-se complexidade computacional e será estudado em outro tópico.

algoritmo2

A precisão das instruções é crucial. Nós podemos tolerar algoritmos descritos imprecisamente, mas não o computador! Além de precisas, as instruções devem ser simples. Simples o bastante para uma máquina executar.

Basicamente, eu posso dizer para alguém: “pegue outra rua” quando o trânsito estiver engarrafado, mas não “dizer” o mesmo ao computador. Ele simplesmente não entenderia.

Portanto, chegamos a uma definição que pode-se dizer suficiente (embora informal):

“Algoritmos são sequências de instruções ou regras simples, ordenadas  e que, se executadas passo a passo, a partir do início, resolvem um determinado problema em um tempo finito”.

Formalmente, a corretude de um algoritmo pode ser provada matematicamente e a análise de sua execução também (complexidade). Estas duas últimas tarefas são metas da Análise de Algoritmos. O conceito  de algoritmo foi formalizado em 1936 por Alan Turing (pela máquina de Turing) e Alonzo Church (pelo cálculo lambda). Os dois conceitos formaram as fundações da Ciência da Computação.

alan_turing_photo

O gênio, Alan Turing (1912-1954)

E eles estão em toda parte. Como eu disse anteriormente, dominam o mundo. Estão no carro quando se usa o GPS para se determinar uma rota de viagem (o aparelho executa os chamados algoritmos de “caminho mínimo“). Estão nas compras pela Internet garantindo a segurança de sites (algoritmos criptográficos). Estão por trás das entregas dos produtos determinando em qual ordem os caminhões devem seguir. São a base das rotas aeroviárias ditando o itinerário dos aviões comerciais e de logística. Estão dentro dos sistemas internos de usinas nucleares e servidores de páginas web como esta que você está lendo, enfim, eles estão sendo executados em computadores em todos os lugares, no notebook, em computadores de grande porte, em smartphones, em carros, TV’s, micro-ondas, enfim, em TODOS os lugares!

Não esqueça disso a próxima vez que marcar sua rota no GPS!

Ainda falaremos muito mais de algoritmos…

Até a próxima!

________________

P.S. o termo “algoritmo”, segundo Donald Knuth, provavelmente o maior cientista da computação vivo, é derivado do nome “al-Khowârizmî“, um matemático persa do século IX. A raiz da palavra, seu radical, é praticamente o mesmo de “álgebra”, “algarismo” e “logaritmo”.

😉

Entry filed under: Algoritmos, Aulas, Programação. Tags: .

E a Probabilidade e a Estatística, hein?

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Follow Computador de papel: o conteúdo da forma on WordPress.com

Feeds

direto do Twitter

O Computador de Papel

O computador de papel nada mais é do que a tentativa de "humanizar" o computador, trazê-lo para a fantasia lúdica da realidade, fazê-lo compreendido pelos milhares que o usam, mas não o entendem. Nasceu de minhas viagens intelectuais defronte da tela de fósforo um dia em que ele retrucou-me: decifra-me ou te devoro. Para não ser devorado, ousei decifrá-lo. É também onde posto minhas aulas, meus trabalhos, minhas impressões de um pouco de nada sobre coisa nenhuma. É o local onde falo das minhas paixões, entre elas, a música, o cinema, a TI e a ciência. É um espaço de discussão sobre a realidade do computador, sua influência, seus avanços, o exercício do óbvio que é mostrar a sua importância no e para o mundo. Tem o estilo de seu criador, acelerado, com um tom sempre professoral, tresloucado, por vezes verborrágico, insano, nevrálgico, sem arroubos literários, atônito e contemplativo diante da realidade, apaixonado, livre, feito para mostrar que a TI é antes de tudo, feita por gente!

Estatísticas do blog

  • 118,174 cliques e contando...

Agenda de posts

novembro 2016
S T Q Q S S D
« jun    
 123456
78910111213
14151617181920
21222324252627
282930  

%d blogueiros gostam disto: