問題タブ [computation-theory]

このDFAを最小化しようとしています：http：//img145.imageshack.us/img145/3006/dfac.png

これが私の最小化されたDFAです：http：//img195.imageshack.us/img195/4131/mdfa.png

私は正しいですか？ありがとう

PS-これは宿題です。宿題について話し合うことができます。私は答えを求めていません。ステートマシンを扱うのはこれが初めてなので、自分が正しい方向に進んでいるかどうかを知りたいだけです。

機械が言語を認識して決定するということの意味を理解するのに苦労しています。私は定義に近いと思いますが、正しくありません。

チューリング マシンTが言語を認識すると言うときL、

ここで、DFA = 決定論的有限オートマトン

私の理解では、これは、あらゆる種類の入力 (文字列、車、人など) が与えられたときに、入力として与えたものが DFA であるかどうかを判断できるチューリング マシンを構築できることを意味します。 . つまり、 は常に DFA を受け入れ、DFA 以外の入力を常に拒否します。

つまり、その入力が のメンバーである場合ですL。他の例として、男 X は自分の父親を認識していると言うでしょう。あなたが彼の前に置くものは何でも、彼は自分の前にあるものが彼の父親であるかどうかをあなたに伝えることができるからです。これは正しいです？正しくないのはどの部分ですか？

一方、deciderオーバー言語はチューリング マシンのように見えloopsます。つまり、どんな入力に対しても受け入れ状態または拒否状態で常に停止することはありません。これは、レコグナイザーについて上で説明したことと似ているか、同じではないでしょうか?

ありがとう

L={ww|w は {0,1}* に属する} の補集合の CFG は?

そのようなものは存在しますか？もしそうなら、例を挙げていただけますか？ありがとう。

時間計算量について話すとき、通常、入力としてnを使用しますが、これは実際の入力サイズの正確な尺度ではありません。入力（ s ）に特定のサイズを使用する場合、アルゴリズムが同じ複雑度クラスのままであることを示すのに問題があります。

たとえば、単純なシーケンシャル検索アルゴリズムを考えてみましょう。最悪の場合、W（n）時間がかかります。特定の入力サイズ（2進数）を適用する場合、順序はW（lg L）になります。ここで、Lは最大の整数です。

シーケンシャル検索または任意のアルゴリズムが同じ複雑度クラス（この場合は線形時間）のままであることをどのように示すことができますか？ ある種の代用が必要なことは理解していますが、どうやって結論を出すのか迷っています。

編集

探していたものが見つかったと思いますが、よくわかりません。

最悪の場合の時間計算量をW（s）として定義する場合、入力サイズsのアルゴリズムによって実行される最大ステップ数、次に入力サイズの定義により、s = lg n、ここでnは入力です。次に、n = 2 ^ sであり、時間計算量はW（2 ^ s）であり、指数関数的複雑であるという結論に至ります。したがって、バイナリエンコーディングを使用したアルゴリズムのパフォーマンスは指数関数的であり、大きさの点で線形ではありません。

特定の時間 (15 分ごと) にジョブを実行する Web サイトを開発する必要があるため、cron を使用して Web ページを実行します。

ジョブ情報を保存する最良の方法は何ですか? 毎日行う仕事もあれば、8 時間ごとに行う仕事もあります。さらに複雑なことに、タイムゾーンの違いも考慮する必要があります。PHP には多くのタイムゾーン関数があるため、これはそれほど難しくありませんが、次に実行するジョブのプログラミングに統合するにはどうすればよいでしょうか?

もう 1 つの質問は、ユーザーがジョブを実行するための情報をどのように入力するかということです。http://www.webcron.orgに似たオプションの 1 つは、ジョブを実行する頻度をユーザーに選択させることですが、その情報をデータベースに保存するにはどうすればよいでしょうか?

どんな支援も大歓迎です！

Greplin チャレンジのレベル 3 で苦労しています。なじみのない人のために、ここに問題があります：

最大数が残りの数の合計である配列のすべてのサブセットを見つける必要があります。たとえば、次の入力の場合:

(1、2、3、4、6)

サブセットは

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

コードを実行する必要がある番号のリストを次に示します。パスワードはサブセットの数です。上記の場合、答えは 4 になります。

3、4、9、14、15、19、28、37、47、50、54、56、59、61、70、73、78、81、92、95、97、99

400 万以上の 22 の数字の組み合わせをすべて構築し、それらすべてをテストして正しい答えを得るソリューションをコーディングすることができました。問題は、クランチするのに40分以上かかることです. Web を検索すると、これに対する答えを 1 秒もかからずに得るアルゴリズムを作成できた人が何人かいるようです。計算コストの高い総当たり法よりも、これに取り組むためのより良い方法を疑似コードで説明できる人はいますか? それは私を夢中にさせています！

回文以外の文字列を生成する CFG が必要です。解決策が提供されており、以下のとおりです。 (計算理論の紹介 - Sipser)

この文法がどのように機能するかについての一般的なアイデアが得られます。これは、 production を通じて、対応する等しくないアルファベットをどちらかの半分に持つ部分文字列の挿入を義務付け、S -> aTb | bTa回文が決して生成されないようにします。

私が理解しているように、最初の 2 つのプロダクションのセマンティクスを書き留めておきます。

• S最初と最後のアルファベットが等しくないため、回文にならない文字列を生成します
• RS回文にならないことを保証する部分文字列として少なくとも 1 つで構成されます。

3 番目のプロダクション、つまり のセマンティクスが完全にはわかりません。

私の見方では、T は a と b の任意の組み合わせ、つまり {a, b}* を生成できます。どうしてこうならなかったんだろう

2つは同等ではありませんか？後者の方がより直感的であるため、なぜ使用されないのですか?

トレーニング セットからトレーニングする機械学習アルゴリズムを考えてみましょう。PAC 学習モデルの助けを借りて、必要なトレーニング サンプル サイズの範囲が得られるため、エラーが (イプシロンによって) 制限される確率は (デルタによって) 制限されます。

PAC学習モデルは、計算（時間）の複雑さについて何を言っていますか。学習アルゴリズムにより多くの時間 (より多くの反復など) が与えられると仮定すると、エラーとエラーが制限される確率がどのように変化するか

トレーニングに 1 時間かかる学習アルゴリズムは、金融予測の問題では実用的ではありません。エラー境界とエラーが制限される確率の両方の観点から、アルゴリズムに与えられた時間が変化するにつれてパフォーマンスがどのように変化するかが必要です

特定のアルファベットにいくつの異なる遷移グラフがあるかをどのように判断しますか? たとえば、アルファベット {x, y} を超える TG の数。Daniel IA Cohen の著書「Introduction to computer theory」からの同様の質問のクラスを受講しています。TG を作成する方法の例はたくさんありますが、言語ごとに作成できる数を決定するものはありません。限られた量のTGを探していると思いますか？どうもありがとうございます！