アルゴリズムとプログラムは違うものです

【 アルゴリズムとプログラムは違うものです 】 プログラムとアルゴリズムは似ています。 我々は、歴史的には、アルゴリズムの記述に、疑似的にプログラム言語を利用してきました。 だから、同じアルゴリズムの説明に、異なるプログラム言語が利用されていても -- 例えば、ある場合にはALGOLが、ある場合にはCが利用されていても --大きな違和感を感じることはなかったかもしれません。 なぜ、複数の異なるプログラム言語が、同一のアルゴリズムの記述に利用できるのでしょう？ それは、自然言語では普通のことです。同じ意味を、大抵の場合、日本語でも英語でもフランス語でも、異なる言語で表現できるからです。 プログラムとアルゴリズムは異なるものです。 プログラムは、具体的なコンピュータによって具体的に実行されるものですが、アルゴリズムは、その「具体的実行」の背後に存在する抽象的な「意味」に関わるものです。 そうしたプログラムの「意味」の記述としてのアルゴリズムの記述は、プログラム言語とは異なる形式が必要です。 ある意味当然のことですが、プログラムとアルゴリズムの違いの認識が生まれたことは重要なことです。さらには、一歩進んで、アルゴリズムを記述する言語の必要性の認識が生まれたことは、とても重要なことです。 ただし、残念なことは、こうした認識は、必ずしも多くの人に共有されていないと思います。 視点を変えましょう。 アルゴリズムとプログラムとの関係は、実践的には、「仕様」とその実装としての「プログラム」の関係としても考えることができます。 アルゴリズムの記述が「仕様」として与えられ、その実装が「プログラム」として与えられるということです。 ランポートによってアルゴリズム記述言語で与えられた、先に見た Algorithm PC は「仕様」です。bounded FIFO queueのプログラムは、この仕様としてのアルゴリズムを実装しなければなりません。 仕様は定義です。ある定義が正しいかと問うことは、形式的には意味がありません。 しかしながら、このアルゴリズムのいくつかの性質を証明することによって、我々はこのアルゴリズムがまさにbounded FIFO queueの仕様であることに確信を持つことができるのです。 我々があるアルゴリズムについて証明する最も重要な性質は、「不変性」という性質です。それについては、次回、具体例をあげて説明しようと思います。 ------------------------------------------- セッションの動画のURL https://youtu.be/a9ShkfCrpYo?list=PLQIrJ0f9gMcOeqlB09PdBddfXLv2QjG-F スライドのpdf https://drive.google.com/file/d/14_uRrUQwBIwKX23tow0bOD3hVdzyP-Nw/view?usp=sharing 関連blog 「アルゴリズムとプログラムは違うものです」https://maruyama097.blogspot.com/2022/07/blog-post_294.html 参考資料 Lamport, L. The Computer Science of Concurrency: The Early Years https://cacm.acm.org/magazines/2015/6/187316-turing-lecture-the-computer-science-of-concurrency/fulltext#R9 Lamport, L. The PlusCal algorithm language.. https://lamport.azurewebsites.net/pubs/pluscal.pdf Leslie Lamport. The pluscal algorithm language. https://research.microsoft.com/users/lamport/tla/pluscal.html セミナーのまとめページ https://www.marulabo.net/docs/concurrent/ セミナー告知・申込ページ https://concurrent.peatix.com/view -------------------------------------------