=== 4月9日 10:15 --- 理学部1号館 450教室にて ===

はじめに ---コースプラン

3年生の皆さん,本郷にはようこそということで、是非頑張っていろいろと聞いていただければ、と思います。この講義は「離散数学」で,グラフ・ネットワーク・組合せ最適化などの情報科学の基礎についての講義します.

コースプランですけれども、まあ離散数学全般をやっていくわけです。基本的には、グラフ、組合せの最適化、離散構造、の話をしましょう。基本的に何をやるかっていうと、とにかくざーっと項目を並べて書くと、次のようになります.

[plan-s]

まず、グラフです。
今日何をやりたいかっていうと、(これは2年生の講義で1講義話してるんですけど)基本的な定義から始まって、2部グラフとかオイラーグラフというのをやりたい。平面グラフの話も、途中、例で述べながら行きましょう.

次に、ちょっとアドバンストなトピックになってくるわけですが、グラフとネットワーク。最大流問題。今度はフローを考えるわけですね。キーワードは「最大流最小カット定理」。次に2部グラフのマッチング、あと、メンガーの定理をやります。

その次はですね、ちょっと話が変わって、線形計画法という、これは最適化の最たるものですが、何をやるかっていうと、単体法あるいはシンプレックス法というものをやります。双対定理というものもやります。

そしてネットワークの話に戻って、ネットワークフローの一般形である 最小費用流問題というのをやります。

あと、パーフェクトグラフの話をやります。まあ、今聞いてもチンプンカンプンでしょうけど。グラフを色で塗分けたり,最大派閥を求めたりとか独立点集合(stable set)とか、そういうキーワードがあります。

あといろんな離散構造に関する問題で、例えば最短路問題(最大流の問題よりは基本的)、あるいは最小木問題、このあたりで(強)連結成分、まあdepth first searchなんていうアルゴリズムをやるわけです。
次に、これは最小木と関係するんですけれども、マトロイドをやります。最小木、行列、グラフ、ここで行列が出てくるなんて変に思うかも知れませんが、線形代数の一番最初に一次独立や一次従属なんていう概念を勉強したと思うんですけど、それとグラフは密接な関係があるんです。
で、あと半順序とか束とかそういう離散構造を勉強します。

キーワードは、これで大体終っている。これを、7月下旬まででカバーしてやろう、というわけですね。

教科書の指定は無し。参考書は、配布資料1を参照して下さい.教科書を指定しないのには理由があって、1冊だけで「これをきっちり最初から最後までします」というよりは、2、3の本が必要なので。で、ちなみに、生協に行ってもらえばいろんな本がありますから、是非色々と見てもらえるといいと思いますし、また図書室をうまく利用して下さい。

で、単位は、これは単に試験。対応する演習は、情報科学演習Iです。これは金曜日の午後ですよね。これは、赤間君がやってくれます、赤間君は去年の4月1日にドクターをとって赴任してきて、頑張ってくれてます。

ここまでで何か質問がございますでしょうか?


離散数学の講義の位置付け

さて、前期にこの離散数学というのがあって、後期にですね、計算量というものがあります。
両方とも僕が担当させてもらうんですが、割と密接に関係している所なんで、こっちの方は何をやりたいかっていうと、前期ではですね、良い離散構造っていうのを勉強することをやります。まずこれの基本を押えようということです。
それに対して後期の計算量っていうのは手に負えない離散構造の話をします。離散っていうのをわざわざつける必要ないんですが。
ただしこれで終っては駄目なわけで、これを何とかする、あるいは、難しさの理論。
本質的に難しいものっていうのはやっぱり難しいわけですね、実際。
だから難しいことが証明できるってことは非常に面白いわけです。

で、基本的にはこう いう枠組になっている。もう一度言うと、離散構造というこの講義では、今、非常にたくさんのキーワードを書きましたよね、これっていうのは、はっきりいうと、こういうのを分かってしまうと非常にいい離散構造っていうのが背景にあって、問題が非常に大きくても解けるし、また、基本的な問題だからいろんな場面に応用できるわけです。
例えば、最短路なんていったら、道路網での最短路だけしかイメージ湧かないかもしれないけど、実は他の問題を解くときに、必ず最短路の問題っていうのが繰り返し繰り返し出てくるわけです。例えば、仕事を割り当てるような問題も最短路を繰り返し解くなんてことによってそういう問題が解けるわけです。
そういう代表的な基本構造を前期でおさえましょうというわけです。

