問題タブ [computer-science-theory]

ラムダ計算について読んでいます。セクション 2.1 の最後からhttp://www.toves.org/books/lambda/ :

それは言う

ただし、実際には、y は 5 ではなく 3 の値を取得する必要があります。これは、最初のベータ還元で 1 が式の x の位置に差し込まれるためです。このため、遅延パラメーターは、各リダクションで現在の変数コンテキストを保持する必要があります。この場合、式 λy.x × y 内では x = 3 ですが、式の外では x = 1 であるという事実を維持します。

しかし、ベータ削減中の操作の順序について混乱しています。残念ながら、説明があいまいです。x は (λx.λy.x × y) 内で 1 である必要があり、次に y = 3 を渡す必要があることを意味する可能性があります。これは、次に渡されるパラメーターであり、x が既に設定されている (間違っていると感じます)、または以下のルートに進むことを意味します。 :

(λx.(λx.λy.x × y) 3 ((λz.x + z) 2)) 1
は (λx.(λt.λy.t × y) 3 ((λz. x + z) 2)) 1

x はここで境界ですか? 1でいいんじゃない？

つまり、これを減らすと、 (λt.λy.t × y) 3 ((λz.1 + z) 2)) x = 1 (λy.3 × y) ((λz.1 + z) 2)) x = 1、t = 3 3 × ((λz.1 + z) 2)) x = 1、t = 3、y = ((λz.1 + z) 2)) 3 × ((λz.1 + z) 2)) x = 1、t = 3、y = ((λz.1 + z) 2))、z = 2 3 × (1 + 2) x = 1、t = 3、y = ((λz.1 + z) 2)), z = 2 3 x 3 = 9

あれは正しいですか？それとも、間違って減らしましたか？

アルゴリズムが次の場合、計算の複雑さはどのように定義されますか?

• ...多くの結果が得られますか? 合計として（その場合、セットを生成するアルゴリズムはO(k)kよりも高速になることはできません）、または要素ごとに（推定値を乗算して、セットを生成しないアルゴリズムと比較する必要があります）？
  • ストレージの複雑さについてはどうですか? セット全体を一度にメモリに存在させる必要があるのか​​、それとも連続する各要素を生成して破棄できるのか、見積もりに反映されますか?
• ...複数のパラメータがありますか? パラメータごとに個別の数値か、それとも何かを組み合わせたものか?

両方のケースに適した例は、kからの要素の選択Nです。例えば、工程が必要かどう~kかで見積もりに違いはありますか？~N

これらの場合の用語の正式な定義、および/または単なるランダムな考えや個人的な経験ではなく、CS論文でこれらのあいまいさがどのように排除されているかなど、いくつかの確固たる証拠を見たいと思います. 目標は、完全で最先端の解決策を見つけて、私の (および他の) テキストからこれらのあいまいさを完全になくすことです。

_{これについて私が困惑した質問は次のとおりです。O(1) の一意の (繰り返さない) 乱数? , 0 と上限 N の間の K 個の非反復整数のリストを効率的に生成するにはどうすればよいですか? 単一のランダムな値の組み合わせを選択するアルゴリズム? 、リンクされたリストから一連のランダムな要素を効率的に選択します。}

2 つの配列があるとします。

両方の配列で前x, yの条件を満たす要素の数を数えます。xy

これまでの進捗状況:

配列をインデックスで並べ替えます。例では、これは次のようになります。

各タプルを別のタプルと比較します。タプルのa両方のインデックスがタプルより低いか高い場合b、条件を満たす要素の数を増やします。

これには (N^2)/2 の時間の複雑さがあるため、O(N^2) となり、遅すぎます。最悪のシナリオの複雑さがこれ以上ないことは理解していますが、主に平均的な結果に関心があります。だから：より良い方法/アルゴリズムはありますか？

私は推移的なプロパティを使用することを考えました（両方が条件(x,y)を満たしている場合は、それも満たしています）が、うまくいきませんでした。(y,z)(x,z)

テストケース

配列の場合:

条件を満たすペアは次のとおりです。

配列の場合:

条件を満たすペアは次のとおりです。

AND、OR、NOT の 3 つの論理ゲートが機能的に完全であることに気付きました。これは、これら 3 つのゲートだけで真のテーブルを表すことができることを意味します。

では、これらの 3 つのゲートだけで計算可能な関数を表現できるかどうかを知りたいですか?

私は今、この問題に遭遇しました : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3155与えられたデータは、最初の n (ランダムにリストされた 1 から n) の自然数のシャッフルされた順序です。

だから、私はそれを考えました：

1. 可能なスワップの最大数 = n(n-1)/2。(降順の場合)
2. 可能なスワップの最小数 = 0。(昇順の場合)

したがって、この分布の最頻値は (0+n(n-1)/2)/2 =n(n-1)/4 です。しかし、これが答えであることが判明しました。モードが平均と一致した理由がわかりません。