クラスでは、停止問題、チューリング マシン、縮約などについて学びました。多くのクラスメートは、これらはすべて抽象的で役に立たない概念であり、それらを知っていても意味がないと言っています (つまり、コースが終わったら忘れることができます)。何も失うことはありません）。
理論はなぜ役に立つのか? 日常のコーディングで使用したことがありますか?
10763 次
24 に答える
29
実話：
私が大学院を出て最初のプログラミングの仕事を得たとき、私が働いていた会社のオーナーはパイロットでした。私が雇われてから数週間後、彼らの一人が私にこの質問をしました：
アーカンソー州には 106 つの空港があります。それらのそれぞれに着陸するために必要な最短ルートを見つけるプログラムを作成できますか?
巡回セールスマン問題と NP 完全性に関する私の知識について、彼が私に質問していると真剣に思っていました。しかし、彼はそうではなかったことが判明しました。彼はそれについて何も知りませんでした。彼は、最短経路を見つけるプログラムが本当に欲しかったのです。106 階乗の解があり、最良の解を見つけることはよく知られた計算上の困難な問題であると私が説明したとき、彼は驚いていました。
これは一例です。
于 2008-10-24T22:12:09.493 に答える
24
大学を卒業したとき、私は他の人と同等だと思っていました。私は最終的に、私の仮定が間違っていることを発見しました。私は際立っていましたが、それには私のバックグラウンド、特に学位が大きく関係していました。
私は「わずかな」違いが 1 つあることを知っていました。それは、私の大学は、CS 学位プログラムの認定を受けた国内で最初の大学の 1 つであったため (1987 年に 2 位だったと思われます)、CS の「BS」を持っていたことです。その認定を受けるために2級を卒業しました。当時は、あまり重要視していませんでした。
また、高校と大学時代に、CS で特に成績が良かったことに気付きました。同級生よりもはるかに優れており、多くの教師よりも優れていました。私は多くの助けを求められ、個人指導を行い、研究プロジェクトを手伝うように求められ、誰もいないときに独立した研究をすることを許可されました. お役に立ててうれしかったのですが、違いについてはあまり考えていませんでした。
大学 (USAFA) の後、私は空軍で 4 年間過ごし、そのうちの 2 年間は CS の学位を申請していました。そこで気づいたのは、私の同僚のほとんどがコンピューター関連の学位を持っていたり、トレーニングさえ受けていなかったことです。空軍は私を 5 か月の認定訓練に送りましたが、そこでも学位や訓練が不足していることに気づきました。しかし、ここで私は違いに気づき始めました。私が出会った人々の多くは、自分が何をしているのかを本当に理解していないことが完全に明らかになりました。説明させてください。
私の空軍認定トレーニングには、合計13人（私を含む）がいました。空軍士官またはそれに相当する者として、私たちは皆、BS の学位を持っていました。私は年齢とランクで中間でした (私は O-1 が 6 人、O-3 以上が 6 人中の O-2 でした)。この訓練の最後に、空軍は私たち全員に、国防総省のあらゆる部分のためのあらゆるコンピューターまたは通信システムを取得、構築、設計、保守、運用する能力があることを認めました。
しかし、私たち 13 人のうち、コンピューター関連の学位を取得していたのは 6 人だけでした。他の 7 人は、航空学から化学/生物学、心理学までの学位を取得していました。コンピューターサイエンスの学位を取得した 6 人のうち、2 人はプログラムをまったく書いたことがなく、コンピュータをカジュアルにしか使ったことがありませんでした (論文を書いたり、ゲームをしたりなど)。別の 2 人は、CS の学位取得プログラムで、1 台のコンピューターで 1 つのプログラムを書いたことがあることを知りました。複数のプログラムを作成したり、複数の種類のコンピューターを使用したりしたのは、他の 1 人と私だけでした。
5 か月のトレーニングの終わりに向けて、私たちのクラスにはプログラミング プロジェクトが割り当てられ、4 つのグループに分かれて別々に取り組みました。私たちのインストラクターは、「プログラミングの才能」を公平に広めるためにクラスを分割し、チームリーダー、技術リーダー、および開発者の役割を割り当てました。各グループには、教官が提供する飛行力学ライブラリの上に、フライト シミュレータ用のフルスクリーンのテキストベースのユーザー インターフェイス (これは 1990 年) を (Ada で) 実装するための 1 週間が与えられました。私は 4 人のチームのテクニカル リーダーとして割り当てられました。
私のチーム リーダー (コンピューターの学位を持っていなかった) は、他の 3 人にプロジェクトをタスクに分割するように依頼し、その 3 分の 1 をそれぞれに割り当てました。初日の半ばまでに 3 番目のタスクを完了し、残りの 2 人のチームメイトを手伝ったり、チーム リーダー (BSing ;^) と話したり、コンピューターで遊んだりしました。
翌朝 (2 日目)、私のチーム リーダーは、他の 2 人のチームメイトが進歩していないことを私に個人的に知らせました (1 人は実際にコンパイルする "if" ステートメントを書くことができませんでした)。私は午後半ばまでにプロジェクト全体を完了し、私のチームはその日の残りをシミュレーターの飛行に費やしました。
同等のコンピューター サイエンスの学位を持つもう 1 人の人物も、彼のチームのテクニカル リーダーとして割り当てられ、3 日目の終わりまでに終了しました。彼らはまた、シミュレーターを飛ばし始めました。残りの 2 つのチームは、その週の終わりまでに完了していないか、大幅な進歩を遂げていませんでした。他のチームを助けることは許されなかったので、そのままにしておきました。
一方、3 日目の半ばまでに、フライト シミュレータが「間違った」動作をしているように見えることに気付きました。同級生の一人が航空学の学位を持っていたので、彼にそれについて尋ねました。彼は戸惑い、飛行機が飛ぶ理由を実際に知らなかったと告白しました!?! 私は唖然としました！彼の学位プログラム全体が安全性と墜落調査に関するものであったことが判明しました。飛行の背後には実際の数学や科学はありません。一方で、私には航空学の未成年者がいたかもしれませんが (USAFA を覚えていますか?)、私たちは翼を設計し、実際の風洞実験を行っていました。そのため、シミュレーターが「正しく」飛行するまで、残りの 1 週間を静かにインストラクター提供の飛行力学ライブラリーの書き換えに費やしました。
それ以来、私は 20 年近く請負業者として、時には従業員として、常にソフトウェア開発と関連する活動 (DBA、アーキテクトなど) を行ってきました。私は同じものをさらに見つけ続けましたが、最終的には若々しい仮定をあきらめました.
それで、私は正確に何を発見しましたか？すべての人が平等というわけではありませんが、それは問題ありません。私は効果的にプログラミングできるので、より優れた人間ではありませんが、あなたが私にそれを求めているのであれば、私はより役に立ちます。私は自分のバックグラウンドが本当に重要であることを学びました: 電気技師と電気技術者の家族で育ち、電子キットを作り、実際のコンピューターにアクセスできなかったので、学校/公共図書館のすべてのコンピューターの本を文字通り読みました。私の高校がコンピューターを持っていた街で、自分のコンピューターを贈り物として手に入れ、さまざまなサイズと種類のコンピューター (PC からメインフレームまで) を備えた学校に通い、非常に優れた工学部から認定学位を取得し、執筆をしなければなりませんでした。さまざまな種類のコンピューター上にさまざまな言語で書かれた多数のプログラム、
最終的に、私の能力は、コンピュータが電気的レベルからどのように機能するかを知るという基盤の上に構築されていることを学びました。ディスクリート電子部品、回路、サブシステム、インターフェース、プロトコル、ビット、バイト、プロセッサ、デバイス、ドライバ、ライブラリ、プログラムです。 、システム、ネットワークから、現在私が日常的に取り組んでいる大規模なエンタープライズ クラスのコングロマリットまで。だから、いまいましいものが誤動作したとき、私はその方法と理由を正確に知っています. そして、できることだけでなく、できないことも知っています。そして、何が行われ、何が試みられ、何が比較的未開拓のままであるかについて、私は多くのことを知っています。
最も重要なことは、それをすべて学んだ後で、私はいまいましいことを何も知らないということを学んだということです. 知るべき可能性のあるすべてのことに直面して、私の知識はごくわずかです。
そして、私はそれに非常に満足しています。しかし、試してみることをお勧めします。
于 2008-10-25T00:06:00.527 に答える
23
確かに、それは便利です。
テンプレート エンジンに取り組んでいる開発者を想像してみてください。あなたはそのようなことを知っています...
Blah blah blah ${MyTemplateString} blah blah blah.
置換を実行する生意気な小さな正規表現で、単純なものから始めます。
しかし、次第にテンプレートが少し凝ったものになり、開発者は文字列のリストとマップをテンプレート化するための機能を組み込みます。それを達成するために、彼は簡単な文法を書き、パーサーを生成します。
テンプレート エンジンは非常に狡猾で、最終的に条件付きロジックの構文を組み込み、引数の値に応じてさまざまなテキスト ブロックを表示する可能性があります。
CS の理論的バックグラウンドを持つ人は、テンプレート言語がゆっくりとチューリング完全になりつつあることを認識するでしょう。おそらく、Interpreter パターンはそれを実装するための良い方法になるでしょう。
テンプレートのインタープリターを作成した後、コンピューター科学者は、テンプレート リクエストの大部分が重複していて、同じ結果が何度も再生成されていることに気付く場合があります。そのため、キャッシュが開発され、すべてのリクエストは、コストのかかる変換を実行する前にキャッシュを介してルーティングされます。
また、一部のテンプレートは他のテンプレートよりもはるかに複雑で、レンダリングに時間がかかります。おそらく誰かが、レンダリングする前に各テンプレートの実行を見積もるというアイデアを思いつくでしょう。
ちょっと待って！！！チームの誰かが、テンプレート言語が本当にチューリング完全である場合、各レンダリング操作の実行時間を見積もるタスクは停止問題のインスタンスであると指摘しています!! うん、それをしないでください!!!
実際の理論については、すべての実践が理論に基づいているということです。理論的に。
于 2008-10-24T22:23:24.960 に答える
17
私が最もよく使うもの：
- 適切にスケーリングするアルゴリズムを作成するための計算の複雑さ
- 効率的なコードを記述できるように、メモリ割り当て、ページング、および CPU キャッシュがどのように機能するかを理解する
- データ構造の理解
- スレッド化、ロック、および関連する問題の理解
チューリングマシンなどに関するものについては、私たち全員が操作する制約を定義するため、重要だと思います。それは感謝することが重要です。
于 2008-10-24T22:05:00.240 に答える
16
代数を学ぶことと電卓の使い方を教えられることの違い
代数を知っていれば、同じ問題がさまざまな形式で現れる可能性があることに気付き、問題をより簡潔な形式に変換するための規則を理解できます
電卓の使い方しか知らない場合は、(a) すでに解決済みの問題、(b) 解決できない問題、または (c) 他の問題のような問題 (解決済みまたは未解決）違う形だからわからない
少しの間、コンピューター サイエンスは物理学であると考えてみてください...その質問はばかげているように思えますか?
于 2008-10-26T17:10:59.387 に答える
8
私の友人は、いくつかのテンプレートを使用して言語の作業を行っています。ちょっとした相談に乗ってもらいました。私たちの議論の一部は、テンプレート機能についてでした。テンプレートが完全なチューリングである場合、VM っぽいプロパティと、コンパイラがそれをサポートする方法/場合を実際に検討する必要があるためです。
私の話はここまでです。オートマトン理論は今でも教えられています。停止の問題は依然として存在し、できることを制限しています。
では、これらのことはデータベース ジョッキーが C# コードを作成することに関連していますか? おそらくそうではありません。しかし、より高度なレベルに移行し始めると、自分のルーツと基盤を理解したいと思うでしょう。
于 2008-10-24T22:07:19.987 に答える
7
それらを日常業務に直接適用することはありませんが、正式なコンピューター サイエンスに関する教育が私の思考プロセスに影響を与えていることはわかっています。フォーマルなアプローチから学んだ教訓が私に植え付けられているので、私は確かに最初から特定の間違いを避けています。
彼らがそれを学んでいる間は、役に立たないように思えるかもしれません。しかし、あなたの同級生は、教えられたこと、または少なくともその背後にある思考パターンを使用するという問題に最終的に遭遇するに違いありません...
ワックスオン...ワックスオフ...ワックスオン...ワックスオフ...とにかく、それは空手と何の関係がありますか?
于 2008-10-24T22:31:19.813 に答える
6
ある仕事で、配電モデルのネットワーク トレース アルゴリズムが遅すぎたので、それを改善するタスクを割り当てられました。3 相ネットワークは基本的に 3 つの n ツリーでした (電気ネットワークではループが許可されていないため)。ネットワーク ノードはデータベース内にあり、元のチームの何人かはメモリ内モデルを構築する方法を理解できなかったため、データベース上で連続する深さの SELECT によってトレースが行われ、各フェーズでフィルタリングされました。そのため、変電所から 10 個のノードを追跡するには、少なくとも 10 個のデータベース クエリが必要になります (元のチーム メンバーはデータベースの達人でしたが、アルゴリズムの十分なバックグラウンドがありませんでした)。
ノードの 3 つの n ツリー ネットワークをデータベースからデータ構造に変換するソリューションを作成しました。このデータ構造では、各ノードはノード構造配列に一度格納され、n ツリーの関係は内部の二重リンク ポインターを使用して 3 つのバイナリ ツリーに変換されます。ネットワークをどちらの方向にも簡単にトレースできるようにします。
少なくとも 2 桁高速で、非常に長いダウンストリーム トレースでは 3 桁高速でした。
悲しいことに、アルゴリズムを理解するために、データベースと VB のトレーニングを受けた他の何人かのプログラマーに、n-ツリー、バイナリー ツリー、ポインター、二重リンク リストのクラスを実際に教えなければなりませんでした。
于 2008-10-27T21:33:42.630 に答える
4
これは、「方法」と「何」の間の古典的な二分法です。あなたのクラスメートはソフトウェアをプログラムする「方法」を見ていて、彼らは近い焦点に非常に焦点を合わせています。その観点、実装の観点からは、停止状態やチューリングマシンなどを知ることは重要ではないようです。
ただし、「どのように」は、コンピュータサイエンスで期待される実際の作業のほとんどではありません。実際、私が知っているほとんどの成功したエンジニアは、おそらく実際の仕事の20パーセント未満にそれを置くでしょう。「何をするか」ははるかに重要です。そのためには、コンピュータサイエンスの基礎が重要です。あなたがやりたい「何」は、実装よりも設計にはるかに関係しています。良いデザインとは...まあ、それを「自明ではない」と呼びましょう。
「ソフトウェア設計を構築する方法は2つあります。1つは明らかに欠陥がないように単純にする方法、もう1つは明らかな欠陥がないように複雑にする方法です。最初の方法ははるかに困難です。 。」 -CAR Hoare
あなたの研究で頑張ってください！
于 2008-10-25T00:48:30.893 に答える
3
計算の基本モデルを理解することは有益だと思います。実際にはチューリング マシンをレジスタ マシンに変換する必要はありませんが、2 つの非常に異なる問題が実際には同じ概念のインスタンスであることを確認する方法を学ぶことは非常に重要です。スキル。
于 2008-10-24T22:10:10.290 に答える
3
ほとんどの知識は「実用的」ではありませんが、予想できない方法で点を結び付けたり、より複雑なアイデアを説明するための豊富な語彙を提供したりします。
于 2008-10-24T22:10:19.357 に答える
3
重要なのは、特定の問題を研究することではなく、それらを研究することで学ぶ原則です。私は毎日の仕事で、アルゴリズム、データ構造、プログラミング言語、およびオペレーティング システムに関する概念を使用しています。プログラマーは、システムのパフォーマンスに影響を与える決定を常に行うことになります。正しい選択をするためには、基本的な抽象的な概念の強固な基盤が必要です。
于 2008-10-25T00:26:02.250 に答える
2
画期的な仕事をしている会社で働いている場合、そのメリットをアーキテクトや開発者に伝えることができることが重要です。あらゆる種類のテクノロジーについて多くの誇大宣伝があり、自分自身のポジショニングが難しい場合があります。科学的および理論的な用語でイノベーションを構築すると、間違いなく有利になり、顧客はあなたが本物であると感じます. 皆さんにお伝えしたいのは、状態、エンコーディング、および非決定性 (複雑さ) に対処する新しい方法があり、現在よりも確実に生産性を高めることができるということです。
キャリアを長い目で見れば、理論について学ぶことで深みが得られます。成長するために必要な深さです。5 番目または 6 番目のプログラミング言語を学習するための投資収益率は、2 番目および 3 番目のプログラミング言語を学習する場合よりもはるかに少なくなります。理論に触れることで、自由度がどこにあり、どのように適切なトレードオフを行うことができるかについて、実際のエンジニアリングの感覚が得られます。
重要な概念は、1) 状態、2) エンコーディング、3) 非決定性です。あなたがそれらを知らなければ、彼らはあなたを助けません。理論で得られるのは、全体像と、基本的な概念がどのように組み合わされるかという感覚です。直感を磨くのに役立つはずです。
例: 上記の回答のいくつかは、停止問題とチューリング マシンに言及しています。大学でチューリングの論文に出くわしたとき、私はまったく悟りを感じませんでした。ある日、私はゲーデルの不完全性定理、特にゲーデル数法に出くわしました。物事は非常に理にかなっています。数年後、書店でゲオルク・カントールについて読みました。これで、チューリングマシンと停止問題について本当に理解できるようになりました。自分で試してみて、ウィキペディアで「カントールの対角論」を調べてください。これは、知的にこれまで遭遇した中で最も素晴らしいものの 1 つです。
考察の材料: 典型的なチューリング マシンは、状態遷移マシンを設計する唯一の方法ではありません。テープが 1 つではなく 2 つあるチューリング マシンを使用すると、多くのアルゴリズムの速度が大幅に向上します。http://www.math.ucla.edu/~ynm/papers/eng.ps
この本を読むことで、私が行ったよりも効率的にこれらの洞察に身をさらすことができます. この投稿の下部にあるリンク。（少なくとも、Amazonの目次をチェックして、これが何であるかを味わってください）：
ローゼンバーグの本はセンセーショナルだと思いました。http://www.amazon.com/The-Pillars-Computation-Theory-Nondeterminism/dp/0387096388理論に関する本が 1 冊しかない場合は、IMHO がその本になるはずです。
于 2014-08-19T14:57:18.217 に答える
1
ええ、私は通常、状態図を使用してプログラムの形状とフローを設計します。理論的には機能するようになったら、コーディングとテストを開始し、状態を確認します。
プロセスの振る舞いを他の人に説明するのにも役立つツールだと思います。
于 2008-10-25T01:02:32.317 に答える
1
正直なところ、私はここでの多くの答えに同意しません。私は、コンパイラーのコースを受講せずに、最初のコンパイラーを作成しました（楽しみのために、コーヒーや空き時間が多すぎます）。基本的に、別のコンパイラのコードをスキャンして、パターンに従いました。頭のてっぺんからCでパーサーを書くことはできましたが、私の人生がそれに依存しているのであれば、プッシュダウンオートマトンを描く方法を思い出せないと思います。
おもちゃの（命令型）プログラミング言語に型推論を入れたいと思ったとき、私は最初におそらく5つの論文を調べ、「型付きラムダ計算」と呼ばれるものが何をしているのかを見つめました。 ....？最初は「一般変数」と「非一般変数」で何かを実装しようとしましたが、何が起こっているのかわかりませんでした。それから私はそれをすべて廃棄し、ノートブックを持ってそこに座って、必要なすべてのもの（サブタイピング、ファーストクラス関数、パラメーター化されたタイプなど）をサポートして実際に実装する方法を考えました。 ＆テストプログラムを書いているとき、私は理論的ながらくたを理解しようとする価値のある1週間以上を吹き飛ばしました。
コンピューティングの基本（つまり、仮想メモリのしくみ、ファイルシステムのしくみ、スレッド化/スケジューリング、SMP、データ構造）を知ることは、すべて非常に役立つことが証明されています。複雑さの理論とBig-Oのものが役立つことが時々証明されています（特にRDBMS設計のようなものに役立ちます）。停止性問題とオートマトン/チューリングマシン理論？一度もない。
于 2010-01-14T06:39:37.317 に答える
1
C++ テンプレートは、実際にはある種のラムダ計算であるためです。www.cs.nott.ac.uk/types06/slides/michelbrink_types_06.pdf を参照してください。
于 2008-10-27T20:57:41.377 に答える
1
私は毎日それを使用しません。しかし、それは私に毎日役立つ多くの理解を与えてくれました.
于 2008-10-24T22:06:46.290 に答える
1
私は今、分散アルゴリズムのコースのために勉強しています。耐障害性に関する章があり、分散アルゴリズムが正しく処理できるように、いくつのプロセスが失敗する (または誤動作する) かについての上限に関するいくつかの証明が含まれています。
多くの問題では、不適切なプロセスの境界は、プロセスの総数の最大 3 分の 1 です。私の意見では、(与えられた仮定の下で) より良いアルゴリズムを開発しようとするのは無意味であることを知っているので、これは非常に便利です。
于 2009-01-06T19:05:02.237 に答える
1
単純。例: RSACryptoServiceProviderを使用している場合、それが何であり、なぜ信頼できるのかを知りたいです。
于 2008-10-26T17:39:20.890 に答える
1
CS 理論の世界で日々至福を味わうために必要なのは、「低結合と高結束」というマントラを唱えることだけであることがわかりました。スティーブ・マコーネルがそれをファッショナブルにする前に、ロジャー・S・プレスマンはそれを学術的にしました。
于 2008-10-24T22:45:57.100 に答える
1
理論的なコースが直接使用されない場合でも、何かをよりよく考えるのに役立つ場合があります。
ジェフリー・L・ホイトレッジが言ったように、上司が何をするように頼むのか分からない場合、有益ではないと思ったものを使用する必要があるかもしれません.
于 2009-02-01T18:35:16.477 に答える
-1
どの分野に進むかにもよると思います。
于 2008-10-24T22:15:45.897 に答える