• 問題１：　 n 個の要素を整列するクイックソートにおいて，軸要素 a を次のように選ぶ．

  アルゴリズムSELECTを用いて, 対象とする部分配列の全要素のメディアン（中央値） を求め a とする．（注：SELECTの最悪時間量は部分配列の大きさを n'として O(n') である．）

  (a) この選択法によるクイックソートの最悪時間量を T(n) とし， T(n) に関する漸化式を導出した後，T(n)=O(n log n) であることを 示せ．
  
  (b) クイックソートにおける通常の軸要素選択法を述べ，上の選択法 との優劣を比較せよ．
  
  略解： (a)　まず、漸化式
  　　　T(n)=2T(n/2)+cn
  を出す。cn はSELECTの時間と 軸要素に基づく配列領域の分割の時間を含む。より精密には、n が奇数と 偶数の場合に分けて考える、あるいは n/2 の切り上げと切り下げに分ける などがあるが、同様の結果になる。もちろん、不等式≦を用いて 記述するのも正解。 漸化式の解析は、T(n)=cn log n を上式に代入すると、左辺と右辺が 等しくなるので、これが答え（の一つ）であることが分かる。この やり方は、講義ではマージソートの解析で用いた。より正直な 解析は、
  　　T(n)=2T(n/2)+cn　
  　　　　=2(2T(n/4)+2c(n/2))+cn = 2²T(n/2²) + 2cn
  　　　　= ... 　
  　　　　=2^(log₂n)T(1) + (log₂n)n
  　　　　=n + (log₂n)n = O(n log n)
  のような議論が書いてあればよい。
  
  (b) 講義では

  1.　ランダムに一つを選ぶ、
  2.　左端、右端、中央の位置の三要素の中央値、
  3.　左から見て最初に得られた２つの異なる値の大きい方、

  などを説明したので、これらが書かれているとよい。これらによる整列は 平均時間は O(n log n) であるが、最悪の場合 O(n²) に なることが欠点。しかし、(a) のSELECTを用いるものは、軸要素の 決定に時間が掛かるので、最悪の場合でも O(n log n) であるものの、 実際にはあまりよくない。その他、同じ値の要素がたくさんある場合 の振る舞いとか、乱数の計算には結構手間がかかることなど、実用上の 観点からの議論があってもよい。
  
  評： クイックソートはよく出るところなので、準備していた人が多かった ようだ。なお、漸化式の解析をオーダー表記を用いて行うと 間違った結論になるので、要注意。たとえば、 T(n)=T(n-1)+cn の解は T(n)=cn(n+1)/2=O(n²) であるが、T(n) にたとえば O(n log n) を代入すると、左辺 = O(n log n), 右辺 = O((n-1)log(n-1)) +O(n)=O(n log n) となって、誤った結論がでてしまう。本問の解析 に類似の議論を適用してしまった人が散見された。
  
  
