Buenas prácticas para escribir algoritmos

22

Esto se trata de cuán efectivamente podemos expresar un algoritmo a mano. Necesito esto para mi enseñanza de pregrado.

Entiendo que no existe una forma estándar de escribir un pseudocódigo. Diferentes autores siguen diferentes convenciones.

Sería útil si las personas aquí señalan la forma en que siguen y piensan cuál es la mejor.

¿Hay algún libro que trate esto con un buen detalle?

usuario3162
fuente
99
"mejor" es muy subjetivo, creo que debería modificar el título y en lugar de pedir "mejor" pregunte qué hace la gente en la práctica. Tal vez algo como "cómo presentar algoritmos" o "buenas prácticas para presentar algoritmos". También es posible que desee ser más específico, ya que presentar algoritmos: 1. a los estudiantes en una clase de pregrado 2. en un libro de texto 3. en un documento de conferencia son tareas muy diferentes.
Kaveh
1
También puede consultar las secciones relevantes de Escritura matemática de Knuth, Larrabee y Roberts.
Kaveh

Respuestas:

26

Escribir pseudocódigo es como escribir código: no es particularmente importante qué estándar sigues, siempre y cuando tú (y las personas con las que escribes) realmente sigan algún estándar.

Pero para que conste, aquí está el estándar idiosincrásico que uso en mis notas de clase, trabajos de investigación y el próximo libro.

  • Utilice la sintaxis imperativa estándar para el flujo de control y el acceso a la memoria: if, while, for, return, array [index], function (argumentos). Deletrea "si no".

    • Pero use Fyomilre(rmidoorre) lugar de record.fieldorecord->field
  • Xyx*yunamodsia%bsts <= t¬pags!pXsqrt(x)πPIMAX_INT

    • Pero use para la asignación, para evitar el problema.Xy==

    • Pero evite la notación (¡y el pseudocódigo!) Por completo si el inglés es más claro.

      • Simétricamente, ¡evita el inglés si la notación es más clara!
  • Minimice el azúcar sintáctico: indique la estructura de bloques mediante una sangría consistente (a la Python). Omita palabras clave azucaradas como "comienzo / fin" o "do / od" o "fi". Omitir números de línea. No no hacer hincapié en palabras clave como "a favor" o "mientras que" o "si" mediante el establecimiento de ellos de una manera diferente typefaceo estilo . Siempre. Solo no lo hagas.

    • Pero los nombres y constantes de algoritmos tipográficos en \ textc {Small Caps}, nombres de variables en cursiva y cadenas literales en sans serif.

    • Pero agregue una pequeña cantidad de espacio vertical de "respiración" ( \\[0.5ex]) entre fragmentos de código significativos.

  • No especifique detalles sin importancia. Si no importa en qué orden visita los vértices, simplemente diga "para todos los vértices".

Por ejemplo, aquí hay una formulación recursiva del algoritmo de árbol de expansión mínimo de Borůvka . Anteriormente definí como el gráfico obtenido de al contraer todos los bordes en el conjunto , y Flatten como una subrutina que elimina los bucles y los bordes paralelos.G Lsol/ /LsolL

Algoritmo de Borůvka

Utilizo mi propio algorithmentorno ligero de LaTeX para componer pseudocódigo. (Es solo un tabbingentorno dentro de un \fbox.) Aquí está mi código fuente para el 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ε
fuente
Es interesante que utilice field (record) en lugar de record [field]. Me imagino que esta es la " vFj(v)jthv
@SureshVenkat: así es como lo haces habitualmente en lenguajes funcionales, y también la notación en TAoCP. (Obviamente, no puedo saber si es por eso que Jɛ ff E usa esta notación.)
Radu GRIGore
55
La razón principal para tener cuidado con el pseudocódigo es que es fácil confundirse con el algoritmo, por lo que es importante enfatizar algunas cosas. El ejemplo anterior de Jeff para Boruvka ilustra esto. En el código L se trata como un conjunto. Un borde uv puede ser el incidente de borde más ligero para usted y v, por lo que se agrega dos veces en el bucle, pero no importa si piensa en L como un conjunto. Sin embargo, esto no es obvio y alguien que lo implemente puede tropezarse fácilmente si implementan L como una lista.
Chandra Chekuri
2
@ChandraChekuri: Sí, implementar conjuntos incorrectamente puede causar problemas en los algoritmos que manipulan los conjuntos.
Jeff el
1
@SureshVenkat: Oh, eso. No, no lo soporto. Las palabras clave en negrita hacen llorar al niño Jesús. Dijkstra debería perder su premio Turing por presentar esa convención tipográfica execrable.
Jeff el
11

Tiendo a usar algo parecido a la sintaxis de Python. Python ya está lo suficientemente cerca del pseudocódigo que, en algunos casos, mi pseudocódigo puede convertirse en un código de trabajo real.

David Eppstein
fuente
Yo también, pero en Ruby. Con github gists puedes compartir fácilmente fragmentos ejecutables para que jueguen. gist.github.com/chadbrewbaker/7202412
Chad Brewbaker
Sin embargo, Python no es bueno para representar álgebra lineal. Octave es una mejor opción, creo en este caso (más cerca del pseudocódigo).
Gaborous
3

Si desea tener un código definido (es decir, poco o nada de matemáticas, cerca de la programación real), puede considerar tener un código que realmente compila. Esto tiene varias ventajas:

  • Obtienes resaltado de sintaxis en todas partes.
  • El compilador verifica la sintaxis por usted y aplica consistencia.
  • Puede probar sus implementaciones para mejorar la calidad del código.
  • Puede ejecutar el algoritmo y comparar los tiempos de ejecución medidos con los análisis (lo que motiva las técnicas de análisis avanzadas).

Un profesor de mi universidad hace esto en su curso de algoritmos. Su lenguaje de elección es Modula. Sin embargo, no creo que la elección particular del idioma importe. Simplemente manténgase en uno (por paradigma) que mejor se adapte a su nivel de abstracción.

Rafael
fuente
"Solo mantén una (por paradigma) que se ajuste mejor a tu nivel de abstracción". Creo que este es un gran consejo para encontrar una alternativa al pseudocódigo. Hay muchos lenguajes, y casi siempre hay al menos uno que apunta a una sintaxis simple para un paradigma específico: Ada para diseño concurrente, Octave para álgebra lineal, Python para procedimientos, NetLogo para sistemas de múltiples agentes, Prolog para lógica, CLIPS para programación basada en reglas, etc.
gaborous
@gaborous Si puede tener un código abstracto y legible, hágalo. Desafortunadamente, sospecho que esto hará que use al menos tres idiomas en cualquier cuerpo de trabajo más grande; eso sería desafortunado también.
Rafael
Por supuesto, estoy de acuerdo con que para un código más grande no hay lenguaje, pero para algoritmos pequeños y centrales, a menudo es posible encontrar un lenguaje que esté muy cerca del pseudocódigo.
Gaborous