サンクトペテルブルクでは、コンピューター科学者がコンピューター科学の理論家を作る素晴らしい場所があります。 これは、ロシア科学アカデミー（AU RAS）の学術大学です。
その瞬間、私がAUの数学および情報技術学科の理論学科に入ったとき、学科には2人の卒業生が1人しかいませんでした。 現在、アカデミックユニバーシティはすでに名声を得ています。 彼の卒業生は市の一流企業で働いており、彼は他の都市からの学生を受け入れて、彼らに住居を提供します。
しかし、私の例では、どのような興味深く深遠な問題を調査できるか、そしてあなたが理論学部の学生になった場合にどれだけ興味深く学ぶことができるかを伝えたいと思います。
AUでの私の研究
AUの理論部門では、修士論文を書くために真剣な研究が必要です。 リーダーは、同時に出版物を入手しようと非常に懸命に努力しています-これはすでに非常に魅力的です。
私の仕事はDmitry Mikhailovich Itsykson（POMI RAS）が監督し、最適なアルゴリズムの研究に専念しました。 これは非常に興味深いトピックですが、説明が簡単であるという点でも注目に値します。今、私はそれを試みます。
やる気
NPの完全な問題、たとえば、実行可能な式の言語を見てみましょう。 任意の式で停止し、答えとして1ビットを返すアルゴリズムを検討します。式は実行可能かどうかです。 今から40年間、このアルゴリズムセットの中に多項式があるかどうかが質問されており、まだ誰も答えることができません。 ただし、この問題に最適なアルゴリズムがあるかどうか、別のおそらく簡単な質問を尋ねることができます。これは、多項式まで他のすべてのアルゴリズムよりも高速に動作するアルゴリズムです（アルゴリズムの多項式にのみ関心があるため）。 そのような最適なアルゴリズムが存在すると仮定し（ Aと呼びましょう）、 NPが Pと等しくないのは 、 Aが多項式でない場合だけです。 問題を解決する可能性のあるすべてのアルゴリズムに対してこれを行うのではなく、特定のアルゴリズムの非多項式性を証明する必要があるため、これはすでに何かです。
別の例を見てみましょう-co-NPでは、完全な問題、たとえばトートロジーの言語（どこでも有効な式）。 トートロジーの証明システムは多数あります。解決方法、割線システム、フレージシステムなどです。多項式サイズの証明を持つ証明システムの存在の問題は、クラスNPとco-NPの等価性の未解決の問題に相当します。 実際、特定のエビデンスシステムを比較し、それらの低い評価を見つけることに多くの人々が関与しているのは驚くべきことです。 最適なエビデンスシステムがあれば素晴らしいのですが、それだけでそれを研究すれば十分でしょう。
したがって、これらの質問は両方とも、修士論文に最適なアルゴリズムを研究する動機となり、この方向で本当に興味深いことがありました。
過去の研究
1年前、D。ItsyksonとE.A. Hirschは、列挙された言語に最適な発見的確率的半アルゴリズムの存在を証明しました。
- 準アルゴリズム-解決アルゴリズムの半分-言語からの入力で1に応答し、他の入力で停止しないアルゴリズム
- 確率的-アルゴリズムはランダムビットにアクセスできます（正直なコインを投げることができます）
- ヒューリスティック-アルゴリズムは小さな（制限された）エラーを引き起こす可能性があり、このエラーは操作時間を増やすことで任意に小さくすることができます。
当然、より弱い計算モデルに最適なアルゴリズムを構築したいと考えています。 第一に、アルゴリズムが与えるエラーを取り除き、第二に、確率的ではなく決定論的とすることです。 後者の変換はランダム化解除と呼ばれ、多かれ少なかれこのための標準的な方法があります。 私はそれらを実践に移そうと誘われました。
結果
ランダムビットを使用する代わりに、入力からランダム性（エントロピー）を抽出する必要があります（他に行く場所がないため）。 これは、2部構成の「混合」グラフ（ルックアップテーブルのようなもの）を使用して行うことができます。左ローブでは入力によってインデックスを作成し、右ローブからの多くの隣接する頂点から多くの擬似ランダムビットを取得します。
グラフに必要な条件を定式化する最初の試みの後、一般的にこれを行うことは不可能であることに気づいたため、より単純なケース、つまり入力を1ビット増やす単射関数の画像セットの言語を検討することにしました。 ここで、読者（ここに来た読者がいる場合）は正当なinりを持つべきです：「誰がそのような言語を気にしているのですか？」 ただし、擬似ランダムジェネレーターに興味があると仮定します（入力を1ビット増やす信頼性の高い単射ジェネレーターの存在は未解決の問題です）。 次に、「指定された（彼に）番号がジェネレーターによって生成されたというのは本当ですか？」という最適なアルゴリズムを取得します。 この最適なアルゴリズムが多項式であることが判明した場合、ジェネレーターを「ブレーク」します。 生成する数字とランダムな数字を区別します！ ほぼすべての既存の暗号システムに対する攻撃が見つかるため、非常にクールです。
そのため、この場合、ランダム化は成功し、さらに、最適なヒューリスティックセミアルゴリズムだけでなく、完全なアルゴリズムで補完しました。
私の研究は論文と理論計算機科学の素晴らしい分野を離れないという大きな願望で終わりました。そこではまだ多くの未解決の問題と未解決の問題があります。
大学院に進学する5つの理由...
...理論的なコンピューターサイエンスを行いたい場合：
- AUはサンクトペテルブルクで唯一の場所であり、ロシアでは数少ないコンピューター理論の研究に専念できる場所の1つです。
- 元気で、紛れもなく才能のある科学者がAUで働いています。
- AUでは、生徒はカリキュラムに影響を与え、希望するコースの一部を選択できます。
- AUは、外国の学校を含む学校への旅行を後援しています。
- AUでは、素晴らしいエスプレッソマシンから無料のコーヒーを見つけることができます！ （そのため、定理に処理するものがありました）。
AUを卒業した後はどうすればいいですか？
私はスタンフォード大学で理論計算機科学を続けています。 前の四半期では、Dan Bonehで暗号化されたデータの計算を行っていましたが、今度はRyan Williamsで回路の複雑さに対処します。
だから、私のアドバイス-それのために行く、それは試してみる価値があります！ 申請書は今すぐ提出できます。