問題タブ [computer-science-theory]

ジョン・マッカーシーがまだ生きていればよかったのに…

LISP 1.5 Programmer's Manualから:

LISP は、S 式の形式で記述されたプログラムを解釈して実行できます。したがって、機械語と同様に、他のほとんどの高水準言語とは異なり、さらに実行するためのプログラムを生成するために使用できます。

機械語を使用してプログラムを生成する方法と、Lisp でそれを行う方法について、もっと明確にする必要がありますか?

コンピュータ サイエンスのすべての基本的なデータ構造は、本質的に再帰的に見えることに気付きました。例: グラフ、リスト、配列、セットなど。

何故ですか？何か根本的な理由があるのでしょうか。帰納法を介して再帰的なデータ構造の特性を証明する方が簡単だからですか?

高さ n の二分木に 2^(n+1)-1 個のノードがあることを帰納法によって証明するにはどうすればよいでしょうか?

Turing のComputing Machinery and Intelligenceを読んだところ、彼は有効な議論として超感覚的知覚 (#9) に言及しています。

「残念ながら、少なくともテレパシーに関しては、統計的証拠が圧倒的です。」

この統計的証拠を見つけることができませんでした。彼が言及していることを知っている人はいますか? これは彼が生きた時代の産物ですか？彼の口調は、彼もそれを信じたくなかったことを暗示しています.

これが質問するのに最適な場所かどうかはわかりませんが、多少関連しているようです。

私は問題に取り組んでおり、自分の仕事が正しいことを確認したいだけなので、誰かが私を批判できれば幸いです.

質問：

検討されている 2 つのアーキテクチャの改善点があります (A1 & A2)。5 つのベンチマーク (B1 ～ B5) のそれぞれについて、ベース システムと比較した速度向上を示す表が渡されました。これらの高速化は、参照コンピューターに対するスペック比です。

A1: B1 = 1.5、B2 = 4、B3 = 3、B4 = 2、B5 = 5

A2: B1=3、B2=1.5、B3=4、B4=4、B5=3

上記の情報を考慮して、どの改善を選択する必要がありますか?

私の答えは次のとおりです。

ベースラインを参照として使用し、改善の仕様比 (A1/A2) の幾何平均を使用して、どちらが優れているかを判断できます。

スペック比は以下の通り。

S1 = 1.5/3

S2 = 4/1.5

S3 = 3/4

S4 = 2/4

S5 = 5/3

幾何平均は次のようになります: (S1*S2*S3*S4*S5)^(1/5) これはおよそ 0.96 に相当します。

したがって、A1 は A2 よりもおよそ 96% しか優れておらず、A2 を選択する必要があります。

繰り返しますが、ここで私の考えが正しいかどうかを確認しています。どんな助けでも大歓迎です。

EDIT1: Mackie の方法論の使用

ベンチマークのベース スピードを取ると、A0 の場合は次のようになります。

B1=B2=B3=B4=B5=1

したがって、Base と A1 のスペック比 (A0/A1) の幾何平均は次のようになります。

((1/1.5) * (1/4) * (1/3) * (1/2) * (1/5)) ^ (1/5) = 0.35

また、Base と A2 のスペック比 (A0/A2) の幾何平均は次のようになります。

((1/3) * (1/1.5) * (1/4) * (1/4) * (1/3)) ^ (1/5) = 0.34

ただし、ここで (Base/A1) と (Base/A2) を比較すると、0.35/0.34 = 1.03 になります。これは、A1 が A2 よりも約 3% 遅いことを意味しますか? 私の計算は間違っていますか、それとも A0 に対して間違ったベンチマークを選択したのでしょうか? 私の最初の方法はより単純に見え、最初の質問が何を求めていたか...

コーディングしたい問題があります。0 から n-1 までの数字を生成するプロセスがあり、最初の繰り返し要素を生成するときにそれを停止したいと考えています。* これを高速化するデータ構造を探しています。特に、新しい要素の追加と、要素が構造内にあるかどうかのテストは高速である必要があります。予想される挿入数は、およそ sqrt(n) (誕生日の問題) か、実際にはもう少し悪い (sqrt(2n) など) です。プロセスが一意の値をわずかに優先するからです。言い換えれば、かなりまばらです。10 億までの数値を扱う場合、約 3 万または 5 万の値しか使用されません。

ハッシュ セットまたはある種の自己均衡二分木が正しいアプローチのように思えますが、もっと良い方法があるのではないでしょうか? 小さい n の場合、ビット配列の方が優れていると思いますが、10 ^ 9 前後の n を見ていると、大きすぎて実用的ではないと思います。

* 実際には、すぐに停止する必要はありません。より効率的であれば、要素をブロックで生成し、時々チェックすることができます。

注: これはもともと math.se に投稿されたものですが、ここに再投稿することを勧められました。これは研究レベルではないため、cstheory.se には適していません。

それが O(1) かどうかを判断しようとしています。どうすれば証明できますか？複雑さに関しては、log_b(n) は log(n) です。O(log_2(n)-log_3(n))=O(0)=O(1) ですか? 有力な証拠とは思えません。また、これは漸近的に収束しないのに、どうして O(1) になるのでしょうか?

これはよくある質問です: 100 万個の 32 ビット整数をソートする最も効率的な (時間の複雑さの点で) 方法は何ですか? ほとんどの回答は、これらの数値のビット数は一定であると想定されているため、基数ソートを使用することが最善の方法の1つであることに同意しているようです。これは、CS の学生が非比較ベースの並べ替えを初めて学習するときによく行われる思考練習でもあります。ただし、詳細に (または少なくとも明確に) 説明されていないのは、アルゴリズムの基数 (またはバケットの数) を最適に選択する方法です。

この観察された回答では、バケットの基数/数の選択は経験的に行われ、32 ビット 100 万の整数に対して 2^8 であることが判明しました。その番号を選択するより良い方法があるかどうか疑問に思っていますか? 「Introduction to Algorithms」(p.198-199) では、Radix のランタイムは Big Theta(d(n+k)) (d=桁/パス、n=項目数、k=可能な値) である必要があると説明されています。さらに、n b ビットの数値と任意の正の整数 r <= b を指定すると、radix-sort は Big Theta((b/r)(n+2^r)) 時間で数値を並べ替えます。次に、「b>= floor(lg(n)) の場合、r ~= floor(lg(n)) を選択すると、一定の係数内で最適な時間が得られます...」。

しかし、観察された答えが示唆するように、 r=lg(1million)~=20 != 8 を選択した場合。

これは、本が示唆している「rの選択」アプローチを誤解している可能性が非常に高く、何かが欠けている（可能性が非常に高い）か、観察された答えが最適な値を選択しなかったことを示しています。

誰かが私のためにこれを片付けることができますか? 前もって感謝します。

私はコンピューターサイエンス研究の初心者です。私は研究プロジェクトに取り組んでいますが、私の質問は、IEEE での出版物のインパクト ファクターをどのように検出できるかということです。IEEE はこの情報を提供していますか?