問題タブ [non-deterministic]

I have a project that I have been working on for a few days and I finally got it to compile cleanly. However, a git clone of the same remote branch (on the same machine, compiled in the same terminal instance) caused a compilation error. A fresh clone on a different machine had the same error. I figured it was an issue with my working directory having some additional untracked files, but I deleted all untracked files to the point where diff says the directories are identical except for things contained in the .git folder. I even checked permissions with tree and compared the resulting files with meld - they were basically identical, although a few source files had slightly different execution permissions.

The error was one that came from a file which I had excluded in the maven-compiler-plugin. This should essentially mean that the filename is never passed to javac, although I don't know exactly how it works under the hood. I realize that clearly the compiler is getting the file from somewhere if it is erroring on code inside it. In the one directory on my computer which worked, there are no errors and it compiles perfectly. On the other clones of the repo (which are, again, identical according to diff) it gives an error on this (excluded) file.

Additional experimentation showed that on a fresh git clone of the remote branch, a cp -R of the local directory, or a git clone of the local directory, compile failed. However, if I did a cp with the --archive option, the compile in the resulting directory succeeded. I narrowed it down to the --preserve=timestamps flag (which is enabled due to the fact that --archive is the same as -dR --preserve=all). If you didn't quite catch that, I'll say it again.

When I copy the directory normally, it refuses to compile properly. Only when the timestamps are preserved does it behave identically to the original directory.

I don't understand this - why does the java compiler (or maven) care about the timestamps?

これは、クロスプラットフォームの一貫性と浮動小数点演算の決定論に関する質問です (IE は、異なる CPU/システムで異なる結果を生成します)

クロスプラットフォームの一貫性を維持する可能性が高いのはどれですか (疑似コード):

また

プラットフォームは C# と AS3 です。

.

AS3 バージョン:

-わかりました、説明のために AS3 バージョンを追加しました。これは、上記の「C 疑似コード」と同等です。AS3 でわかるように、すべての計算は、整数であっても、自動的に Float として実行されます。キャストは必要ありません (また、キャストを回避したり、ランタイムに真の整数除算を実行させたりすることもできません)。フロートに: 私は違います! これは、ターゲット言語の 1 つで起こることです。

ウィキペディアのGLRの説明によると、「非決定論的で曖昧な文法を処理します」。ぶら下がっているelse問題 のように、あいまいな文法を視覚化することはできますが、あいまいではない非決定論的なCF文法とは何ですか？

