Псевдокод

В информатике с псевдокод — это описание шагов алгоритма использованием сочетания соглашений языков программирования (таких как оператор присваивания , условный оператор , цикл ) с неформальными, обычно не требующими пояснений, обозначениями действий и условий. ^[1]^[2] Хотя псевдокод имеет общие характеристики с обычными языками программирования , он предназначен для чтения человеком, а не для управления машиной. В псевдокоде обычно отсутствуют детали, необходимые для машинной реализации алгоритма, а это означает, что псевдокод можно проверить только вручную. ^[3] Язык программирования дополняется подробностями описания естественного языка , где это удобно, или компактными математическими обозначениями . Цель использования псевдокода состоит в том, чтобы людям было легче его понять, чем код обычного языка программирования, и чтобы он представлял собой эффективное и независимое от среды описание ключевых принципов алгоритма. Он обычно используется в учебниках и научных публикациях для документирования алгоритмов, а также при планировании программного обеспечения и других алгоритмов.

псевдокода Не существует широкого стандарта синтаксиса , поскольку программа в псевдокоде не является исполняемой программой; однако существуют определенные ограниченные стандарты (например, академическая оценка). Псевдокод напоминает программы-скелетоны , которые можно скомпилировать без ошибок. Блок-схемы , drakon-charts и диаграммы Unified Modeling Language (UML) можно рассматривать как графическую альтернативу псевдокоду, но для них требуется больше места на бумаге. Такие языки, как HAGGIS, устраняют разрыв между псевдокодом и кодом, написанным на языках программирования.

Приложение

В учебниках и научных публикациях, связанных с информатикой и численными вычислениями , при описании алгоритмов часто используется псевдокод, чтобы все программисты могли их понять, даже если не все они знают одни и те же языки программирования. В учебниках обычно имеется введение, объясняющее конкретные используемые условные обозначения. Уровень детализации псевдокода в некоторых случаях может приближаться к уровню детализации формализованных языков общего назначения.

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

Псевдокод также используется в стандартизации. Например, в стандартах MPEG широко используется формальный C -подобный псевдокод, и его невозможно понять без понимания деталей кода. ^[4]

Синтаксис

Псевдокод обычно фактически не подчиняется синтаксическим правилам какого-либо конкретного языка; не существует систематической стандартной формы. Некоторые авторы заимствуют стиль и синтаксис управляющих структур некоторых традиционных языков программирования, хотя это не рекомендуется. ^[5]^[6] Некоторые источники синтаксиса включают Fortran , Pascal , BASIC , C , C++ , Java , Lisp и ALGOL . Объявления переменных обычно опускаются. Вызовы функций и блоки кода, например код, содержащийся в цикле, часто заменяются однострочным предложением на естественном языке.

Таким образом, в зависимости от автора псевдокод может сильно различаться по стилю: от почти точной имитации реального языка программирования, с одной стороны, до описания, приближающегося к форматированной прозе, с другой.

Эта гибкость имеет как основные преимущества, так и недостатки: с положительной стороны, ни один исполняемый язык программирования «не может превзойти удобство изобретения новых конструкций по мере необходимости и предоставления читателю возможности попытаться вывести их значение из неформальных объяснений», с отрицательной стороны: «непроверенный код обычно неверно». ^[7]

Пример псевдокода (для математической игры fizz buzz )

Паскаль в стиле:

procedure fizzbuzz;
  for i := 1 to 100 do
    print_number := true;
    if i is divisible by 3 then begin
      print "Fizz";
      print_number := false;
    end;
    if i is divisible by 5 then begin
      print "Buzz";
      print_number := false;
    end;
    if print_number, print i;
    print a newline;
  end

Стиль С:

fizzbuzz() {
  for (i = 1; i <= 100; i++) {
    print_number = true;
    if (i is divisible by 3) {
      print "Fizz";
      print_number = false;
    }
    if (i is divisible by 5) {
      print "Buzz";
      print_number = false;
    }
    if (print_number) print i;
    print a newline;
  }
}

Стиль Python:

def fizzbuzz():
  for i in range(1,101): 
    print_number = true
    if i is divisible by 3: 
      print "Fizz"
      print_number = false
    if i is divisible by 5:
      print "Buzz"
      print_number = false
    if print_number: print i
    print a newline

