有界線形作用素の二乗のノルム
用語 1
自然言語を使ってプラットフォームに依存せずに詳細なコードについて説明したものを疑似コードpseudo codeという。
説明
疑似コードは文字通りコードのように見えるが、実際にはコードではない表現であり、特定のプログラミング言語に縛られずにアルゴリズムを説明するために使われる。疑似コードは自然言語はもちろん数式を使ってもよく、その定義が明確で伝達力に問題がなければ特定言語の文法を借用しても構わない。
そのアルゴリズムをどう実装するかはプログラマーのスタイルや様々な制約条件によって千差万別であるかもしれないが、疑似コードは最も基本的に動くアルゴリズムの原型として存在しなければならない。
アイロニカルなのは疑似コードが「アルゴリズムの原型」という説明に反して疑似コードの書き方自体にも様々なスタイルが存在するということだ。例として選択ソートを説明する二つのスタイルの疑似コードを見てみよう。どのスタイルで実装するにしても構わないが、基本的には最小値を反復的に求めることでソートを行うのだ。
| アルゴリズム: 選択ソート 1 | ||
|---|---|---|
| In | 長さ$n$の配列$A = \left[ a_{1} , \cdots , a_{n} \right]$ | |
| 1. | for $i = 1, \cdots, n$ do | |
| 2. | $j \gets \argmin \left[ a_{i+1} , \cdots , a_{n} \right]$ | |
| 3. | $a_{i} , a_{j} \gets a_{j} , a_{i}$ | # 位置交換 |
| 4. | end for | |
| Out | 昇順にソートされた配列$A$ |
フォートランやC、MATLABのような手続き指向が強いスタイルだ。ループや条件文などのブロックをendといった明示的なキーワードで閉じる場合が多く、配列単位から正確にアプローチして読みやすい。
| アルゴリズム: 選択ソート 2 | ||
|---|---|---|
| In | 長さ$n$の配列$A = \left[ a_{1} , \cdots , a_{n} \right]$ | |
| 1. | $B \gets \emptyset$ | # 空リストの初期化 |
| 2. | while $A \ne \emptyset$ | |
| 3. | $a \gets \operatorname{pop} \left( A, \min A \right)$ | |
| 4. | $\operatorname{push} \left( B , a \right)$ | |
| Out | 昇順にソートされた配列$B$ |
Pythonのようにオブジェクト指向が強いスタイルだ。文法もPythonを模してインデントindentでブロックを区別することが多く、その論文や教科書を読んでいるのであれば常識的に知っているはずのデータ構造が突然登場することがある。どうにもインデックスを一つ一つ確認しながら読むより概念的に理解しやすいという利点がある。
A. Alhefdhi, H. K. Dam, H. Hata and A. Ghose, “Generating Pseudo-Code from Source Code Using Deep Learning,” 2018 25th Australasian Software Engineering Conference (ASWEC), Adelaide, SA, Australia, 2018, pp. 21-25, https://doi.org/10.1109/ASWEC.2018.00011 ↩︎