問題タブ [computation-theory]

私は最近、テキストの断片で最適な一致を見つけるプログラムを作成するように依頼されました。私はこのプログラムをうまく書きましたが、その時間の複雑さについて質問があります。

問題は次のように定義されます。

クエリが与えられた場合、ドキュメント内のクエリ ワードの出現箇所を見つけて、最適なトークンを強調表示します。

私のプログラムにかかる時間

O(m + n + p)

ここ

m = ドキュメントの長さ (文字数)

n = クエリの長​​さ (文字数)

p = ドキュメント内の一致の合計数

この場合、最大の用語は常に「m」になります。ほとんどの場合、ドキュメントはクエリ自体よりも大きくなるためです。

私のプログラムの時間計算量は O(m) であると安全に推測できますか?

重複の可能性:
浮動小数点値の比較 浮動小数点値
を比較するのはどれほど危険ですか?

プログラミングで実数の比較が悪い習慣である理由がわかりません。もちろん、実数はある程度の精度で表現できることは理解しています。この種の数字を比較してはいけない重大な理由を教えていただけますか? 例は良いでしょう、記事も大歓迎です。事前に感謝します。

計算コースのモデルで得た HW に関するいくつかの質問についてサポートが必要です。テキストの関連する章 (Michael Sipser の計算理論入門) を読みましたが、これらのハードウェアに関する質問には、この本では得られなかった知識が必要であると感じています... 最初の質問は次のとおりです。

(1) L* = {a}* {b}* となるような言語 L が存在しないことを証明せよ。

明らかに右側は正規表現です。0 個以上の a の後に 0 個以上の b が続きます。これは、空の文字列イプシロンの場合もあります。

問題は L* で発生します。言語に適用された * が何をするのか、または言語 L の * のためにこの方程式をどのように処理するのか、まったくわかりません。

この質問に対するヘルプまたはリソースをいただければ幸いです。

=====

2番目の質問は簡単で、ほとんどできる気がします。私はそれを自分自身に正当化できるので、問題はそれを正式に書くことだと思います。2番目の質問はこれです：

(2) A と V が同じアルファベット (シグマ) の言語であり、A (が B の部分集合) である場合、A* (は B* の部分集合) であることを証明してください。ヒントは、誘導を使用することです。

明らかに (たとえば) sigma = {1, 0} の場合

および A = {00, 01, 10, 11}

B = {00, 01, 10, 11, 100, 101, 110, 111}

次に、B = A + 他のものがあるため、A * 内のすべてが B * の下で閉じられます...誰かがこれを帰納的な形式に形式化するのを手伝ってくれれば、私はそれを感謝します。

ありがとう

スイスチーズの立方体の形を想像してみてください。20x20x20グリッドでチーズをモデル化します。簡単にするために、各グリッドキューブは完全にチーズまたは完全に空気で構成されていると仮定します。次に、スイスチーズの立方体の上側に水を注ぎます。水は、立方体の空気穴からのみチーズに浸透します。水は上から下へと連続したチャネルを通って流れる可能性がありますが、2つの立方体が（エッジやコーナーだけでなく）面を介して接続されている場合、1つのエアキューブから次のエアキューブにのみ流れる可能性があります。水はシンクドレントラップなどの迂回路でも流れることができますが、チーズキューブの側壁には流れ出ない場合があります。

ここで、上記のように空気とチーズキューブのランダムな分布を使用して、チーズpの確率と空気1-pの確率を使用して、スイスチーズのモデルをプログラムで実装し、チーズを流れる水をシミュレートして調べます。 、水がスイスチーズキューブの底に流れるかどうか。

チーズと空気の確率が異なるスイスのチーズキューブを流れる水を繰り返しシミュレートすることで、pとスイスのチーズキューブの底に流れる水の確率との関係を確認できます。名前をqとしましょう。結果は次のようになります。

私の質問：なぜそのような奇妙な曲線ですか？

この質問は、ドイツで開催された第23回連邦情報学コンクール（2004/2005）から引用したものです。「なぜそのような奇妙な曲線なのか」に対する答えはウェブ上で提供されていません（解決策が提供されています）。

私はこの種の質問で正しい場所にいることを願っています。

正規表現のようなものを使用して文字列内のパターンを見つけるツールを構築しようとしています (テキスト文字列ではありませんが、現時点では重要ではありません)。私はオートマトン理論に精通しています。つまり、基本的な正規表現マッチングを実装する方法を知っており、文字列が正規表現と一致する場合は、教科書の方法でオートマトンをシミュレートすることにより、true または false を出力します。

