Псевдокод

В информатике ) с неформальными псевдокод — это описание шагов алгоритма с использованием сочетания соглашений языков программирования (таких как оператор присваивания , условный оператор , цикл , обычно не требующими пояснений, обозначениями действий и условий. ^[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 )

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

процедура   физзбазз  ; 
    для   i   :=   от 1   до   100   do 
     print_number   :=   true  ; 
      если   я   делится   ,   на   3   то   начните 
       печатать   «  Fizz  »  ; 
        номер_печати   : =   ложь  ; 
      конец  ; 
      если   я   делится   ,   на   5   то   начните 
       печатать   «  Buzz  »  ; 
        номер_печати   : =   ложь  ; 
      конец  ; 
      если   print_number  ,   напечатайте   i  ; 
      напечатать   строку   новую  ; 
    конец

Стиль С:

fizzbuzz  ()   { 
   for   (  я   =   1  ;   я   <=   100  ;   я  ++  )   { 
     print_number   =   true  ; 
      if   (  i   делится   на   3   )  "   { 
       print   "Fizz  ; 
        print_number   =   ложь  ; 
      } 
     if   (  i   делится   на   5   )  "   { 
       print   "Buzz  ; 
        print_number   =   ложь  ; 
      } 
     Если   (  print_number  )   напечатайте   я  ; 
      напечатать   строку   новую  ; 
    } 
 }

Стиль Python:

def   fizzbuzz  (): 
   для   i   в   диапазоне  (  1  ,  101  ):  
     =   true,   если 
     3   :   напечатать   "   я делится на   Fizz  "  
       print_number   = 
       false   ,   если 
     я   делится   на   5   print_number   :  напечатать 
       "   Buzz" 
       print_number   =   false 
     , если   print_number  :   напечатать   я 
     печатаю   строку   новую

Псевдокод математического стиля [ править ]

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

Возвращаться  $\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`

Пример [ править ]

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

 вход алгоритма  Форда-Фалкерсона на 
     :  график  G  с пропускной способностью  c  ,  
             исходный узел  s  ,  
             узла стока  t 
     Выход  : поток  f  такой, что  f  максимален от  s  до  t 

     (обратите внимание, что f _(u,v) — это поток от узла u к узлу v, а c _(u,v) — пропускная способность от узла u к узлу v. узел v) 

     для каждого  ребра (  u  ,  v  )  в   G _E  do 
         f _{(  u  ,  v  )} ← 0 
          ж _{(  v  ,  ты  )} ← 0 

      в то время как  существует путь  p  от  s  до  t   в  остаточной сети  G _f  do 
          пусть  c _f будет пропускной способностью остаточной сети  G _f
         c _f (  p  ) ← min {  c _f (  u  ,  v  ) |   (  ты  ,  v  )  в   п  } 
          для каждого  ребра (  ты  ,  v  )  в   p   do 
             f _{(  ты  ,  v  )} ←  f _{(  ты  ,  v  )} +  c _f (  п  ) 
              ж _{(  v  ,  ты  )} ← -  ж _{(  ты  ,  v  )}

     вернуть   ж

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

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

Различные попытки привнести элементы грамматики естественного языка в компьютерное программирование привели к появлению таких языков программирования, как 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]