学童向けアルゴリズム:初心者からオリンピックメダリストまで

モスクワ物理技術研究所の学生であり、 アルゴリズムコースの教師であるPavel Dubovによる記事を公開しています 1Cでのオリンピアードプログラミングプログラマーのクラブであり、オリンピックチームのコーチです。



画像



遅かれ早かれ、IT専攻のためにまともな大学に入学しようとする学生には、疑問が生じます。 もちろん、最も平凡な答えは、試験の準備をすることであり、重大な瞬間の間違いを避けるために、狂気の自動化に自己制御をもたらします。 しかし、別の方法があります。それは、自分自身に追加のチャンスを与えるだけでなく、良い会社で仕事を得るために必要なスキルを習得することも可能にします。



これは、アルゴリズムプログラミングを学習する方法です。 上記のすべてに加えて、非常にエキサイティングで楽しいです。



現時点では、コンピューターサイエンスにはいくつかのレベルのオリンピックがあります。 「最高」レベルにあるのは、学童向けの全ロシアのオリンピックです。 このオリンピアードで卒業証書を取得すると、試験なしで、対応するプロフィールの大学への参加者が入学することが保証されます。 他のレベルのオリンピックは、大学によって異なりますが、試験なしで入学するか、コンピューターサイエンスの試験で100点を獲得できます。 このようなメリットを得るには、試験自体で最低スコアを獲得する必要があります。通常は65ポイントです。これは、一般的に卒業証書を受け取っても難しくありません。 レベルごとのオリンピックの分布は、教育科学省がインターネットで毎年公開しています。 オリンピックがいくつかあるため、成功を数回試みることができ、タスクを簡素化できます。







それでは、準備を始めるために何が必要ですか?



最悪の場合-忍耐の海、そのような分野の多くのことは「口頭で」伝えられます、そして花崗岩の要塞だけで勇敢に突進することを決心した勇敢な男は、勉強の道に沿って非常に滑り落ちる危険があります。 コードの量と潜在的なエラーを減らすいくつかのトリック、アイデア、およびテクニックは、単に文書化されていません。 学習の順序も重要です。たとえば、グラフトラバーサルアルゴリズムを理解する方がはるかに簡単で、再帰とは何かを理解できます。



環境は、学習においても同様に重要な役割を果たします。 第一に、志を同じくする人々の間で、学ぶことはより興味深いです、友人は元気づけて、そしてプロンプトすることができます。 第二に、チームを結成して、チームコンテストに参加することもできますが、それはメリットをもたらしませんが、それでもなお、非常に面白くて便利です。 そして、学生団体では、すでにチームOlympiads ACM-ICPCに参加できます。このチームの勝者は、多くの有名な企業がすぐに契約を提供します。



画像








構造化された素材と良い会社を組み合わせたい人のために、1C:プログラマーのクラブ( http://club.1c.ru )があります:あらゆるレベルの知識を持つ人が自分にふさわしいコースのシーケンス。 Javaのアルゴリズムコースに加えて、産業用Java、システム管理、プロジェクト開発管理のコースもあります。



アルゴリズムの研究は、アルゴリズムの開始モジュールから始まります(各モジュールは6か月間、週に1回、休憩付きで2時間、クラスがあります)。これは、プログラミングの経験がない人向けです。 ここでは、算術演算、条件演算子、サイクル演算子と関数、テストシステムの問題の解決策を渡す方法など、基本を詳細に研究しています。



次に、取得したスキルが統合され、NOD / NOC、配列と並べ替え、行、スタックとキュー、グラフと回避策、動的プログラミング法など、取得したスキルが統合された第1モジュールと第2モジュールが続きます。



3-4モジュールは、深刻なオリンピックでよく使用されるツールの準備を目的としています:コンビナトリアル生成、最大増加/合計サブシーケンス、グラフアルゴリズム、ゲームの合計、バイナリ検索、計算幾何学、凸包、バイナリヒープ、セグメントツリー、ハッシュ。



もちろん、Startモジュールに正確にアクセスする必要はありません。基本的な言語構造があれば、すぐにFirstから開始できます。 1つ目または2つ目が退屈で理解しやすいと思われる場合は、スキップできます。



基本クラスが十分にない人には、4時間の特別料金がかかります。特定の競技の準備、問題解決の手法と認識方法の磨き、アイデアやアルゴリズムの非標準的な適用などです。



私は3〜4モジュールのグループで作業し、トレーニングを実施しています。



通常、モジュールのクラス3〜4は次のようになります。最初に必要な理論を分析し、次に問題を解決してテストシステムに送信します。 ほとんどの場合、約10のタスクがあります-最も単純なタスク(必要なスキルを開発するためのもの)からオリンピアードのレベルまで。 同時に、記述中にコードを見て、プロセスが正しい方向に進んでいることを確認し、配信後に、将来のソリューションの開発を高速化または簡素化するヒントを提供します。



画像








トレーニングキャンプでは、実際の競技会の状況をシミュレートします。問題をほぼ継続的に解決する必要がある時間を考えます。 当然ながら、私はいくつかのヒントを述べていますが、それらはほとんどイデオロギー的な性質のものであるか、ツアーでより正確に動作するのに役立ちます。 終わりに、私たちは要約し、ソルバーの1人が各タスクを指示し、未解決のタスクを指示します。 ストレステストや標準ライブラリの使用など、モジュールでカバーされていない重要なトピックにクラスを捧げることもあります。



トレーニングキャンプのメンバーには、1つのタスクがありません。たとえば、今年2人はオールロシアンオリンピックの最終ステージの準備をしており、大部分はモスクワオリンピックの準備をしていました。モスクワオリンピックはグレード7-9および10-11のバージョンで開催されます その結果、各コンペティションで賞を獲得することができました。



画像








課外活動の期間には、クラブは自分自身の生活を送っています。映画館への旅行や遠足が手配されます。 そして私は通常、その日の最後のグループの人と一緒に歩きます。



彼らは私に何かを教えてくれることがあります:例えば、セグメントのツリーを書くときに±1を取り除く方法、最もおいしいホットドッグまたは何年にMarie Antoinetteが生まれたのか。 だから退屈することはありません。



秘密は何なのかわかりませんが、クラブはとても家庭的です。 友達、カウンターストライクチーム、ボードゲームの会社を見つけるか、2人のハッカソンを手配してクラスメートとマリオを作りましょう。



そして誰も空腹のままではありません。 これはおそらく、このような雰囲気の理由の1つです。ソーシャルネットワークフィードをめくって時間を過ごすことと、スマートフォンを片付けてサンドイッチを食べ、クッキーでお茶を飲むことです。 ここで必ず誰かに会います!



画像







All Articles