• 問題２： f(x) は整数値 x=0, 1, 2, ..., N に対して定義されている 凸関数である．すなわち，f の差分 d(x)=f(x)-f(x-1) は d(0)≦d(1)≦ ... ≦d(N+1) をみたす．ただし，簡単のため，d(0)=-∞, d(N+1)=∞ と定めている.
  
  (a) f(x) が x∈ {0, 1, ..., N} において最小値をとる ための必要十分条件は d(x)≦0, d(x+1)≧0 であることを示せ．
  
  (b) f(x) を最小にする x∈ {0, 1, ..., N} を求める 最悪時間量 O(log N) のアルゴリズムを与えよ．(一つの x に 対する f(x) の値は O(1) 時間で求まると仮定する.)
  
  略解： (a)　必要性と十分性を区別して証明すること。
  
  必要性： f(x) が最小だとすると、当然 f(x-1)≧f(x), f(x)≦f(x+1) が成立する。これは、d(x) の定義から、d(x)≦0, d(x+1)≧0 を意味する。 (x が 0 あるいは N であってもこの議論は正しいことに注意。）
  
  十分性： d(x)≦0, d(x+1)≧0 を仮定すると、d(0)≦d(1)≦ ... ≦d(x)≦0 から f(0)≧f(1)≧...≧f(x) が導かれる。同様に、0≦d(x+1)≦...≦d(N) から f(x)≦f(x+1)≦...≦f(N) を得る。よって、f(x) は最小値である。
  
  (b)　d(0),d(1), ..., d(N+1) の配列があると考えると（実際に構成 する必要はない）、すでに d(0)≦d(1)≦ ... ≦d(N+1) と整列されている ので、ここに d(x)=0 を満たす要素が存在するかどうかの２分探索を 適用すればよい。d(x)=0 を満たす要素が存在するならば、d(x) と d(x+1) は d(x)=0, d(x+1)≧0 を満たす。d(x)=0 を満たす要素が存在 しないならば、計算終了時の2要素は d(x)<0, d(x+1)>0 を満たす。 ２分探索は反復毎に探索領域を半分に絞る方法であるが、詳細は 講義で説明したので、省略。計算は O(log N) 回の反復で終了する。一回の反復は、ひとつの f(x) の値を求めるだけだから、仮定によって O(1) 時間、 結局、最悪時間量は O(log N) である。
  
  この変形として、反復毎に2要素、d(x), d(x+1) を計算して 条件 d(x)≦0, d(x+1)≧0 をその度に調べる方法も正解としたが、 オーダーは変わらないものの、反復毎の計算量は大きくなる。
  
  評： 比較的易しい問題。結構出来ている人が多かった。凸関数は 他の講義でも出てくるのか、最小点が一つであるとか、単調減少のあと 単調増加に移る関数であるという性質を既知のこととして用いた 人もいたが、これらは上に書いたようにきちんと証明してほしい。
  
  
• 問題３： 携帯電話のA社では, 全加入者の名簿リストを作る予定である.

  ・加入者の名前は15文字以内のカタカナで書かれている. 簡単のため, 同姓同名はないものとする.
  ・電話番号は11桁の10進数である.
  ・この会社には新しい加入者が頻繁にあり, また解約する者も ある.
  ・加入者総数 n は変動するが, 100万人以下である.
  ・名簿に発せられる質問のタイプは次の二つに限られている.
  　(i) 名前を与え, 加入者ならばその番号を出力する.
  　(ii) 電話番号を与え, その番号を持つ加入者があれば, その名前を出力する.

  さて, このような名簿をコンピュータ上に構築するとして, そのデータ構造にどのようなものを用いるのが適当であるか 考察し, その領域量を示せ. また, (1) 新しい加入者の追加, (2) 解約者のデータの削除, (3) 上の二つのタイプの質問に 答える, という操作に必要な時間量を求めよ. 領域量, 時間量共に, n のオーダー表記で示せ. もちろん, 領域量, 時間量ともに小さいものが求められている.
  
  略解：　 このような状況に対しては、辞書というデータ構造があったことを思い出して ほしい。ついで、辞書の大きさがダイナミックに変動することから、 辞書のデータ構造の中でもハッシュ表が適していることに気付けば、ほぼ 出来たというわけ。名前から番号を見つけるためと、番号から名前を 見つけるために、２種のハッシュ表を別個につくるのが最も簡単。 あとは、ハッシュ表について学んだことから、領域量と 時間量などを、個々の作業について書けばよい。大体は講義で話したこと なので、詳細は略すが、領域量は O(n), 平均時間量はそれぞれ O(1) で済む。
  
  実際のシステムでは、利用者のデータ（名前、番号の他に、住所、年齢、性別、 支払方法、支払いに必要なデータ、支払記録、利用記録、その他）が格納された データベースがあるはずなので、上の二つのハッシュ表には、対応する 利用者データへのポインタを付すことになろう。
  
  解答の中には、すべての名前（あるいは番号）を整列しておくという データ構造を書いたものが結構あった。利用者が固定されている場合は、 これも悪くないが、この問題のように変動する場合は、新しい名前の 挿入や、名前の削除に O(n) 時間掛かってしまうので困る。ただし、 そこそこの点は与えた。また、 携帯の番号は 090 で始まるのでその部分は冗長 であるなどのコメントもあったが、これらは枝葉末節。また、n を 100万人以下に限ると、n は定数とみなせるので、すべての計算量は O(1) と書けると指摘したものもあった。これは正しい。一本取られた という感じ。
  
  評： この問題は、実は、昨年夏の大学院の試験問題に出した。自分では 気に入った問題であったが、選択した受験生が少なかったので、 今回再利用したという次第。ハッシュ表は基本的なデータ構造の一つで、 簡単な割に、この問題のように実用性が非常に高いので、よく覚えておいて ほしい。
  
  全体の評： ３題とも難度が高くなかったせいか、出来は悪くなかった。 結果として、例年に比べ多くの人が単位を獲得した。
  
  ★　　　　　★　　　　　★
  
  講義についての感想： 今年も、レポートに書いてもらった皆さんの感想をまとめてみました。
  
  講義内容については、よくわかった、興味を持てたという感想が 圧倒的でした。私としても、分かり易い講義を心がけている積もりなので、 このような感想をもらって、大変嬉しく思いました。
  
  板書については、よく分かって良いという支持の意見が多く、 今後もこの方式でやって行く積もりです。板書の欠点は、時間がかかる ので、講義でカバーできる範囲が限られてしまう点にあるのですが、 幸い教科書も分かり易いという評をいただいているので、 自分で読み進んで理解できる人は、他のトピックスも 積極的に勉強して下さい。
  
  講義の内容では、いろいろなソーティングのアルゴリズムを楽しんだと いう感想が多い。アルゴリズムの動きはよく分かったが、計算量の 議論が難しいとの感想も。領域量の説明をあまりしなかったので、 その指摘もあった。アルゴリズムはパズルみたいだ、というのは その通りです。パズルは単に結果だけでなく、それを解く経過が 楽しいのですが、アルゴリズムも似たところがあります。講義を通して アルゴリズムの面白さを理解してもらうことができれば幸いです。
  
  講義の殆どの話題は、教科書にあるが、いくつか番外の話題も入れた。 議員定数の話は面白かったという感想が多かった。もっと応用的な 話がほしいという意見も多いので、今後も、 興味深そうな話題を拾って行きたいと思います。
  
  レポートと試験の両方はつらい、と書いた人も何人かあったが、これは 情報学の基礎知識として大切な講義だということで、了解してほしい。 レポートの問いの解説がほしいという意見は、考えてみます。あまり 時間をとるのは困るのですが、問題によっては簡単に説明をする ことも検討の価値はありそうです。また、 情報学の他の講義の内容と重複している部分があるとの指摘も あった。この辺りは検討課題ですが、講義の中で体系付けて話を 完結させたいので、他の講義にあるからといって省略するのは 疑問に思っています。
  
  この講義の時点では、C言語についてあまり知識がないので、教科書 のプログラムが分からないというのはもっともです。ただ、おおよその 理解は、教科書の巻末の説明を見ておく程度で分かると思います。この後、 学年が進むにつれて、Cに触れる機会は増えるはずなので、それに応じて プログラムの理解は詳細化されていくと思います。
  
  講義は午後のしかも昼食の後なのでつい寝てしまう、とか、私の 声がソフトなので子守歌に聞こえる、などと書いてありましたが、 声を変える訳にはいかないので困ってしまいます。ともあれ、 この講義で得た知識をもとに、興味を持って、情報学の 専門科目の勉強に進んで行って下さい。
  
  

< Last update: February, 2001 >