DIY：アメリカのトップホーム大学レベルでの修士課程コンピュータサイエンス

エントリー

私は長い間、コンピュータサイエンスの教育に関する記事を書きたいと思っていましたが、私の手は届きませんでした。 それでも、私は最終的にそれをすることにしました。 それでは、何について話しましょうか？ それは、修士課程コンピュータサイエンスの卒業証書が米国のトップ大学からのものであるかどうか（基本コース、書籍、プロジェクトを含むすべての詳細）とその遵守方法についてです。



なぜ修士号？ これは一種の分岐点です：一方では、修士課程の後、あなたは生涯の準備ができたエンジニアです（はい、これは私たちの教育システムで最も苦痛な場所であると思われるため、エンジニアリングトレーニングについて話しています） ご存知のように、プログラム方法を実際に知らなくても博士課程プログラムに参加することができます-これは特に理論的なコンピューターサイエンスに当てはまります。 一方、プログラマーの仕事を見つけることもそれほど難しくなく、多くの場合、強力な教育を必要としません。 しかし、修士課程レベルに到達すると、コンピューターサイエンスのすべての新しいアイデアを理解する機会と、それらを実践する機会が得られます。 つまり、一方では、深層学習を理解し、その中で何か新しいことを行い、独自のオペレーティングシステム（誰がこれを実行したのか）を取得して作成するのはクールです。 そして、あなたは狭い専門分野の枠組みにとらわれていません（もちろん、勉強を続けている場合を除きます）。 つまり、あなたは今や万物の兵士であり、何に対しても準備ができています。



この記事がお役に立てば幸いです。

1.米国のトップ大学の高い基準を満たすことを希望する学生、またはコンピューターサイエンスの大学院に進学する学生

2.「穴」とギャップを埋めたい専門家

3.おそらく、教師の一人がコースに注意を払うでしょう。

4.学生、アメリカの大学の大学院生-特に教育の最新動向に関するフィードバックも受け取りたい



ここに何が書かれますか？ 最低限の哲学と一般的な考え方：学部課程と大学院課程の特定のプログラム。もちろん、私に最も近い分野から。 すべてのコースは自分の肌で個人的に感じられたので、これが私が書いている理由です。 （私はすべての興味深いコースにサインアップしようとしましたが、私の主な重点はシステムプログラミング、データベース、人工知能です。したがって、もちろんある程度のバイアスがありますが、多かれ少なかれ普遍的なプログラムを提供しようとしています）。

内容

1.基本トレーニング

2.学部課程

3.大学院プログラム

4.自分でテストする準備はできましたか？ コンピュータサイエンスコンプ。

基本的なトレーニング

最初に行うことは、数学を通過することです。 ロシアの学術環境で一般に受け入れられている理論は、私たちの数学は非常にクールであり、私たちは他の先を行っているということです。 しかし、理論的なコンピューターサイエンスと数学の境界線は狭く、さらに、コンピューターサイエンスに含まれるすべてが数学と呼ばれるわけではありません。 まあ、コンピューターサイエンスでは、近年の成功は悲しいかな...



一言で言えば、本質はこれです-多くの数学はありませんが、行き過ぎてはいけません。 科学者とエンジニアの混成であるハイブリッド教育を取得する必要があり、終了時にそれを行います。 したがって、数学を最小限に抑える必要があります。 コンピュータサイエンスには非常に多くの興味深いことがあります。



-分析-基本に関する自信のある知識が伝わります。つまり、多次元分析を理解する必要がありますが、すべての証拠を深く掘り下げる必要はありません。

-線形代数-どこでも非常に必要なことをよく理解する必要があります。 さらに、かなり高度なレベル（固有ベクトル、特異展開、共役勾配）で望ましい

-ディフラ-あなたはそれを安全に無視することができます、非常にまれにあなたはそれらを必要とします

-最適化は非常に便利です。特に機械学習では、単なる鉄壁です

-代数、トポロジーなど-一方では、これは非常に便利ですが、他方では、直接適用せずに数学的に、抽象的に研究する価値がないと思われます-必要なときにそれを習得できます（たとえば、関係代数や型システムのカテゴリー理論）そして、必要な特性と原則はすでに実践と併せて研究されています

-論理、集合論-基本を理解する必要があると思います。 ZFCを服用する必要があります。

