シラバス:専門科目
(コンピュータサイエンス分野)


知的空間設計論 (偶数年度開講)
Intelligent Spatial Design

担当   西原 清一
email: nishihar@is.tsukuba.ac.jp
学期・時限 1学期・木曜日・1・2時限
対象学生・単位 1・2年次・2単位
授業形態 講義および輪講
授業内容
1. 計算の理論(計算可能性および計算複雑さ)の復習
コンピュータで処理することのできる問題、すなわちプログラムで処理できる問題が形成する関数族すなわち問題空間について復習する。
2. 組合せ探索/組合せ最適化とNP完全性
コンピュータで手間のかかる処理すなわち組合せ探索および組合せ最適化について学び、NP完全の概念を歴史的な意義についても触れつつ復習する。
3. 状態空間の探索アルゴリズム
組合せ的処理を含む問題に付随している状態空間(解空間)を探索する方法を具体化したものとしての探索アルゴリズムについて、基本的な概念および事項を学ぶ。
4. 制約充足パラダイムと相転移
代表的な組合せ問題の一つである制約充足問題を紹介し、近年盛んに研究されている相転移現象を、NP完全性と関連づけながら考察する。 
5. Lシステムと仮想空間
問題空間や状態空間以外にも、現実には、いろいろな空間が存在する。視覚的な空間を生成するLシステムをはじめ、種々の空間やその設計法について考察したい。
           以上の各テーマについて、理解度や興味を見ながら、講義と輪講を行う。

授業概要(補足)
上の各テーマは、'空間'という一つのキーワードの下にまとめることができる。すなわち、コンピュータで処理することのできる問題、換言すれば、プログラムで処理できる問題は、一つの関数の階層をなす族すなわち空間を形成している。また、コンピュータで計算できる関数にも比較的簡単に計算できるものと非常に手間のかかるものとがある。このうち後者に属する問題は、何らかの形で組合せ的な処理を含んでおり、再び一つの空間を形成している。組合せ処理を含む問題の一部はとくに'NP完全'と呼ばれ、(我慢できる程度の時間内には結果が得られないという意味で)事実上、実用的な汎用プログラムを組むことは原理的に不可能であると予想されている。しかし現実には、NP完全な問題は多い。また、実用的なプログラムが存在しないことが証明されたわけでもなく、また、プログラムの開発をあきらめるわけにもいかない。組合せ処理を含むアルゴリズムは、いわば、巨大な空間を探索する具体的な方法を示したものといえるので、探索アルゴリズムあるいは推論アルゴリズムと呼ばれるのがふさわしい。近年,組合せ処理の問題であっても、実際に組合せオーダの時間がかかるような問題は、問題空間の一部に局所的に存在するのみで、大部分は実用的な時間でとける問題であることが知られるようになってきた。そのような性質を、相転移と呼ぶ。平成12年度では、代表的な組合せを含む問題の一つである制約充足問題を取り上げて、その相転移現象について学ぶことにする。
        


Topページへ