問題タブ [discrete-mathematics]

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

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

例:

ODUのCS 381

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

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

私は個別の構造で下位部門のコースを教えるつもりです。私がテキスト ブックDiscrete Structures, Logic, and Computabilityを選択した理由の 1 つは、関数型プログラミング言語での実装に役立つ例と概念が含まれているためです。（私も良い教科書だと思います。）

DS の概念を説明し、学生が使用できる、わかりやすい FP 言語が必要です。ほとんどの学生は、せいぜい 1 学期か 2 学期の Java プログラミングしか経験していません。Scheme、Erlang、Haskell、Ocaml、SML を検討した結果、Haskell または標準 ML のいずれかに落ち着きました。以下に概説する理由から、私は Haskell に傾倒していますが、いずれかのアクティブなプログラマーの意見を求めています。

• Haskell と SML の両方にパターン マッチングがあり、再帰アルゴリズムの記述が簡単になります。
• Haskell には、そのようなリストを数学的に表現する方法とうまく一致する優れたリスト内包表記があります。
• Haskell には遅延評価があります。リスト内包表記法を使用して無限リストを構築するのに最適です。
• SML には、関数の定義と使用の両方が可能な真にインタラクティブなインタープリターがあります。Haskell では、関数は別のファイルで定義し、対話型シェルで使用する前にコンパイルする必要があります。
• SML は、理解しやすい構文で関数の引数と戻り値の型を明示的に確認します。例: val foo = fn : int * int -> int. Haskell の暗黙のカリー構文はもう少し鈍いですが、完全に異質というわけではありません。例: foo :: Int -> Int -> Int。
• Haskell はデフォルトで任意精度の整数を使用します。SML/NJ の外部ライブラリです。また、SML/NJ はデフォルトで出力を 70 文字に切り捨てます。
• Haskell のラムダ構文は巧妙で、単一のバックスラッシュを使用します。SML はより明示的です。ただし、このクラスでラムダが必要になるかどうかはわかりません。

基本的に、SML と Haskell はほぼ同等です。Haskell のリスト内包表記と無限リストが大好きなので、Haskell に傾倒しています。しかし、Haskell のコンパクトな構文の膨大な数のシンボルが学生に問題を引き起こすのではないかと心配しています。SOに関する他の投稿を読んで集めたものから、HaskellはFPから始める初心者にはお勧めできません。ただし、本格的なアプリケーションを構築するつもりはなく、単純なアルゴリズムを試すだけです。

どう思いますか？

編集：あなたの素晴らしい回答のいくつかを読んで、私の箇条書きのいくつかを明確にする必要があります.

SML では、インタープリターでの関数の定義と外部ファイルでの関数の定義の間に構文上の違いはありません。階乗関数を書きたいとしましょう。Haskell では、この定義をファイルに入れ、GHCi にロードできます。

私にとって、それは明確で簡潔であり、本の数学的定義と一致しています。しかし、GHCi で関数を直接書きたい場合は、別の構文を使用する必要があります。

対話型インタープリターを使用する場合、教育の観点からは、学生がファイルとコマンド ラインの両方で同じコードを使用できると非常に便利です。

「関数の明示的な確認」とは、関数を定義すると、SML がすぐに関数の名前、引数の型、および戻り値の型を通知することを意味します。Haskell では、:typeコマンドを使用する必要があり、やや混乱するカレー表記が表示されます。

Haskell のもう 1 つの優れた点 - これは有効な関数定義です。

繰り返しますが、これは彼らが教科書で見つけるかもしれない定義と一致します。SML ではできません。

ボイヤームーアアルゴリズムが最悪の場合の線形であるためには、不一致テーブルの計算はO（m）でなければなりません。ただし、単純な実装では、すべての接尾辞O（m）がループされ、その接尾辞のすべての位置が等しくなるかどうかがチェックされます...これはO（m ³）です。

以下は、テーブル作成アルゴリズムの単純な実装です。したがって、この質問は次のようになります。このアルゴリズムの実行時間をO（m）に改善するにはどうすればよいですか？