as の前に来るすべての s に興味があるとします。sの前にbs はもうありません。しかし、文字列にそのような部分が含まれているかどうかを確認したいだけではなく、出力として を取得して、それを検査できるようにしたい (実際にテキストを扱っているわけではないことを思い出してください)。aba[^a]*ba

a要約すると、次のように括弧でマークを付け(a)[^a]*bて、入力文字列で実行するとbcadacb、2番目の文字列が出力として必要になるとしましょうa。

または、より一般的には、入力文字列のどの文字が正規表現のどの部分に一致するかを見つけることができますか? テキストエディタではどのように行われますか? 一致を強調表示できるため、少なくとも一致が開始された場所がわかります。バックトラッキング アプローチを使用する必要がありますか? それとも、よりスマートで計算コストの低い方法がありますか?

編集: 適切な後方参照、つまり、括弧でキャプチャして \1 で参照するなどは必要ない場合があります。私は、後方参照がバックトラッキング (または同様のもの) の必要性を導入し、問題 (IIRC) を NP 困難にすることを知っています。私の質問は、本質的には次のとおりです。後方参照なしのキャプチャ部分は、適切な後方参照よりも計算コストが低くなりますか?

計算モデルが同等であることをどのように証明できるかについての説明を求めています。同等性の証明が省略されていることを除いて、私はこの主題に関する本を読んでいます。2つの計算モデルが同等であるとはどういう意味かについての基本的な考え方があります（オートマトンビュー：同じ言語を受け入れる場合）。同等性について他の考え方はありますか？チューリングマシンモデルがラムダ計算と同等であることを証明する方法を理解するのを手伝っていただければ、それで十分です。

C++ テンプレートは turing-completeであり、CSS は turing-complete (!) であり、C# のオーバーロードの解決は(ジェネリックがなくても) NP 困難であるというよく知られた事実があります。

しかし、C# 4.0 (co/contravariance、generics など)のコンパイル時のチューリングは完了していますか?

内部データ構造としてバイナリ ヒープを使用するプライオリティ キューを研究しています。ブロック サイズ M の外部メモリ モデルを考慮すると、スライドでは、deleteMin にはほぼ2log(n/M)ブロック アクセスが必要であると主張しています。

どうしてこれなの？ボトムアップ ヒューリスティック (Wegener 93) を記述した元の論文にも、スライドにも説明が見つかりませんでした。

最初のブロックには、ルートとヒープの最初の log(M) レベルが含まれます。その後、ノードごとに、レベルごとに 1 つのブロックを読み取る必要があります。これには、2 つの連続する子ノードが含まれます。ノードの両方の子を取得するために 2 つのブロックを読み取る必要があるのは、ごくまれなケースです (したがって「概算」)。最初のログ (M) レベルは 1 回のブロック アクセスで読み取られるため、最低(log n - log M) = log n/Mレベルのブロックをロードするだけで済みます。

はどこ2から来たのですか？キャッシュの削除時にブロックをディスクに書き戻す必要がありますが、それは通常、負荷で説明されていませんか?

質問を十分に説明できたことを願っています。どうもありがとう！

Big-Theta に関する情報をあちこち探しましたが、十分に理解できたと思います。ただし、疑問が残ります。予想される入力サイズが小さい場合、Big Theta Notation はアルゴリズム効率の効率的な尺度でしょうか?

予想される入力サイズが小さい場合、Big Theta Notation はアルゴリズム効率の効率的な尺度ではないと考えています。まず、Big Theta についての私の理解の一部を次に示します。関数 f(n) は、O(n) と Big Omega(n) の場合、Big Theta(n) です。これらすべての値の数学的定義には、n>n0 が必要です。したがって、私の推論によれば、小さな入力サイズが n0 未満になる可能性があります (そして可能性が高いです)。したがって、私の推論は、Big Theta Notation は、n< n0 の値のアルゴリズム効率の効率的な尺度ではないということです。

ウィキペディアによると、概念NP、NP 完全、およびNP ハードを理解しようとしています。

与えられたテキストを正しく理解している場合:

編集：デビッドに従って修正

NP == 答えが多項式時間で検証できる決定問題 (解が与えられた場合)

NP完了== NPとNPハードを同時に

NP ハード==多項式時間チューリングで還元可能なNP 完全問題があります。

ですから、NP完全性の概念を理解するためには、まずNP硬度を理解する必要があります。そこで、上記のステートメントに従ってNP ハードとは何かを分析してみます。だから私は得る：

NP ハード== NP ハードである と同時にNPである問題があり、それに還元できます。しかし、定義には循環があります。非循環的定義とは何ですか?