二つの異なる図形が与えられたときに、その二つが同じものであるか、違うものであるかを判定することは、幾何学において最も基本的なテーマです。今回の講演では、セル複体と呼ばれる構造を持つ図形に対して、ホモロジーというものを定義します。同じ図形は同じホモロジーを持つので、もし二つの図形が異なるホモロジーを持てば、それらは異なる図形であることが証明できたことになります。
ホモロジーは加群と呼ばれる代数的な構造です。講演の前半では、加群について勉強します。講演の後半では、セル複体を定義し、セル複体からホモロジーを求める方法を解説します。
０．イントロダクション
アルゴリズムにおける乱数性（ランダムネス）の意義についてお話します．アルゴリズムとは，コンピュータに計算をさせるときの手順のことです．皆さんは，どんなものを「計算」と考えていますか？おつりの勘定も計算ですし，コンピュータを駆使した高度な科学計算も計算です．しかし計算はそれだけではありません．ワープロで文字変換をするのも計算ですし， Web のブラウザが，ネットワーク上の必要な情報を取りに行くのも計算です．大きく言ってしまえば，決められたルールに基づいて動くもはすべて，「計算」と見なすことができます．その決められたルール（手順）がアルゴリズムです．同じ計算をするにも，アルゴリズムの善し悪しで効率が大きく違います．そこで，優れたアルゴリズムの開発は，コンピュータの有効利用のための重要なテーマであり，アルゴリズムの研究は，コンピュータ・サイエンス（計算機科学）の主要な研究分野の一つです．アルゴリズム研究には，離散数学の技法や考え方が非常に多く使われています，また，アルゴリズム研究の中から，新たな離散数学が生まれて来ています．今回は，そうしたアルゴリズム研究の重要な話題の一つ，「乱数性（ランダムネス）」についてお話しします．話の内容は，大きく分けて二つあります．
１．アルゴリズムにおけるランダムネスの利用
計算の途中で乱数を利用するアルゴリズムを，ここでは乱拓アルゴリズム（これはRandomized Algorithmの訳）と呼ぶことにします．「乱数を利用する」というのは， 0か1を毎回，独立に等確率で出力するような乱数ビット生成命令を利用できるということです．そのような乱拓アルゴリズムが活躍する場面をいくつか紹介しましょう．
２．ランダムネスは本質的か？
では，ランダムネスは「計算の効率化」に本質的なのでしょうか？実は，今のところまだわかっていないのです．一般のプログラムでは，真の乱数列を生成するような「乱数ビット生成命令」を使用する代わりに，それと同じような「擬似」乱数をソフト的に作って使います．そうした擬似乱数が，真の乱数とほとんど変わりなければ，ランダムネスは本質的に不要となるのです．では，真の乱数とほとんど変わりのない，高性能な擬似乱数生成は可能なのでしょうか？その前に「真の乱数とほとんど変わりない」というのは，どういう基準で考えるのでしょうか？そもそも「真の乱数」って何なんでしょう？こうした乱数性の意義についての研究は，アルゴリズム研究（正確に言うと「計算の複雑さ」という分野）で，盛んに研究されています．また，最近の情報セキュリティ技術の基礎理論にもなっているのです．こうした研究の一端を紹介しましょう．
３．参考文献
以上の話は，コンピュータの知識やプログラムの知識がない人でも十分わかるように講義するつもりです．ただ，前もって，コンピュータ・サイエンスという分野を覗いてみたい，という方は，以下の本を参考にされるとよいでしょう．
- 渡辺 治， 教養としてのコンピュータ・サイエンス，サイエンス社
- 徳田 雄洋， ジュニア版 コンピュータ科学入門 １〜５，岩波書店
- 西野 哲朗， 中国人郵便配達問題＝コンピュータサイエンス最大の難関，講談社選書メチエ73．
４．宿題
時間がある人は次の問題を考えておいてください．皆さんならば簡単に解けるかな？
n 個の数の集合 B={b_1,...,b_n} から数を r 個（重複無しで）等確率に選び，選ばれた数の集合を B' とします．また，B' 中の最小の数を b とします．このとき， B-B' の中で，選ばれた b より小さい数の個数の期待値（平均値）はいくつになるでしょうか？ （とりあえず簡単のため， B 中には同じ数が重複して現れないと仮定しても結構です．）