それに対して、後期はですね、やっぱりそうはいってもコンピュータで解ける問題には限界があるわけです。限界を何とかしていこうとするのが情報科学全体の取り組んでいることそのものだともいえるわけです。
例えばどうして並列計算機が必要かっていうと、今解ける問題のサイズが小さいから、もっと大きな問題を解きたい、もっと速く解きたい。っていうことで、実際、並列計算機というものを作るわけですね。
あるいはもちろん最終的には、そういうコンピュータというものを通して例えば人間的なものを理解しようとか、そこまで発展していくわけです。
一方後期では何をやるかっていうと、本当に難しいものは難しいわけで、そういう理論をきっちりやりましょうということです。

こうするとなんか前期と後期、全然違うことを話しているように思うかもしれませんが、是非1年終った時に理解してもらえばいいと思うことは、離散構造が分かると、実は計算量の時に、結局手に負えない問題っていうのは、まず難しさの理論を示して、この問題を解くのは実際難しいんだってことを理論的に示すわけですが、でも解かなきゃいけないものは解かなきゃいけないわけで、何とかする時に結局何やるかっていうと、離散数学のこの講義でやるいろんな手法をうまく何とか使っていくっていうのがこういう手におえない問題を何とかするための常套手段なわけですね。
要するに、何も道具を持たないで難しい問題にチャレンジしても跳ね返されるだけで、ある程度この前期で道具をきっちり押えて、その道具自身直接いろいろな問題に使えるし、またさらにより難しい問題に発展する時に結構これが有用な道具なので、それでチャレンジをしていこうということをやるわけです。
これ、例えば、基礎論のIIでこういう絵を書いたかどうか忘れましたが、

[難しさ]

これが計算の難しさという軸で、上の方が難しい、下の方が簡単という時に、この辺りに(と、図の下の方を指す)ソーティングがあって、中央値、というのは、n個の数が与えられた時に最大値を求めるのは簡単ですよね、linear time で解けますが、n個の数が与えられた時にn/2番目の大きさのものを求める問題とかも linear time で解けるわけです。
この辺りに(と、図の一番下を指す) linear time で解ける問題っていうのがあるわけです。例えば十万個なんていう問題を与えられても解けるわけですね。例えばみんな、延々とアルゴリズムとデータ構造のI(現在の「アルゴリズムとデータ構造」)でやったと思うんですけど、ソーティングなんてのがあるわけですね。
ヒープソートとかマージソートとかクイックソートとかバブルソートとかシェルソートとかナンタラカンタラといろいろありましたよね。

この辺りになると(と、図の一番上を指す)、例えばですね、チューリングマシンの停止問題なんていうのがあるわけですね。これ、基礎論のII(現在の「形式言語理論」)でやりましたよね。
ここは、undecidableなんですね。日本語でいえば、決定不能。決定不能な世界があるわけです。ようするにこれはアルゴリズムが存在しない世界っていうのが実際あるわけですね。
計算の難しさっていった時に解けない問題っていうのがあるんですけれども、それはああいう対角線論法を使って証明するわけですね。
一方こうやって中央値とかあるいはソーティングとかあるいはn×nの行列に関する線形方程式を解く問題なんていうのは、ガウスの消去法とかを使えばnの3乗で求まるという感じになってるわけですね。こういう解きやすい問題があるわけです。ここは一つの非常に大きなスレッシュホールドなんですけれども、

ここはもちろんひとつの大きな線があるわけです。
こっから上は解けないといっても何とかしようというのももちろんやらなければいけないんですけれども、まあ、まずは、アルゴリズムは存在するんだけども、時間的に例えば爆発的に時間がかかってしまって、みんなが生きている間には解けない問題、みんなどころか地球が存在しなくなるまで時間をかけないと解けない問題っていうのもいくらでもあるわけです。

