Python で学ぶアルゴリズムとデータ構造

現代社会を支える根幹技術を Python で! Python プログラミングのスキルアップにも最適!

名著『Python スタートブック』の著者である辻真吾氏が書き下ろす至極の入門書! ソートやグラフ構造など基本的な内容から、乱択アルゴリズムや数論、ブロックチェーンの仕組みなどの幅広い話題までを解説。コードは Web 公開 (
https: / / github.com/tsjshg/pyalgdata)。

【データサイエンス入門シリーズ】
第 2 期として、以下の 2 点を同時刊行!

『統計モデルと推測』松井秀俊・小泉和之 (著) 竹村彰通 (編)
『Python で学ぶアルゴリズムとデータ構造』辻真吾 (著) 下平英寿 (編)

第 3 期の刊行は 2020 年 2 月の予定 (^o^)/

【「巻頭言」より抜粋】
文部科学省は「数理及びデータサイエンスに係る教育強化拠点」6 大学 (北海道大学、東京大学、滋賀大学、京都大学、大阪大学、九州大学) を選定し、拠点校は「数理・データサイエンス教育強化拠点コンソーシアム」を設立して、全国の大学に向けたデータサイエンス教育の指針や教育コンテンツの作成をおこなっています。
本シリーズは、コンソーシアムのカリキュラム分科会が作成したデータサイエンスに関するスキルセットに準拠した標準的な教科書シリーズを目指して編集されました。またコンソーシアムの教材分科会委員の先生方には各巻の原稿を読んでいただき、貴重なコメントをいただきました。
データサイエンスは、従来からの統計学とデータサイエンスに必要な情報学の二つの分野を基礎としますが、データサイエンスの教育のためには、データという共通点からこれらの二つの分野を融合的に扱うことが必要です。この点で本シリーズは、これまでの統計学やコンピュータ科学の個々の教科書とは性格を異にしており、ビッグデータの時代にふさわしい内容を提供します。本シリーズが全国の大学で活用されることを期待いたします。
ーー編集委員長 竹村彰通 (滋賀大学データサイエンス学部学部長、教授)

【推薦の言葉】
データサイエンスの教育の場や実践の場で利用されることを強く意識して、動機付け、題材選び、説明の仕方、例題選びが工夫されており、従来の教科書とは異なりデータサイエンス向けの入門書となっている。
ーー北川源四郎 (東京大学特任教授、元統計数理研究所所長)

国を挙げて先端 IT 人材の育成を迅速に進める必要があり、本シリーズはまさにこの目的に合致しています。本シリーズが、初学者にとって信頼できる案内人となることを期待します。
ーー杉山将 (理化学研究所革新知能統合研究センターセンター長、東京大学教授)

『Python で学ぶアルゴリズムとデータ構造』 (辻 真吾 著、下平 英寿 編、講談社、2019 年 11 月刊) は、アルゴリズムとデータ構造の基本を Python のコードで学ぶ、大学の学部教育向けの教科書です。講談社サイエンティフィクの「データサイエンス入門シリーズ」の一冊で、版元は教科書としての利用を想定した書籍と案内しています。著者は『Python スタートブック』の著者でもあり、本書のコードは GitHub で公開されています。ソートやグラフといった基本から、乱択アルゴリズムや数論、ブロックチェーンの仕組みまでを扱う範囲の広さが特徴です。

データサイエンス教育の教科書シリーズとしての位置づけ

シリーズの巻頭言によれば、データサイエンス入門シリーズは、文部科学省が選定した教育強化拠点の大学が設立した数理 / データサイエンス教育強化拠点コンソーシアムのスキルセットに準拠した、標準的な教科書を目指して編集されています。本書はその第 2 期として『統計モデルと推測』と同時に刊行されました。統計学と情報学の両方を基礎とするデータサイエンスのうち、情報学の側にある計算の考え方を担う巻と読めます。データを扱う人にとって、同じ処理でもアルゴリズムの選び方で実行時間が桁違いに変わることを知っているかどうかは、扱えるデータの大きさを直接左右します。

Python 入門から動的計画法まで、前半から中盤の章立て

目次は全 10 章です。第 1 章で Python の文法と実践的なプログラミングを確認し、第 2 章でコンピューターの基本原理、配列で見るデータ構造、計算量 の考え方という土台を置きます。第 3 章と第 4 章はソートを題材に、素朴な配列のソートから問題を分割する考え方、クイックソートへと改良を重ねます。第 5 章は探索で、配列の探索、探索のためのデータ構造、ハッシュを使った探索を扱います。第 6 章はグラフの表現方法から グラフ探索 のアルゴリズム、最短距離を求める方法までを、第 7 章は問題を解くための技術として 動的計画法 を取り上げます。

ソートを 2 章にわたって改良していく構成には、技術的な意味があります。単純なソートは要素数の 2 乗に比例して時間が伸びますが、分割統治にもとづくクイックソートは平均で要素数とその対数の積に抑えられます。1 万件と 100 万件では、この差が実行時間で何百倍、何千倍という開きになって表れます。同じ問題を解くコードでも計算量の違いが規模に応じてどれほど効くのかを、手元で実際に計測して確かめられる題材として、ソートはもっとも扱いやすい入り口です。

計算の難しさ、乱択と数論、暗号と圧縮を扱う後半

第 8 章「問題の難しさ」は計算にかかるコストと難しさの分類を扱い、効率よく解けない問題があることを示します。第 9 章「乱択アルゴリズムと数論」は乱数を使うアルゴリズム、数論の入門、素数判定アルゴリズムへ進みます。第 10 章「現代社会を支えるアルゴリズム」はハッシュ関数、公開鍵暗号、データ圧縮の技術を取り上げ、教科書で学んだ考え方が通信の安全やファイルの圧縮といった身近な仕組みにつながることを見せる締めくくりになっています。一般的なアルゴリズムの入門書がソート、探索、グラフで終わることが多いのに比べ、数論から暗号までを一冊の中で扱う点は本書の個性です。

向いているのは、Python の基本的な文法は書けるものの、計算量やデータ構造を体系立てて学んだことがない学部生や、データ分析の仕事で処理の遅さに悩み、原因を理論から理解したい人です。逆に、競技プログラミングの問題演習を大量にこなしたい人や、発展的なデータ構造の実装を網羅的に学びたい人には、目的に特化した別の本が合います。2019 年 11 月刊の教科書なので、Python の版による細かな違いは公開コードと手元の環境で確かめながら読むのが確実です。他のアルゴリズム本との選び分けは アルゴリズム本の選び方 にまとめています。講義の教科書として、あるいは独学で基礎を一巡りする一冊として、Python で読めるアルゴリズムの教科書を探している人には有力な候補です。