-確率論、統計-最小限の古典数学から、機械学習の文脈でコンピューターサイエンスに必要なものを学ぶことをお勧めします。さもなければ、特に有用ではない何かを掘り起こす危険があります。

-ゲーム理論は有用なものですが、長い間表面的な知識で十分です

-機能分析、変分法-非常にクールですが、機械学習などでロックされている場合にのみ学習します

-数値的手法-後で対処したい場合のみ



それ以外はすべて数学ではなく、コンピューターサイエンスであるか、必要ではありません（特定のケースで必要になるまで）

プログラミング言語

論争のトピック、多くの選択肢があります、私はそのような最小限の紳士のセットを提案します：



-アセンブラ-独自のコンパイラを作成する必要があるため、何らかの種類のアセンブラを所有する必要があります。 いくつかのオプションがあります：

• RISCは良いことですが、どこで入手するか、エミュレートするだけではあまり便利ではありません。 ただし、環境をセットアップする場合は、RISC
• LLVMは便利ですが、100％の鉄ではなく、多くのことが簡単になります。
• x86はひどいですが、ラップトップでgcc -Sを使用すると本当に便利です。
• JVMバイトコード-生成しようとしませんでした。おそらく便利な方法があります。 ただし、後でJVMを使用する場合は、非常に便利です。

-C ++ / Java-残念ながら、システムプログラミングでこれらから遠く離れることはありません。 しかし、最大限にそれらなしで行う必要があります。

Python

-Scalaは実用的な関数型言語です。必要に応じて、ハードウェアに十分に近づくことができます。 多くのシステムのことは既にScalaで書かれています。 それが主力になるはずです。



（SQL、Prolog-当然ですが、これらは小さなリードです）



始めましょうか？

学部

コースは1四半期-3か月と見なされます。 すべての入門プログラミングコースをスキップします。



1.離散数学（これはもはや数学ではないことを忘れないでください）

組み合わせ論、グラフ理論、離散ター。 Ver。、再帰関係、ジェネレーター関数。



実際、これは通常最初のコースです。たとえば、MITでオンラインで見ることができます。

ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-math-s-for-computer-science-fall-2010



これはすべてスキップして、他のコースで習得することができます（時間が迫っていないため）。 そして、それは退屈になる可能性がありますが、それは悪いです。



2.アルゴリズムとデータ構造

すべての種類、ハッシュテーブル、さまざまなツリー、グラフ上のアルゴリズム（ジクストラ、最小カット/最大フロー）から開始します。

概念的知識による：O表記法の複雑さの評価、貪欲、動的プログラミング。

追加トピック：線形計画法、文字列アルゴリズム、ランダムアルゴリズム。

複雑性理論の最初の原則。



本： www.amazon.com/Introduction-Algorithms-Edition-Thomas-Cormen/dp/0262033844



動的プログラミングは遍在し、木を理解する必要があり、ソートの下限を推定できる必要があります。 純粋に理論的なコースであり、教科書には問題があります。 一般に、非常に単純に、それほど時間はかかりません。



PSアルゴリズムは各分野でさらに進んでおり、大学院プログラムでのみ一般コースに戻ります。

しかし、あなたはすぐにランダムなアルゴリズムに関する本を勧めることができます（最近、同僚はこれまでのところひっくり返しただけですが、それは非常に有能だと思われます）、それは大学院レベルですが、あなたは早くダイビングを始める必要があります： www.designofapproxalgs.com/index.php



3.コンピューティングの理論

ここでは、一般的に優れた本であるSipserを宣伝しています。必読であり、大学院プログラムにも適しています。

www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X



これは非常に重要なコースであり、他のすべての基礎を築きます。 Sipserでは、すべてが非常に直感的で、論理的で、接続されています。 （最近、コルモゴロフをめくってみました-すぐに、Mehmatレベルなしにしない方が良いことが明らかになりました。それに対して、Sipsterには、最小限の要件、最小限の形式化、最も必要なもののみがあり、すべてが非常にアクセスしやすくなっています）。



「タスク」の定義から始めます-Sipserでそれは言語です。 それはたくさんの行です。 アルゴリズムは、任意の文字列を言うものです-はい/いいえ。 この概念はすべての作業です。 さらに、言語の階層：通常、コンテキスト非依存、計算可能、列挙可能、計算不可。 複雑さも非常によく示されています-P、NP、NP完全、NPハード、co-NP +ランダムクラス。



