演習問題 1 平成 27 年 4 月 6 日問 1.1 6 函数の増大する速さを大まかに表す漸近記法を講義で扱った．正確に定義を述べると，自然数を非負実数に移す函数 f ，g : N → R≥0 について，（1）f (n) = O(g(n)) とは，或る c ∈ R≥0 が存在し，十大きなすべての n ∈ N について f (n) ≤ c · g(n) が成立つことをいう．（2）f (n) = Ω(g(n)) とは，g(n) = O(f (n)) であることをいう．（3）f (n) = Θ(g(n)) とは，f (n) = O(g(n)) かつ f (n) = Ω(g(n)) が成立つことをいう．つまり f (n) = O(g(n)) は「f の値は定数倍を無視すれば概ね g 以下である」を表す．逆に Ω は「…以上である」を表す．利な書き方だが，「存在」「すべて」のやや混み入った意味を式の中に隠しており，二つの物が等しいわけでもないのに等号をうという聊か怪しい記法であるから，誤解を与えぬよう注意して用いるべきである．本講義では式の右辺でのみ（或いは「…の値は O(log n) である」のごとくの述語として）うことにする．この記法を f (n) = n3 − O(n2 ) のごとく式の中に入れてうこともある．これは或る c ∈ R が存在し，十大きなすべての n ∈ N で f (n) ≥ n3 − c · n2 という意味になる．つまり O が右辺になるように移項した n3 − f (n) = O(n2 ) として解釈すればよいのである．次の各主張の成否を○か×かで答えよ（提出では理由は不要）．（イ）n2 = O(n) （ロ）n2 = Ω(n) （ハ）5n + 3 = O(n) （ニ）25n+3 = O(2n ) （ホ）3n = O(2n) （ヘ）3n = O(2n ) （ト）3n = 2O(n) （チ）log2 n = Θ(log7 n) 以下 log は log2 を意味する．（リ）log(n2 ) = O(log n) （ヌ）(log n)2 = O(log n) √ （ル）n(log n)2 = O(n n) （ヲ）n! = O(10n ) 1-1 問 1.2 2＋2 （1）函数 f ，g ，h : N → R≥0 について，f (n) = O(g(n)) かつ g(n) = O(h(n)) ならば必ず f (n) = O(h(n)) が成立つといえるか．（2）常に正の値をとる任意の函数 f ，g : N → R>0 について，f (n) = O(g(n)) または f (n) = Ω(g(n)) の少くとも一方は必ず成立つといえるか．くじ問 1.3 正の定数 p < 1 を固定する．確率 p で当る籤を独立に l 回引くとき，当りの出る 1＋4＋2＋4 回数 X の期待値は勿論 pl であるが，これよりも割合 δ > 0 だけ多めに当る確率を考えよう．つまり X ≥ pl(1 + δ) となる確率を f (l, δ) とする．このとき任意の δ > 0 について， f (l, δ) = 2−Ω(l) (◎) が成立つ．このことを示そう．（1）式 (◎) の意味を，漸近記法をわずに述べよ．（2）(1 + δ)X の期待値を求めよ．（3）f (l, δ) · (1 + δ)pl(1+δ) は（2）の値以下である．何故か．（4）(◎) を示せ．問 1.4 3＋7 与えられた（十進法で）n 桁の平方数 S の平方根を知るため，正整数 x0 ，x1 ， …を x0 = 10 ⌈n/2⌉ xi+1 ⌊ ( )⌋ 1 S = xi + 2 xi (i = 0, 1, . . .) で順次求めることにする．但し ⌈·⌉ と ⌊·⌋ とはそれぞれ整数への切上げ，切捨てを表す．（1）xi と正しい平方根との差 di = xi − （2）xi = √ √ S について，di+1 を di と S とで表せ． √ S となる i が存在し，そのうち最小のものは O(log n) であることを示せ． 1-2 n 2 9 17 30 45 62 69 80 比 7 22 26 31 36 42 51 75 2 7 9 17 22 26 2n 図1 問 1.5 1＋3＋5 比長さ n の既に整列された配列二つを併合して長さ 2n の配列にする．与えられた配列の要素を小さい順に並べ替える（整列する）という問題について，の回数が O(n log n) である算法を示す．（1）長さ n の整数配列が二つあり，それぞれは既に昇順に整列されている．両者を並行して先頭から読みながら比することで，これら 2n 個の整数が昇順に整列された新たな配列を作ることができる（図 1）が，このとき整数値の比は最大で何回行われるか．答のみでよい．（2）併合整列（merge sort）は（1）を繰返し用いることで配列を整列する算法である．如何にして用いるか述べ，この算法で長さ n の整数配列を整列するときに行われる整数値の比の最大回数 T (n) について次が成立つことを説明せよ． T (2n) = 2T (n) + O(n) (★) （3）(★) を満す任意の非減少函数 T について T (n) = O(n log n) が成立つことを示せ．注意（3）では (★) の O 記法の正確な定義に照して正しく議論すること．問 1.6 前問の併合整列が（漸近的に）最良（のものの一つ）であることを示そう．すなわ 3 ち与えられた n 個の相異なる整数 a1 ， …，an を，二つの整数の比のみを用いて整列したいとき，必要な比二整数の比の回数 k の下界を求めよう．空欄を埋めよ．により a1 ，…，an の大小関係を決定する手順は，二木を根からることで表される．葉以外の各節点には n 以下の正整数の組 (i, j) が指定されており，二つの子に向う枝にはそれぞれ「ai < aj のとき」「ai > aj のとき」と書かれている．葉に至ったときには a1 ，…，an の大小関係がわかっている．この手順に従ったときに行う比さが k の二木に葉は高々イの回数の最大値 k は，すなわち木の深さである．深枚である．一方 n 個の相異なる整数の大小関係は 1-3 ロ通りあり得るから，葉は少くともこれらよりイ ≥ ロロ枚ある．．スターリングの式 n! lim √ =1 n→∞ 2πn (n/e)n により k = Ω( 問 1.7 或る 7 ハ ) とわかる．共施設があり，利用したい団体は開始・終了時刻を決めて申込む．希望者は多いが一度に利用できるのは一団体だから，施設では時間が重ならないよう申込の一部を選んで受入れ，残りは断らざるを得ない．さて，今この施設には来季のの申込書 n 枚が届いており，このうちなるべく多数を受入れたい．講義では，まず申込書を終了時間の早い順に並べ替えてから，それを先頭から順に見て，受入可能な申込を貪慾に選べばよいと述べた．何故これで最大数の申込を受入れることになるか，証明せよ． 1-4