Boas práticas para escrever algoritmos

22

É sobre a eficácia com que podemos expressar um algoritmo em questão. Eu preciso disso para o meu ensino de graduação.

Entendo que não existe uma maneira padrão de escrever um pseudo-código. Diferentes autores seguem diferentes convenções.

Seria útil se as pessoas aqui indicassem o modo como seguem e pensam o melhor.

Existe algum livro que lide com isso com bons detalhes?

user3162
fonte
9
"best" é muito subjetivo, acho que você deve modificar o título e, em vez de pedir "best", pergunte o que as pessoas fazem na prática. Talvez algo como "como apresentar algoritmos" ou "boas práticas para apresentar algoritmos". Você também pode querer ser mais específico desde a apresentação de algoritmos: 1. para alunos de uma turma de graduação 2. de um livro didático 3. de um artigo de conferência são tarefas muito diferentes.
Kaveh
1
Você também pode verificar as seções relevantes da Escrita matemática de Knuth, Larrabee e Roberts.
Kaveh

Respostas:

26

Escrever pseudocódigo é como escrever código: não é particularmente importante qual padrão você segue, desde que você (e as pessoas com quem você escreve) realmente siga algum padrão.

Mas, para constar, aqui está o padrão idiossincrático que uso em minhas anotações de aula, trabalhos de pesquisa e próximo livro.

  • Use a sintaxe imperativa padrão para fluxo de controle e acesso à memória - se, enquanto, para, retornar, matriz [índice], função (argumentos). Soletre "else if".

    • Mas use o vez de oufield(record)record.fieldrecord->field
  • Use notação matemática padrão para matemática - Escreva vez de , vez de , vez de , não vez de , vez de , em vez de vez de , vez de , etc.a mod bxyx*yamodba%b¬ p sts <= t¬p!p πxsqrt(x)πPIMAX_INT

    • Mas use para atribuição, para evitar o problema.xy==

    • Mas evite a notação (e o pseudocódigo!) Inteiramente se o inglês for mais claro.

      • Simetricamente, evite o inglês se a notação for mais clara!
  • Minimize o açúcar sintático - Indique a estrutura do bloco por recuo consistente (à la Python). Omita palavras-chave açucaradas como "começo / fim" ou "faça / od" ou "fi". Omita números de linha. Você não enfatizar palavras-chave como "a favor" ou "quando" ou "se", definindo-as de uma forma diferente typefaceou estilo . Sempre. Apenas não.

    • Porém, nomes e constantes de tipos de algoritmos em \ textc {Small Caps}, nomes de variáveis ​​em itálico e cadeias literais em sans serif.

    • Mas adicione uma pequena quantidade de espaço "respiratório" vertical ( \\[0.5ex]) entre pedaços de código significativos.

  • Não especifique detalhes sem importância. Se não importa qual ordem você visita os vértices, basta dizer "para todos os vértices".

Por exemplo, aqui está uma formulação recursiva do algoritmo de spanning tree mínimo de Borůvka . Eu já defini como o gráfico obtido de contratando todas as arestas no conjunto e Flatten como uma sub-rotina que remove loops e arestas paralelas.G LG/LGL

Algoritmo de Borůvka

Eu uso meu próprio algorithmambiente leve do LaTeX para digitar pseudocódigo. (É apenas um tabbingambiente dentro de um \fbox.) Aqui está o meu código-fonte para o algoritmo de Borůvka:

\begin{algorithm}
	\textul{$\textsc{Borůvka}(G)$:}\+
\\	if $G$ has no edges\+
\\		return $\varnothing$\-
\\[0.5ex]
	$L \gets \varnothing$
\\	for each vertex $v$ of $G$\+
\\		add the lightest edge incident to $v$ to $L$\-
\\[0.5ex]
	return $L \cup \textsc{Borůvka}(\textsc{Flatten}(G / L))$
\end{algorithm}
Jeffε
fonte
interessante que você use campo (registro) em vez de registro [campo]. Eu imagino que essa seja a " é a coordenada de " do mundo? j t h vfj(v)jthv
precisa
@SureshVenkat: É como você costuma fazer em linguagens funcionais e também na notação no TAoCP. (Obviamente, eu não posso saber se é por isso Jɛ ff E usa esta notação.)
Radu Grigore
5
O principal motivo para ter cuidado com o pseudo-código é que é fácil ficar confuso sobre o algoritmo, por isso é importante enfatizar algumas coisas. O exemplo de Jeff acima para Boruvka ilustra isso. No código L está sendo tratado como um conjunto. Um edge uv pode ser o incidente de borda mais leve para u e v, por isso é adicionado duas vezes no loop, mas não importa se você pensa em L como um conjunto. No entanto, isso não é óbvio e alguém que implementa isso pode ser facilmente tropeçado se implementar L como uma lista.
Chandra Chekuri
2
@ChandraChekuri: Sim, implementar conjuntos incorretamente pode causar problemas em algoritmos que manipulam conjuntos.
Jeffε
1
@SureshVenkat: Ah, isso. Não, eu não aguento mais. Palavras-chave em negrito fazem o bebê Jesus chorar. Dijkstra deve perder seu prêmio de Turing por introduzir essa convenção tipográfica execrável.
Jeffε
11

Eu costumo usar algo parecido com a sintaxe do Python. O Python está próximo o suficiente para pseudocódigo já que, em alguns casos, meu pseudocódigo pode transformar-se em código de trabalho real.

David Eppstein
fonte
Eu também, mas em Ruby. Com o github gists, você pode compartilhar facilmente snippets executáveis ​​para que eles possam brincar. gist.github.com/chadbrewbaker/7202412
Chad Brewbaker
Python, no entanto, não é bom para representar álgebra linear. Octave é um ajuste melhor, eu acho neste caso (mais próximo do pseudocódigo).
gaborous
3

Se você deseja ter um código definido (ou seja, pouca ou nenhuma matemática, próximo à programação real), convém considerar um código que realmente seja compilado. Isso tem várias vantagens:

  • Você obtém a sintaxe destacada em todos os lugares.
  • O compilador verifica a sintaxe e reforça a consistência.
  • Você pode testar suas implementações para melhorar a qualidade do código.
  • Você pode executar o algoritmo e comparar os tempos de execução medidos com as análises (motivando assim as técnicas avançadas de análise).

Um professor da minha universidade faz isso em seu curso de algoritmos. Sua língua de escolha é Modula. Não acho que a escolha específica da linguagem seja importante. Basta manter um (por paradigma) que melhor se adapte ao seu nível de abstração.

Rafael
fonte
"Basta manter um (por paradigma) que melhor se adapte ao seu nível de abstração." Eu acho que esse é um ótimo conselho para encontrar uma alternativa ao pseudocódigo. Existem muitas linguagens, e quase sempre há pelo menos uma que visa uma sintaxe simples para paradigmas específicos: Ada para design simultâneo, Octave para álgebra linear, Python para procedimentos, NetLogo para sistemas multi-agentes, Prolog para lógica, CLIPS para programação baseada em regras, etc.
gaborous
@gaborous Se você pode ter um código legível e abstrato - vá em frente. Infelizmente, suspeito que isso fará com que você use pelo menos três idiomas em qualquer corpo de trabalho maior; isso seria lamentável também.
Raphael
é claro que concordo que em códigos maiores não há linguagem, mas para algoritmos pequenos e principais, geralmente é possível encontrar uma linguagem muito próxima do pseudocódigo.
gaborous 27/05