問題タブ [discrete-mathematics]

まず第一に、私はJavaの初心者なので、これが可能かどうかさえわかりません! 基本的に、私はリレーショナルデータの巨大な（300万以上）データソースを持っています（つまり、AはB + C + Dと友達であり、BはD + G + Zと友達です（ただし、Aではありません-つまり、相互的ではありません）など）。この (必ずしも接続されていない) 有向グラフ内のすべてのサイクルを検索します。

Finding all cycles in graphというスレッドを見つけました。これは、少なくとも表面的には、私が求めていることを実行するように見える、Donald Johnson の (基本的な) サイクル検出アルゴリズムを示しています (試してみます火曜日に仕事に戻ったら、その間に聞いても問題ないと思います!)。

Johnson のアルゴリズムの Java 実装のコード (そのスレッド) をざっとスキャンしたところ、関係のマトリックスが最初のステップのように見えたので、私の質問は次のとおりだと思います。

a) Java は 3+million*3+million 行列を処理できますか? (A-friends-with-B を 2 値疎行列で表すことを計画していました)

b) 最初の問題として、すべての接続されたサブグラフを見つける必要がありますか?それとも、循環探索アルゴリズムが互いに素なデータを処理しますか?

c) これは実際に問題の適切な解決策ですか? 「基本」サイクルについての私の理解では、下のグラフでは、ABCDEF を選択するのではなく、ABF、BCD などを選択しますが、タスクを考えると、それは世界の終わりではありません。

d) 必要に応じて、関係の相互性を強制することで問題を単純化できます。つまり、A-friends-with-B <==> B-friends-with-A です。本当に必要な場合は、データ サイズを削減することもできますが、現実的には、常に 1mil マーク前後になります。

z) これは P タスクですか、それとも NP タスクですか?! 私は噛むことができる以上に噛んでいますか？

ありがとうございました。アンディ

質問の解決策を見つけようとしています....数字があります、例：20 ...そして6つの数字があります：{a、b、c、d、e、f} <20、tは見つけようとしますこれらの数値のすべての値、ただし、この数値の 2 つを (+ または -) 組み合わせて、以下のすべての値を 20 にすることができる場合に限ります。たとえば、

31 を選択します。

a = 22 b = 21 c = 14 d = 11 e = 9 f = 5

22 - 21 = 1 ; 11 - 9 = 2 ; 14 - 11 = 3 ; 9 - 5 = 4 ; f = 5; 11 - 5 = 6 ; 21 - 14 = 7 ; .... .... .... .... .... 21 + 9 = 30 ; 9 + 22 = 31 ;

入力は常に同じ数 N の数値 (たとえば 5) であり、整数には実際に数学的な関係があると仮定します (数値の長さ「1」、「2」、n 番目の月の日数などはありません)。出力は、次の整数と検出されたルール、またはルールが検出されなかったというメッセージのいずれかになります。私は1-2-3の順序で、隣接する数字、1つ離れた数字、2つ離れた数字などの合計および/または差を計算してパターンを探し、モジュールに焦点を当てて、算術シーケンスルールを見つけようとするモジュールを用意することを考えていました同じ方法で乗算および/または除算することによる幾何学的シーケンス、および一般的なアプローチがある場合は、再帰シーケンスを検出するためのモジュール。

ありがとう！

私はかなり奇妙な問題に直面しています。私はビット演算をサポートしないアーキテクチャ用のコンパイラに取り組んでいます。ただし、符号付き16ビット整数演算を処理するため、以下のみを使用してビット単位の演算を実装できるかどうか疑問に思いました。

• 加算（c = a + b）
• 減算（c = a --b ）
• 除算（c = a / b）
• 乗算（c = a * b）
• 係数（c = a％b）
• 最小（c = min（a、b））
• 最大（c = max（a、b））
• 比較（c =（a <b）、c =（a == b）、c =（a <= b）など）
• ジャンプ（goto、for、et.c.）

サポートできるようにしたいビット演算は次のとおりです。

• または（c = a | b）
• そして（c = a＆b）
• Xor（c = a ^ b）
• 左シフト（c = a << b）
• 右シフト（c = a >> b）
• （すべての整数は符号付きなので、これは問題です）
• 符号付きシフト（c = a >>> b）
• 1の補数（a = 〜b ）
• （すでに解決策が見つかりました。以下を参照してください）

通常、問題はその逆です。ビット単位のハックを使用して算術最適化を実現する方法。ただし、この場合はそうではありません。

このアーキテクチャでは書き込み可能なメモリが非常に少ないため、ビット単位の演算が必要です。ビット単位の関数自体は、多くの一時変数を使用するべきではありません。ただし、一定の読み取り専用データと命令メモリは豊富です。ここでの注意点は、ジャンプとブランチは高価ではなく、すべてのデータが簡単にキャッシュされることです。ジャンプのコストは、算術（ロード/ストアを含む）命令の半分のサイクルです。つまり、上記でサポートされているすべての関数は、1回のジャンプの2倍のサイクルのコストがかかります。

役立つかもしれないいくつかの考え：

次のコードで1の補数（ビットを否定）を実行できることがわかりました。

