情報科学
形式言語
形式言語、アルファベット、語とは何か。形式言語の理論の基本用語を、ふだんの言語と比べながら例を使って解説します。
有限オートマトン
状態と遷移からなる計算モデルとしての有限オートマトン。定義、状態遷移図、計算の形式化、受理される語の例。
オートマトンの最小化
有限オートマトンの到達不能状態とは、初期状態からたどり着けない状態のことです。定義と、オートマトンから安全に取り除く手順。
正規言語の閉包性
正規言語は和集合、共通部分、連接、クリーネ閉包について閉じています。演算について閉じているとはどういうことか、なぜ正規言語で成り立つのか。
正規表現
正規表現とは何か、語の集合をどのように表すか。定義、算術の式との比較、有限オートマトンとの関係。
異なる値の個数の推定
Linear Counting で、大量のデータに含まれる異なる値の個数を推定する方法。ハッシュ関数、ビットマップ、そして素朴な方法ではうまくいかない理由。
ブルームフィルタ:要素は集合に含まれているか
ブルームフィルタは、要素が集合に含まれているかどうかをすばやく答える確率的データ構造です。しくみ、ハッシュ関数、実際の使い方。
シーザー暗号
文章を暗号化するもっとも古い方法の一つ、シーザー暗号のしくみ。文字をずらす原理、暗号の一般化、オンラインの暗号化ツール。
ヴィジュネル暗号
ヴィジュネル暗号は複数の暗号のアルファベットを使うので、頻度分析に強い暗号です。暗号化のしくみ、ヴィジュネル方陣、鍵の選び方、オンラインツール。