離散数学

離散数学は、連続的（連続関数に類似）ではなく「離散的」（自然数の集合と一対一である離散変数に類似）とみなせる数学的構造の研究である。離散数学で研究される対象には、整数、グラフ、論理のステートメントなどがある。^{[1] [2] [3]}対照的に、離散数学では、実数、微積分、ユークリッド幾何学などの「連続数学」のトピックは除外される。離散オブジェクトは整数で列挙できることが多い。より正式には、離散数学は可算集合^[4]（有限集合または自然数と同じ濃度の集合）を扱う数学の分野として特徴付けられている。しかし、「離散数学」という用語の正確な定義はない。^[5]

離散数学で研究されるオブジェクトの集合は、有限の場合も無限の場合もあります。有限数学という用語は、離散数学の分野のうち有限集合を扱う部分、特にビジネスに関連する領域に適用されることがあります。

離散数学の研究は、20 世紀後半に増加しました。これは、離散的なステップで動作し、データを離散的なビットで保存するデジタル コンピュータの開発によるところが大きいです。離散数学の概念と表記法は、コンピュータ アルゴリズム、プログラミング言語、暗号化、自動定理証明、ソフトウェア開発など、コンピュータサイエンスの分野におけるオブジェクトと問題を研究および記述するのに役立ちます。逆に、コンピュータ実装は、離散数学のアイデアを現実世界の問題に適用する上で重要です。

離散数学の主な研究対象は離散的なオブジェクトですが、 「連続」数学の解析手法もしばしば採用されます。

大学のカリキュラムでは、離散数学は1980年代にコンピュータサイエンスのサポートコースとして登場しました。その内容は当時はやや場当たり的でした。その後、カリキュラムはACMとMAAの努力と連携して、基本的に1年生の数学的成熟度を高めることを目的としたコースに発展しました。そのため、今日では一部の大学では数学専攻の必須科目となっています。^{[6] [7]}高校レベルの離散数学の教科書もいくつか登場しています。^{[8]このレベルでは、離散数学は、この点で}プレカルキュラスと同様に準備コースと見なされることがあります。^[9]

フルカーソン賞は離散数学の優れた論文に授与されます。

理論計算機科学には、コンピューティングに関連する離散数学の領域が含まれます。グラフ理論と数理論理学に大きく依存しています。理論計算機科学には、アルゴリズムとデータ構造の研究が含まれます。計算可能性は、原理的に計算できるものを研究し、論理と密接な関係があります。一方、複雑性は、計算にかかる時間、空間、その他のリソースを研究します。オートマトン理論と形式言語理論は、計算可能性と密接に関連しています。ペトリネットとプロセス代数は、コンピュータ システムをモデル化するために使用され、離散数学の方法は、 VLSI電子回路の解析に使用されます。計算幾何学は、アルゴリズムを幾何学的問題と幾何学的オブジェクトの表現に適用し、コンピュータ画像解析は、アルゴリズムを画像の表現に適用します。理論計算機科学には、さまざまな連続計算トピックの研究も含まれます。

情報理論には、情報の定量化が含まれます。これに密接に関連しているのが、効率的で信頼性の高いデータ伝送および保存方法を設計するために使用される符号化理論です。情報理論には、アナログ信号、アナログ符号化、アナログ暗号化などの継続的なトピックも含まれます。

論理学は、有効な推論と推論の原理、および一貫性、健全性、完全性の研究です。たとえば、ほとんどの論理システムでは（直観主義論理ではそうではありませんが）、パースの法則（（（P → Q）→ P）→ P）は定理です。古典論理の場合、これは真理値表で簡単に検証できます。数学的証明の研究は論理学において特に重要であり、自動化された定理証明やソフトウェアの形式的検証にまで蓄積されてきました。

論理式は離散構造であり、証明も同様に有限木^{[10] 、}またはより一般的には有向非巡回グラフ構造^{[11] [12]}（各推論ステップで1つ以上の前提ブランチを組み合わせて1つの結論を導く）を形成します。論理式の真理値は通常有限集合を形成し、一般的にはtrueとfalse の2つの値に制限されますが、論理は連続値になることもあります（例：ファジー論理）。無限証明木や無限導出木などの概念も研究されています（例：無限論理^{[13] ）}。

集合論は、{青、白、赤} やすべての素数の（無限）集合などのオブジェクトの集合である集合を研究する数学の分野です。部分的に順序付けられた集合や他の関係を持つ集合は、いくつかの分野で応用されています。

