Introduo a algoritmos e estruturas de dados

Se voc novo na rea de TI, mas j sabe alguma linguagem de programao (mesmo que s o bsico de lgica de programao) e est comeando agora a estudar algoritmos e estruturas de dados, talvez a srie de posts que se inicia com este possa te ajudar.

Particularmente eu tive bastante dificuldade quando comecei a estudar alguns algoritmos mais mirabolantes e algumas estruturas de dados (se voc algum que no curte livros to maantes sobre as coisas, assim como eu, talvez se identifique). Pretendo botar nesse e nos prximos posts explicaes que funcionaram muito bem para mim no meu tempo na universidade e espero que possam te servir tambm!

Antes de comearmos por alguns conceitinhos bsicos, j quero deixar claro que irei usar a linguagem Python nos meus exemplos, ento bom que voc saiba ao menos um pouco sobre a sintaxe da linguagem. Beleza, com tudo isso em mente, vamos l!

O que um algoritmo computacional?

Um algoritmo computacional (ou apenas algoritmo, para os mais ntimos) qualquer procedimento computacional bem definido que aceita um valor ou um conjunto de valores como entrada e produz um valor ou um conjunto de valores como sada. Para quem j estudou funes (as da matemtica mesmo), deve achar essa definio bem familiar, no ?

E no por acaso, no! As funes da matemtica so algoritmos tambm e vice-versa, mas no se preocupe se nunca tiver estudado isso na escola, no vai ser nada complicado.

A gente geralmente usa os algoritmos para resolver algum problema de computao. Um exemplo disso o algoritmo de soma (sim, um exemplo bsico, mas no deixa de ser um algoritmo):

def soma(a, b):    resultado = a + b    return resultado

O que o algoritmo acima faz solucionar um problema de computao, que somar dois nmeros (somar uma computao). Este algoritmo descrito numa linguagem que o computador consegue entender (Python) e sem ambiguidades, com isso tendo a chamada preciso. Considere que executemos o algoritmo com as entradas 1 e 9:

teste = soma(1, 9)print(teste)

O cdigo acima ir imprimir 10 na tela, o que de se esperar. Quando o nosso algoritmo produz os resultados esperados, dizemos que ele tem a propriedade de correo.

Um bom algoritmo sempre atende aos critrios de preciso e correo. Tambm bom quando o nosso algoritmo faz um uso eficiente dos recursos do computador em que ele vai rodar, j que o tempo e os recursos so finitos.

Corretude dos algoritmos

Como acabamos de ver, um algoritmo atende ao critrio de correo quando o que ele retorna considerado correto de acordo com a(s) entrada(s) considerada(s). Bem, nem sempre fcil ou possvel saber se a sada do algoritmo est certa de acordo com a(s) entrada(s).

Um exemplo comum quando consideramos o problema de achar o melhor caminho entre dois lugares, um problema que vamos falar em um futuro post. Considere a imagem abaixo, queremos achar uma rota entre os pontos A e B e que precisamos desenvolver um algoritmo que ache uma rota entre esses dois pontos.

Se o nosso problema fazer o algoritmo retornar uma rota qualquer entre A e B (ou seja, nosso critrio para considerar correta a sada do algoritmo ele retornar uma caminho qualquer entre A e B), fcil.

Agora, quando o problema considerado encontrar a melhor rota entre A e B, a coisa complica um pouco, j que bem difcil determinar se a resposta est certa ou no. Neste caso, precisamos arranjar uma forma de medir o quo "tima" a resposta que o algoritmo nos d.

Eficincia de algoritmos

Uma forma de sabermos se o nosso algoritmo est fazendo um uso eficiente dos recursos (computacionais e de tempo) analisar o tempo de execuo e a memria exigida para que ele rode na nossa mquina.

Diferentes algoritmos que resolvem o exato mesmo problema podem ter desempenhos bem diferentes. Mais para frente iremos falar sobre a anlise da complexidade de algoritmos, que uma forma de estimar o tempo de execuo e a memria utilizada durante a execuo do algoritmo, tcnica bastante utilizada durante o desenvolvimento. Vale ressaltar que, depois de termos desenvolvido o algoritmo, podemos usar ferramentas que nos indicam de forma quantitativa esses parmetros, como o caso do benchmarking.

A anlise dos algoritmos independe da tecnologia utilizada (linguagem de programao, etc). A anlise importante pois nos d um norte de qual algoritmo, dentre os possveis vrios que resolvem o mesmo problema, devemos escolher, tendo em vista os recursos computacionais e o tempo limitados.

Estrutura de dados

Uma estrutura de dados uma forma de organizar, armazenar, acessar e modificar dados que esto na memria do computador. Um exemplo clssico o array (ou vetor), presente em todas as principais linguagens de programao.

No nosso vetor acima, temos os nomes "Maria", "Lucas", "Jos" e "Frida" armazenados nesta ordem. Na maioria das linguagens de programao, temos mtodos para buscar, remover e inserir dados no nosso array (operaes de manipulao de dados).

T, mas o que estrutura de dados tem a ver com algoritmos? A resposta simples: tem tudo a ver! A estrutura de dados costuma interferir na eficincia dos algoritmos, uma vez que em uma estrutura de dados A qualquer podemos ter um tempo de acesso a um elemento diferente do tempo de acesso em uma estrutura de dados B.

No h estrutura de dados perfeita, cada uma tem seus pontos fortes e fracos. Temos que analisar, durante a construo de um algoritmo, qual/quais seria(m) a(s) estrutura(s) de dados mais adequada(s) a ser(em) utilizada(s) no caso.

Um exemplo quando consideramos um comrcio e o processamento de pedidos deste em sua loja virtual. Seria um enorme desperdcio de memria guardar todos os pedidos em um vetor/array, alm de que os pedidos s podem ser removidos ou adicionados em ordem. Uma melhor estrutura de dados para armazenar os pedidos seria uma lista ligada, em que temos alocao e desalocao dinmica de memria (vamos falar melhor disso mais para frente).

isso!

Enfim, basicamente isso! Isso apenas um introduo aos conceitos mais importantes de algoritmos e estruturas de dados, nada muito aprofundado. Como j disse vrias vezes, pretendo fazer mais posts entrando em detalhes, em algoritmos mais especficos, etc. Espero que tenha gostado da leitura. Qualquer coisa, me chama no twitter!