Хорошая практика для написания алгоритмов

22

Речь идет о том, как эффективно мы можем выразить алгоритм под рукой. Мне нужно это для моего обучения студентов.

Я понимаю, что нет такой вещи, как стандартный способ написания псевдокода. Разные авторы следуют различным соглашениям.

Было бы полезно, если бы люди указывали на то, как они следуют и считают лучшим.

Есть ли книга, которая имеет дело с этим в деталях?

user3162
источник
9
«лучший» очень субъективен, я думаю, что вы должны изменить название и вместо того, чтобы спрашивать «лучший», спрашивайте, что люди делают на практике. Может быть, что-то вроде «как представить алгоритмы» или «хорошие практики для представления алгоритмов». Вы также можете захотеть быть более конкретным, представив алгоритмы: 1. для учащихся в старших классах 2. в учебнике 3. в работе конференции очень разные задачи.
Каве
1
Вы также можете проверить соответствующие разделы математического письма Кнута, Ларраби и Робертса.
Каве

Ответы:

26

Написание псевдокода похоже на написание кода: не очень важно, какой стандарт вы соблюдаете, если вы (и люди, с которыми вы пишете) действительно следует некоторому стандарту.

Но для справки, вот особенный стандарт, который я использую в своих конспектах лекций, исследовательских работах и ​​будущих книгах.

  • Используйте стандартный императивный синтаксис для потока управления и доступа к памяти - если, пока, для, return, array [index], function (arguments). Разобрать "еще, если".

    • Но использование вместо илиfield(record)record.fieldrecord->field
  • xyx*yamodba%bsts <= t¬p!pxsqrt(x)πPIMAX_INT

    • Но используйте для назначения, чтобы избежать проблемы.xy==

    • Но избегайте обозначений (и псевдокодов!) Полностью, если английский понятнее.

      • Симметрично, избегайте английского, если обозначения понятнее!
  • Минимизируйте синтаксический сахар - укажите блочную структуру с помощью последовательного отступа (как на Python). Пропустите сладкие ключевые слова, такие как «начало / конец» или «do / od» или «fi». Опустить номера строк. Вы не подчеркнуть ключевые слова , как «за» или «а» или «если», установив их в другой typefaceили стиле . Когда-либо. Просто не надо.

    • Но набирайте имена алгоритмов и константы в \ textc {Small Caps}, имена переменных в курсиве и буквенные строки в sans serif.

    • Но добавьте небольшое количество вертикального «дышащего» пространства ( \\[0.5ex]) между значимыми кусками кода.

  • Не указывайте неважные детали. Если не имеет значения, в каком порядке вы посещаете вершины, просто скажите «для всех вершин».

Например, вот рекурсивная формулировка алгоритма минимального связующего дерева Боровки . Ранее я определил как график, полученный из G путем сжатия всех ребер в множестве L , и Flatten как подпрограмму, которая удаляет петли и параллельные ребра.G/LGL

Алгоритм Боровки

Я использую свою собственную облегченную algorithmсреду LaTeX для набора псевдокода. (Это просто tabbingсреда внутри \fbox.) Вот мой исходный код для алгоритма Боровки:

\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ε
источник
fj(v)jthv
@SureshVenkat: Это то, как вы обычно делаете это на функциональных языках, а также обозначения в TAoCP. (Очевидно, я не могу знать, именно поэтому Jɛ ff E использует эту запись.)
Раду GRIGore
5
Основная причина быть осторожным с псевдокодом состоит в том, что легко запутаться в алгоритме, поэтому важно подчеркнуть некоторые вещи. Приведенный выше пример Джеффа для Борувки иллюстрирует это. В коде L рассматривается как набор. Край uv может быть самым легким краем, падающим на u, а также на v, поэтому он добавляется дважды в цикле, но это не имеет значения, если вы думаете о L как о множестве. Тем не менее, это не очевидно, и кто-то, кто реализует это, может быть легко отключен, если они реализуют L как список.
Чандра Чекури
2
@ChandraChekuri: Да, неправильная реализация множеств может вызвать проблемы в алгоритмах, которые манипулируют множествами.
Джефф
1
@SureshVenkat: О, это. Нет, я терпеть не могу. Жирные ключевые слова заставляют младенца плакать. Дейкстра должен потерять свою награду Тьюринга за то, что ввел в действие это типичное условное обозначение.
Джефф
11

Я склонен использовать что-то похожее на синтаксис Python. Python уже достаточно близок к псевдокоду, и в некоторых случаях мой псевдокод может превратиться в реальный рабочий код.

Дэвид Эппштейн
источник
Я тоже, но в Ruby. С помощью github вы можете легко обмениваться исполняемыми фрагментами, чтобы играть с ними. gist.github.com/chadbrewbaker/7202412
Чад Brewbaker
Python, однако, не подходит для представления линейной алгебры. Я думаю, что октава лучше подходит в этом случае (ближе к псевдокоду).
Габорист
3

Если вы хотите иметь определенный код (т. Е. Практически без математики, близкий к реальному программированию), вы можете подумать о том, чтобы иметь код, который фактически компилируется. Это имеет несколько преимуществ:

  • Вы получаете подсветку синтаксиса везде.
  • Компилятор проверяет синтаксис для вас и обеспечивает согласованность.
  • Вы можете выполнить модульное тестирование своих реализаций, чтобы улучшить качество кода.
  • Вы можете запустить алгоритм и сравнить измеренное время выполнения с анализом (таким образом мотивируя продвинутые методы анализа).

Профессор в моем университете делает это в своем курсе алгоритмов. Его язык выбора - Модула. Я не думаю, что конкретный выбор языка имеет значение, хотя. Просто придерживайтесь одного (на каждую парадигму), которое наилучшим образом соответствует вашему уровню абстракции.

Рафаэль
источник
«Просто придерживайтесь одного (на каждую парадигму), которое наилучшим образом соответствует вашему уровню абстракции». Я думаю, что это отличный совет, чтобы найти альтернативу псевдокоду. Существует множество языков, и почти всегда есть хотя бы один, предназначенный для простого синтаксиса для конкретной парадигмы: Ada для параллельного проектирования, Octave для линейной алгебры, Python для процедурного, NetLogo для систем с несколькими агентами, Prolog для логики, CLIPS для программирование на основе правил и т. д.
Габорист
@gaborous Если у вас может быть читабельный, абстрактный код - дерзайте. К сожалению, я подозреваю, что это приведет к тому, что вы будете использовать по крайней мере три языка в любом большом объеме работы; это тоже было бы прискорбно.
Рафаэль
конечно, я согласен, что для более крупного кода нет языка, но для небольших основных алгоритмов часто можно найти язык, очень близкий к псевдокоду.
Габорист