Boas práticas para escrever algoritmos

É 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?

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 ou$field(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 $xy$x*y$a\bmod b$a%b¬ p $s\le t$s <= t$\lnot p$!p π$\sqrt{x}$sqrt(x)$\pi$PI$\infty$MAX_INT

  • Mas use para atribuição, para evitar o problema.$x\gets y$==

  • 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 $G / L$$G$$L$

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}

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.

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.