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 deste capítulo.
Objetivos do pseudocódigo
O pseudocódigo pode ser visto como uma mistura de aspectos mais formais, como computação ou notação matemática, com linguagem natural.
Como um primeiro exemplo é apresentado o Algoritmo 1, que considera uma forma de se obter indiretamente a altura de um prédio dados os comprimentos das sombras do prédio de de uma pessoa, juntamente com a altura dessa pessoa. Este tipo de algoritmo pode ser facilmente implementado em C.
Algoritmo 1: Estimativa da altura de um prédio em função de sobras projetadas.
Este é um típico problema e programa solicitado em listas de exercícios de cursos de programação. O algoritmo apresenta uma solução praticamente pronta para a implementação do programa, incluindo sugestões para os nomes das variáveis e até induzindo os comandos que serão usados. A escrita do Algoritmo 1 foi feita considerando que o algoritmo seria lido por um programador com, minimamente, as capacidades básicas de codificação.
Como um segundo exemplo de pseudocódigo, o Algoritmo 2 pode ser considerado.
Algoritmo 2: PNN based LPP, adaptado de Levada (2022)
Este algoritmo é uma adaptação do apresentado no artigo de Levada (2022) e, para entendê-lo por completo, tanto o texto do artigo deve ser lido quanto o leitor deve ter conhecimento sobre o tema abordado. O objetivo do algoritmo não é o entendimento do procedimento que ele realiza em detalhes, mas observar a sequência de passos para produzir o resultado desejado. Ele ainda envolve a integração da linguagem natural com notação matemática para representar as expressões e matrizes utilizadas. No algoritmo original não há a documentação com a descrição nem as pré e pós-condições, uma vez que ele está inserido na discussão apresentada pelo artigo como um todo.
O Algoritmo 2 não foi escrito para pronta implementação. Ele deixa muitos pontos em aberto, mesmo sendo claro quanto a todos os cálculos que devem ser feitos e em que sequência. Esse é um algoritmo de nível alto de abstração, ou seja, muitos detalhes são omitidos propositalmente em função do público-alvo, que são os leitores do artigo científico. Apresentar todos os detalhes, como o passo a passo da criação dos vetores de distâncias \(\vec{d}_i\) ou a própria fórmula usada para a distância somente tornaria o código desnecessariamente complexo, prejudicando a compreensão da estratégia da solução.
Público-alvo e nível de abstração
Quando um algoritmo vai ser escrito, é preciso ter claro qual é o público-alvo que ele pretende atingir. As instruções, portanto, assumem uma forma baseada no conhecimento prévio de quem vai interpretá-las. Essa decisão implica na escolha do nível de abstração que será empregado.
Um algoritmo escrito com nível de abstração baixo é aquele mais próximo do programa que será implementado. Ele costuma apresentar as variáveis e comandos de forma mais explícita. Quando o nível de abstração sobe, os detalhes de implementação são substituídos por descrições mais genéricas.
Supondo que o problema a ser resolvido seja a soma de duas matrizes de mesma dimensão, são apresentados algoritmos em níveis de abstração diferentes, todos corretos e abordando exatamente a mesma solução. O Algoritmo 3 possui um nível de abstração bastante alto, seguido pelo Algoritmo 4, o qual apresenta mais detalhes e pode ser considerado de nível médio; por sua vez, o Algoritmo 5 e o Algoritmo 6 já possuem nível baixo e se aproximam mais de uma possível implementação em um programa.
Algoritmo 3: Soma de duas matrizes de mesma dimensão (nível alto).
Algoritmo 4: Soma de duas matrizes de mesma dimensão (nível médio).
Algoritmo 5: Soma de duas matrizes de mesma dimensão (nível mais baixo).
Algoritmo 6: Soma de duas matrizes de mesma dimensão (nível baixo).
Os algoritmos são apresentados em quatro níveis de abstração diferentes. A Tabela 1 sumariza uma comparação desses algoritmos.
| Algoritmo | Nível | Comentário |
|---|---|---|
| Algoritmo 3 | Alto | Pressupõe o conhecimento de matrizes e suas operações; detalhes como as dimensões são omitidos. |
| Algoritmo 4 | Médio | Ainda considera o conhecimento sobre matrizes; há mais detalhes de como os dados são obtidos e como o cálculo da soma é feito. |
| Algoritmo 5 | Mais baixo | A necessidade de conhecer matrizes é mínima, bastando assumir cada elemento como uma variável separada; introduz a necessidade das dimensões para controle da somas; mantém uma linguagem mais natural. |
| Algoritmo 6 | Baixo | Não há praticamente necessidade de entender o que é uma matriz; uma estruturação de pseudocódigo é adicionada; cada ação é hiperdetalhada; a linguagem natural é mínima. |
Da mesma forma que o nível de abstração depende do público-alvo, também inexiste a necessidade de que um mesmo algoritmo mantenha o nível de abstração constante para todas suas partes. Desse modo, pontos menos importantes, ou seja, que não são o foco do algoritmo, podem ter nível mais alto enquanto outras partes podem ser mais detalhadas, deixando o nível mais baixo para explicitar pontos relevantes da solução.
Formalização do pseudocódigo
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á um convenção geral adotada pela comunidade, ficando um grupo de estruturas e aspectos relativamente consolidados.
Padronização
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 pré e pós-condições) e outras não sã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. Estes dois elementos são apresentados no ?@sec-nocoes-de-algoritmos.
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 7, além do já mencionado Algoritmo 2.
Algoritmo 7: 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 7 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 7, 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 8.
Algoritmo 8: Cálculo do aumento de um salário.
Para contastratar, o Algoritmo 9 seria a versão mais sintética e com menor clareza do Algoritmo 8. Quase uma versão “criptográfica” do anterior.
Algoritmo 9: Cálculo do aumento de um salário.
O uso de uma notação com nomes mais signficativos, embora parece 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!