非決定性チューリングマシンの概念がわかりません。非決定性アルゴリズムという用語を理解していると思います:(非決定性アルゴリズムは、決定論的アルゴリズムとは対照的に、さまざまな実行でさまざまな動作を示すことができるアルゴリズムです）。したがって、アルゴリズムは次のようになります。

しかし、私が読んだ非決定性チューリングマシンの場合、一度に複数の状態になる可能性があります。また、ウィキペディアの記事は、 「非決定性チューリングマシン（NTM）には、特定の状況に対して複数のアクションを規定する一連のルールがある場合がある」と示唆しています。

どういう意味ですか ？..特定の状況に対する複数のアクション...複数の状態...私は単にこれを理解していません。

こんにちは私は問題の同じ入力で異なる解決策が必要なので、非決定論的制約充足問題ツールが必要です。誰かがこの特徴を持つツールについて知っていますか？

私は、Gecode（c ++）、Choco（Java）、Curry（Haskell）のような、決定論的な方法で機能すると思うツールしか知りません。

Haskellで非決定論的な状態モナドを構築したいと思います。これにより、ビルドアップ状態を使用して検索スペース内のすべての要素を生成し、不良な場所を取り除くことができます。次の（擬似）コードがあるとします。

ここで機能しないことがいくつかあります。私が理解する必要がある最も基本的なことは、何かを述べてから、それを各expandブランチにパイプする方法です。型の関数を使ってさまざまな方法を試しましたState Int [ State Int Element]が、最終的には、リストモナドのブランチを状態ラッパーでラップすると、削除できなくなります。それで、これを行う方法はありますか？

ありがとう。

私は、Haskellで非決定論的なモナド変換子を構築したいと思います。これは、ListTやhttp://www.haskell.org/haskellwiki/ListT_done_rightで提案されている代替のListTとは異なる動作をすると思います。これらの最初のものは、モナドをアイテムのリストに関連付けます。2つ目は、モナドを個々のアイテムに関連付けますが、特定の要素のモナドアクションが、リストの後続のスロットのモナド要素に影響を与えるというプロパティを持っています。目標は、次の形式のモナド変換子を作成することです。

リストのすべての要素に独自のモナドが関連付けられ、連続する要素には独立したモナドが関連付けられます。この投稿の最後に、このモナドが与えるべき動作の種類について少し説明します。この動作を実現するためにListTのバリアントを取得する方法を知っている場合は、それも役立ちます。

以下は私の試みです。unpack関数が定義されていないため、不完全です。どうすれば定義できますか？Emptyこれを定義するための不完全な試みが1つありますが、モナドmにAmbリストが含まれている場合は処理されません。

完全な（不完全な）コード：

望ましい動作の例

ここで、ベースモナドはState Int

ありがとう。

更新：LogicTが私が望むことを行わない理由の例。

上記の簡単な例でLogicTが行うことは次のとおりです。

Java で遺伝的アルゴリズムを作成しました。これは、複数のアプリケーションに追加できるライブラリの形式です。開発中に、機能テストとなる (jUnit) テストをいくつか作成しましたが、アルゴリズムが非決定論的であるため、それらにはアサートがありません。そのため、これらは自動テストには適していません。また、後で実行したときに、ソリューションを確認するために時間を費やさなければなりません。

ソリューションは車両ルートであり、XLS 形式で出力でき、実際のテストは必要なときに行われるため、その瞬間に何を探すべきかがわかります。それらには距離値と時間値があり、すべての例とルート自体に妥当な値があり、特定のジグザグがあってはなりませんが、ジグザグが必要な場合もあります。

値がその妥当な範囲内にあると断言できますが、これらは明確ではなく、悪い解決策を残していないと確信できません。人々が何をしているのか、またはこの問題についてどう思うかを知ることは素晴らしいことです.

編集: 目標を明確にするには:

• 単体テストはかなり解決されています。さまざまな関数のロジック コードから乱数生成コードを分離することができ、テスト コードから非乱数を渡すロジック関数をテストします。
• Cucumber または Selenium テストのように、偽のデータを使用せずにいくつかの機能テストを実行したいと考えています。実数出力を生成する実数入力。(Cucumber や Selenium を具体的に使いたいと言っているのではなく、私が求めているのは単体テストではなく、アルゴリズムの動作は本物でなければならず、決して偽造されてはならないということだけです)

ライブラリはさまざまなプロジェクトで使用され、すべてのプロジェクトの入力データは同じモデルに従いますが、さまざまな方法で偏っています。あるプロジェクト データでは、同じポイントが何度も繰り返される場合がありますが、別のプロジェクトではそうではありません。制限容量に非常に速く到達する車両がある場合もあれば、この制限にほとんど到達しない場合もあります。

目標は、挿入されたすべてのプロジェクトからサンプル データを取得して、アルゴリズムの変更中にアルゴリズムの動作をすばやくフィードバックすることです (突然変異またはクロスオーバー オペレーターの変更または追加、新しいパラメーター化の追加など)。したがって、その動作は決して偽造されてはなりません。

これらすべてを考慮して、私が尋ねる問題は、動作全体を効果的に主張する方法を見つけることです。他の人がこの問題にどのように対処したか、またはそれについて何を言うことができるかを尋ねたかった.

1テープの決定性マシン、2テープの決定性マシン、1テープの非決定性マシンの、3つのケースで繰り返し文字列（ww）を受け入れるチューリングマシンの時間計算量を把握しようとしています。

今の私の考えはそれです

• 1テープの決定論的マシンは、O（n ^ 2）を使用して中点を見つけ（入力の最初と最後の記号を繰り返し消して）、O（n ^ 2）を使用して前半と秒の半分を比較します（必要に応じて）文字列のn/2を通過するたびに、n / 2回前後に移動します）、

• 2テープTMは、中点を見つけるためにO（n ^ 2）を取り、後半を2番目のテープにコピーするためにO（n）を取り、次に2つの半分を同時に比較するためにO（n）を取ります。

• 非決定論的なものは中点を推測し、O（n ^ 2）を使用して2つの半分を比較します。

しかし、3つのケースすべてがO（n ^ 2）の同じ時間計算量を持つべきではないように感じるので、私の推論がどこかで間違っているのか（または私が正しいのか、問題についてよく考えているだけなのか）疑問に思いました。任意の入力をいただければ幸いです！

私は.NETの浮動小数点決定論について多くのことを読んでいます。つまり、同じ入力を持つ同じコードが異なるマシン間で同じ結果をもたらすことを保証します。.NETにはJavaのfpstrictやMSVCのfp：strictなどのオプションがないため、純粋なマネージコードを使用してこの問題を回避する方法はないというのがコンセンサスのようです。C＃ゲームのAI Warsは、代わりに固定小数点演算を使用することに決めましたが、これは面倒な解決策です。

主な問題は、CLRにより、中間結果がタイプのネイティブ精度よりも高い精度のFPUレジスタに存在できるようになり、予想外に高い精度の結果が得られることです。CLRエンジニアのDavidNotarioによるMSDNの記事では、次のように説明しています。

現在の仕様では、「予測可能性」を与えることは依然として言語の選択であることに注意してください。言語は、すべてのFP操作の後にconv.r4またはconv.r8命令を挿入して、「予測可能な」動作を取得する場合があります。 明らかに、これは本当に高価であり、言語が異なれば妥協点も異なります。たとえば、C＃は何もしません。絞り込みが必要な場合は、（フロート）キャストと（ダブル）キャストを手動で挿入する必要があります。

これは、浮動小数点と評価されるすべての式と部分式に明示的なキャストを挿入するだけで、浮動小数点の決定論を実現できることを示しています。このタスクを自動化するために、floatの周りにラッパータイプを書くかもしれません。これはシンプルで理想的なソリューションです！

しかし、他のコメントは、それがそれほど単純ではないことを示唆しています。Eric Lippertは最近述べました（私の強調）：

ランタイムの一部のバージョンでは、floatにキャストすると、明示的にキャストしない場合とは異なる結果が得られます。明示的にfloatにキャストすると、C＃コンパイラはランタイムに「この最適化を使用している場合は、これを超高精度モードから外してください」というヒントを提供します。

ランタイムへのこの「ヒント」は何ですか？C＃仕様では、floatへの明示的なキャストにより、ILにconv.r4が挿入されると規定されていますか？CLR仕様では、conv.r4命令によって値がネイティブサイズに絞り込まれることが規定されていますか？これらの両方が当てはまる場合にのみ、David Notarioによって説明されているように、浮動小数点の「予測可能性」を提供するために明示的なキャストに依存できます。

最後に、実際にすべての中間結果をタイプのネイティブサイズに強制できる場合でも、これはマシン間の再現性を保証するのに十分ですか、それともFPU / SSEランタイム設定などの他の要因がありますか？