優れた理論的トレーニングに加えて、優れたスキルが得られます。

有限状態マシンとレギュラーで動作します

私たちは文法とスタックを備えたマシンで作業します

私たちはチューリングマシンでプログラムを作成します-それは本当に必要で、クールで、意識を広げます。

ブレークポイントがあっても、ここでマシン上でプログラムできます！ morphett.info/turing/turing.html

どの問題が解決できないか、最も便利で最速の方法で証明することを学びます。

私たちは削減で遊びます-あるタスクを別のタスクに移す-また、意識を大きく広げます



コースは純粋に理論的で優れたタスクであり、アスタリスクで脳を破壊することができます

たとえば、テープ上の入力文字を書き換えることが禁止されている場合、チューリングマシンが電源状態マシンになることを証明します。



4.数学的論理と集合論

通常、コンピューターサイエンスには含まれていませんが、マスターする必要があると思います。 私はこの本から学んだ、非常にシンプルな本、非常に楽しい：

www.amazon.com/Elements-Set-Theory-Herbert-Enderton/dp/0122384407



これで、学部のコンピューターサイエンスの純粋に理論的な準備が終わりました。

5.コンパイラ（2四半期）

本： en.wikipedia.org/wiki/Compilers ：_Principles、_Techniques、_and_Tools



計算理論から多くのことがすでに学ばれています;ここでは、全体が実践に重点を置いています。 私たちの仕事は、本格的なコンパイラーを本格的な言語からアセンブラーにすることです。 たとえば、 en.wikipedia.org/wiki/Object-Oriented_Turingが与えられましたが、もっと面白いことが可能です。



-解析：ここでは、JavaCCやANTLRなどの合理的なものを使用する必要があります。

-ASTへの翻訳

-セマンティック分析：軽いが、型システムと混同される可能性がある

-コード生成



時間と労力があれば-ここに中間言語と少し簡単な最適化を追加してください。



その結果、コンパイラの動作、関数呼び出しの実装方法、オブジェクト、メソッド、配列などの作成方法を完全に理解しています。



注：すべてをC ++で記述する必要がありましたが、現代の世界ではこれは教育目的には絶対に必要ではありません。 一方、コンパイラーがPythonまたはScalaで記述している場合（ANTLRはpythonで動作しますが、それが何であるかわかりません-誰かが良いツールを知っているなら、教えてください。最小の損失ではるかに興味深い。



6.アーキテクチャ

本： www.amazon.com/Computer-Architecture-Fifth-Edition-Quantitative/dp/012383872X



さて、それは-読むこと、パズルをすることです。 ただし、可能であれば、ミニCPUを設計することをお勧めします。

次のようなもの： www.logiccircuit.org



7.高度なデータ構造

良い本がここにあるかどうかはわかりませんが、ディスクにインデックスを作成しておくといいでしょう。

-Bツリー

-線形ハッシュ

-Rツリー



ここではすべてが困難です、C ++。 しかし、データベース/検索エンジンを構築したくない限り、気にすることはできません。



8.オペレーティングシステム（2四半期）

ここに私はこのアプローチを持っています-本を読んでください： www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720ですが、一般的な概念のみです。 しかし、実際にこの方法でOSを習得してください：



Nachos： en.wikipedia.org/wiki/Not_Another_Completely_Heuristic_Operating_System （またはNachos 5.0j）を使用して、モジュールを記述します。

-同期のプリミティブ

-ストリームライブラリ

-マルチプロセッシング

-ミニシェル

-仮想メモリ

-ファイルシステム



注：これはもちろんかなりハードコアですが、それだけの価値があります。 Nachos 5.0jを使用して仮想メモリをデバッグする方がおそらく良いでしょう。メモリの問題自体はあまり快適ではありません。



このような演習の後、オペレーティングシステムに関する謎はなくなります。



9.データベース（2四半期）

本を読む： www.amazon.com/Database-Systems-Complete-Book-Edition/dp/0131873253

次のプロジェクトを実行します。時間が短い場合、SQLエンジンを単純なリポジトリの上に記述します。MySQLのように、ASTを起動します。 さらに時間があれば、関係代数に変換し、いくつかの最適化（いくつかのルールベースの最適化）を追加します。



