問題タブ [computer-science]

私はしばらくの間、ニューラル ネットワークについて学ぼうとしてきました。オンラインでいくつかの基本的なチュートリアルを理解することができました。また、ニューラル コンピューティングの一部を理解することができました。たくさんの数学があり、最初の数章を過ぎると完全に頭から離れてしまいます。それでも、私が見つけることができる最も「数学的な」本ではありません。

数学などを恐れているわけではありません。必要なことを学んでおらず、正確に何が必要なのかわからないだけです。私は現在、地元の大学に在籍しており、Comp の MS に入るために必要なクラスに追いつくために取り組んでいます。科学プログラム (私の学士号はビジネス/情報システムです) ですが、あまり進んでいません。大学の小さなコースの説明によると、NN は実際にはパターン認識に関する電気工学コースでカバーされています (このコースが EE であることは私には奇妙に思えます)。 . 科学。プログラム。

私はこのトピックに非常に興味があり、最終的にはそれについてもっと多くのことを学びたいと思っています。問題は、最初に何を知る必要があるのか​​ わからないことです. 必要だと思われるトピックは次のとおりですが、これは無知からの憶測にすぎません。

• 単変数微積分 (私は Calc I と II を持っていたので、完全を期すためにここで取り上げていると思います)
• 多変数微積分
• 線形代数 (まだ正式には理解していませんが、ウィキペディアや他のサイトでなんとか理解できたことから、多くの概念を実際に理解できます)
• 離散数学 (正式には受講していないが、一部は独学で学んだ別の科目)
• グラフ理論
• 確率論
• ベイジアン統計
• 回路設計
• 他の数学？
• その他のコンプ科学トピック

明らかにここにも神経科学の要素がありますが、主にその概念的な理由から、NN に適用されると彼らが話しているとき、私は実際に本を理解するのに何の問題もありませんでした。

要するに、誰かが本当に理解し、本を読んで、最終的にニューラルネットワークを実装する必要がある半明確な道筋を示すことができますか?

次の問題を最適な方法で解決する必要があります。

入力データは次のとおりです。

• 整数座標の (x, y) ペアとして与えられる平面上の N 点
• 円の中心を表す整数座標の (x, y) ペアとして与えられる同じ平面上の M 点。このすべての円の端には (0, 0) があります。

選択した円または選択した円の端に最初の N 点からの点がない「良い」円よりもプロパティを持ついくつかの円を分離する方法を見つける必要があります。

点と円の数は 100,000 のオーダーです。すべての点ですべての円をチェックする明白な解決策は、複雑さ O(N * M) を持ち、100,000 の円と 100,000 の点で、64 ビット SSE3 単精度コードを使用する Core 2 Duo で約 15 秒かかります。私が競合する参照実装は、同じデータで約 0.1 秒しかかかりません。リファレンス実装が O(Nlog N + Mlog M) であることは知っています。

次の方法でアルゴリズムを最適化することを考えました。ポイント データの 2 つのコピーを作成し、それぞれ x 座標、y 座標に関してコピーを並べ替えます。次に、[(xc - r, yc - r); で定義される正方形内にある点のみを使用します。(xc + r, yc + r)]、ここで (xc, yc) は半径 r の「現在の」円の中心です。ソートされたデータを扱うようになったので、バイナリ検索を使用してその間隔内のポイントを見つけることができます。このアプローチの複雑さは O(Nlog N + Mlog^2 N) である必要があり、実際には参照よりも高速ですが、それでもかなり低速です。

リファレンス実装がどのように機能するかはある程度知っていますが、理解できない手順がいくつかあります。私がこれまでに知っていることを説明しようとします：

座標 (Xc, Yc) の円の半径は次のとおりです。

• Rc = sqrt(Xc * Xc + Yc * Yc) (1)

これは、(0, 0) が円の端にあるためです。

点 P(x, y) が円の外側にあるためには、次の不等式が真でなければなりません。

• sqrt((Xc - x)^2 + (Yc - y)^2) > Rc (2)

ここで、Rc を (1) から (2) に代入すると、いくつかの簡単な計算を行った後に不等式を 2 乗すると、次のようになります。

• Yc < 1/2y * (x^2 + y^2) - Xc * x/y (3.1) for y > 0
• Yc > 1/2y * (x^2 + y^2) - Xc * x/y (3.2) for y < 0

(3.1) と (3.2) は、入力データから選択された任意の (x, y) の任意の円 C(Xc, Yc) に対して真でなければなりません。

簡単にするために、いくつかの表記を作成しましょう。

• A(x, y) = 1/2y * (x^2 + y^2) (4.1)
• B(x, y) = -x/y (4.2)
• E(Xc) = 1/2y * (x^2 + y^2) - Xc * x/y = A(x, y) + Xc * B(x, y) (4.3)

与えられた円 C(Xc, Yc) に対して、(3) を次のように書けることがわかります。

• Yc < MIN(E(Xc)) (5.1) y > 0 のすべてのポイント
• Yc > MAX(E(Xc)) (5.2) y < 0 のすべてのポイント

E(Xc) は、A(x, y) と B(x, y) の 2 つのパラメーターを持つ Xc に関する線形関数であることがわかります。つまり、基本的に E(Xc) は、ユークリッド空間で 2 つのパラメーターを持つ直線のファミリーを表します。