心を休めるために、これは宿題ではありません。誰かが改善のためのアイデアを投稿したときに改訂を追加します。

実際に変換してカウントせずに、数値のバイナリ表現で「1」の数を取得するにはどうすればよいですか?

例えば

次のステートメントの対比を構築しようとしています: A が 0 または B が 0 の場合、A*B は 0 です。

これが私の試みです: A*B が 0 でない場合、A は 0 ではないか、B は 0 ではありません。

元のステートメントは true ですが、A*B が非ゼロになるためには AとB の両方が非ゼロでなければならないため、対比は偽です...何か間違ったことをしていますか?

私はオンラインでConcreteMathsの内容をちらっと見ていました。私は少なくとも言及された機能とトリックのほとんどを聞いたことがありますが、特別な番号に関するセクション全体があります。これらの数には、スターリング数、オイラー数、調和数などが含まれます。今、私はこれらの奇妙な数字のいずれにも遭遇したことがありません。それらは計算問題をどのように助けますか？それらは一般的にどこで使用されますか？

1 人が 8 面体のサイコロを 20 個振って、合計 8 の 20 乗の可能な結果が得られるゲームを想定します。特定のイベントが発生する確率を計算するには、イベントが発生する可能性のある方法の数を 8^20 で割ります。

値 3 のサイコロを正確に 5 つ得る方法の数を計算できます。(20 が 5 を選択) は、3 のオーダー数を示します。7^15 は、15 回のロールで値 3 を取得できない方法の数を示します。 .

答えは、文字列 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0 を並べ替えることができる方法の数として見ることもできます,0,0 (20 は 5 を選択) にゼロの値の総数 (有効な値が 7 つあると仮定) 7^15 を掛けます (これは正しいです)。

• 質問 1: 同じ値 (つまり、すべてのサイコロの値) のサイコロを正確に 5 つ得る方法の数を計算するにはどうすればよいですか? 注: 上記の最初の答えを単純に使用して bt 8 を掛けると、膨大な量の二重カウントが発生しますか?

  ケース (5 1's)、(5, 2's)、(5, 3's)、... (5's, 8) のそれぞれについて、それらを合計することができることを理解しています (より単純には 8*(5 1's) )。次に、オーバーラップ数の合計 (5 1) と (5 2)、(5 1) と (5 3)... (5 1) と (5, 2) と ... と (5, 8) を引きます。しかし、これは非常に面倒です。これを一般化して、多数のサンプルと多数のクラスにスケールアップします。

• 同じ値のサイコロを 5つ以上得る方法の数を計算するにはどうすればよいですか?

  したがって、11111000000000000000 または 11110100000000000002 または 11111100000001110000 または 11011211222222223333 ですが、00001111222233334444 または 00051174134252 ではありません。

数学を説明するか、これをサポートするライブラリ（特にpythonモジュール）を指す答えを探しています。詳細と例の追加ポイント。

大きなスパース行列（たとえば、10k + x 1M +）が与えられた場合、密行列（すべてゼロ以外の要素）を形成する行と列のサブセット（必ずしも連続ではない）を見つける必要があります。このサブ行列は、アスペクト比の制約内で可能な限り大きくする必要があります（最大の合計ではなく、要素の最大数）。

この問題に対する既知の正確なまたはアプロキサメートの解決策はありますか？

グーグルでのクイックスキャンは、多くの近いが正確ではない結果を与えるようです。どのような用語を探す必要がありますか？

編集：明確にするために; サブ行列は連続である必要はありません。実際、行と列の順序は完全に任意であるため、隣接関係は完全に無関係です。

チャド・オケレの考えに基づく考え

1. 行を最大数から最小数の順に並べます（必須ではありませんが、パフォーマンスに役立つ場合があります）
2. 「大きな」オーバーラップがある2つの行を選択します
3. 重複を減らさない他のすべての行を追加します
4. そのセットを記録する
5. オーバーラップを最小限に抑える行を追加します
6. 結果が小さくなるまで＃3で繰り返します
7. 別の開始ペアで＃2からやり直します
8. 結果が十分に良いと判断するまで続けます