注：繰り返しになりますが、一度にすべてをC ++ / lex / yaccで行う必要がありました。 時間が先に進んでいます。PythonまたはRockで行った場合、より少ない損失でより多くのことができます。 または、OQLやSQL ++など、より興味深いクエリ言語をすぐに使用してください。



10.人工知能

AI-私の目では、常に非常に複雑な問題を解決するため、コンピューターサイエンスで最も興味深い分野であり続けています。 この場合、何かがうまくいくとすぐに、それはAIでなくなり、別の分野で際立っています。 一般的に、私たちは素晴らしい本を読んで、2〜3つのプロジェクトを行います。

www.amazon.com/Artificial-Intelligence-Modern-Approach-Edition/dp/0136042597



推奨プロジェクト：

-8人の女王またはその他のタスク、ヒューリスティックをいじくり回すタスクの検索

-証​​明定理証明

-ベイジアンネットワークの効果的な結論を出す

-Alainの一時的なロジックを実装する

-チェッカーをプレイしたり、ミニマックスチェスをプレイしたりする（ツリーを数える）自己学習



ハードコア：確率的グラフィカルモデルコースのすべてのタスクを実行できますが、これは大学院レベルに向いています。



11.機械学習

現在、このトピックなしには方法がありません。 どのチュートリアルが学部生に最適かわからないが、理想的にはビショップを学ぶ：

www.amazon.com/Pattern-Recognition-Learning-Information-Statistics/dp/0387310738



スタンフォード大学の学部生向けのAndew Ngクラスは、完全に異なるレベルのKurserのクラスと混同しないでください。

cs229.stanford.edu



また、YouTube（mathematicalmonk）ですばらしい講義を見つけました： www.youtube.com/playlist?list=PLD0F06AA0D2E8FFBA



12.コンピューターグラフィックス

本当に必要なわけではありませんが、すべてのプログラマーはかつて自分のゲームを書きたいと思っていたので、ファンとビールを飲みながら話すためにそれを受け取らなければなりません。

良い本が今何であるかわからない。

CでOpenGLの一部を作成しました。これは非常に便利です。すべての3Dエンジンがどのように機能するかを示しています。

独自のRay-Tracerを作成することもできます-これも素晴らしいことです。



13.コンピューターネットワーク

このコースを逃しましたが、Kurserにはとても良いコースがあります

www.coursera.org/course/comnetworks



14.分散システム

オペレーティングシステムと強力に交差しますが、それらの重要なチップの多く。

特定のシステムではなく、本、特に重要な概念を読むだけです。

www.amazon.com/Distributed-Systems-Concepts-Design-Edition/dp/0132143011



同期、グローバルシステム状態、コンセンサス、トランザクションなど。 あらゆる種類のMPPシステムが非常に人気になりました。ここに、それらの基礎となる基本を示します（または、そうではなく、あらゆる種類のファッショナブルなデータベースに関する人気記事を準備しています）。



15.プログラミング言語

このようなコースはしばしば遭遇しますが、通常は時間の無駄です。 この時点で、TuringおよびSQL用のコンパイラが作成されました。すべてが明確です。 HaskellやMLのようなものと混同される可能性があります。 オプションとして、意識を少し拡大するためにXQueryを学んでください。



その後、私は学部課程を修了します。修士号を取得しました。おめでとうございます。



または、セキュリティ/暗号化、科学的プログラミング、AIのドリル：計算言語学など、広範囲に進むことができます。 そのようなプログラムの後には何がありますか？ 安全に仕事に行くことができますが、理論的根拠にはまだギャップがあります。 あなたはすべて自分で記入するか、M.Scで勉強を続けることができます。



卒業生



コンピュータサイエンスの大学院研究は、私たちの大学院研究ではありません。 ここでは、数年間勉強を続け、5つの分野の博士号の場合、包括的な試験に合格します。つまり、現時点では非常に深刻な基盤を念頭に置く必要があります。 非常に有用な演習（私は修士課程で3番目を取りましたが、はるかに簡単です）。



そして、専門化は非常に迅速に始まります。 しかし、基本を理解しましょう。



1.アルゴリズム

学部と同じ、実際の、より深い、そしてランダム化のみ。

