IT専門分野のトレーニングプログラムを見ると、通常は1年生または2年生向けの（おそらくは異なる名前の）離散数学の分野が表示されます。 そして、その存在は非常に合理的です。 離散数学と連続数学 （数学の分析によって太古の昔から研究所の最初の年に表されていた）は、美しい強力な科学である単一の数学の2つの側面です。
以前は「離散数学」のようなものはありませんでしたが、これは離散的な問題がなかったことを意味するものではありません。離散数学の研究の過程で名前が現れるアベル、ディリクレ、フィボナッチ、オイラーは決して私たちの同時代人ではありません！ しかし、当時、数学の独立した部門を分離するために、問題と方法の重大な質量がまだ開発されていなかったため、それらの間に目に見える関係はなかった。 そして、一見したところ、さまざまな概念の間の実り多い相互接続の多くは、数学者が彼らの科学で高く評価するものです。
まあ、数学者は数学のすべてに興味があります。 プログラマーにとって離散数学はなぜですか？
ITスペシャリスト向けの理由
第一に、個別のタスクで特に鮮明に示されている多くのアイデアも、コンピューターサイエンスに不可欠です。 たとえば、 再帰と帰納の基本概念を考えてみましょう。
再帰は、文字通り、戻り、自分へのアピールです。 よく知られているユビキタスなフィボナッチ数は最も簡単に再帰的に決定されます。最初の2つのフィボナッチ数は1に等しく、次の各数はその2つの前任者の合計に等しい：1,1,2,3,5,8、...したがって、次の数を計算するには、同じ種類の計算済みの数字。 関数型プログラミングがどのように研究されるか、そして実際に再帰に慣れることなく、コンピューターサイエンスの他の多くの分野を想像することは困難です。 再帰に非常に近いプロセスは、数学的ステートメントを証明する方法である帰納法です。ここでは、複雑なケースを証明する際に単純なステートメントに依存しています。 再帰との類似点は明らかであり、実際、オブジェクトの存在の帰納的証拠を、このオブジェクトを構築する再帰的な方法の記述に再定式化できる場合、それは一般的なことです。
帰納法や再帰などの基本的なことについて話しているので、離散数学の例で非常にはっきりと見える技術の多くは、数学全体で効果的であると言わざるを得ません。 これは帰納法だけでなく、ディリクレ原理、平均値に応じた選択原理などでもあります。
コンピュータサイエンスが想像できない次の要素はグラフです。 最も単純なグラフアルゴリズムは、アルゴリズムのあらゆる入門コースにも含まれています。 たとえば、コンピューターサイエンスの古典的な問題の1つである巡回セールスマン問題は、ハミルトニアンサイクルの概念に関連付けられています。
もう1つのアーカイブスキルは、およその量を正確に計算して推定することです。 たとえば、ループで比較操作が実行される回数を計算する方法：
for i ≔ 1 to n do for j ≔ i to n do for k ≔ i to j do if a[i] > a[k] then …
または、別の例を示します。 100個の製品のリストから20個を選択する必要があるため、それらの合計コストは正確に2,000ルーブル（「変更なし」）になります。 これは、古典的なバックパック問題のバリエーションです。 あなたの同僚が夜を考えて、徹底的な検索で問題を解決すると申し出たとします：20種類の商品のあらゆる種類のセットを並べ替え、検索中に目的のセットが表示されたらすぐに答えを出します。 ちなみに、「ブルートフォース」特性は、常にアルゴリズムにスティグマをかけるとは限りません。 それはすべて入力のサイズに依存します。 だから、合理的な時間で、100から20個のオブジェクトを選択するこの問題をブルートフォースで解決できるかどうかをどのように把握するのですか？
最後に、現代の「アルゴリズムの設計者」にとって 、 確率論的方法も理解する必要があります。 これは、現代の組み合わせ論の多くの問題を解決する一般的な方法です。 非常に多くの場合、今日知られている問題の最良の解決策は、この方法によって得られます。 実践者にとって、この方法を習得することは、 確率論的アルゴリズムが現代のコンピューターサイエンスで確実にその位置を占める限りにおいて有用です。 そして、そのようなアルゴリズムの動作を分析するとき、確率論的手法の研究中に開発された直感は非常に役立ちます。
離散構造オンラインコース
離散数学のリストされた概念は実際にはプログラマーを妨害することはないが、それらの無知が妨害するという信念を持って、モスクワ物理学技術学部の対応するコースを読みました。 そして最近、私は喜んで利用したオンラインコースを行う機会がありました。 リンクからサインアップできます。 サインアップしたすべての人に私が望む主なことは、困難を恐れることなく、コースを最後までやり、認定裁量の称号を受け取ることです。 一般的に、MOOCは苦痛を伴わずに知識を豊かにします。 また、私自身の自己利益もあります。オンライン学生が増えれば増えるほど、ディスカッションを読んだり、問題解決の統計を観察したりすることで、より多くを学ぶことができます。 結局のところ、学ぶことを学ぶことも遅すぎることはありません！
必要な知識
最初の2つのモジュールを完了するには、学校の知識のみが必要です。 3番目のモジュールでは、「限界とは何か」および「関数x 20または2 xのどれがより速く成長するか（関数の導関数）」のレベルで数学的分析の基礎に関する知識が必要です。 最後の3つのモジュールでは、確率とは何か、条件付き確率、期待、分散の概念が必要です。 また、線形空間の基礎と次元が何であるかを知っておくといいでしょう。 確率と線形代数に精通していない場合は、 これらの入門コースに同時に登録できます。 そうすれば、この知識が必要になった瞬間に間に合うようになります。
ポスト台本
私は利害の対立で告発される可能性があります、結局、私は数学者であり、そしてもちろん、できるだけ多くのHabrの常連を私の宗派にもたらしたいです。 私の弁護では、Quoraでこの回答を参照できます。 この回答にリストされているほとんどのトピックの下で、私は個人的に購読する準備ができています。それらの多くはオンラインコースに含まれています。 また、Yandexoidsの意見の選択にも言及します。