問題タブ [transitivity]

15都市のリストがあります。可能な 15*14/2=105 組の都市から 70 組を無作為に抽出します。70 組のそれぞれについて、参加者に都市 A が都市 B よりも大きいかどうかを判断してもらいます。重要なことは、参加者が「間違い」を犯して、以前の回答と矛盾する回答をすることがあることです。(つまり、推移性に違反しています)。

推移性に違反する試行の数を最小限に抑える方法で、各参加者の応答に基づいて都市を並べ替える方法が必要です。

一意の解決策がない可能性があるため、都市の実際の順序は必要ありません。各参加者によって与えられた自動詞の回答の (最小) 数を計算する必要があるだけです。

徹底的な検索を使用する以外に、どうすればこれを行うことができますか?

編集: 例として、都市 A、B、C、D、および E を取り上げます。参加者のジョン ドウは、都市の正しい順序 (最小から最大) は ABCDE であると考えています。私は、彼が実際に正しいかどうかは気にしません。ただ、彼の反応 (以下にリストされています) が彼の信念とどれだけ一致しているかだけに関心があります。

3 回の独立した裁判で、ジョンは次のように答えました。

試行 1: A < B

試行 2: B < C (+)

試行 3: C < D

試行 4: D < E (+)

試行 5: E > B (*)

したがって、試行 5 の回答 (*) は、試行 2 および 4 の回答と矛盾します。1 つの試行 (番号 5) がジョンの信念と一致しなかったか、2 つの試行 (2 と 4) が一致しませんでした。どちらがジョンの信念 (ABCDE) であったかはわかりませんが、ジョン・ドウの「自動詞の最小数」が 1 であることを知る必要があるだけです。

依存しているプロジェクト (compile("foobar")) から推移的な依存関係のみを取得し、他のすべての推移性を無効にするように hibernate を構成することは可能ですか? それが私がこれまでに試したことです：

そうはいきません。推移的な依存関係はまったくプルされません。

提案されたように1を更新

ただし、foobar からの依存関係は考慮されません。

更新 2

次の解決策は今私のために働きます：

以下の CTL 式が同等であるかどうか疑問に思っています。同等である場合は、同等であると自分自身に納得させるのを手伝ってもらえますか? A(p U ( A(q U r) )) = A(A(p U q) U r)

私はそれと矛盾するモデルを思いつくことができず、私の直感は式が同等であると言っていますが、そのステートメントをサポートする同等物を見つけることができません. 等価性 A(p U q) == not(E ((not q) U not(p or q)) または EG (not q)) を何か役に立つものに書き直そうとしましたが、何度か失敗しました。

コースの資料とグーグルを調べましたが、何も見つかりません。ただし、同じ同等の質問がありますが、回答がない別の質問をここで見つけたので、もう一度試してみます。

私は最近、メモリバリアの cpu の推移性を読みましたが、著者は、一般的なバリアのみが推移性を保証できると強調しています。でも、よくわかりません。例えば：

X が CPU3 のキャッシュでステータスが変更され、Y が CPU2 のキャッシュでステータスも変更されたとします。

読み取りバリアの前に書き込みバリアを追加すると、CPU1 はそのストア バッファを CPU2 と共有します。（一般バリアとなります）

1) CPU1 はストアバッファに X(X=1) の値を設定します。

2) CPU2 は、ストア バッファ (共有ストア バッファ) から X の値を読み取ります。

3) CPU2 はストア バッファ (書き込みバリア) で X をマークし、無効化キューを読み取り、CPU3 からの無効化メッセージがないことを確認します (読み取りバリア)。

4) CPU2 は、X のキャッシュ ラインを無効から変更済みに変更したいので、無効化メッセージを CPU3 に送信します。

5) CPU3 は X の無効化メッセージを受信し、無効化キューに入れ、CPU2 に応答します。

6) CPU2 は応答を受信し、X = 1 をメモリまたはキャッシュに書き込み、Y == 0 をロードします。

...

7) CPU3 は、ジェネラル バリアを実行すると、無効化されたキューに X の無効化メッセージがあることを検出します。その後、X は 1 に等しくなければなりません。

わかります。ただし、perbook の図 14.3 から別の例を読みました。

アサートを発射する機会がいくつかあります。Quick Quiz 14.2 の回答で、すべてのバリアを smp_mb に変更すると修正できると著者は述べています。

では、私の質問は、なぜスレッド 1 のバリアを smp_mb に変更する必要があるのですか? スレッド 0 とスレッド 1 が CPU0 と CPU1 で実行され、それらがストア バッファを共有している場合です。スレッド 1 が Store C = 1 を実行した後、それらのストア バッファは吹き飛ばされます。

[A(wb)、B、C]

スレッド 2 (CPU2 で実行) もバリアの代わりに smp_mb を使用するため、C == 1 が表示される場合、A が 1 でなければならないことが保証されます。

上記のすべてを MESI メモリ コヒーレンシ プロトコルで説明します。作者は、CPU の推移性を保証するために、smp_mb の代わりにスレッド 1 にバリアを作成する別のプロトコルがあることを意味するのでしょうか?

誰か私に例を教えてください。

特定のプロトコルでの推移性について考えるのは間違いかもしれません。覚えておかなければならないことは、非常に多くの異なるプロトコルとアーキテクチャーがあるため、rmb() または wmb() は CPU の推移性を保証できないということです。