第322回 テトラちゃんのアルゴリズム講義(後編)

「僕」にアルゴリズムを教えることになったテトラちゃん。やさしそうな問題なのに、意外に「僕」は苦戦して……さあ、いっしょにアルゴリズムを学ぼう!

新シリーズ「数学ガールの物理ノート」始動!

『数学ガールの物理ノート/ニュートン力学』

『数学ガールの物理ノート/ニュートン力学』をアマゾンで見る

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

$ \newcommand{\ABS}[1]{\left|\mathstrut #1\right|} \newcommand{\TT}[1]{\textrm{#1}} \newcommand{\ANGLE}[1]{\angle\textrm{#1}} \newcommand{\TRI}[1]{\triangle\textrm{#1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\FOCUS}[1]{\fbox{$#1$}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\PS}[1]{\left(#1\right)} \newcommand{\LL}{\left\langle\,} \newcommand{\RR}{\,\right\rangle} \newcommand{\LLRR}[1]{\LL#1\RR} \newcommand{\Enil}{\textbf{nil}} \newcommand{\Fnext}{\textrm{next}} \newcommand{\Fvalue}{\textrm{value}} $

二つの実装の《対応》を見る

双倉図書館の一般講座《リンクとストラクチャー》でアルゴリズムを学んできたテトラちゃんは、 自分の理解のため、学んだことをに向けて《講義》している。

これまでに、 数列の中から最大の値を求めるMAX-VALUEを題材にして議論をしてきた(第321回参照)。

「テトラちゃんが教えてくれたから、ノードリンクを使った線形リストについてはだいぶわかったと思うよ。ありがとう」

テトラ「い、いえ……あたしこそ、先輩に説明しながら理解が深まりました」

「気がついたことがあるんだけど……MAX-VALUEのアルゴリズムを《配列で実装した場合》と《線形リストで実装した場合》を比べてみると、うまく対応がついているよね」

テトラ「はいっ! そうですよねっ!」

「たとえば《数列のすべての要素を確かめたかどうか》という判定をしている部分は、どっちもwhileの条件に書かれていて……」

  • 配列で実装した場合》は、$k \LEQ n$が偽になったときに、すべての要素を確かめたといえる。
  • 線形リストで実装した場合》は、$c \NEQ \Enil$が偽になったときに、すべての要素を確かめたといえる。

List 5(再掲)(第321回参照)

MAX-VALUE: 最大値をもとめるアルゴリズム(配列版)

入力

  • 配列で表現した数列$A = \LLRR{a_1, a_2, a_3, \ldots, a_n}$
  • 数列のサイズ$n\quad (n \GEQ 1)$

出力

  • 数列の要素のうち最大の値

手続き

例:$L = \LLRR{31,41,59,26}, n = 4$で、最初に4行目に来たときの様子

List 6(再掲)(第321回参照)

MAX-VALUE: 最大値をもとめるアルゴリズム(線形リスト版)

入力

  • 線形リストで表現した数列$L = \LLRR{a_1, a_2, a_3, \ldots, a_n}\quad(n \GEQ 1)$

出力

  • 数列の要素のうち最大の値

手続き

例:$L = \LLRR{31,41,59,26}$で、最初に5行目に来たときの様子

テトラ「はい。《すべての要素を確かめた》という条件は、実装の仕方で変わりますが、ちゃんと対応がついています。《配列で実装した場合》は、kという変数の値が要素数を越えたときです。 《線形リストで実装した場合》は、cという変数の値がnilになったときになりますね。 その他にもきれいに対応がついています。たとえば《kを1増やす》と《cにc.nextを代入する》のが対応しています。 これは《次の要素を調べるための準備》になりますね」

「うん。書き方は違うけれど、うまく対応してるなあと思ったんだ」

テトラ「このお話、双倉図書館であたしが聞いた一般講座では《抽象度を変えて理解する》と教えていただきました」

「抽象度を変える?」

抽象度を変えて理解する

テトラ「はいはい。たとえば$k \LEQ n$という式を見たときに《変数kの値は変数nの値以下である》と理解する抽象度と、《まだ調べていない要素がある》と理解する抽象度は違います」

「なるほど。《変数kの値は変数nの値以下である》という方が抽象度は……高いのかな、低いのかな」

テトラ「講義では《低い》としていましたね。《実装寄り》という表現もありました。コンピュータという具体的なものに近いということでしょうか」

「コンピュータに近いの方が抽象度が低くて具体的なんだね」

テトラ「実装寄りの抽象度で理解しますと、次の二つの式はまったく違うように見えます」

  • $k \LEQ n$
  • $c \NEQ \Enil$

「……」

テトラ「でもこの二つの式はどちらも、List 5List 6というプログラムの中にそれぞれ置けば《数列を最後まで調べたかどうか》を表しているといえます。つまり、まったく違うように見えた二つの式も、抽象度を上げると同じ意味に見える。それが《抽象度を変えて理解する》ことなんです」

「なるほどなあ! 字面にとらわれず、抽象度を上げて理解することが大切なんだね!」

テトラ「そうなんです! あ、ええっと……そうなんですが、《抽象度を上げる》だけではなくて《抽象度を変える》ことが大事だそうです。必要に応じて抽象度を上げて理解し、必要に応じて抽象度を下げて理解する。必要とあらば、ぐぐっと実装寄りに理解することも大切……ということでした」

「……」

テトラ「せ、説明が下手ですみません」

「いやいや! 逆だよ。テトラちゃんの説明はすごくよくわかる。《抽象度を上げる》って表現、ミルカさんが言いそうだなって思っていたんだ。《抽象度を下げる》ことも大事なんだね」

テトラ「はい……ああ、それから《抽象度を変えて理解する》ことがどうして大事なのかという話題もありました」

テトラちゃんは用意してきたノートをめくりながらそう言った。

に《講義》するため、彼女はずいぶん準備をしてきたんだな。

「《抽象度を変えて理解する》ことがどうして大事か? うーん……改めて答えようとすると難しいな。どうして大事なんだろう」

テトラ「はい。理由はいくつかありますが、たとえば《アルゴリズムの誤りを見つけやすくなるから》だそうです。なるほどですよね」

「なるほど……」

テトラ「アルゴリズムを複数の方法で実装したり、プログラムを移植したりすると誤りが見つかりやすくなることも多いそうです。 《移植》ってすごい表現ですよね。 一つのプログラムを別の動作環境で動かすために書き直したり、修正したりすることだそうです」

「検算と似ている発想かもしれない。数学の問題で答えが出たあと、答えを吟味するのにも似てるかな」

テトラ「ああ、そうですね。描いた絵を左右反転しておかしな点を見つけるのにも似ています」

線形リストの意義

「ところでテトラちゃん……テトラ先生、質問です!」

はいつものテトラちゃんを真似して、さっと手を挙げた。

テトラ「はい、何でしょう」

テトラちゃんはそんなをにこにこしながら指さした。

「さっきから気になってたんだけど、配列で実装する方が単純なように思うんだ。どうして線形リストなんて使うんだろう」

テトラ「とてもいい質問ですっ! たとえば、配列の途中にある数を《先頭に移動》したいとします。 すると、それまで1番目にあった数は2番目に、2番目にあった数は3番目に……のようにずるずると移動しなくてはいけません。 こんなふうになります」

配列の途中にある要素を先頭に移動する

「ああ、確かにそうだね。単に、$$ A[1] \leftarrow A[k] $$ のように代入しちゃだめか。$A[1]$の情報が消えちゃうから?」

テトラ「そうですっ! 配列の各要素は、コンピュータ上ではメモリ上で連続した領域に置かれているので、途中に要素を挿入したり、途中から要素を削除したりすると、大量の移動が発生してしまうんです……」

「なるほど。たとえば配列で最後の要素を先頭に持ってくるとなると、残り全部を一つ後ろに移さないといけないんだね」

配列の最後にある要素を先頭に移動する

テトラ「そうです。この例では5個しかありませんが、データの個数に合わせて掛かる時間が増えてしまいます」

「線形リストだと、リンクが指すノードを切り換えるだけで済むということ……」

テトラ「そうです。こちらをご覧ください。先頭に持ってくる要素が途中にある場合でも、最後にある場合でも書き換えるnextフィールドの個数は変わりませんっ!」

線形リストの途中にある要素を先頭に移動する

線形リストの最後にある要素を先頭に移動する

「なるほどねえ……だとすると確かに線形リストを考える価値はありそうだね。でもそうなると順番が大事になりそう」

テトラ「順番といいますと?」

「リンクを切り換える順番だよ。ほら、プログラムでは、数学と違って変数の値が書き換えられるよね。 だから、リンクを切り換える順番を間違えると期待したようなリンクにならないんじゃないかと思ったんだ」

テトラ「まさに、その通りですっ! あたし、演習でたくさん間違えましたよ……」

テトラちゃんはそう言いながら両手で頭を抱えた。

「へえ、演習の時間もあったんだ」

テトラ「はい。ところどころで小さなプログラムを書きながら進みましたので、まさに《例示は理解の試金石》でした。お話を聞いたり、書かれたプログラムを読んだりしているときは理解したつもりになっていても、 実際に書こうとすると、自分がまったく理解していなかったということがありありとわかるんです。それはもう驚くほどです」

「そうなんだ……」

テトラ「先輩も、やってみます?」

テトラちゃんの大きな目がきらりと光った。この輝きはめずらしいぞ。

「う、うん……やってみたいな」

テトラ「では問題1です! 線形リストが状態Aで、Lとpが与えられているとします。これを状態Bに変えるプログラムを書いてください!」

問題1 状態Aを状態Bに変えるプログラムを書きましょう(pが指しているノードを先頭に移動)

は考える。

順番が大事になるのは確かだけど……とはいえ、リンクを切り換えるだけなんだから、 何回か代入するだけでいいはず。

代入は何回必要だろうか……

うん、書き換えるnextフィールドは3箇所あるから、3回だけ代入すれば……いや? どうなる?

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

アルゴリズムを楽しく学ぼう!

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 難しすぎる。とりあえず要点をノートにまとめて後でまた考える。 約1ヶ月前 replyretweetfavorite

fall_twtr えーと、値渡しだから、qをLに代入してLをreturnしなくても、qをreturn… https://t.co/jtzeErHUd5 約1ヶ月前 replyretweetfavorite

Lsdu2DalePerry 今回もアルゴリズムの話。テトラちゃんの先生っぷりと『僕』の生徒っぷりがいつもと反対で面白い。 約1ヶ月前 replyretweetfavorite

cielavenir そういえばこの言語(ならびにhello algorithm)では値渡しはC(++)の意味かJava等の意味かどちらでしょうね…? 約1ヶ月前 replyretweetfavorite