で、そういうのに対して、アルゴリズムが存在する世界の中をクラス分けする時に、intractableな問題とtractableな問題というのを考えましょう。tractableっていうのは手に負える問題で、intractableっていうのは手に負えない問題なわけですね。
例えばこのあたりにですね(と、図の中ほど少し上を指す)、PresburgerのArithmeticっていうのがあります。
あんまり論理といっても聞く機会はないと思いますが、整数でuniversal quantifier(∀)とかexistential quantifier(∃)とかいうquantifierをつけて、整数で足し算をして、それに関する論理式がsatisfiableであるかどうかなんていうのを判定する問題なんです。
これは、decidableな問題なんだけど、time complexityとかビッグオーノーテーションとかいう概念は分かっていると思うんだけど、nのサイズの問題が与えられたら2^2^n以上は必ずワーストケースで時間がかかってしまうようなdoubly-exponential boundがあるような非常に難しい問題なんですね。

まあ、そういう問題もあるし、例えばこの辺りにグラフの問題でいうと、ハミルトン閉路の問題、あるいはトラベリングセールスマンの問題(TSP)なんてものはこの辺りにあるんです(と、図の中ほどを指す)。
で、オイラーとかいう名前は出てきたんだけどハミルトン閉路とかいうのは少なくともこの講義ではキーワードとしては出てきてないですよね。それはどうしてかっていうと、ここで線を引いてるんですけど、これは難しい方の問題になってるんですね。
今日やる話からすると、この辺りにですね(と、図の一番下を指す)、オイラー閉路の問題があるわけです。まだ、こういう有名人、昔の数学者のような名前だけ書いておいて、何もこれだけでは分からないんだけど、オイラー閉路の問題っていうのは、まあ基本的に線形時間で解けるわけです。
実は、オイラー閉路の問題っていうのは別に何か難しい問題ではないわけで、噛み砕いた言葉でいえば、一筆書きの問題なんです。
一筆書きができるかどうかって問題なんですが、そういう問題も、実は、計算の難しさっていう概念からは一番下の線形時間で解けるクラスになっているわけです。

ここに(と、図の中ほどを指す)どうやら境界がありそうだということなんですが、実はこの境界は、理論的に最終的に、示されているわけではないんですが、まあいろんな傍証の積み上げでここにだいたい境界っていうのがあって、アルゴリズムはあるんだけども、多分入力に対して指数時間かかって、解く問題が大きくなるともう爆発的に時間がかかるようになるわけです。
そういう問題だろうと思われているのが、ハミルトン閉路の問題やトラベリングセールスマンの問題なんですけれども、この辺りに例えば最短路とか最大流とかあるいは線形計画とか今日ここで挙げたキーワードの問題は、すべてこのスレッシュホールドから下のやつです。

で、グラフっていうのはいろんな離散的な事象をモデル化する代表選手なわけですね。
もちろん、みんなは、オートマトンのように状態が遷移していくモデルも知っているわけです。だから、グラフとかオートマトンっていうのはコンピュータで問題を解きたいと思った時に、対象の構造を表す非常にいい道具なわけです。
で、この講義でやるのは、このあたりの離散構造で、もちろんまだみんながあまり知らないことで、これから知っておかないとはっきりいって何もできないっていうぐらいの基本的なことをこの離散数学の講義でやりましょうというわけですね。
この辺りのことに関してはこれを後期の計算量でやりましょうと、あ、ごめん、Presburger Arithmeticなんてそんな上まで行けないんですが。

基本的には、こういうことをやっていきたいっていうことです。だから、実際この講義、前期の講義で、そこで単位が出るんですが、最終的には、後期の計算量の話とか、さらに、例えばさっき、情報基礎論II(現在の「形式言語理論」)の話なんかでチューリングマシーンの停止問題を勉強したでしょうとか言いましたけれども、他のすべての問題と絡んでやってくるわけですね。
3年の間、みんな全部必修でなかなか大変でしょうけれどもやっぱり言葉の定義を知らないとまず話が分からないわけですから、単に定義だけでなくその中身まで知った上で使えるような話にやっていきましょうということです。

とにかく離散構造ではここの対応する離散構造が非常にいい構造を持っていて、それがゆえに手に負える問題、きれいな世界なんですけど、それをやっていきます。

ちなみに、まだこの辺りチンプンカンプンな所ももちろんあるんですが、その辺りはおいおい。


Next

 

〔トップページへ〕 〔離散数学の仮想講義のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 6 May, 1999