INFORMATION

PROCESSING

LABORATORY

Department of Mathematical Informatics, Graduate School of Information Science and Technology /
Department of Mathematical Engineering and Information Physics, Faculty of Engineering,
University of Tokyo
TOP MEMBERS RESEARCH PAPERS SEMINARS ACCESS Japanese
TOP(J) MEMBERS(J) RESEARCH(J) PAPERS(J) SEMINARS(J) ACCESS(J) English

学生へのメッセージ

計算機プログラムの数理

計算機を用いて問題を解決するには、アルゴリズムをプログラムとして表現し、そのプログラムにしたがって計算機を動作させればよい。計算機のハードウェアの進歩とともに、対象とする問題もより高度なものとなり、それに応じてプログラムもますます複雑さを増している。問題解決の過程には、アルゴリズムをプログラムとして表現するプログラミングの段階と、そのプログラムを計算機で実現する段階とがある。これらのいずれの段階においても、プログラムに内在するさまざまな性質を扱う工学が求められる。これに対して、計算機プログラムを厳密な科学・工学の対象として数理的にとらえて、プログラミングの方法論にあらたな視点を与えるとともに、効率のよいプログラムの実現法を得ることが計算機プログラムの数理工学の目的である。

計算モデル

計算機プログラムは、アルゴリズムを計算機構としての計算機上で実現するように(計算機構を反映した言語によって)記述したもののことである。計算機構は計算そのものを実現するためのモデルであり、代表的なものとして、現在の計算機の仕組み(演算・記憶・入出力)に対応する手続き型や、数学的な集合間の写像(関数)を基礎とする関数型などがある。たとえば、Pascalでプログラムを書くというのは、問題を解くためのひとつのアルゴリズムを手続き型の計算機構によって実現しようとすることに相当する。

プログラムの計算術

ひとつの問題を解くのにいくつものアルゴリズムが存在する。したがって、計算機構を定めたとしても、同じ問題を解くいくつものプログラムが存在することになる。これらのプログラムのあいだの関係やそれらを変換する規則が明らかになれば、プログラムを合成する手法や効率のよいプログラムを求める手法を確立することができるようになる。プログラムから成る領域は単純な代数構造に比べてきわめて複雑な構造であるが、代数学・圏論(カテゴリー論)のような数学を用いてあらたな理論を構築することによりこれをあきらかにすることができる。これまでに、いわば多項式の因数分解のように単純な操作によってプログラムを対象とする計算術が適用できることがわかってきた。プログラムを対象とする理論はプログラムの構成手段として用いることができるばかりでなく、プログラムの性質を把握するにも有効であり、実際のプログラミングの基盤としてもきわめて重要なものである。

並列計算機構

プログラムを計算機上に実現するにあたっては、並列計算機におけるプログラミングが重要になってきている。それには、計算を逐次的に進めるだけではなく、いくつかの計算を並行して進めてゆくという並列計算機構が必要である。一般に、計算機構はプログラムを書くための言語に反映され、人が設計したアルゴリズムを表現する手段として用いられる。また、計算機構をプログラム言語の処理系(コンパイラなど)として計算機上に構築することによって、アルゴリズムを計算機上に実現できることになる。プログラム言語の定義においては形式言語論・論理学などの理論が用いられ、処理系の実現にはこれらをもとにした系統的な構成法が使われる。逐次的な計算機構に対する言語処理系の設計技術はかなりよく整理されてきているが、並列計算機構については未解決の問題が多い。並列計算機上でプログラムを効率よく実行するための計算機構とそれに基づくプログラム言語の処理系を構築することは重要な課題のひとつである。

このように、計算機プログラムを対象とした研究には、あらたな視点からとりくむことのできる多くの興味深いテーマがあるといえる。


Last Modified: Wednesday, 19-Jan-2005 13:21:59 JST

Valid HTML 4.01!   Valid CSS!