問題タブ [deterministic]

こんばんは、誰かが決定論的アルゴリズムの簡単な疑似コードの例を教えてくれませんか? ありがとう

ウィキペディアは、決定論的ステート オートメーションは「入力文字列ごとにオートマトンの一意の計算 (または実行) を生成する」と述べています。

一意の文字列を計算するための可能なパスは1つしかないため、これを常に理解していました。その場合、以下は DSM です。

しかし今、私はこれを考え直し、説明を各入力文字列が単一の可能なパスを持ち、そのパスは他のすべての入力文字列から一意であると解釈しています。この場合、'11' と '12' は同じパスをたどるので、以下は DSM ではありません。

私の質問は、次は DSM または NDSM ですか?

私はそのように設定された事実を持っています...

好きな果物が 1 つ以上ある (性別、年齢) のグループがあるかどうかを調べる必要があります (上記の事実に対する答えは (女性、若い) になります)。

私が理解しようとしてきたのは、プロローグでaggregateorfindall関数を使用して、.... のようなある種のリストを返す方法です。

...そうすれば、各メンバーの合計を確認して、それが 1 より大きいかどうかをテストできます。

どんなアイデアでも大歓迎です。

次の遷移図で表される 2 つの決定論的有限状態オートマトンがあるとします。

キーワード IF の FSA: IF

ID の FSA: [AZ][A-Z0-9]*

次の遷移図で表される、3 つの最終状態を持つ単一の決定論的有限状態オートマトンにそれらを結合するために、どのアルゴリズムを使用できますか?

次の関数を使用して浮動小数点数が切り捨てられる、決定論的シミュレーションを構築しようとしています:(ここで見つけました：http： //joshblog.net/2007/01/30/flash-floating-point-number-エラー）

私の質問は、私がそれを10000で割っているという事実自体が、フロートポイントエラーの原因ではないかということです。 IEは、除算が行われるたびに、新しいフロートになり、さらに非決定的な結果が生じる可能性があります。

編集：これはどうですか？2の累乗のみを使用

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

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

また

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

.

AS3 バージョン:

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

32ビットIEEE754浮動小数点を符号付きQ19.12固定小数点形式に変換する必要があります。問題は、完全に決定論的な方法で実行する必要があることです。したがって、通常の（int）（f *（1 << FRACTION_SHIFT））は、非決定論的な浮動小数点演算を使用するため、適切ではありません。「ビットいじり」または同様の決定論的変換方法はありますか？

編集：この場合の決定論は次のように想定されます：同じ浮動小数点データが与えられた場合、異なるプラットフォームでまったく同じ変換結果が得られます。

私はこれを次のテストケースに要約することができましたが、これがC＃コードコントラクトの静的チェッカーの制限なのか、それとも私が見逃しているものなのか疑問に思っています。あるスタイルのコードを使用してコントラクトを証明しようとすると、不変の証明されていない警告がスローされますが、それでも（私が思うに）それを証明する同等の方法は問題なく機能します。

当初、これはPureプロパティを持つオブジェクトを使用していなかったため（したがって、コードコントラクトはプロパティが決定論的であるかどうかを評価できなかったため）、オブジェクトの周りにPureラッパーを作成したためだと思いました（Nullable <Int64>になる可能性があります）助けにはならなかった。

最初のテストケースと3番目のテストケースに違いはありますか、それとも同等であると信じて正しいのでしょうか。静的チェッカーが3番目のケースを正しく評価できないというだけですか。

職場で新しいプラットフォームの設計について話し合っていますが、上級管理職の 1 人が、現在のコード ベース (Linux では C) を実行する必要があるが、さまざまな入力に 1 秒以内に応答する必要があるため、リアルタイムである必要があると述べました。 . 私は次のように指摘しました。

1. その点は、「リアルタイム」である必要があるという意味ではなく、より高速なクロックと割り込み処理の合理化が必要なだけです。
2. 考慮すべき重要なポイントの 1 つは、使用されている OS です。彼らは組み込み Linux に固執したかったので、私は RTOS が必要だと指摘しました。Linux を使用すると、カーネル/ユーザー空間のメモリが分割されるため「リアルタイム」が妨げられるため、I/O はファイルとソケットを介して行われ、遅延が発生します。
3. 本当に決定する必要があるのは、決定論的である必要があるかどうかです (たとえば、90% の時間で 200 ミリ秒未満で入力に応答する必要があります)。

ポイント 3 が当てはまる場合、それはリアルタイム システムである必要があり、ポイント 2 が最大の考慮事項です。

自信を持って答えられたのですが、後で考えていました... 他の人はどう思いますか？私はここで正しい軌道に乗っていますか、それとも何か不足していますか?

「リアルタイム」システムと「決定論的」なシステムの間に見落としている違いはありますか? また、RTC と RTOS 以外に、真のリアルタイム システムを実行するために必要な主要なものがありませんか?

素晴らしい回答をお待ちしております！

編集：

これまでのところ、いくつかの良い反応を得ています。私のシステムと要件について少し好奇心が強いようです。興味のある人のためにいくつかのメモを追加します。

1. 私の会社は数万台のユニットを販売しているので、価格を殺したくありません
2. 通常、メイン プロセッサ ボードと独立したディスプレイを販売しています。他の CAN デバイスのネットワークも接続されています。
3. ボードは (現在) デバイスを実行し、基本的な XML ドキュメントをエンド ユーザーのディスプレイに送信する Web サーバーとしても機能します。

要件は、管理者がディスプレイを「迅速に」(<1 秒) 更新することを望んでいる場合です。ただし、IMO の真の制約は、CAN 経由で接続できるデバイスに由来します。これらのデバイスは、多くの場合、「200ms 未満で応答する必要がある」などの要件を持つモーター制御デバイスです。

1 つがエラー状態のときに、2 つの DFA を結合する方法を考えています。具体的には、最初の DFA は次のとおりです。

2 番目のものはあまり重要ではありませんが、すべての状態で 'a' または 'b' のいずれかを取るため、エラー状態は必要ありません。したがって、状態q3に到達するまでは、製品構成を問題なく使用できます。マシンが (q3,z) (z は 2 番目の DFA からのランダムな状態) にあり、a を読み取るとします。2 番目の DFA は問題なく続行できますが、最初の DFA はエラー状態になり、それ以上の入力を受け付けないようにする必要があります。これはもちろん交差ではなく結合であるため、エラー状態に達するかどうかを確認するために、秒をシミュレートし続ける必要があります。

結合された DFA を構築するときに、これをどのように示すことができますか?