南山の先生

学部別インデックス

理工学部・電子情報工学科

横山 哲郎

職名 教授
専攻分野 コンピュータサイエンス(計算機科学)
主要著書・論文 "Fundamentals of Reversible Flowchart Languages," Theoretical Computer Science, 2016. 共著 <doi:10.1016/j.tcs.2015.07.046>
将来的研究分野 プログラミング,プログラミング言語
担当の授業科目 理工学概論[SE], 情報科学概論, ソフトウェア工学演習I-VIII, 卒業研究IE-IVE, 知識・言語と情報社会(情報社会の構造)<国際科目群>, プログラミング基礎[S], プログラミング基礎実習, 組込みシステム工学研究, ソフトウェア工学実習[S]

効率の良い整理整頓を考える
~コンピュータ科学の考え方~

高校生の皆さんが大学の勉強内容を予め正しく知るのは難しいと伺いますので、ここでは日常生活の中の問題をコンピュータ科学の観点から考えてみたいと思います。

Aさんが靴下10ペア(20足)を持っていたとします。
そして、左右ばらばらのままカゴにしまっていたとします。
靴下をカゴにしまうのは簡単です。ただ選んだ靴下をカゴに入れるだけです。
しかし、靴下のペアを探し出すのにどれほど手間がかかるでしょうか。
適当に手に取った靴下と対になるものを19足の中から探し出さなければなりません。
一度に2足の靴下しか比べることしかできなく、また一度見た靴下は別のカゴに移せるとすると、平均すると9~10足を見る必要があります。

Bさんも靴下10ペア(20足)を持っていたとします。
そして、左右のペアをつくってカゴにしまっていたとします。
靴下のペアを探し出すのにどれほど手間がかかるでしょうか。
適当に手に取っても靴下はペアになっているのですから、1回取り出すだけで充分です。

さて、靴下のペアを探すというのは、情報検索の問題と考えることもできます。
上の例では、Bさんの方がAさんよりも効率的に靴下のペアを見つけられるようです。
一般に、欲しい情報をどのように保存して、どのように探せば、効率良く見つけやすいのでしょうか。
情報検索は、コンピュータ科学における基本的な問題のひとつです。

おまけの問題です。
(1) AさんがBさんのように、すべての靴下のペアを作るのには、通算すると平均何足の靴下を見る必要があるでしょうか。
(2) 5ペアの靴下のみが洗われて一カ所においてあるとすると、通算で平均何足の靴下を見ればすべての靴下のペアを作ることができるでしょうか。
(3) Aさんは片方の靴下のみ、Bさんはペアを一度に取り出して見ることができると仮定されています。この仮定は妥当でしょうか?