離散数学りさんすうがくへの導入どうにゅう

1離散数学りさんすうがくの対象たいしょう

この講義こうぎでは、離散数学りさんすうがくが識別可能しきべつかのうな要素ようそとその関係かんけいからなる構造こうぞうを記述きじゅつし、その性質せいしつを有限ゆうげんの記号列きごうれつと推論規則すいろんきそくによって論証ろんしょうする数学すうがくであることを説明せつめいする。

離散的りさんてきな構造こうぞうDiscrete structure とは、要素ようそを個別こべつに識別しきべつし、その要素間ようそかんの関係かんけいを記述きじゅつする構造こうぞうである。整数せいすう、有限文字列ゆうげんもじれつ、グラフ、論理式ろんりしきなどが代表例だいひょうれいである。

ただし、現実げんじつの対象たいしょうが離散的りさんてきなものと連続的れんぞくてきなものに完全かんぜんに分離ぶんりされるわけではない。例たとえば、温度おんどは実数じっすうによる連続量れんぞくりょうとして表現ひょうげんできるが、計算機けいさんきでは有限精度ゆうげんせいどの数値すうちとして符号化ふごうかする。離散性りさんせいは、対象たいしょうそのものだけでなく、問題もんだいをどの粒度りゅうどでモデル化かするかにも依存いぞんする。

2基本概念きほんがいねん

命題めいだいProposition とは、真しんまたは偽ぎのいずれかが確定かくていする主張しゅちょうである。論理ろんりは、命題めいだいを結合けつごうし、推論すいろんの妥当性だとうせいを検証けんしょうするための言語げんごである。

集合しゅうごうSet とは、対象たいしょうを要素ようそとしてまとめたものである。写像しゃぞうMap $$f:A\to B$$f:A\to B とは、集合しゅうごう $$A$$A の各要素かくようそに $$B$$B の要素ようそを一ひとつずつ対応たいおうさせる規則きそくである。

関係かんけいRelation とは、複数ふくすうの集合しゅうごうの要素間ようそかんに成立せいりつする対応たいおうを集合しゅうごうとして表現ひょうげんしたものである。二項関係にこうかんけい $$R$$R は、$$R\subseteq A\times B$$R\subseteq A\times B と記述きじゅつできる。

グラフGraph $$G=(V,E)$$G=(V,E) とは、対象たいしょうを頂点集合ちょうてんしゅうごう $$V$$V、対象間たいしょうかんの関係かんけいを辺集合へんしゅうごう $$E$$E で表現ひょうげんする構造こうぞうである。

アルゴリズムAlgorithm とは、入力にゅうりょくから出力しゅつりょくを得えるための、停止ていしする明確めいかくな手順てじゅんである。離散数学りさんすうがくは、その入力にゅうりょくと出力しゅつりょくを定義ていぎし、手順てじゅんの正当性せいとうせいと計算量けいさんりょうを論証ろんしょうするための基盤きばんを提供ていきょうする。

3学習順序がくしゅうじゅんじょ

最初さいしょに、命題めいだいと論理ろんりを学習がくしゅうし、仮定かていと結論けつろんを区別くべつして推論すいろんを記述きじゅつする。これは、後続こうぞくするすべての定義ていぎと証明しょうめいの形式けいしきを構成こうせいする。

次つぎに、集合しゅうごうによって対象たいしょうの範囲はんいを、写像しゃぞうによって入力にゅうりょくと出力しゅつりょくの対応たいおうを定義ていぎする。関係かんけいは、順序じゅんじょ、同値性どうちせい、接続せつぞくなどを統一的とういつてきに表現ひょうげんする。

その後ご、関係かんけいの重要じゅうような具体例ぐたいれいとしてグラフを学習がくしゅうし、頂点間ちょうてんかんの到達可能性とうたつかのうせいや距離きょりを定式化ていしきかする。

最後さいごに、これらの構造こうぞうを処理しょりするアルゴリズムを設計せっけいし、論理ろんりや数学的帰納法すうがくてききのうほうによって正当性せいとうせいを、数かずえ上あげによって計算量けいさんりょうを解析かいせきする。

4情報工学じょうほうこうがくにおける役割やくわり

• 論理ろんりは、プログラムの条件じょうけん、仕様しよう、検証条件けんしょうじょうけんを明確化めいかくかする。
• 集合しゅうごうと写像しゃぞうは、データの型かた、状態空間じょうたいくうかん、関数かんすうの定義域ていぎいき・終域しゅういき・像ぞうを記述きじゅつする。
• 関係かんけいとグラフは、データベース、ネットワーク、依存関係いぞんかんけいを抽象化ちゅうしょうかする。
• アルゴリズムの解析かいせきは、有限ゆうげんの資源しげんで計算けいさんを実行じっこうできるかを評価ひょうかする。

5まとめ

• 離散数学りさんすうがくは、識別可能しきべつかのうな要素ようそとその関係かんけいを記述きじゅつし、有限ゆうげんの記述きじゅつによってその性質せいしつを論証ろんしょうする。
• 離散的りさんてきか連続的れんぞくてきかという区別くべつは、対象たいしょうの性質せいしつだけでなく、採用さいようするモデルにも依存いぞんする。
• 命題めいだい、集合しゅうごう、写像しゃぞう、関係かんけい、グラフ、アルゴリズムという順序じゅんじょは、定義ていぎから計算手順けいさんてじゅんへ段階的だんかいてきに進すすむ学習経路がくしゅうけいろを構成こうせいする。