✖

情報科学

形式言語

形式言語、アルファベット、語とは何か。形式言語の理論の基本用語を、ふだんの言語と比べながら例を使って解説します。

有限オートマトン

状態と遷移からなる計算モデルとしての有限オートマトン。定義、状態遷移図、計算の形式化、受理される語の例。

オートマトンの最小化

有限オートマトンの到達不能状態とは、初期状態からたどり着けない状態のことです。定義と、オートマトンから安全に取り除く手順。

正規言語の閉包性

正規言語は和集合、共通部分、連接、クリーネ閉包について閉じています。演算について閉じているとはどういうことか、なぜ正規言語で成り立つのか。

正規表現

正規表現とは何か、語の集合をどのように表すか。定義、算術の式との比較、有限オートマトンとの関係。

異なる値の個数の推定

Linear Counting で、大量のデータに含まれる異なる値の個数を推定する方法。ハッシュ関数、ビットマップ、そして素朴な方法ではうまくいかない理由。

ブルームフィルタ:要素は集合に含まれているか

ブルームフィルタは、要素が集合に含まれているかどうかをすばやく答える確率的データ構造です。しくみ、ハッシュ関数、実際の使い方。

シーザー暗号

文章を暗号化するもっとも古い方法の一つ、シーザー暗号のしくみ。文字をずらす原理、暗号の一般化、オンラインの暗号化ツール。

ヴィジュネル暗号

ヴィジュネル暗号は複数の暗号のアルファベットを使うので、頻度分析に強い暗号です。暗号化のしくみ、ヴィジュネル方陣、鍵の選び方、オンラインツール。