Introdução a algoritmos e estruturas de dados

Se você é novo na área de TI, mas já sabe alguma linguagem de programação (mesmo que só o básico de lógica de programação) e está começando agora a estudar algoritmos e estruturas de dados, talvez a série 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ê é alguém que não curte livros tão maçantes sobre as coisas, assim como eu, talvez se identifique). Pretendo botar nesse e nos próximos posts explicações que funcionaram muito bem para mim no meu tempo na universidade e espero que possam te servir também! 😃

Antes de começarmos por alguns conceitinhos básicos, já quero deixar claro que irei usar a linguagem Python nos meus exemplos, então é 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 saída. Para quem já estudou funções (as da matemática mesmo), deve achar essa definição bem familiar, não é?

E não é por acaso, não! As funções da matemática são algoritmos também e vice-versa, mas não se preocupe se nunca tiver estudado isso na escola, não vai ser nada complicado.😉

A gente geralmente usa os algoritmos para resolver algum problema de computação. Um exemplo disso é o algoritmo de soma (sim, é um exemplo básico, mas não deixa de ser um algoritmo):

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

O que o algoritmo acima faz é solucionar um problema de computação, que é somar dois números (somar é uma computação). Este algoritmo é descrito numa linguagem que o computador consegue entender (Python) e sem ambiguidades, com isso tendo a chamada precisão. Considere que executemos o algoritmo com as entradas 1 e 9:

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

O código 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 correção.

Um bom algoritmo sempre atende aos critérios de precisão e correção. Também é 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 são finitos.

Corretude dos algoritmos

Como acabamos de ver, um algoritmo atende ao critério de correção quando o que ele retorna é considerado correto de acordo com a(s) entrada(s) considerada(s). Bem, nem sempre é fácil ou possível saber se a saída 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 critério para considerar correta a saída do algoritmo é ele retornar uma caminho qualquer entre A e B), é fácil.

Agora, quando o problema considerado é encontrar a melhor rota entre A e B, a coisa complica um pouco, já que é bem difícil determinar se a resposta está certa ou não. Neste caso, precisamos arranjar uma forma de medir o quão "ótima" é a resposta que o algoritmo nos dá.

Eficiência 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 execução e a memória exigida para que ele rode na nossa máquina.

Diferentes algoritmos que resolvem o exato mesmo problema podem ter desempenhos bem diferentes. Mais para frente iremos falar sobre a análise da complexidade de algoritmos, que é uma forma de estimar o tempo de execução e a memória utilizada durante a execução do algoritmo, técnica bastante utilizada durante o desenvolvimento. Vale ressaltar que, depois de termos desenvolvido o algoritmo, podemos usar ferramentas que nos indicam de forma quantitativa esses parâmetros, como é o caso do benchmarking.

A análise dos algoritmos independe da tecnologia utilizada (linguagem de programação, etc). A análise é importante pois nos dá um norte de qual algoritmo, dentre os possíveis vários 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 estão na memória do computador. Um exemplo clássico é o array (ou vetor), presente em todas as principais linguagens de programação.

No nosso vetor acima, temos os nomes "Maria", "Lucas", "José" e "Frida" armazenados nesta ordem. Na maioria das linguagens de programação, temos métodos para buscar, remover e inserir dados no nosso array (operações de manipulação 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 eficiência 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.

Não há estrutura de dados perfeita, cada uma tem seus pontos fortes e fracos. Temos que analisar, durante a construção 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 comércio e o processamento de pedidos deste em sua loja virtual. Seria um enorme desperdício de memória guardar todos os pedidos em um vetor/array, além 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 alocação e desalocação dinâmica de memória (vamos falar melhor disso mais para frente).

É isso!

Enfim, é basicamente isso! Isso é apenas um introdução aos conceitos mais importantes de algoritmos e estruturas de dados, nada muito aprofundado. Como já disse várias vezes, pretendo fazer mais posts entrando em detalhes, em algoritmos mais específicos, etc. Espero que tenha gostado da leitura. Qualquer coisa, me chama no twitter!