Псевдокод математического стиля

В числовых вычислениях псевдокод часто состоит из математических обозначений , обычно из матриц и теории множеств , смешанных со структурами управления обычного языка программирования и, возможно, также описаниями на естественном языке . Это компактное и зачастую неформальное обозначение, понятное широкому кругу людей с математическим образованием, которое часто используется для описания математических алгоритмов . Например, оператор суммы ( нотация с заглавной буквой «сигма» ) или оператор произведения ( нотация с заглавной буквой «пи» ) могут представлять цикл for и структуру выбора в одном выражении:

Return  $\sum _{k\in S}x_{k}$

Обычно , отличный от ASCII для математических уравнений используется набор текста , например, с помощью языков разметки, таких как TeX или MathML , или собственных редакторов формул .

Псевдокод математического стиля иногда называют пиджин-кодом , например пиджин ALGOL (происхождение концепции), пиджин Fortran , пиджин BASIC , пиджин Pascal , пиджин C и пиджин Lisp .

Общие математические символы

Тип операции	Символ	Пример
Назначение	← или :=	`c ← 2πr`, `c := 2πr`
Сравнение	=, ≠, <, >, ≤, ≥
Арифметика	+, −, ×, /, мод
Пол/потолок	⌊, ⌋, ⌈, ⌉	`a ← ⌊b⌋ + ⌈c⌉`
Логический	и , или
Суммы, произведения	С П	`h ← Σ_a∈A 1/a`

Пример

Ниже приведен более длинный пример псевдокода математического стиля для алгоритма Форда – Фулкерсона :

algorithm ford-fulkerson is
    input: Graph G with flow capacity c, 
           source node s, 
           sink node t
    output: Flow f such that f is maximal from s to t

    (Note that f_(u,v) is the flow from node u to node v, and c_(u,v) is the flow capacity from node u to node v)

    for each edge (u, v) in G_E do
        f_{(u, v)} ← 0
        f_{(v, u)} ← 0

    while there exists a path p from s to t in the residual network G_f do
        let c_f be the flow capacity of the residual network G_f
        c_f(p) ← min{c_f(u, v) | (u, v) in p}
        for each edge (u, v) in p do
            f_{(u, v)} ←  f_{(u, v)} + c_f(p)
            f_{(v, u)} ← −f_{(u, v)}

    return f

Машинная компиляция языков стиля псевдокода

Грамматика естественного языка в языках программирования

Различные попытки привнести элементы грамматики естественного языка в компьютерное программирование привели к появлению таких языков программирования, как HyperTalk , Lingo , AppleScript , SQL , Inform и в некоторой степени Python . В этих языках круглые скобки и другие специальные символы заменяются предлогами, что приводит к весьма многословному коду. Эти языки обычно являются динамически типизированными , что означает, что объявления переменных и другой шаблонный код могут быть опущены. Такие языки могут облегчить человеку, не знающему язык, понимание кода и, возможно, также изучение языка. Однако сходство с естественным языком обычно носит скорее косметический, чем подлинный характер. Правила синтаксиса могут быть такими же строгими и формальными, как и в обычном программировании, и не обязательно облегчают разработку программ.

Математические языки программирования

Альтернативой использованию математического псевдокода (включающего нотацию теории множеств или матричные операции) для документирования алгоритмов является использование формального математического языка программирования, который представляет собой смесь математической нотации, отличной от ASCII, и структур управления программой. Затем код может быть проанализирован и интерпретирован машиной.

формальных Некоторые языки спецификаций включают нотацию теории множеств с использованием специальных символов. Примеры:

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

Язык программирования (APL) и его диалекты APLX и A+ .
Маткад .

См. также

Ссылки

