本文へジャンプ

学科概要
  • HOME
  • 学科概要
  • 学生による学科紹介

学生による学科紹介

実際の授業をいくつか文書におこしてみました。先生方の仮想講義を体験してみてください。情報科学科の講義は90分授業です。午前中の講義は10時15分から、午後の講義は13時から始まります。14時45分からの講義がある曜日もあります。

離散数学 | 今井浩
開講時間:火曜2限 | 1
シラバス
離散数学(グラフ理論、線形計画法、マトロイド理論)、ならびに、離散数学的手法によるアルゴリズムの設計と解析、離散最適化法(最小木問題、最大流問題、割当問題)。
概要
 離散数学は三年生の夏学期、つまりこの学科の最初の学期に行われる必修の授業です。
これは文字どおり離散的な、連続でない対象を扱う数学です。例えば離散的な問題の例として、順列や組み合わせをしらみつぶしに調べる問題などは、コンピュータを用いて解くとよいのですが、その効率的な解法の設計や研究は重要です。というのは、ある問題を解く(コンピュータに解かせる)のに要する時間は解法の設計に大きく依存するからです。設計が悪いために解けるはずの問題が現実的な時間内に解けなくなることさえあります。
 この講義では離散数学とその手法を用いたアルゴリズムの設計や解析の初歩を学びます。
離散数学の例え話
**離散数学的問題の例 「巡回セールスマン問題」

  ―商品を売ろう。ある営業マンの今日の予定。

 -鈴木さん、田中さん、高橋さん、澤さんの4件のお宅にお邪魔し、商品のプレゼンテーションをしたいと思います。
 -会社から出発して4件のお宅を全て訪問し、出来るだけ早く会社に帰って来たいと思います(*1)
 -早く移動できるルートもあれば、ひどく時間がかかってしまうルートもあります。

どういう風に巡回すれば最も効率的か。各ルート毎に所要時間が分かっていて、図にすると以下のようになっているとします。

(* 画像 pict.GIF*)



 元来、このような問題は数学としては低級な問題とみなされてきました。全ての場合を網羅すれは必ず解けることがただちにわかるからです。ところが、

  訪問するのが、たった4件のお宅でも、

  (会社) → 1 → 2 → 3 → 4 → (会社) 

可能なルートは
 4! = 24
通りあります。訪問する場所が増えれば当然、可能なルートは階乗で増えていきます。コンピュータがいくら人間より高速に計算できるからといえ、たとえば話を世界規模に持っていって「100都市を巡回する」ように考えると、1秒間に10億個の順列を作り出せるコンピュータを用いても100億世紀以上かかってしまうことが単純計算でわかります。つまり、「全ての場合を網羅すれば解けるはずであるが、それが現実的に不可能」であるということです。

 このような状況、問題に対処する方法を数学的に考える。これも離散数学の分野です。
実はこの「巡回セールスマン問題」は難しく、問題の規模がある程度大きいときに現実的な時間内で厳密に解けるような方法(アルゴリズム)は発見されていません。ここでは解法のいくつかを紹介したいと思います。

 <近似的な解法の例> 欲張り法(Greedy Algorithm)

方針:現在地から次の目的地へ最もコストの掛からないルートを毎回選択。

コストの最小値だけを調べればよいので、総当りよりは圧倒的に早い。単純な方法。

 会社 → 澤さん → 高橋さん → 鈴木さん → 田中さん → 会社 (4.7時間)

 この問題では実は最適解です。

が、この方針は精度に関してはいくらでも悪くなります。(田中→会社間が10000時間かかるようになっていても、このアルゴリズムではここを選ばざるを得ません)
まとめ
巡回セールスマン問題を例にお話させて頂きましたが、この問題は離散数学の体系のなかでは「グラフ理論」という分類になります。この「グラフ理論」は現実への応用分野も実に広く、たとえばデッドロックの検出、コンピュータネットワーク(インターネット)の構造モデル化、はたまた集積回路の設計にまで役に立っています。
 また、これに限らず離散的な値を考えなければならない問題というのはあちこちにあり、線形計画問題、マトロイド、組み合わせ論などがあります。
線形計画問題
せっかくなので、もうひとつ、離散数学の問題を見てみましょう。

* 線形計画問題とは


最適化問題のひとつで、目的関数と制約条件がすべて線形関数で表せる問題を線形計画問題といいます。

問1 製品A,Bを生産するためには原料a,b,cが必要です。売却利益はAが3、Bが2です。各製品の生産に必要な原料の量と在庫は図のとおりとします。このとき、売却利益を最大にするためにはA,Bをどのように生産すればよいでしょうか?

A B 在庫

a 3 1 10.5
b 2 2 9
c 1 2 8


解説 この問題を定式化すると、以下のようになります。Aの生産単位をx、Bの生産単位をyとします。

目的関数
z = 3x + 2y
を、制約条件
3x + y <= 10.5
2x + 2y <= 9

x + 2y <= 8

の下で最大にするx,yとそのときのzの値を求めなさい。

今回のように変数が2つだけであれば、図を描いて交点を求めれば解を得ることが出来ます。

#図を挿入

しかし、製品の数が3つ以上になると図を描くのはほぼ不可能になります。授業ではそのような線形計画問題を解くための方法(線形計画法)を学びます。具体的なアルゴリズムは書きませんが、それを用いることで多変数の場合でも効率よく解を求めることが出来ます。


問2 製品A,B,C,Dを生産するためには原料a,b,c,d,eが必要です。売却利益はAが3、Bが2、Cが1、Dが2です。各製品の生産に必要な原料の量と在庫は図のとおりとします。このとき、売却利益を最大にするためにはA,B,C,Dをどのように生産すればよいでしょうか?

A B C D 在庫

a 3 1 1 2 10.5
b 2 2 0 2 9
c 1 2 1 0 8
d 3 1 2 1 10
e 1 1 2 1 7.5

解説 これでは図を書くことが出来ませんね。どう解くのかは授業でのお楽しみに!
離散数学の学習効果
授業では、コンピュータを使って解く数学的問題とそれに対する今日までに考えられてきた解法が多数紹介され、まず離散的な問題の類型と有名な手法を学ぶことが出来ます。学んだ解法はいざ自分がアルゴリズムを設計する時に利用できることがあり、またアルゴリズムの効率を評価するための基礎知識が身につきます。
授業の進行について(今井先生の場合)
先生の説明を聞きながら板書を書き取っていく形です。先生曰く、板書はスライドよりほどよく遅いので、その場で考えて理解していくとよいとのことです。内容は今井先生が本質的なところから犀利な論理を用いて語って下さいます。受講生の自習のためとして「証明は略証明を与える。各自完成させよ。」のような指示がよく出ます。ですから少し厳しめな印象をもつこともあると思いますが、努力してついていけば必ず力はつきます。
試験について
大問4〜6題程度で大体が授業で扱う問題だと思います。後半の授業で、試験問題の出題範囲を先生が詳しく教えてくださいます。例年ほぼ試験のみで成績が決まるようです。
次のステップへ
次の学期(つまり3年冬学期)の全く同じ時間帯に今井先生による「計算量理論」の講義があります。困難さの尺度を導入することで離散数学的問題を分類し、計算の時間空間効率の解析に特化した議論をします。
注釈
1 巡回セールスマン問題(Traveling Salesman Problem, TSP)
  本来は一度訪れた場所に二度訪問してはいけないというルールがある。