離散数学

大学の授業で離散数学にものすごく苦労しています。
コンピュータ系の学科で勉強する科目のようで他の学科の学生に聞いても「何それ？」って言われてしまいます。
出版されている本の数もすくないようでどうやって勉強したものか・・・。
またどんなときに活躍するのか教えてください。
コンピュータ系の専門の道に進んだ方、ぜひ回答を！

No.4 ベストアンサー 回答者： uyama33 回答日時： 2004/03/24 21:25

Discrete-Time

Signal
Processing

A.V.Oppenheime and R.W.Schafer

Prentice Hall

が、読みやすかったです。
内容は、離散フーリエ変換とか
フィルタとか、Ｚ変換とか
信号処理一般です。


もう一つは
コンピュータの数学
共立出版
はもっと離散数学的かな？

他にも沢山ありますが、
こつは、大学の教授の推薦する
参考書を４，５冊買って読むことだと思います。

この回答へのお礼

ありがとうございました。
教えていただいた本を読んでみようと思います。

お礼日時：2004/04/11 22:49

No.3 回答者： stomachman 回答日時： 2004/03/24 13:34

コンピュータ系の専門の道には進んでないのですが…

出版されている本は少なくないと思います。ただ「離散数学」というひとつの理論体系があるわけではなくて、（つまり、「離散数学の公理」というものはなくて、）類縁の手法、対象を扱う分野をおおざっぱに括って言う言葉に過ぎませんから、これをタイトルにした本が少ないというだけのことではないでしょうか。

ということは、大学の「離散数学」の授業で一体何を勉強しているのか、そこんとこを教えて戴かないと、「どうやって勉強したものか」も分からないです。

ですが、取り敢えず、離散数学がどんな広がりを持つのか、ちょっと概観してみようかと思います。

身近なところで、漸化式と母関数、再帰的アルゴリズムだとか、順列組み合わせの理論（組合せ論。これはまた離散確率論にも繋がります）、グラフ理論など、応用に直結する直感的に分かりやすいところから始めるのも一つの道ではないでしょうか。また、数学基礎論のうち、自然数の基礎論である、集合論による自然数の構成、素数の基本的性質などは、早く学び始めておく方がよいかと思います。

具体的なアルゴリズムの実例が豊富にあるのは、グラフ理論と計算幾何学かと思います。グラフでは、木の探索のアルゴリズムやソートは基本中の基本でもあります。ゲームの木の理論も面白いと思います。計算幾何学は計算量を非常に重視するのが特徴で、言い換えれば実用性が問われます。（計算幾何学をやるには、解析幾何学の基礎知識は必要です。）

シャノンの情報理論は初歩的な確率の知識だけあれば行けちゃいます（そして熱力学とも繋がっていきます）が、そのあとに続く符号理論では代数学が応用されます。
抽象代数（群論・環論・類体論など）は（符号理論に使うだけじゃなく、）自分でかってにこしらえた演算の性質を検討するのに必須のスキルでもあって、その基本的概念は必須になります。関係(relation)の代数はグラフ理論に直結しますし、データベースの理論にも関連する。また同型写像の概念はプログラムの意味論や計算可能性の理論で必要です。

数学の定理や証明とアルゴリズムの関係がはっきりしていないと、数学からアルゴリズムを創り出すことができませんね。ここでプログラムの意味論(semantics)、プログラムの検証(verification)の理論などが重要になってきます。再帰的アルゴリズムが数学的帰納法と対応していること、つまり無限に続く計算を有限のステップで扱うことが本質的です。
意味論の関連からは、様相論理などの非古典論理学も重要かとおもいます。

形式論理は数学の基礎のひとつですが、これはまた、形式言語の一種として、離散数学が扱う対象にもなりますし、ブール代数と直接の関連を持ってもいます。無限集合の内包と外延の概念との関わりも重要です。
形式言語とオートマトンの理論、そして計算可能性の理論は、形式論理による証明とは何か、ということと深い関連があり、（当然の事ながら）数学の本質、「知」の本質ともかかわってきます。超数学（ゲーデルの完全性定理・不完全性定理）へ進むことができます。

計算量の理論はひとつのハイライトでしょうか。グラフ理論や計算幾何学などにおける具体的アルゴリズムの検討と計算可能性の検討とが同時に必要になるので、いろんな知識が求められます。だから却って、計算量の理論から先に手を付けて、必要になった勉強を遡ってやっていく、というのもストーリーを作りやすいのではないかと思います。暗号理論（情報セキュリティ）と深い関係を持っています。

可逆機械や量子コンピュータ、という話になると、物理学と思われるかもしれませんけど、量子力学の物理法則を公理とした数学、ととらえることができます。後者は特に暗号理論と関連しています。

この回答へのお礼

長い回答をありがとうございました。
正直、まだピンときませんが、もう一度がんばってみようと思います。

お礼日時：2004/04/11 22:44

No.2 回答者： neKo_deux 回答日時： 2004/03/24 13:23

画像処理なんかですと、離散フーリエ変換を利用したFFT(高速フーリエ変換)法なんてのが、お馴染みのjpegの圧縮に利用されています。

コンピュータ系ですと、むしろ連続(アナログ)を扱う事の方が少ないですね。

フーリエ変換の良書として「フーリエの冒険」(ヒッポファミリークラブ)という本があります。
離散フーリエ変換やFFTに関して触れているのは一部ですが、他の書籍と比べると書き方が断然わかりやすいので、図書館などで一読してみては？

この回答へのお礼

ありがとうございます。
正直、まだいまいちピンときませんが、とりあえずもう一度勉強し直します。

お礼日時：2004/04/11 22:41

No.1 回答者： noname#21649 回答日時： 2004/03/24 03:18

＞どうやって勉強したものか

中学校入学試験（マスコミ用語のお受験）用算数関係。
和算
＞どんなときに活躍するのか
整数問題（do-loop, for-next等のループ回数の低減）

なお.コンピューターは専門ではありません。

この回答へのお礼

遅くなって申し訳ございません。
ありがとうございました。

お礼日時：2004/04/11 22:39