離散数学では、可算集合（有限集合を含む）が主な焦点です。数学の一分野としての集合論の始まりは、通常、三角級数の研究に動機付けられた、さまざまな種類の無限集合を区別するゲオルク・カントールの研究によって特徴付けられ、無限集合の理論のさらなる発展は離散数学の範囲外です。実際、記述的集合論の現代の研究では、伝統的な連続数学が広範に使用されています。

組合せ論では、個別の構造を組み合わせたり配置したりする方法を研究します。 列挙的組合せ論は、特定の組合せオブジェクトの数を数えることに重点を置いています。たとえば、12 倍法は、順列、組み合わせ、および分割を数えるための統一されたフレームワークを提供します。 解析的組合せ論は、複素解析と確率論のツールを使用して、組合せ構造を列挙 (つまり、数を決定) することを扱います。明示的な組合せ式と生成関数を使用して結果を記述する列挙的組合せ論とは対照的に、解析的組合せ論は漸近式を取得することを目的としています。 位相的組合せ論は、位相幾何学と代数的位相幾何学/組合せ的位相幾何学の手法を組合せ論で使用することを扱います。設計理論は、特定の交差プロパティを持つサブセットのコレクションである組合せ設計の研究です。 分割理論は、整数分割に関連するさまざまな列挙および漸近問題を研究し、q 級数、特殊関数、直交多項式と密接に関連しています。分割理論は、もともと数論と解析学の一部でしたが、現在では組合せ論の一部​​または独立した分野と見なされています。 順序理論は、有限と無限の両方の部分的に順序付けられた集合の研究です。

グラフとネットワークの研究であるグラフ理論は、しばしば組合せ論の一部​​であると考えられるが、独自の問題を抱えるほど大きく独特なものとなり、独立した学問分野とみなされるようになった。^[14]グラフは離散数学の主要な研究対象の1つである。グラフは、自然構造と人工構造の両方において最も普遍的なモデルの1つである。グラフは、物理システム、生物システム、社会システムにおける多くの種類の関係やプロセスダイナミクスをモデル化することができる。コンピュータサイエンスでは、通信ネットワーク、データ編成、計算装置、計算の流れなどをグラフで表現できる。数学では、幾何学や、結び目理論などの位相幾何学の特定の部分で役立つ。代数グラフ理論は群論と密接な関係があり、位相グラフ理論は位相幾何学と密接な関係がある。連続グラフもあるが、グラフ理論の研究は大部分、離散数学の領域に属する。

数論は、一般的に数、特に整数の性質を扱っています。暗号学や暗号解読学にも応用されており、特にモジュラー算術、ディオファントス方程式、線形および二次合同、素数、素数判定などにおいて応用されています。数論のその他の離散的側面には、数の幾何学があります。解析的数論では、連続数学の手法も使用されます。離散的対象を超えるトピックには、超越数、ディオファントス近似、p進解析、関数体などがあります。

代数構造は、離散例と連続例の両方として現れます。離散代数には、論理ゲートとプログラミングで使用されるブール代数、データベースで使用される関係代数、代数符号理論で重要な群、環、体の離散バージョンと有限バージョン、形式言語の理論に登場する離散半群とモノイドが含まれます。

連続数学には、離散計算、離散フーリエ変換、離散幾何学、離散対数、離散微分幾何学、離散外積分、離散モース理論、離散最適化、離散確率論、離散確率分布、差分方程式、離散力学系、離散ベクトル測度など、離散バージョンを持つ概念や理論が数多くあります。

離散計算と差分積分学では、整数の区間で定義される関数は通常、数列と呼ばれます。数列は、データ ソースからの有限数列、または離散動的システムからの無限数列です。このような離散関数は、リスト (定義域が有限の場合) またはその一般項の式によって明示的に定義することも、再帰関係または差分方程式によって暗黙的に与えることもできます。差分方程式は微分方程式に似ていますが、微分の代わりに隣接する項の差をとります。差分方程式は微分方程式を近似するために使用することも、(より一般的には) それ自体で研究することもできます。微分方程式に関する多くの問題や方法には、差分方程式に対応するものがあります。たとえば、連続関数やアナログ信号を研究するための調和解析には積分変換がありますが、離散関数やデジタル信号には離散変換があります。離散距離空間の他に、より一般的な離散位相空間、有限距離空間、有限位相空間が存在します。