また、2の累乗で除算するときの古いシフトハックを覚えているので、ビット単位のシフトは次のように表すことができます。

残りのビット演算については、私は少し無知です。このアーキテクチャのアーキテクトがビット演算を提供してくれればよかったのにと思います。

また、メモリデータテーブルを使用せずに（シフト操作の場合）2の累乗を計算する高速で簡単な方法があるかどうかも知りたいです。素朴な解決策は、掛け算の分野に飛び込むことです：

またはセット＆ジャンプアプローチ：

浮かんだ質問があります。これは基本的なSQL用語で設定されていますが、その性質は純粋数学です（したがって、https：//mathoverflow.netにもアクセスする必要があります）。

いくつかの理論データベースに6つのフィールドを持つテーブルがあり、すべて数値です。また、Field_1> Field_5、Field_4 = 3などの基本的な条件があり、合計7つの条件があります。少なくとも4つを満たすselectを作成する必要があります。

（cond_1 AND cond_2 AND cond_3 and cond_4）OR（...）などの多くの論理条件でlong selectを書き込むことは、7つの要素からの4つの組み合わせが140に等しいため、方法ではありません。多くの条件。

では、どのようにすればその簡略化された形式でselectを書くことができますか？

これは私が長い間頭を悩ませてきた問題なので、どんな助けでも素晴らしいでしょう。次の形式の複数の行を含むファイルがあります（単語、単語が出現した時間、および特定のインスタンス内の特定の単語を含むドキュメントの頻度）。以下は、inputfileがどのように見えるかの例です。

以下にPythonクラスがあり、キーとして使用し、値として頻度を使用して上記のファイルを格納するための2次元辞書を作成するために使用しました。

私が持っている質問は、この2D辞書のエントリを反復処理しながら特定のものを計算することに関するものです。各時間「t」での各単語「w」について、以下を計算します。

1. 時間「t」内 の単語「w」を含むドキュメントの数。（a）
2. 時間「t」内に 単語「w」がないドキュメントの数。（b）
3. 時間「t」以外 の単語「w」を含むドキュメントの数。（c）
4. 時間't'以外 の単語'w'のないドキュメントの数。（d）

上記の各項目は、各単語と時間のカイ2乗分割表のセルの1つを表しています。これらすべてを単一のループ内で計算できますか、それとも一度に1つずつ実行する必要がありますか？

理想的には、出力を以下のようにしたいと思います。ここで、a、b、c、dは、上記で計算されたすべての項目です。

上記の入力ファイルの場合、時間「1」で単語「apple」の分割表を見つけようとした結果は、になります(3,2,1,6)。各セルの計算方法を説明します。

• 「3」ドキュメントには、時間「1」内に「apple」が含まれています。
• 時間「1」内に「apple」を含まない「2」ドキュメントがあります。
• 時間「1」の外に「apple」を含む「1」ドキュメントがあります。
• 「apple」（1 + 4 + 1）という単語を含まない「1」以外の6つのドキュメントがあります。

私はこのようなものに減らすことができる手元に問題があります:

2 次元平面 XY に多数のランダムな点があり、Y ごとに X に複数の点があり、X ごとに Y に複数の点があるとします。

点 (Xi,Yi) が選択されるときはいつでも、X = Xi または Y = Yi を持つ他の点を選択することはできません。ポイントの最大数を選択する必要があります。

北の場合は0、北北西の場合は15までの整数値（列挙型）を使用して風向を表しています。

与えられた風向（0から15の間の整数値）が特定の範囲内にあるかどうかを確認する必要があります。許容風向の範囲を指定するために、WindDirectionFrom最初に時計回りに移動する値を指定します。WindDirectionTo

明らかに、WindDirectionFrom=0and WindDirectionTo=4（N方向とE方向の間）で風向がNE（2）の場合、計算は単純です。

ただし、たとえばWindDirectionFrom=15、WindDirectionTo=4風向が再びNE（2）である別のケースでは、計算はすぐに中断されます...

これはそれほど難しいことではないと確信していますが、私はこれで本当の精神的なブロックを持っています。

次の関数を使用して、整数の底 2 の対数を計算します。

最適なパフォーマンスが得られますか?

誰かがその目的のために準備ができているJ2SE API関数を知っていますか?

UPD1 驚いたことに、浮動小数点演算は整数演算よりも高速に見えます。

UPD2 コメントがあったため、より詳細な調査を行います。

UPD3 私の整数算術関数は、Math.log(n)/Math.log(2) よりも 10 倍高速です。

質問が言っていることとほぼ同じです。私は思いついた

もっと読みやすいものはありますか？それともこれは間違っていますか？コードに！〜/ bbb /を入れることができるのに、正規表現でこのようなことを実際に行うべきではないことはわかっていますが、これは理論上の演習です。

ありがとう。

明確化のための編集：正規|表現のORビットを表すために使用しておらず+、代わりに使用しています。混乱させて申し訳ありません。

編集2：{a,b}「a」と「b」の文字だけの言語用です。{最小、最大}ではありません。またすみません。

編集3：これは理論クラスの一部であるため、正規表現の基本を扱っているだけです。使用が許可されているのは、+、？、（）、および*のみです。{最小、最大）は使用できません。