イベント / EVENT

平成22年度 第2回 Q&A

第2回 2010年7月14日(水)

意外と身近な離散数学とは?
計算しない数学

河原林 健一(情報学プリンシプル研究系 教授/所長補佐)

講演当日に頂いたご質問への回答(全18件)

※回答が可能な質問のみ掲載しています。

今日、解説していただいたパ・リーグの対戦スケジュールは規定条件の中で削減される移動距離が最大となる最適解ですか?

最適解ではないと思います。おそらく最適解を見つけるのは大変だ(途方もなく時間がかかる)と思うので、なるべく近づくようにしようとしています。

サッカーに数学的な考えでできる部分はありますか?
例えば、ゴールからどれくらいの地点で、シュートをうつべきか、パスを選択すべきか、ドリブルを選択すべきかなど。PKのキッカーを誰にするといいとか。

サッカーのポジションを瞬時に把握するためには、空間的能力が必要でしょう。これは近いかも知れません。

19枚目のスライドの時間量は、220の計算量で1秒かかるときの相対的な量と思っていいですか。単純に量子コンピュータとPCでは違うと思うので。

古展での意味です。ただし量子コンピューターが実現したからといって、難しい問題(NP困難)が、高速で解けるとは専門家の中では信じられていません。

コンピュータは3つの数字の大小を1回で決めることはできない。
→人間の脳が4回で決めることができるのはなぜですか?演算の方法が人間の脳とコンピュータでは、どう違うのでしょうか?

私は脳の専門家でないからよくわかりませんが、人間が把握できる視覚情報は、明らかにコンピューターの入力よりも優秀です。また視覚情報から大きさも瞬時に把握できる能力があるのではないでしょうか?コンピューターは1か0のみしか扱えませんから。

画像データの圧縮に使われているのも、この離散数学でしょうか?(今日の話はソーティングに使われたが)

データの圧縮にも使われています。

計算量の下限が明らかになったアルゴリズムはどのようなものがあるのでしょうか?

計算量の下限を求めることはとても難しい。既存のアルゴリズムより速いものは存在しない!と言わないといけないので。一つの例をあげると、コンピューターは入力をすべて見る必要があります。ですから線形時間のアルゴリズムは、それより速くすることは困難です。

三次元の問題を二次元のみで考えるのに本当に適当か?(Dranker Wlakに二次元では元の場所に戻ってくるか、三次元では戻れない)

全てが適当だとは思いませんが、3次元にした瞬間に問題が飛躍的に難しくなることが多いです。その場合、2次元に落として考えるのが適当だとは思います。

n2の要素のソートの計算量はO(nlogn)だという話だったが、nコの要素の順列はn!、つまり、ある列はソートすると考えると、限界は[logn!]だと思うのだが、限界値に迫るアルゴリズムはあるのか?

ソートのポイントは、1回の作業によって、大きさの情報を得るということです。なので全ての順列を調べる必要はありません。たとえば、1回の比較によって、2つの数の大小がわかります。そうすると、順列の数は減りますよね?

計算機の高速化とアルゴリズムの高速化は、どちらの進歩が速いのでしょうか?
また、前者は連続的、後者は離散的なのでしょうか?

計算機の高速化は、ハード面の問題で、これは科学の進歩です。アルゴリズムの高速化は人間のアイディアによります。ですから単純に比較はできないと思います。

高速道路の無料化政策で、税金投入コストを最小限にしながら無料化の効果(輸送の効率アップなど)を最大化する方法を離散数学によって導き出せるか。

効率化に関しては、高速道路に限らず、あらゆる場面で離散数学が役立つと思います。

なぜ今まで離散が注目されず、連続が注目されていたのですか?

世の中の現象はほとんどが、「連続」です。しかし連続を扱うことは困難(たとえばコンピューターで扱わせることは困難)。ですから「連続」を「離散」に帰着する学問が発展したのだと思います。

離散数学自体どんなものか分かりませんでした。(コンピュータに計算させる時など)より効率的に解を出せるかという点で、離散数学というものは使われてることは何となく分かりました。
わかりやすく離散数学がどういうものか教えてください。

離散数学とは、離散的な対象、たとえば、数であったり、グラフであったりを解析する学問です。

STOCやFOCSの結果は(もちろん理論的な結果ですが)、応用(例えば特許など)されている、もしくは応用される予定はありますか?

論文での手法を実用問題に使うことはあるかもしれませんが、現在のところ特許などは考えていません。数学のアイディアは、地球全体でシェアーするべきだと思います。

離散数学を英語では何といいますか?

Discrete Mathematics

将来、離散数学の研究業績でフィールズ賞をもらえる可能性は?

ネバンリンナ賞は、離散数学の業績も含まれている人は何人かいます。

グーグルでどんなところで離散数学を応用していますか?

グーグルの検索エンジンは、WEB構造をグラフにして、グラフにおける問題を解いています。ですからまさしく離散数学です。

数学とは何なのでしょうか?

数字を使って物事を解析できるものは、数学と言ってしまってかまわないと思います。

離散数学は、暗号(の技術)にどのように利用できますか?

暗号には、離散数学よりも、整数論のほうが応用されていると思います。

数学において、数学を使うものと、図形(視覚的にとらえる事ができるもの)は全く違うものですか。それとも同じ種類のものですか。

図形も数式化できます。ですから、紙の上で議論可能です。ただし数学者は図形は図形として捉えて議論はしていると思います。しかし論文という形ではすべてが紙の上の議論になります。

講座のトピックから離れますが、「離散数学におけるグラフ彩色問題」とは何ですか?

グラフ彩色問題とは、たとえば、4色問題のように、隣り合った領域が異なるような色を持つように地図全体を着色する、といった問題です。

猫の名前を教えてください。

たま(三毛)、はな(クロトラ)、チー(チャトラ)です。

①「講師プロフィール」掲載の「現在関心を持っていること」の3。について。
猫の工事現場の足跡の向きは、離散数学あるいは情報学で、どのように解き明かされるのでしょうか?(そもそも、猫の足跡の前/後向きというのはどのように判別するのですか?)
②p。35について(一番右の猫の写真)
かねがね抱いていた疑問なのですが良い機会と思いお伺いします。鈴を付けられた猫は、動くといつも鈴の音がする情況を嫌がったりしないものでしょうか?私(人間)でさえ電車の中の携帯ストラップの鈴の音がうるさくてならないのに・・・。

猫の足にも指があるので、そちらの方が前です。猫は混乱すると後ろ向きには走れないようです。また、猫は何回も同じ音を聞いていると、すぐに慣れるようです。ですから鈴はあまり問題ないようです。

shimin 2010-qa_2 page2562

注目コンテンツ / SPECIAL