問題タブ [computation-theory]

私は興味深い理論的問題に来ました：

プログラム A とプログラム B が tcp ソケットや名前付きパイプなどの IPC を介して接続されているとします。プログラム A はプログラム B にデータを送信し、データ配信の成功に応じて、A と B の両方が何らかの操作を行います。ただし、B は、A が配達確認を取得したことが確実な場合にのみ、その操作を行う必要があります。A→B【データ転送】B→A【配達確認】A→B【配達確認の確認】

奇妙に見えるかもしれませんが、目標は、データが転送されたことを両側が知るまで、A にも B にも操作を行わないことです。

そして、ここに問題があります。これは、2 番目の接続が最初の接続の成功を確認するためのものだからです。そして 3 番目は 2 番目の確認ですが、実際には接続 2 と 3 が失敗しないという保証はなく、その場合は確認の無限ループに陥ります。その問題を解決するCS理論はありますか？

2 つの要素間の推移的な関係を特定しようとしています。c でコーディングしています。

例: a->b は、1 行 2 列の隣接行列の "1" で表されます。

したがって、a->b および b-> c および c->d の場合

a->d かどうかを特定したい。隣接行列を更新する必要はありません。

私が採用したアプローチ：aに対応する行のすべての1をチェックしてください。2列目、つまりbに1があるとしましょう。[(a->b)] 、b->d かどうかをチェックし、そうでない場合は B の行のすべての 1 をチェックし、26 行目まで続けます。

複雑さにはあまり関心がありません。私はこれを実装することを望んでいます。

以下の言語の左線形および右線形の文法を構築するのに助けが必要ですか？

a）私は以下を持っています：

これは正しいです？b＆cのサポートが必要です。

私はこの文法を持っています

S+S本当に混乱しているので、この文法から左再帰を排除する方法を知りたいです...

文脈依存の文法を理解しようとしていて、言語が

1. {ww | w は文字列です}
2. {a ⁿ b ⁿ c ⁿ | a、b、cは記号です}

文脈自由ではありませんが、型指定されていないラムダ計算に似た言語が文脈依存であるかどうかを知りたいです。単純だがおもちゃではない例 (上記のおもちゃの例を考えます) の例を見てみたいと思います。たとえば、記号の文字列がは現在スコープ内にあります (たとえば、関数の本体を生成する場合)。文脈依存文法は、未定義/未宣言/未結合の変数を (セマンティックではなく) 構文エラーにするのに十分強力ですか?

これは私が描いたDFAです-

それが正しいか？の規則に違反する同じ入力シンボルに対して状態の遷移が異なる
ため、私は混乱していますが、他の解決策は考えられません。q42DFA

私はチューリング マシンについて多くのことを読み、その仕組みを理解していますが、理解できないこと (そしてどの本も教えようとしないこと) は、与えられた問題にどのようにアプローチすればよいのかということです。つまり、たとえば、単語が回文であるかどうかを確認することは、私が学んでいる本の 11 の状態で構成されています。私の現在の知識では、空の紙の上に座ってこれらすべての状態を思いつくだけでは、控えめに言ってもほとんど不可能に思えます。このようなことをしようとすると、これらの状態を何らかの形で「一緒に」機能させるにはどうすればよいかわからないため、すぐに行き詰まります。プログラミング時にはそのような問題はありませんが、ここでは、n-teen状態で構成されるものにどのようにアプローチすればよいかわかりません。それについて学ぶための方向性を教えてください。

私は明日の試験のために勉強していて、NFA を Regex に変換する方法を説明する多くのチュートリアルをチェックしましたが、自分の答えを確認できないようです。チュートリアルに従って、そのNFAを解決しました

私の解決策は次のとおりです。

あば_

私は正しいですか？

ノードのネットワークがありN、それぞれが一意の ID (公開鍵など) を持ち、中央サーバーのないプロトコル (DHT、Kad など) と通信しているとします。各ノードには変数が格納されますV。簡単な例として電子投票を参照すると、その変数は候補者の名前である可能性があります。

Vここで、ネットワークで使用可能なすべての変数に対して「集計」関数を実行したいと考えています。電子投票の例を参考に、票を数えたいと思います。

私の質問は完全に理論的なものです (質問の最後に声明と詳細を証明する必要があります)。そのため、電子投票とそのすべてのセキュリティ面に焦点を合わせないでください。もう一度言う必要がありますか？「ノードは、より多くのキーを生成することで任意の数のアイデンティティを持つことができる」、「IPを追跡できる」などと答えないでください。それは別の問題だからです。

プライバシーの観点からのみ、分散アグリゲーションを見てみましょう。

質問

一般的なケースでは、ノードが他のノードに保存されている変数の関数を、ノードの ID に関連付けられた値を取得せずに計算することは可能ですか? 研究者は、そのようなプライバシーを意識した分散アルゴリズムを設計しましたか?

一般的なセキュリティではなく、プライバシーの側面のみを扱っています。

現在の考え

私の現在の答えはノーなので、すべての s を取得し、V保存せずに処理する中央サーバーが必要であり、個々のノードのデータが中央サーバーによって保存または再送信されないようにするための技術的手段が必要です。私の前の発言が間違っていることを証明するように求めています:)

電子投票の例では、すべてのノードに 1 つずつ「ねえ、誰に投票しますか?」Aliceと尋ねずに、何人が投票したかを数えることは不可能だと思います。Bob

実際のケース

パーソナル データ ストアの分野で研究を行っています。通話ログを PDS に保存していて、誰かが通話に関する統計値 (つまり、平均時間、1 日あたりの通話数、分散、st-dev) を見つけたいと考えているとします。は、私が誰に電話するか、また私自身の平均通話時間も誰にも知られてはなりません)。

信頼できるブローカーが存在し、誰もがそれを信頼している場合、そのノードは、最初にネットワーク内のすべての PDS で呼び出し、次にすべての行で統計を操作するdouble getMeanCallDuration()API を公開できます。CallRecord[] getCalls()中央の信頼できるブローカーがなければ、公開されている各 PDSdouble getMyMeanCallDuration()は統計的に使用できません (平均値がすべての平均値であってはなりません...)。

(a) 配列の次元と valuecip(int[] v, int n)に従って、メソッドの計算コストを計算します。vn

(b) 前のステップで計算されたコストを、入力のサイズの関数として表します。

これは私の教授が教室で行った演習ですが、私には多くの疑問があります。入力のサイズの関数としてアルゴリズムの計算コストを計算するには、一般的に行う必要がありますか? 入力を設定しましたか？または、提供されているメソッドから入力を取得しますか? 「計算コスト」は「時間に関するコスト」または「空間と時間に関するコスト」を意味しますか?