Um algoritmo é um conjunto de instruções passo-a-passo para resolver um problema. O algoritmo identifica o que precisa ser feito (cada instrução a ser seguida) e a ordem com que estas instrução precisam ser executadas. Provavelmente é o tópico mais estudado desde o início da computação como a conhecemos e foi responsável por uma revolução tecnológica no início do século XX. Além de servir como uma ferramenta de comunicação entre humanos e humanos e computadores, algoritmos são também poderosas ferramentas de análise para decidir entre diferentes formas de resolver um mesmo problema. Vamos estudar alguns algoritmos comumente utilizados na resolução de problemas, uma forma de descrevê-los chamada fluxograma e um tipo de análise que podemos realizar sobre algoritmos.
Todos os semestres, na formatura da turma de Engenharia de Computação, é entregue o prêmio de aluno destaque daquela turma. A escolha é feita pelo coordenador de curso e o critério mais comum é escolher dentre os formando aquele estudante com o maior índice de rendimento acadêmico — IRA. Por exemplo, considere a turma de formandos do 2019/2 e seus IRAs a seguir.
Encontrar o valor máximo ou mínimo em uma coleção é um problema comum em computação como parte de outros problemas mais complexos. Para esta lista pequena de 8 números você rapidamente identificou Alonzo Church como o aluno destaque, a pergunta é: como você fez isso?
Provavelmente a esta altura da vida você bate o olho nos números e consegue tomar decisões subconscientes sobre eles. Talvez o formato dos números tenha te ajudado. Agora olhe para a lista a seguir com 100 números, qual deles é o maior?
É o número 4.8530 que está na segunda linha da segunda coluna. Provavelmente esta foi uma tarefa bem mais difícil e você precisou trabalhar de forma mais sistemática. Essa é justamente a ideia por trás de um algoritmo, descrever uma forma sistematizada de resolver um determinado problema de forma que uma pessoa ou um computador possam encontrar a solução.
Uma curiosidade, até meados dos anos 1940 computadores eram pessoas e não máquinas! O próprio Alan Turing, um dos pais da computação, descreveu um computador como "alguém que deve seguir um conjunto fixo de regras sem autoridade para desviar delas em nenhum detalhe". Pessoas seguiram trabalhando como computadores até a década de 1970. A maioria eram mulheres e várias foram depois escolhidas como as primeiras programadoras de computadores eletrônicos.
Estas computadoras foram as primeiras programadoras profissionais escolhidas para programar o ENIAC, o primeiro computador eletrônico de propósito geral da história).
Vamos adicionar algumas restrições em relação as operações que um computador é capaz de executar, seja ele humano ou máquina. Esse tipo de restrição com relação às capacidades da pessoa ou máquina que irá executar o algoritmo é chamado de Modelo de Computação e é um dos conceitos mais importantes na computação. No caso de humanos, nós sabemos que podemos realizar operações mais complexas do que as que normalmente utilizamos, mas quanto mais complexo o tipo de operação básica permitirmos, mais difícil é compreender o que a máquina está fazendo e provavelmente mais difícil é reproduzir aquele comportamento.
Vamos considerar que um computador somente pode realizar operações binárias. Operações binárias recebem dois operandos e geram um resultado. Por exemplo, a operação de soma recebe dois operando $a$ e $b$ e gera um resultado $c$. A operação maior que para comparar dois números recebe dois operandos $a$ e $b$ e gera uma resposta do tipo sim (verdadeiro) ou não (falso). Chamamos este último tipo de resultado de booleano em homenagem ao matemático inglês George Boole que sistematizou este tipo de operação.
$$ a+b = c \\ +:\mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R} $$
$$ a>b = c \\
:\mathbb{R} \times \mathbb{R} \rightarrow \mathbb{B} $$
Vamos começar pelo início da lista e observar cada elemento da lista na sequência. O primeiro elemento é o IRA da Ada Lovelace. Como é o maior valor que vimos até agora, vamos anotar como sendo o maior valor da lista. Passamos para o próximo formando, George Boole, o IRA dele é 4.08. Como esse valor é maior do que o que vimos anteriormente, vamos anotá-lo como o maior valor da lista. Agora vamos considerar o Claude Shannon que tem IRA 4.32. Esse número é maior do que o valor que estamos guardando, então vamos considerar agora o IRA do Shannon como o maior da lista.
Seguimos comparando Alan Turing e John von Neumann, cada um com IRA menor do que o que estamos recordando. Alonzo Church formou com IRA de 4.76, então vamos anotar este valor como o maior da lista até agora. Seguimos analisando Margareth Hamilton e John Backus, ambos com IRA menor do que o valor que estamos guardando. Como chegamos no fim da lista, concluímos que Alonzo Church é o formando com o maior IRA e irá receber a homenagem de aluno destaque.
A descrição que fizemos do algoritmo para encontrar o maior valor em uma lista foi descrito com base em um exemplo. Normalmente essa abordagem é razoável quando estamos tentando entender um problema e bolar uma estratégia inicial, mas essa não é uma descrição precisa o suficiente para comunicar o processo para outras pessoas nem para programar um computador. Uma linguagem gráfica interessante e bastante utilizada em computação é o fluxograma.
