Представление кода алгебраически

Question

У меня есть несколько небольших алгоритмов, которые я хотел бы написать в статье. Они относительно короткие и лаконичные. Однако вместо того, чтобы писать их в псевдокоде (например, Кормен или даже Кнут), я хотел бы написать их алгебраическое представление (более линейный и лучший рендеринг в LaTeX). Тем не менее, я не могу найти ресурсы для лучшего обозначения для этого, если есть что-то: например, как мне представить цикл? Если? Добавление кортежа в список?

Кто-нибудь из вас сталкивался с этой проблемой и как-то решил ее?

Спасибо.

РЕДАКТИРОВАТЬ : Спасибо, люди. Я думаю, что плохо справился с формулировкой вопроса. Опять же, надеясь, что я проясню это: каковы общие обозначения для разговоров о циклах и предложениях if-then в математической записи? Например, я могу использовать $acc \leftarrow acc \cup \langle i,i+1 \rangle$ для представления метода добавления списка.

Answer 1

Не делай этого. Вы отклоняетесь от того, что люди ожидают увидеть, когда читают статью об алгоритмах. Вы должны следовать ожидаемым практикам; Ваши идеи с большей вероятностью привлекут внимание, которого они заслуживают. В Риме делай так, как делают римляне.

Форматирование кода (или псевдокода, как это может быть) в бумаге с латексом очень легко См., Например, Форматирование кода в LaTeX .

Answer 2

Я часто вижу if-выражения в математических обозначениях. Обычной вещью для цикла является рекуррентное отношение , или, что эквивалентно, функция, определенная рекурсивно.

Вот как функция Аккермана определяется в Википедии, например:

0 and n=0; and A(m-1, A(m, n-1)) if m>0 and n>0.">

Эта картинка хороша, потому что она выглядит математически, но вы можете четко напечатать ее почти точно так, как написано, и иметь реализацию. Не всегда возможно достичь этого.

Другие математические обозначения, которые соответствуют циклам, включают ∑-нотацию для суммирования и нотацию построителя множеств .

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

Answer 3

Символ для общих циклов не существует; обычно вы используете оператор суммирования . «если» представлено с использованием значений , а для «добавления кортежа в список» вы должны использовать union .

Однако , в общем, немного многословия не обязательно плохая вещь - иногда, особенно для сложных алгоритмов, лучше всего изложить это на простом английском языке, используя примеры и диаграммы. Это вдвойне верно для не кодеров.

Подумайте об этом: когда вы читаете учебник по математике об алгоритме Евклида для GCD или о сите Эратосфена, как он написан? Обычно сам алгоритм находится в прозе, в то время как доказательство алгоритма - то, где математические символы лежат.

Answer 4

Я бы скопировал Кнута. Мало кто знает, как лучше общаться с ним в информатике.

Answer 5

Lisp начинался как математическая запись вычислительной модели, чтобы у лектора был лучший инструмент, чем машины Тьюринга. Случайно оказывается, что это может быть реализовано в ассемблере - таким образом, lisp, язык программирования родился.

Но я не думаю, что это действительно то, что вы ищете, поскольку вычислительная модель, описанная в lisp, не имеет циклов: вместо этого используется рекурсия. Синтаксис происходит от алгебры, где фигурные скобки обозначают оценку-это-и-заменитель-результат. Действительно, модель вычислений в Лиспе - это, по сути, замена - то, что по сути является алгеброй.

Действительно, большинство функциональных языков, таких как Lisp, Haskell и Erlang, являются производными от математики. Хаскель на самом деле является результатом доказательства того, что лямбда-исчисление может быть использовано для реализации систем типов. Так что Хаскелл, как Лисп, родился из чистой математики. Но опять же, синтаксис не тот, к которому вы, вероятно, привыкли бы.

Вы, конечно, можете объяснить синтаксис Lisp и Haskell математикам, и они воспримут это как "игру". Языковые конструкции, такие как циклы, рекурсия и условные выражения, могут быть проверены вне правил игры, а не реализованы вслепую, как в других языках. Это привело бы вас в сферу комбинатроники, еще одной области математики. Действительно, в комбинатронике даже концепция чисел может быть построена из правил игры, а не как часть языка (церковные цифры Google).

Так что взгляните на Lisp / Scheme, Erlang и Haskell, если хотите. Эрланг особенно имеет синтаксис, близкий к тому, что вы хотите:

add(a,b) -> a + b

Но я рекомендую писать в C-подобном псевдокоде. Это своего рода самый низкий общий знаменатель в языках программирования. Имеет синтаксис, который довольно легко понять и очистить. И синтаксис функции даже происходит от функций в математике. Помните f(x)?

Как плюс, математики привыкли писать C, статистики - писать C (хотя обычно они предпочитают R), физики - писать C, программисты привыкли хотя бы смотреть на C (я знаю несколько, кто никогда не трогал C).

На самом деле, поцарапайте это. Вы упоминаете, что вашей целевой аудиторией являются статистики. Пишите в R

Answer 6

Вы можете взглянуть на Haskell. Haskell хорошо форматируется в латексе, имеет хороший алгебраический синтаксис, и вы даже можете скомпилировать латексный файл с Haskell, при условии, что код обернут в \begin{code} и \end{code}. Смотрите здесь: http://www.haskell.org/haskellwiki/Literate_programming. Вероятно, есть грамотные инструменты программирования для других языков.

Answer 7

APL ?Единственная проблема заключается в том, что мало кто может прочитать его.

Answer 8

Как-то так сайт описывает?