問題タブ [computation]

クラスでは、停止問題、チューリング マシン、縮約などについて学びました。多くのクラスメートは、これらはすべて抽象的で役に立たない概念であり、それらを知っていても意味がないと言っています (つまり、コースが終わったら忘れることができます)。何も失うことはありません）。

理論はなぜ役に立つのか? 日常のコーディングで使用したことがありますか?

valueそれぞれがとを持つアイテムの配列が与えられた場合、最小コストで最小値に到達するために必要なアイテムを決定する最適なアルゴリズムは何ですかcost? 例えば：

最後の全体的な価値: コストの比率は無関係であることに注意してください (A + Aお金に見合う最高の価値が得られますがA + B + B、最小値に達するより安価なオプションです)。

プロジェクトでは、数式を使用した仕様があり、実装する必要があります。これらの式には、フロートを取り、確率を出力する累積標準正規分布関数が存在します。関数は Φ で表されます。この関数を計算する Java ライブラリはありますか?

高価な計算があり、その結果をキャッシュしたいと考えています。2 つのキーでマップを作成する方法はありますか? みたいなことを考えていMap<(Thing1, Thing2), Integer>ます。

次に、次を確認できます。

擬似コード。しかし、それらの線に沿った何か。

私の Ruby (MRI) の整数は、オーバーフローを拒否します。クラスが fixnum から bignum に変更されたことに気付きましたが、これがどのようにモデル化されているのか、Ruby がこれらの巨大な整数の演算を実行するためにどのようなプロセスを使用しているのか疑問に思っています。この動作は、SCHEME や他の環境でも見られます。

C プログラムで同様のものを実装したいので、bignum + bignum がプリミティブ演算にどのように還元されるかを知りたいので、質問します。

ポインタはありますか？

モジュールで使用されているメルセンヌ ツイスターの周期randomは (聞いたところでは) 2**19937 - 1 です。2 進数としては、19937 '1 が連続しています (私の間違いでなければ)。Python はこれを非常に高速に 10 進数に変換します。

変換が必要なのは 2 番目のバージョンだと思いますか?

そして、それは単なるバイナリではありません。これも速いです。(数字を表示するのではなく、文字列に変換された 10 進数の長さを表示します):

タイミング：

問題は、これが実際にどのように行われるかです。

私は感動するのが単純ですか？Python シェルが 5000 か所ほどの場所を一瞬で生成する様子は、まさに圧巻です。

編集：

@dalke と @truppo によって提案された追加のタイミング

result = 0; result += 2**19937したがって、おそらく変換を強制するように見えます。

大学で勉強している間、私は計算理論について多くを学ばなければなりませんでした。私はそのテーマを 3 学期勉強しました。苦労しましたし、忘れ物が多かったことを認めざるを得ません。

これは個人的な問題なのか、それとも（多かれ少なかれ）役に立たないことをたくさん学ばなければならなかっただけなのか、疑問に思っています。

私の質問は次のとおりです。計算理論の分野でどのトピックが最も重要だと思いますか。どの部分について学ぶ価値がありますか。通常の仕事ではどのトピックを使用しますか?

個人的には、言語の理論(特に正規言語 => 正規表現 - 適用できる場合と適用できない場合) と、さまざまな時間 (および空間) の複雑さ、特に O(n)について聞いてよかったです。表記。

しかし、次のことを含め、さらに多くのことを研究する必要がありました。

• 計算可能性理論
  • 停止問題
  • 半決定問題
• 複雑さの理論
  • p=np?
• 論理の理論
  • 命題計算
  • 述語ロジック

これらのトピックについて聞くのは興味深いことでしたが、それらを深く研究することがどれほど必要かはわかりません。

この質問は主観的なものであり、日々の仕事や個人的な経験によって答えが大きく異なることは承知しています. しかし、私が覚えているよりも興味深いトピックについて知りたい.

入力として、平面の三角形化されたジオメトリを受け取ります。ここで、外接する四角形の角の 4 つの座標を計算する必要があります。何か案は？

方程式y=3（x + 1）^ 2 + 5（x + 1）^4があります。

ホーナーのスキームを使用して、この多項式をこの形式で評価できます。y= 8 + x（26 + x（33 + x（20 + 5x）））、したがって8つの算術演算が必要です。

y =（x + 1）^ 2 *（（5x + 10）x + 8）の形式で評価することもでき、7回の操作が必要です。

これは5つの操作で実行できると言われていますが、ホーナーのアルゴリズムが最も効率的であると考えられており、7つの操作でしか実行できません。私は何かが足りないのですか？