^ Рейзиг 2007 , с. 23, Псевдокодовые программы и их семантика.
^ Часто повторяемое определение псевдокода, по крайней мере, с 2003 года, представляет собой «подробное, но читаемое описание того, что должна делать компьютерная программа или алгоритм, выраженное на формальном естественном языке».
^ Улате-Кабальеро, Брайан Александер; Беррокаль-Рохас, Аллан; Идальго-Сеспедес, Джейссон (2021). «Параллельный и распределенный псевдокод: систематический обзор литературы». XLVII Латиноамериканская компьютерная конференция (CLEI) 2021 г .: 1–10. дои : 10.1109/CLEI53233.2021.9640222 .
^ Митчелл и др. 1996 , с. 105.
^ МакКоннелл, Стив (2004). Код завершен . Пирсон Образование. п. 54. ИСБН 978-0-7356-1967-8 . Избегайте синтаксических элементов целевого языка программирования.
^ Приглашение к информатике, 8-е издание Шнайдера/ Герстинг , «Сохраняйте язык операторов независимым», как указано в этом вопросе по обмену стеками.
^ Лэмпорт, Лесли (2 января 2009 г.). «Язык алгоритмов PlusCal» (PDF) . Исследования Майкрософт . Проверено 28 мая 2024 г.

Дальнейшее чтение

Зобель, Джастин (2013). «Алгоритмы». Написание статей по информатике (второе изд.). Спрингер. ISBN 978-1-85233-802-2 .
Рой, Джеффри Дж. (2006). «Проектирование и объяснение программ с помощью грамотного псевдокода». Журнал образовательных ресурсов в области вычислительной техники . 6 (1). Ассоциация вычислительной техники (ACM): 1. doi : 10.1145/1217862.1217863 . ISSN 1531-4278 . S2CID 25810599 .
Улате-Кабальеро, Брайан Александер; Беррокаль-Рохас, Аллан; Идальго-Сеспедес, Джейссон (25 октября 2021 г.). «Параллельный и распределенный псевдокод: систематический обзор литературы». XLVII Латиноамериканская компьютерная конференция (CLEI) 2021 г. IEEE. стр. 1–10. дои : 10.1109/clei53233.2021.9640222 . ISBN 978-1-6654-9503-5 .
Райзиг, Вольфганг (2007). «Абстрактные конечные автоматы для класса» . Логика языков спецификации . Монографии по теоретической информатике. Серия EATCS. Шпрингер Берлин Гейдельберг. стр. 15–46. ISBN 978-3-540-74107-7 . Проверено 5 октября 2023 г.
Митчелл, Джоан Л.; Пеннебейкер, Уильям Б.; Фогг, Чад Э.; ЛеГалл, Дидье Дж. (1996). «Псевдокод и блок-схемы». Стандарт сжатия видео MPEG . Нью-Йорк, штат Нью-Йорк: Springer US. стр. 105–116. дои : 10.1007/0-306-46983-9_6 . ISBN 978-0-412-08771-4 .
Беллами, Рэйчел (1 июня 1994 г.). «Что делает псевдокод? Психологический анализ использования псевдокода опытными программистами». Взаимодействие человека и компьютера . 9 (2). Информа UK Limited: 225–246. дои : 10.1207/s15327051hci0902_3 . ISSN 0737-0024 .

Внешние ссылки

Стандарт псевдокода
Сборник ACM алгоритмов
Рекомендации по псевдокодированию , PDF-файл.

[FOOTNOTEReisig200723Pseudocode_Programs_and_Their_Semantics-1] Рейзиг 2007 , с. 23, Псевдокодовые программы и их семантика.

[2] Часто повторяемое определение псевдокода, по крайней мере, с 2003 года, представляет собой «подробное, но читаемое описание того, что должна делать компьютерная программа или алгоритм, выраженное на формальном естественном языке».

[3] Улате-Кабальеро, Брайан Александер; Беррокаль-Рохас, Аллан; Идальго-Сеспедес, Джейссон (2021). «Параллельный и распределенный псевдокод: систематический обзор литературы». XLVII Латиноамериканская компьютерная конференция (CLEI) 2021 г .: 1–10. дои : 10.1109/CLEI53233.2021.9640222 .

[FOOTNOTEMitchellPennebakerFoggLeGall1996105-4] Митчелл и др. 1996 , с. 105.

[5] МакКоннелл, Стив (2004). Код завершен . Пирсон Образование. п. 54. ИСБН 978-0-7356-1967-8 . Избегайте синтаксических элементов целевого языка программирования.

[6] Приглашение к информатике, 8-е издание Шнайдера/ Герстинг , «Сохраняйте язык операторов независимым», как указано в этом вопросе по обмену стеками.

[7] Лэмпорт, Лесли (2 января 2009 г.). «Язык алгоритмов PlusCal» (PDF) . Исследования Майкрософт . Проверено 28 мая 2024 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]