ここに、それがあったように、普遍的に認められた本はありません、私はあなたが大学のウェブサイトに登ることを勧めます。 つまり、多くの費用のある記事、スライドなどです。

ランダムアルゴリズムがすべてです。 だから本を開きます： www.designofapproxalgs.com/index.php



2.計算理論、本質的に純粋な複雑性理論

Sipserをカバーして、他の何かを読んでみてください。 パパディミトローがありましたが、これは確かに弱い人向けではありません。 ここでは主にNP完全である削減を使用しますが、現在ではランダムクラスに多くの削減があります。



また、ロジックが好きな場合は、記述の複雑さを読むのが理にかなっています： people.cs.umass.edu/~immerman/book/descriptiveComplexity.html



3.アーキテクチャ

同じ本ですが、成人向けです。 ある種の高度なCPUを構築できます。



全般的なさらなる専門化。 私はそのような領域をお勧めしますが、これはすでに私のバイアスです：



4.機械学習

大学院レベルでは、ビショップ（彼はまだすべてを完了していません）、および機械学習の理論を取ることができます

古き良き時代が好きです： www.amazon.com/An-Introduction-Computational-Learning-Theory/dp/0262111934

しかし、おそらくもっと関連性の高い本がすでにあるでしょう。



そして、あなたはカーソルを掛けることができます：

-確率的グラフィカルモデル

-コロンビア大学の別の非常に優れた自然言語処理コース

-最新のニューラルネットワーク： class.coursera.org/neuralnets-2012-001



5.データベース理論

www.e-booksdirectory.com/details.php?ebook=7942

これは非常にエキサイティングな分野であり、可能なすべてがここに混在しています：論理、モデル理論、複雑さ、記述的複雑さ、ゲーム理論さえも活用されています。 この本はかなり重く形式的ですが、それだけの価値があり、少なくとも選択的に読んで演習を行ってください。



何が欠けていますか？

正式な方法についてはまったく何もありません。まあ、難しいことがあります。 理論的には、集合論、人工知能、データベース理論+記述の複雑さの間-検証と証拠のためのすべてのツールがあるため、このコースはすでに純粋に適用されるべきです。 あなたがそのようなコースの経験がある場合、知ることは非常に興味深いでしょう。



インターネット数学-まあ、これは少し別のトピックでもありますが、基礎はすべて整っています。



ここに来て、プロジェクトを行って問題を解決すると、すべてがM.Scのレベルに到達したと想定できます。 世界のトップ大学レベルのコンピューターサイエンスで。



テストに合格しましょうか？



Computer Science Comprehensive Examまたはこのようなものを検索して、実際のM.Sc.試験を見つけることができます。 と博士号



通常はあまり分散されていないので、もう一度飛び出さないように、リンクを広げないことにしました。



PSそれだけです。 おそらく古いものがありますが、基本は常に適切です。



PPSもちろん、自宅でソファに座って、そのようなプログラムを習得することは困難です。 演習や大きなプロジェクトを行うことは特に困難です。 大学の環境がなければ、それも非常に困難です（しかし、大学では難しいこともあります-実験室での夜は私的な現象です）。 しかし！ -すべてが可能です。 これらの本はすべて（まあ、ほぼすべて）できるだけシンプルに書かれており、最小限の事前知識が必要です。習得した知識をどのように適用するかをすぐに示します。 カーソルを使ったコースや大学からの講義を録音することも非常に便利です。講義を見るには、本を読んだり問題を解決したりするよりもはるかに少ない労力で済みます。



「すべてを忘れた」専門家向けのPPPSのヒントはニッチに詰まっていますが、再び最先端に行きたいと思っています。彼はそれを自分で経験しました。脳混濁があり、すべてが失われ、希望はありません。 しかし本質的に、これは数年のジャンクフードの後に​​スポーツを始める方法です-私たちは小さなことを始め、短い目標を設定し、最小の進歩を楽しみ、十分にすべての式が再び明らかになり、世界の全体像が再び構築され、再び学生/大学院生のように感じることができます。



大学のサイト：



スタンフォード： cs.stanford.edu

MIT： www.eecs.mit.edu

UCバークレー： www.cs.berkeley.edu

UCサンディエゴ： cs.ucsd.edu （私の母、まあ、まだ＃4ではなく、毎年忍び寄っています！）