昨日無事に試験が終わりました．研究室の修論・卒論の指導をしつつ，採点と解答・解説の作成も進めています．
問題の一つに，ホーナー法を用いて多項式を計算するプログラムを読んで論述するというのを入れました．プログラムは関数の授業で，論述の仕方は試験直前の授業で，それぞれ解説していました．
関数の授業の中で，ホーナー法を用いることのメリットについて，簡単に触れました．乗算の数が減らせるのです．
しかし「減らせる」というとき，比較対象が必要なのですが，授業中に明示するのを忘れていて，解答例では少し丁寧に書きました．例のごとくすでにPDFファイルを公開しているので，例のごとくリンクするのは避けますが，「n次の項を
として求めるとn個の乗算を行う．n次未満の各項も同様にして別々に計算すると，n次の多項式では
回の乗算を必要とする．ホーナー法では乗算回数がnであり，格段に小さくすることができる」といったところです．
各項別々に乗算する方法は，「素朴な方法」だとか「ナイーブなアルゴリズム」だとか呼ばれます．Googleで調べると，それぞれ数万件ヒットします．多項式計算のアルゴリズムの例も見つかりますが，大部分はそうではありません．wikipedia:離散対数にも，出現します．
この「素朴な方法」「ナイーブなアルゴリズム」というのはおもしろい表現で，問題に依存しつつも，特定の意味を持つ，テクニカルタームと呼んでいい言葉なのです．
たとえば「縦型探索」とか「グリーディ」とかいえば，大学の授業にせよ研究室にせよ，ある程度学べば，あのアルゴリズムなのだなとピンと来ます．当然，テクニカルタームです．
一方，素朴（ナイーブ）な方法というのは，強く問題に依存します．問題に書かれている定義に即して手続きを書けば，それがナイーブなアルゴリズムです．
さて，よく知られたアルゴリズムは，関連して，おおむねどんな問題に適用すればよいかも連想することになりますが，素朴（ナイーブ）という概念*1は，あとで，より洗練された手法を考えることになる，ということを含みます．
ホーナー法の上記の議論も…プログラムの例は2〜3次なので，計算時間は大差ないのですが…授業の中で素朴な方法を提示し，確認しておけばよかったなあ，と少し後悔です．
ちなみに，「素朴な方法」は，研究室内の会話では「普通の方法」とか「単純な方法」といった表現にすることが多いです．しかしこれらだと，重みがうんと下がります．さらに言うと，「普通の方法」は論文にはそぐわない表現ですし，「単純な方法」は「計算量の少なくなる方法」と誤解されかねないので，論文で使う際には注意したいところです．
「素朴」について昔書いたこと：
*1:意味は全然違いますが，教育の分野で「素朴概念」という用語があります．http://liliput.hp.infoseek.co.jp/yougo.html など．これはこれで，大学で教える者として，意識しています．