ここで、私が理解できない部分が来ます。彼らは、上記の段落で述べた特性により、エンベロープアルゴリズムを使用して O(N) 時間ではなく O(1) 償却時間で MIN() と MAX() を計算できると言っています。Envelope アルゴリズムがどのように機能するかはわかりません。

Envelope アルゴリズムの実装方法に関するヒントはありますか?

前もって感謝します！

編集：

問題は、数学的な意味でのエンベロープが何であるかではありません - 私はすでにそれを知っています. 問題は、O(n) よりも適切な時間でエンベロープを決定する方法です。明らかに、償却された O(1) で実行できます。

エンベロープを計算するために必要な一連の関数があり、可能なすべてのパラメーターの配列があります。最大化問題を最適な方法で解くにはどうすればよいですか?

再度、感謝します！

わかりました、これは特定の言語に基づく質問ではなく、コンピューター サイエンスに関する質問ですが、map 操作と foreach 操作に違いはありますか? それとも、同じものの名前が違うだけですか？

私は完全に盲目の個人であり、コンピュータサイエンスの理論的側面についてもっと学びたいと思っています。イントロデータ構造クラスと一般的なイントロプログラミングを持っていますが、ソフトウェア設計、高度なデータ構造、コンパイラ設計などについてもっと学びたいと思います。私はこれを大学の授業の一部としてではなく、独学のコースとしてやりたいと思っています。

残念ながら、私が通常教科書を入手している「盲人と失読症のための録音」から、コンピュータサイエンスで利用できる教科書は多くありません。多くのプログラミングサイトが焦点を当てているように見える最新の言語やプラットフォームではなく、コンピュータサイエンスの教育を受けるのに役立つ、できれば無料の電子リソースをいただければ幸いです。

3 年間趣味のプログラマー (主に Python と C) をしてきましたが、500 行を超えるコードのアプリケーションを作成したことがないため、次の 2 つの選択肢に直面していることに気付きました。

(1) l33t コンピューター科学者になるために、データ構造とアルゴリズム設計の基礎を学びます。

(2) Qt について学びます。これは、私が長い間構築したいと思っていたプロジェクトを構築するのに役立ちます。

(1) の学習には、CLRS を読むことを誰もが推奨しているようです。残念ながら、CLRS を読むには、少なくとも 1 年 (またはそれ以上、私は Peter Krumins ではありません) の学習が必要です。また、(2) を使用して適度に複雑なタスクを達成するには、少なくとも (1) の基礎を理解する必要があることも理解しています。 CLRS は、(2) を使用して大規模なプロジェクトで作業するためのアルゴリズムとデータ構造に関する十分な知識を与えてくれますか?

言い換えれば、毎日のアプリケーション プログラミング タスクに絶対に不可欠な理論的な CompSci トピックのリストが必要です。また、CLRS を便利なリファレンスとして使用したいので、本書の後半のセクションを理解するために重要な資料を飛ばしたくありません。

ここで誤解しないでください。離散数学と CompSci の理論的基盤は、約 6 か月前から私の「TODO: 緊急」リストに載っていますが、大学の仕事のために十分な時間がありません。久しぶりに 15 日間のオフがあり、好きなことを何でもできます。この 15 日間は、机に座ってペンと紙を手に書き留めようとするのではなく、本当に作りたいアプリケーションを作成することに費やしたいと思います。教科書問題の解法。

(ちなみに、アルゴリズムに関する数学の少ないコードのリソースは高く評価されます。私は高校を卒業したばかりで、数学はあるべきレベルに達していません。)

ありがとう ：）

「レキシカル変数」という用語は、主にクロージャーのコンテキストで数回見たことがあります。Paul Graham は、Lisp に関する彼の著書で、 let 式を使用して定義された変数を参照する用語を使用しています。

レキシカルスコープは静的スコープの別名であることを理解しています。レキシカル変数は、プログラム単位の参照環境で見える単なる変数ですか?

このホリデー シーズンに、この言葉を使って友人や家族に感銘を与えたいと思っています。誰か助けてくれませんか?

開発者として、どの講演やビデオに魅力を感じましたか?

私は Clay Shirky によるこの講演が本当に好きです:
http://www.youtube.com/watch?v=Xe1TZaElTAs
そして、David による Startup School の講演:
http://www.omnisio.com/startupschool08/david-heinemeier-hansson- at-startup-school-08

あなたはどれをお勧めしますか？可能であれば、リンクと簡単な説明を提供してください。

編集: スレッドがあることは知っています。プログラミング関連の優れたオンライン トーク / ビデオとは何ですか? ..しかし、特に焦点を絞ったトーク/ビデオをプログラミングするのではなく、より一般的なものを探しています。

MP3 (またはその他のオーディオ形式) としてオンラインでダウンロードできる、特に優れた大学の講義はありますか? コンパイラ、オペレーティング システム、AI、暗号化など、工学の学位では受けられなかった、より高度なクラスのいくつかを聞くことに特に興味があります。

CS動画講義についてまた質問なのですが、MP3プレーヤーで講義を聞きたいです。

私は空白を描いている、または一部の人が言うように、シニアの瞬間を持っています。データベースで実行されるdb操作（ストアドプロシージャ）が繰り返し実行された場合に同じ結果が得られるという概念の正式な定義と名前があることを私は知っています。

これは、数学者の反射的、対称的、推移的などのジャンルの何かです。