アルゴリズムと数学の本を書きました
1. はじめに
こんにちは、はじめまして。東京大学 1 年生の米田優峻(E869120)と申します。私は競技プログラミングが趣味で、AtCoder や国際情報オリンピックなどの大会に出場しています1。2021 年 11 月時点で、AtCoder では赤色(レッドコーダー)です。また、2020 年以降、アルゴリズムを学べる以下のようなコンテンツや資料を作成してきました。
さて、このたびは技術評論社から、書籍を出版させていただくことになりました2。アルゴリズムと数学が同時に学べる新しい入門書です。
発売日は今年のクリスマス、2021/12/25 です。電子書籍版も同時期に出る予定です。本記事では、この本の内容と想定読者について、簡単に紹介させていただきます。
2. 本書の特徴
Amazon の商品ページにも書かれていますが、本書には以下の 5 つの大きな特徴があります。
- 本書は有名なアルゴリズムの紹介に終始せず、それに関連する数学的知識、そしてアルゴリズム効率化に応用可能な数学的考察も解説している。
- 手計算問題・プログラミング問題合わせて全 200 問の例題・演習問題が掲載されており、知識がしっかり身につきやすい。
- プログラミング問題の 8 割以上について、自分のプログラムが正しいかどうかを自動で採点するシステムが提供されており、演習が進めやすい。
- 多数の図(計 250 個以上)を用いるなどして、初学者でも読みやすい工夫を施している。
- C++/Python/JAVA/C のソースコードを用いて解説している。
特に 1. については、アルゴリズムに関する書籍のほとんどが高校数学の履修を前提としているか、多くのアルゴリズムを表面的になぞるにすぎないかのいずれかであることから、本書最大の特徴であると考えています。
なお、5. についてはページ数を抑えるため、紙面に掲載されているソースコードは C++ のみになっています。しかし、本書に対応している GitHub ページには 4 つの言語すべての解答例が掲載される予定です。
3. 本書の構成について
本書は以下の通り全 5 章(+ 最終確認問題)から構成されます。長さは 約 280 ページ です。
以下、それぞれの章の内容について、簡単に記します。
第 1 章・第 2 章
まず、第 1 章ではアルゴリズムとは何かを解説し、アルゴリズムと数学の関係について簡単に記します。第 2 章では、アルゴリズムを学ぶために必要となる、文字式・2 進法・指数関数・対数関数・ランダウの O 記法をはじめとする数学の前提知識を解説します。
第 3 章・第 4 章
第 3 章・第 4 章では、二分探索・ソート・モンテカルロ法・動的計画法・深さ優先探索・幅優先探索・ユークリッドの互除法・エラトステネスのふるい・ニュートン法などの有名なアルゴリズムを扱います。また、関連する数学の知識は、必要になったときに図を用いて解説します。扱うアルゴリズムと数学的知識については、「本書で扱うコンテンツ」をご覧ください。
第 5 章
第 5 章では、アルゴリズムの問題における典型的な考察パターンを紹介します。数学的考察といえば競技プログラミングを思い浮かべる人がいるかもしれませんが、本書では競技プログラミング参加者以外にも知っていただきたいものを 10 個程度のポイントに分けて整理します。多くの読者にとって、最もたのしい章でしょう。
最終確認問題
最後に、全 30 問の最終確認問題で、本書で扱った内容を振り返ります。
本書で扱うコンテンツ
本書で扱うアルゴリズム・数学的知識・数学的考察は次の通りです。数学的知識に関しては、中学レベル~大学教養レベルの範囲の中から、アルゴリズムに必要なところだけに絞って解説されています。(280 ページに分かりやすくまとめるため、データ構造はあまり多く扱っていません)
4. 本書の対象読者
数学が苦手な人も、そうでない人も利用できるものを目指して本書を作成しました。たとえば、以下のようなターゲット層を想定しています(もちろん、これだけではありません)。
- まだ数学を一通り修了していない中高生の方
- 数学に苦手意識があるけれど、この機に数学とアルゴリズムを学び、プログラミングなどに応用できるようにしたい方
- 数学は苦手ではないが、これまでに学んだ数学の知識と関連付け、応用可能な形でアルゴリズムを理解したい方
- 競技プログラミングの実力を上げたい方
5. 競プロ参加者向け補足
本書の難易度を類書と比べると、以下のようなイメージだと考えています。しかしながら、本書はほかのアルゴリズム本とは異なり、数学的な事柄についても記されているため、人によって意見が分かれると思います。
アルゴリズム図鑑 << チーター本 << 本書 < PAST 本 < 螺旋本 <= けんちょん本 < 典型 90 問 << 蟻本
また、競プロ典型 90 問 や その書籍版(2022 年 5~6 月頃出版予定) の方が難易度や網羅度が高いです3。本書で基礎的な数学的知識とアルゴリズムの知識を得てから、典型 90 問に挑戦するのもアリです。
6. おわりに
本の執筆はとても大変な試みであり、時間数にして約 800 時間をかけることになりました4。しかし、本の原稿を丹念に読み、たくさんの指摘をくださった 10 名以上の reviewer を含め、とても多くの方々にお世話になりました。本当にありがとうございます。
また、私は「日本情報オリンピック」という大会をきっかけにアルゴリズムを本格的に学び始め、プログラミングコンテストサイト「AtCoder」に参加することで自身のスキルに磨きをかけることで、最終的に本を書けるレベルまで至りました。このような環境には感謝しております。そして、これまでの私の活動を支えてくださった競プロコミュニティには大変感謝しております。
最後に、本書を通して、何か一つでも有益な知識を得られれば、筆者としては本当に嬉しいです。