問題タブ [discrete-mathematics]

それで、私は MIT の OpenCourseWare から Discrete Math コースを受講していますが、疑問に思っています...関係とグラフの関係はわかりますが、それを「所有」するには十分ではありません。私は単純なステート マシンを SQL にも実装したので、関係とセットがどのように完全に適用されるかについてのより厳密な研究ではなく、グラフをかなりよく理解しています。すぐには理解できないものをざっと見て、もっと学んだときに戻ってくるというYeggeの一連の思考に従うべきですか？日々作成しているグラフ構造をよりよく分析できるようになりたいと思っています (面白そうです)。また、今すぐ貴重な情報を逃さないようにしたいと思っています。

（編集：さまざまな集合と関係のプロパティがグラフ理論などにどのように関連しているか、および基本的なグラフ理論が集合/関係にどのように関連しているかについて、より良いアイデアを得たいと思います。）

これについてもっと学ぶことができる良いリソースはありますか? 重要な場合に備えて、Rosen の Discrete Mathematics and Its Applications の第 5 版を使用しています。

ありがとう！

数学のスキルはますます重要になってきていますが、CompSci 固有のものに移る前に、いくつかの基本をブラッシュアップするのに適した場所はどこでしょうか?

たくさんのビデオと練習用のエクササイズがあるサイトは二重の勝利になるでしょうが、私はそれを見つけることができないようです.

離散数学（有限数学も）は、論理、集合論、情報理論、部分的に順序付けられた集合、証明、関係、および他の多くのトピックなどのトピックを扱います。

数学の他の分野では、プログラミングをサポートするツールがあります。統計には、多くの便利な統計関数が組み込まれているRとSがあります。数値解析の場合、 Octaveは言語として使用することも、C++に統合することもできます。

離散数学を具体的に扱う言語やパッケージを知りません（離散数学で使用されるアルゴリズムの実装にはほぼすべての言語を使用できますが、これらのアプリケーション用に特別に設計されたライブラリまたは環境が存在するはずです）。

一連のシーケンスを連続した整数にマップする方法について困惑しています。

すべてのシーケンスは次の規則に従います。

そのようなシーケンスが与えられた場合、テーブルへのルックアップを行うための整数を計算し、テーブルへのインデックスを与えられた場合、シーケンスを生成できるソリューションを探しています。

例: 長さ 3 の場合、5 つの有効なシーケンスがあります。次のマップを実行するための高速関数 (できれば両方向) が良い解決策になります。

• 演習のポイントは、有効なシーケンスとセルの間の 1 対 1 のマッピングでパックされたテーブルを取得することです。
• セットのサイズは、可能な一意のシーケンスの数によってのみ制限されます。
• シーケンスの長さがどのくらいになるかはわかりませんが、12 未満の小さい定数で、事前にわかっています。
• 遅かれ早かれこれに着手しますが、それまでの間、コミュニティが「楽しむ」ためにそれを捨てます.

これらは異なる有効なシーケンスです

これらはそうではありません

これに関連する

すべてのノードが他のすべてのノードに接続されている (冗長接続なし) グラフはどのように呼び出されますか?

このグラフには N * (N - 1) / 2 個のエッジがあることがわかっています。

病院の看護師にシフトを最適に割り当てるアプリケーションを開発しています。これは離散変数を使用した線形計画法の問題であり、したがっておそらく NP 困難であると思います。

• 毎日、各看護師 (約 15 ～ 20 歳) にシフトが割り当てられます。
• 少数 (約 6) の異なるシフトがあります。
• 1 日に関して、または従業員に関して、かなりの数の制約と最適化基準があります。
  • 毎日、各シフトに割り当てられる最小人数が必要です
  • 一部のシフトは重複しているため、中間シフトを行っている人がいる場合は、早いシフトの人が 1 人少なくても問題ありません。
  • 早いシフトを好む人もいれば、遅いシフトを好む人もいますが、より高いシフト勤務賃金を得るには、最小限のシフト変更が必要です。
  • ある日は遅番、翌日は早番で働くことは認められていません（最低休憩時間の規定による）。
  • 割り当てられた週の勤務時間のミーティング (人によって異なります)
  • ...

したがって、基本的に、それぞれが少数の離散値を取ることができる多数の (aout 20*30 = 600) 変数があります。

現在、私の計画は、修正されたMin-conflicts アルゴリズムを使用することです

• ランダムな割り当てから始める
• 一人一人、毎日のためのフィットネス機能を持っています
• 最悪のフィットネス値を持つ人または日を選択します
• その日/人の割り当ての 1 つをランダムに選択し、最適なフィットネス値をもたらす値に設定します
• 繰り返しの最大回数に達するか、選択した日/人に改善が見られなくなるまで繰り返します

より良いアイデアはありますか？局所最適に陥ってしまうのではないかと少し心配です。何らかの形式のシミュレーテッド アニーリングを使用する必要がありますか? それとも、一度に 1 つの変数を変更するだけでなく、具体的には 2 人の間でシフトを切り替えること (現在の手動アルゴリズムの主要コンポーネント) を検討しますか? 変更される可能性があるため、現在の制約に合わせてアルゴリズムを調整することは避けたいと思います。

編集:厳密に最適なソリューションを見つける必要はありません。名簿は現在手動で作成されており、ほとんどの場合、結果はかなり最適化されていないと確信しています-それを打ち負かすのは難しいことではありません. 短期的な調整と手動によるオーバーライドも間違いなく必要ですが、これが問題になるとは思いません。過去の割り当てと手動割り当てを「修正済み」としてマークすると、実際には、ソリューション スペースが減り、タスクが単純化されます。

離散的で高速な方法を使用して導関数を計算する方法を探しています。方程式の種類がわからないので、オイラー法などの積分に類似した離散的な方法を探しています。

関係が推移的であるかどうかを確認する必要がありますか？

関係の推移性をチェックするためのアルゴリズムを提案していただけますか？

関係をブール行列として格納しています。グラフのように要素が他の方法で関連している場合は1があります。

ありがとう。

質問が少し技術的ではないかと思いますが、誰かが同様の主題に出くわしたり、何らかのポインタをくれたりすることを願っています.

G が (代数構造の意味で) 群であり、g ₁ , ..., g _nが G の元である場合、アルゴリズム (または GAP などの専用プログラムの関数) があるかどうかを判断します。は、これらの要素が部分群の剰余類の代表の集合を形成するような G の部分群ですか? (G は置換群であり、おそらく完全な対称群であると仮定することもできます。)

(もちろん、Todd-Coxeter アルゴリズムのように、特定のサブグループの剰余類を見つけるアルゴリズムはいくつかあります。これは一種の逆問題です。)

ありがとう、ダニエレ

私はまだ良い答えを見つけていません。または、そのことについては、任意の答え。私は CS コースの個別の構造を教えるように依頼されましたが、同時に、数学部門が提供する個別の数学コースではないことを確認してください。

多くの大学は離散構造コースを提供しています。DSの教科書もたくさんあります。しかし、コースのシラバスや教科書の紹介を見ると、「離散構造」という用語はまったく使われていません。代わりに「離散数学」を使用します。DS は、コース/教科書のタイトルにのみ表示されます。

例:

ODUのCS 381

ウィキペディアの離散構造のエントリ

離散構造とは何ですか?離散数学との違いは何ですか?