時間スケール計算は、差分方程式の理論と微分方程式の理論を統合したもので、離散データと連続データの同時モデリングを必要とする分野に応用されています。このような状況をモデリングする別の方法は、ハイブリッド動的システムの概念です。

離散幾何学と組合せ幾何学は、幾何学的オブジェクトの離散的な集合の組合せ的特性に関するものです。離散幾何学における長年のトピックは、平面のタイリングです。

代数幾何学では、曲線の概念は、有限体上の多項式環のスペクトルをその体上のアフィン空間のモデルと見なし、他の環の部分多様体またはスペクトルがその空間にある曲線を提供するようにすることで、離散幾何学に拡張できます。曲線が現れる空間には有限個の点がありますが、曲線は点の集合というよりも、連続設定における曲線の類似物です。たとえば、体の形式のすべての点は、点として、または(xc) における局所環のスペクトル として、点とその周りの近傍として研究できます。代数多様体には、ザリスキ接空間と呼ばれる明確に定義された接空間の概念もあり、これにより、微積分の多くの特徴を有限設定でも適用できます。 ${\displaystyle V(x-c)\subset \operatorname {Spec} K[x]=\mathbb {A} ^{1}}$${\displaystyle K}$${\displaystyle \operatorname {Spec} K[x]/(x-c)\cong \operatorname {Spec} K}$${\displaystyle \operatorname {Spec} K[x]_{(x-c)}}$

応用数学において、離散モデリングは連続モデリングの離散版です。離散モデリングでは、離散式をデータに当てはめます。この形式のモデリングでは、再帰関係を使用するのが一般的です。離散化とは、連続モデルと方程式を離散モデルに変換するプロセスであり、多くの場合、近似値を使用して計算を容易にする目的で行われます。数値解析は重要な例です。

離散数学の歴史には、この分野のさまざまな領域で注目を集めてきた多くの困難な問題が含まれています。グラフ理論では、 1852年に初めて提唱され、1976年まで証明されなかった四色定理を証明しようとする試みが多くの研究の動機となりました（ケネス・アペルとヴォルフガング・ハーケンがコンピュータの多大な支援を受けて証明しました）。^[15]

論理学では、 1900年にデイヴィッド・ヒルベルトが提示した未解決問題のリストの2番目の問題は、算術の公理が矛盾しないことを証明することだった。 1931年に証明されたゲーデルの第二不完全性定理は、これが不可能であることを示した。少なくとも算術自体では不可能だった。ヒルベルトの10番目の問題は、整数係数を持つ与えられた多項式ディオファントス方程式に整数解があるかどうかを判断することだった。1970年に、ユーリ・マティヤセビッチはこれが不可能であることを証明した。

第二次世界大戦でドイツの暗号を解読する必要があったため、暗号技術と理論計算機科学が進歩し、イギリスのブレッチリー・パークでアラン・チューリングの指導の下、最初のプログラム可能なデジタル電子計算機が開発され、彼の代表作『計算可能数について』が出版された。^[16]冷戦下でも暗号技術は重要であり続け、その後数十年間で公開鍵暗号などの基本的な進歩が遂げられた。通信産業も離散数学、特にグラフ理論と情報理論の進歩を促した。論理ステートメントの形式的検証は安全性が重視されるシステムのソフトウェア開発に必要であり、自動定理証明の進歩はこの必要性によって推進されてきた。

計算幾何学は、現代のビデオゲームやコンピュータ支援設計ツールに組み込まれているコンピュータグラフィックスにおいて重要な役割を果たしています。

離散数学のいくつかの分野、特に理論計算機科学、グラフ理論、組合せ論は、生命の樹の理解に関連する困難なバイオインフォマティクスの問題に対処する上で重要である。^[17]

現在、理論計算機科学における最も有名な未解決問題の一つは、複雑性クラスPとNPの関係に関するP = NP問題である。クレイ数学研究所は、最初の正しい証明に対して100万ドルの賞金を、他の6つの数学問題に対しても賞金を出している。 [ 18 ^]

• 離散数学の概要
• 子供たちに離散数学を教える番組「サイバーチェイス」

ウィキブックスには離散数学に関する本があります。

ウィキメディア・コモンズには、離散数学に関連するメディアがあります。

• 離散数学は、2011 年 8 月 29 日にutk.edu 数学アーカイブのWayback Machineにアーカイブされ、シラバス、チュートリアル、プログラムなどへのリンクが提供されています。
• アイオワセントラル：電気技術プログラム電気工学のための離散数学。