Formalização dos algoritmos computacionais
Neste material as soluções algorítmicas serão apresentadas por meio de pseudocódigo, embora haja uma certa variedade de outras opções de representação.
A formalização do pseudocódigo a ser adotado neste material é o foco desta seção.
Formalização
Não existem regras para a escrita de pseudocódigo. Nada é necessariamente fixo, nem existem estruturas imutáveis que possam ser empregadas. O principal ponto é a representação clara do algoritmo para o leitor.
Embora as regras não existam absolutamente, há uma convenção geral adotada pela comunidade, ficando um grupo de estruturas e aspectos bem consolidados.
Os algoritmos apresentados neste material seguem um pseudocódigo próprio, baseado no uso geral dos algoritmos escritos pela comunidade de computação. Alguns elementos são mais usuais (condicionais, repetições e funções), outras são menos utilizadas (documentação com as pré-condições e pós-condições) e outras não são tão convencionais (condicional de seleção).
A opção por ter tanto os elementos de uso geral e quanto algumas “invovações” vem do caráter didático a que este material se propõe a ter.
Documentação
Todos os algoritmos neste material conterão um cabeçalho de documentação. Nele são exibidos os seguintes elementos:
- Descrição;
- Pré-condições;
- Pós-condições.
A descrição é a caracterização do problema que o algoritmo resolve e tem a extensão necessária para apresentar com clareza o problema. Em particular, a descrição não apresenta como o problema é resolvido, pois isso é a parte das instruções.
As pré-condições e pós-condições reportam de forma tão precisa quanto possível, o que o algoritmo precisa e em que condições esses dados devem estar e também o que ele produz, dando detalhes para que não haja problemas em interpretar o que o algoritmo produz como resultado.
Declaração e uso de variáveis
Embora ocorram em alguns algoritmos, as declarações de variáveis não são empregadas nas soluções apresentadas. A ideia de declaração introduz um detalhamento desnecessário no pseudocódigo, pois levaria à necessidade de especificar tipos de dados e impor, eventualmente, limitações e particularidades a eles. Manteve-se, assim, um nível mais alto de abstração para as variáveis.
Os identificadores são expressos de forma relativamente livre, usando snake case e notação matemática. As atribuições usam
Elementos estruturais
Seguindo uma convenção geral, o pseudocódigo adotado segue padrões comuns a artigos científicos e muitos outros materiais disponíveis. Em particular, a formalização adotada no texto segue alguns elementos de estruturação importantes.
Execução sequencial
Cada instrução do algoritmo é escrita em sua própria linha, estabelecendo uma execução sequencial das instruções. Uma nova instrução somente será executada depois da anterior ter sido completamente finalizada.
Muitas vezes a inversão na ordem não impacta no resultado, mas uma ordem incorreta implica em uma solução incorreta.
Como o algoritmo é uma sequência de ordens que devem ser seguidas à risca, o modo verbal usado será sempre o imperativo.
Obtenção e apresentação de dados
Nos algoritmos, os dados necessários devem ser “entrados” de forma a produzir “saídas”. Por uma associação livre e direta, as entradas são as informações que um usuário digitaria para o programa utilizar, enquanto as saídas são os resultados apresentados no terminal.
Neste texto, as entradas estarão associadas principalmente ao verbo obter, enquanto a saída usa o verbo apresentar. Por associação às linguagens de programação, também é comum o uso dos verbos ler e escrever, respectivamente.
Na sequência é apresentada uma entrada e uma saída de dados.
Alternativamente, as mesmas instruções podem ser apresentadas como se segue. Nesta versão a verbosidade dá lugar a uma apresentação mais compacta e mais próxima a uma linguagem de programação.
Execução condicional
A execução condicional assume a forma tradicional da estrutura se, na qual a lista de instruções indicada somente deve ser executada quando a condição verificada for verdadeira.
Nesta estrutura condicional, a ação somente será executada se a condição indicada for verdadeira. Caso seja falsa, essa ação é simplesmente ignorada.
Alternativamente, uma ação pode ser indicada caso a condição não seja satisfeita, usando-se uma alternativa com senão.
Uma terceira forma de expressar a execução condicional com se é pelo sequenciamento de condições, cada uma excluindo a condição anterior.
Cada novo se somente é verificado caso o imediatamente anterior tenha condição avaliada como falsa.
Esta última construção da estrutura condicional equivale à apresentada na sequência.
As duas formas são equivalentes, porém a primeira é mais sintética e clara.
Outro modo de execução condicional pode ser indicado pela estrutura de seleção. Embora estruturas similares estejam presentes em linguagens de programação, esta alternativa é raramente usada em pseudocódigos em geral.
A estrutura de seleção é uma comparação por igualdades e tem a estrutura seguinte.
O conceito desta estrutura de condicional é a indicação de seleções diretas. Assim, entende-se que apenas uma das alternativas será executada e que os valores constantes indicados (cada \(c_i\) do exemplo anterior) serão distintos entre si.
A omissão do caso contrário representa a situação em que, não havendo coincidência com nenhuma das opções, nenhuma ação é realizada.
Qualquer seleção pode ser escrita com a estrutura condicional se.
Repetições
Instruções executadas repetidamente são representadas pelas repetições com enquanto, repita e para.
A estrutura enquanto utiliza o teste de continuidade da repetição no início, permitindo zero ou mais repetições. Para a condição é esperado uma expressão que resulte em verdadeiro ou falso.
A repetição com teste no final utiliza a estrutura repita, encerrada com até que, na qual consta a condição de término das repetições. A condição é avaliada apenas ao final de cada execução, o que implica que pelo menos a primeira das repetições tem que ser completada.
Tanto as repetições com enquanto quanto com repita são “abertas”, ou seja, dependem das ações nas instruções internas alterarem a condição para que laço seja interrompido.
As repetições definidas (i.e., não “abertas”) são expressas com para. Usualmente uma repetição deste tipo pressupões o conhecimento do número de vezes que as instruções serão executadas. Na sequência são apresentadas as estruturas com para.
Repetições com para podem ser abertas como no exemplo seguinte.
Esse uso é evitado (com sucesso relativo) neste material, dando-se preferência para laços com enquanto e repita quando o número de repetições é desconhecido.
Notação matemática \(\times\) notação programática
Os algoritmos apresentados em publicações científicas tendem a usar pseudocódigo com uma denotação muito próxima da matemática, ou seja, laçam mão de um formato mais formal, técnico e compacto. Como exemplos é apresentado o Algoritmo 1, além do já mencionado Algoritmo 2.
Algoritmo 1: Algoritmo de Bellman-Ford (adaptado de Cormen et al. (2002)).
Esse aspecto mais “matemático” contrasta com as escolhas feitas quando são codificados programas nas mais diversas linguagens de programação. Na sequência é apresentada uma versão (incompleta) do Algoritmo 1 codificada em Python. Nela, as opções foram por um código bem estruturado e organizado. Por exemplo, \(E[G]\), que é a notação formal para a lista de arestas foi subsituída pela variável lista_arestas, assim como \(u\) e \(v\) deram lugar aos (vértices) origem e destino.
# Inicia as distâncias de todos os vértices como infinito e a origem como 0
distancias = [float('inf')] * num_vertices
distancias[vertice_inicio] = 0
# Relaxa todas as arestas num_vertices-1 vezes
for _ in range(num_vertices - 1):
for origem, destino, peso in lista_arestas:
if (distancias[origem] != float('inf') and
distancias[origem] + peso < distancias[destino]):
distancias[destino] = distancias[origem] + peso
# Verifica ciclos de peso negativo
for origem, destino, peso in lista_arestas:
if (distancias[origem] != float('inf') and
distancias[origem] + peso < distancias[destino]):
return False
return TrueA resposta para qual seria a melhor representação tem uma resposta simples: depende.
Nenhuma delas é melhor ou pior que a outra, pois devem ser aplicadas em seus próprios contextos. Para o caso dos grafos orientados do Algoritmo 1, o uso de \(G\) para o grafo e \(u\) e \(v\) para arestas é o mais usual e, portanto, óbvio para quem conhece o assunto. Dessa forma, seu uso é apropriado e, também, conveniente.
Na escrita de programas e, em associação, de algoritmos computacionais, a notação matemática tende a ser substituída por nomes mais significativos, como origem (ou até vertice_origem), por exemplo. Nessa situação, a clareza do código é mais relevante.
Para exemplificar, o seguinte programa escrito em Fortran pode ser considerado. Sua função é, a partir de um salário inicial e de uma porcentagem de aumento, calcular o salário final resultante.
PROGRAM SCalc
IMPLICIT NONE
REAL :: S, P, A, NS
! Entrada de dados
PRINT *, "Salário:"
READ *, S
PRINT *, "Aumento (%):"
READ *, P
! Cálculo
A = S * (P / 100.0)
NS = S + A
! Exibição do resultado
PRINT *, "Salário atualizado:", NS
END PROGRAM SCalcNesse código, S pode ser facilmente associado ao salário, assim como P à porcentagem. Porém, porque NS? Talvez seja fácil ou talvez não chegar à conclusão de que a opção por NS se deve a Novo Salário. Nos programas, a opção da clareza leva a códigos como o seguinte, que apenas reapresenta o programa anterior usando uma notação mais direta e clara.
PROGRAM CalculoSalario
IMPLICIT NONE
REAL :: salario, percentual, aumento, novo_salario
! Entrada de dados
PRINT *, "Digite o salário atual:"
READ *, salario
PRINT *, "Digite a porcentagem de aumento:"
READ *, percentual
! Cálculo do aumento e do novo salário
aumento = salario * (percentual / 100.0)
novo_salario = salario + aumento
! Exibição do resultado
PRINT *, "O novo salário é:", novo_salario
END PROGRAM CalculoSalarioPara os algoritmos, portanto, valem os mesmos argumentos. A notação mais matemática pode ser usada em várias situações e a notação mais usualmente empregada em programas, em outras. Por uma questão de clareza, todo o material faz como opção a escolha de uma notação que preza mais pela clareza.
Em conclusão, os programas em Fortran apresentados seriam implementações do Algoritmo 2.
Algoritmo 2: Cálculo do aumento de um salário.
Para contastratar, o Algoritmo 3 seria a versão mais sintética e com menor clareza do Algoritmo 2. Quase uma versão “criptográfica” do anterior.
Algoritmo 3: Cálculo do aumento de um salário.
O uso de uma notação com nomes mais signficativos, embora pareça irrelevante em problemas pequenos, torna-se essencial para soluções mais complexas e, em consequência, com mais instruções.
Acostumar-se a fazer o melhor logo de início é a melhor alternativa!