markdown
集合と写像の基本md eec1d89
lecture/information/discrete-math/集合と写像の基本-講義.n.md
Download as PDF
集合と写像の基本
informationdiscrete-mathundergraduatelecture
導入
この講義で最重要なのは、情報工学では「何をひとまとめに見るか」を集合で、「どこへ対応させるか」を写像で表すことです。
分類と対応付けが曖昧だと、データ構造や関数やグラフの話がばらばらに見えてしまいます。集合と写像は、それらを共通の言葉で整理する道具です。
用語と定義
集合 とは、対象をひとまとまりとして集めたものです。
要素 とは、集合を構成する 1 つ 1 つの対象です。
写像 とは、ある集合の各要素を、別の集合の要素に対応させる規則です。
方針
まず対象を集合として切り出します。そのあと、要素どうしの対応を写像として書き、どの情報が保たれているかを見ます。
直感的な説明
学生の集まりを 1 つの集合、学籍番号の集まりを別の集合だとします。「各学生に 1 つの番号を対応させる」規則は写像です。この見方をすると、データベースの主キーや配列の添字も同じ構造として見えてきます。
厳密な説明
1. 集合
A=\{1,2,3\}
のように要素を並べて表します。
2. 写像
f:A\to B
と書くとき、A が始域、B が終域です。
3. 情報工学とのつながり
配列は「添字の集合から値の集合への写像」と見なせます。
見分け方
- 対象の集まりを定めたいなら、まず集合を作ります。
- 1 つ 1 つの要素がどこへ対応するかを決めるなら、写像として見ます。
- 入力と出力の関係を整理したいときも、写像の言葉が便利です。
最終形
\boxed{\text{集合}=\text{対象のまとまり}}
\boxed{\text{写像}=\text{要素の対応付け}}
\boxed{f:A\to B}
一言でいうと
- 集合と写像は、情報を分類し、対応付けるための基本言語です。