Michael Feather の SCNA トーク「Self-Education and the Craftsman」を見て触発されたので、離散数学が役立つことが証明されているソフトウェア開発の実際の例について聞くことに興味があります。
5858 次
6 に答える
4
ソフトウェア開発はその中核にあるコンピューター サイエンスに基づいているため、離散数学はソフトウェア開発のあらゆる側面に影響を与えてきました。
http://en.wikipedia.org/wiki/Discrete_math
そのリンクを読んでください。このウィキペディアのエントリは主に理論的な用語で述べていますが、多数の実用的なアプリケーションがあることがわかります。
于 2009-11-13T17:03:59.180 に答える
2
San Jacinto が指摘するように、プログラミングの基礎は離散数学に密接に結びついています。さらに、「離散数学」は非常に広い用語です。これらのことが、特定の例を選ぶのを難しくしているのかもしれません。私はほんの一握りを思いつくことができますが、他にもたくさんあります。
コンパイラの実装は、例の良いソースです。明らかに、そこにはオートマトン/形式言語理論があります。レジスタの割り当ては、グラフの色分けで表現できます。コンパイラーの最適化に使用される古典的なデータフロー分析は、格子状の代数構造上の関数で表現できます。
有向グラフの使用の簡単な例は、トポロジー ソートを実行することによって個々のタスクに関連する依存関係を取得するビルド システムです。有向グラフの概念を持たずにこの問題を解決しようとすると、面倒な簿記コードを使用して、ビルド全体で依存関係を追跡しようとすることになると思います (そして、循環的な依存関係はエレガントではありませんでした)。
明らかに、ほとんどのプログラマーは独自の最適化コンパイラーを作成したり、システムを構築したりしていないため、私自身の経験から例を取り上げます。衛星ナビシステムに道路データを提供している会社があります。彼らは、データの自動整合性チェックを望んでいました。その 1 つは、ネットワークがすべて接続されている必要があることです。つまり、任意の開始点からどこにでもアクセスできる必要があります。位置のすべてのペア間のルートを見つけようとしてデータをチェックすることは、実際的ではありません。ただし、道路網データから有向グラフを導出することは可能であり (右折制限などをエンコードする方法で)、グラフの強連結成分 (標準グラフ) を見つけることに問題が軽減されます。効率的なアルゴリズムによって解決される理論的な概念。
于 2009-11-19T22:34:56.667 に答える
2
大学の離散数学コースで学んだテクニックは、レイトン教授のゲームでかなり役に立ちました。
それは役に立ちます...そうですか？
マップの色付けだけでなく、マップの色付けアルゴリズムが役立つ実際の例がたくさんあります。最終試験の問題は、六差路交差点の信号機プログラミングに関するものでした。
于 2009-11-13T17:25:29.853 に答える
1
テスト自体は、次のような命題論理 (したがって離散数学) の概念である modus tollens から適切に進められると私は信じています。
P=>Q. !Q、したがって !P。
P=>Q に対して「機能が適切に動作している場合、テストに合格する」とプラグインし、与えられた !Q を使用する場合 (「テストに合格しなかった」)、これらすべてのステートメントが事実上正しい場合、修正のために機能を返却するための有効で健全な根拠があります。対照的に、多くの、おそらくほとんどのテスターは、次の原則に従って動作します。
「プログラムが正常に動作している場合、テストに合格します。テストに合格したので、プログラムは正常に動作しています。」
これは、P=>Q のように記述できます。Q、したがって P.
しかし、これは「結果を肯定する」という誤謬であり、テスターがそれが示していると信じていることを示していません。つまり、彼らはその機能が「検証済み」であり、出荷できると誤って信じています。Q が与えられたとき、P は実際には真であるか、または P=>Q に対して真ではない可能性があり、これは真理値表で示すことができます。
Modus tollens は、Karl Popper の反証としての科学の概念の中核であり、テストはほぼ同じ方法で進められるべきです。私たちは、この機能が何らかの禁止された方法で機能するという狭い意味で機能することを検証しようとするのではなく、すべての明示的および暗黙的な状況下で機能が常に機能するという主張を反証しようとしています.
于 2011-10-26T07:17:07.877 に答える
1
多くの多くのうちの1つの例...
ビルド システムでは、ジョブのトポロジカル ソートを使用するのが一般的です。
ビルドシステムとは、依存関係でジョブを管理する必要があるシステムを意味します。
プログラムのコンパイル、ドキュメントの生成、建物の構築、会議の開催など、タスク管理ツールやコラボレーション ツールなどに応用できます。
于 2011-08-11T11:10:05.680 に答える
1
私はソフトウェア テストのコースを受講しており、そのうちの 3 つの講義は、テストに関連する離散数学の復習に専念していました。このような観点からテスト計画を考えることは、テストをより効果的にするのに本当に役立つようです。
特に集合論の理解は、データベース開発において特に重要です。
他にもたくさんのアプリケーションがあると思いますが、ここで思い浮かぶのはこれらの 2 つです。
于 2009-11-13T17:07:11.787 に答える