離散アルゴリズム特論レポート問題集

離散アルゴリズム特論レポート問題集
2015 年 7 月 20 日更新, 担当宇野
¶
³
自分の言葉で表現されていないと推測・判断される答案は, オリジナル/コピーを問わずその
評価を著しく下げます. 注意して下さい.
µ
´
問題 1 初等的な整列法の解析.
問題 SORT を解く初等的なアルゴリズムとして, 挿入ソート, バブルソート, 選択ソート
の 3 つの方法を取り上げた. 講義で詳細に説明した挿入ソート以外の, バブルソートある
いは選択ソートの::::::::::::::::::::
いずれか一方のみを選択し, それを明示した上で以下の問いに答えよ.
1.
2.
3.
4.
方法のアイデアを, (図や例を用いるなどして) わかりやすく説明せよ.
その方法を擬似コードで表現せよ.
その方法の正当性を説明せよ.
自分の記述した擬似コードの時間計算量を (講義で説明したものと同様の方法で) 理
論的に解析し, 最悪時間計算量を導出せよ.
5. 上の解析における最悪時間計算量を実現する入力の例を示せ.
問題 2 初等的な整列法における挿入ソートの優位性.
講義中に説明した 3 つの初等的な整列法 (挿入ソート, バブルソート, 選択ソート) の中
では, 実用上は挿入ソートが圧倒的に高速であるとされている. その理由を考察せよ.
問題 3 マージソートの実装.
問題 SORT を解くマージソートについて, 以下の問いに答えよ.
1. その方法を C 言語を用いて実現し, 完全に動作するプログラムを作成せよ. (ソース
プログラムとその解説を示し, さらにその動作例を挙げよ.) ただし, 入力データは以
下のような形式でファイルとして与えられ, これを scanf 関数を用いて, 順次対応す
る変数や配列に格納するものとする.
要素数 n
要素 1 要素 2 ... 要素 n
たとえば,
10
15 21 7 3 19 30 6 22 10 7
という入力は, 10 要素からなるリスト L = (15, 21, 7, 3, 19, 30, 6, 22, 10, 7) を表し,
これが input.dat という名前のファイルで与えられ, ソートの実行ファイル名が
yoursort であるとすると, コマンドラインから
# yoursort < input.dat
あるいは
# yoursort input.dat
のように実行すると結果が得られるものとする.
2. マージソートを,「その場ソート」として実現することは可能か. 自分の作成したプ
ログラムを分析した上で, 一般にどうであるかを議論し考察せよ. ただしその場ソー
トとは, 入力となる n 要素を格納する領域以外に必要となる記憶領域が, O(1) である
方法をいうことにする.
問題 4 整列法. アルゴリズムの正当性.
問題 SORT を解く方法として, 以下の擬似コード MySort で示される方法を考案した.
これについて, 以下の問いに答えよ.
MySort (L[n])
f lag := 1;
while ( f lag = 1) do
f lag := 0;
for j = 1 to n − 1 by 2
if (L[ j] > L[ j + 1]) {swap(L[ j], L[ j + 1]); f lag := 1; }
for j = 2 to n − 1 by 2
if (L[ j] > L[ j + 1]) {swap(L[ j], L[ j + 1]); f lag := 1; }
end.
1. この擬似コードが実現しようとしているアイデアを理解し, その動作がよく表現で
きる入力例 L = (a1 , a2 , . . . , an ) を考え, それに対する動作例を具体的に示した上で, こ
の方法のアイデアを説明せよ.
2. このアルゴリズム MySort(L[n]) は正しいか (問題 SORT に対するアルゴリズムか).
もし正しい場合は, その正当性を説明し, このアルゴリズムの最悪時間量を解析せよ.
もし正しくない場合は, その理由を示せ.
問題 5 整列法の最悪計算時間の下界.
2 要素の大小の比較にもとづく任意の整列法は, その最悪時間計算量が Ω(n log n) である
ことを示したい. これについて, 以下の問いに答えよ. ただし, n は入力要素数である.
1. n! 個の葉節点をもつ 2 分 (決定) 木の高さ h について, h = Ω(n log n) であることを示
せ (数学的な議論を要求している).
2. 2 の事実にもとづき, 2 要素の比較にもとづく任意の整列法の最悪時間計算量が
Ω(n log n) であることを, 自分の言葉で表現して説明せよ.
問題 6 2 要素の比較にもとづかない整列法.
挿入ソートやマージソートなどの整列法は, 2 要素の比較にもとづいて動作している. こ
れに対して, 2 要素の比較に::::::::::::::::
もとづかない整列法とはどのようなものか. それらの動作原理
は何にもとづいているか. また, そのことで計算量はどのような影響を受けどのように変
化するか.
これらについて調査をし, 理解したことを説明せよ.
問題 7 要素同一性判定問題.
次の問題を考える.
要素同一性
入力: 自然数 n, 整数 a1 , . . . , an ,
出力: 入力要素の中に値が同一の要素があれば yes, そうでなければ no.
1. この問題を正しく解くアルゴリズムを考案し, そのアイデアを説明した上で擬似コー
ドで表現せよ.
2. 考案したアルゴリズムの最悪時間計算量を解析せよ.
3. この問題の時間計算量の下界について考察せよ.
問題 9 Randomized Selection の実装.
問題第 p 要素の選択を解く乱択アルゴリズムである Randomized Selection について, 以
下の問いに答えよ.
1. その方法を C 言語を用いて実現し, 完全に動作するプログラムを作成せよ. (ソース
プログラムとその解説を示し, さらにその動作例を挙げよ.) ただし入力データの与
え方などは, 問題 3 におけるマージソートに対するものに準ずるものとする.
2. 乱択アルゴリズムでは, プログラム中に乱数を発生するメカニズムが必要となる. 自
分の作成したプログラムでは, それをどのように準備したかを説明せよ.
問題 10 Randomized QuickSort の設計, 解析, 実装.
第 p 要素の選択に対するアルゴリズム Randomized Selection (RS) と同様のアイデアで,
問題 SORT 解くアルゴリズムを設計したい.
1. SORT を解く乱択アルゴリズムとして Randomized QuickSort (RQS) を設計し, その
アイデアを説明した上で擬似コードで表現せよ.
2. 考案したアルゴリズムの時間計算量を解析せよ.
3. RQS を C 言語を用いて実現し, 完全に動作するプログラムを作成せよ. (ソースプロ
グラムとその解説を示し, さらにその動作例を挙げよ.) ただし入力データの与え方
などは, 問題 3 におけるマージソートに対するものに準ずるものとする.
4. 乱択アルゴリズムでは, プログラム中に乱数を発生するメカニズムが必要となる. 自
分の作成したプログラムでは, それをどのように準備したかを説明せよ.
問題 11 確率的手法.
2 次元平面上の 10 点は, どのような配置にあっても (重なることのない) 単位円盤でカ
バーできることを証明 (説明) せよ.
問題 12 確率的手法.
n 変数, m 節からなる kSAT は, m ≤ 2k − 1 であるとき充足可能であることを証明 (説明)
せよ.
問題 13 最長増加部分列.
L = (a1 , . . . , an ) を n 個の正整数からなるリストとする. このとき, リスト (ai1 , . . . , aik )
(1 ≤ i1 < · · · < ik ≤ n) を L の部分列といい, ai1 < · · · < aik を満たす部分列を増加部分列と
いう. 例えば, 与えられたリストが
L = (11, 17, 5, 8, 6, 4, 7, 12, 3)
である場合, 5, 6, 7, 12 は増加部分列で, その長さは 4 である.
いま, L における長さ最大の増加部分列 (最長増加部分列 (longest increasing subsequence,
LIS)) の長さを求める方法を考えたい.
1. 最長増加部分列問題を解くアルゴリズムを考案し設計せよ. また, 設計したアリゴリ
ズムの時間計算量を解析せよ.
√
2. 与えられたリスト L の n 個の値がすべて異なるとき, L は少なくとも長さ d n e の増
加部分列, あるいは減少部分列をもつことを証明せよ.
問題 14 連続行列積, 三角形分割.
n (≥ 2) 個の行列の積を計算するとき, 結合則にもとづく異なる計算順序 (括弧のつけ方)
の総数を Pn とする. また, 凸 n 角形 (n ≥ 3) に n − 3 本の交差しない対角線を引いて, n − 2
個の三角形に分割する異なる分割の総数を Dn とする.
(1) n ≥ 2 に対して, Pn = Dn+1 であることを示せ.
(2) 自然数 n に対して Cn を (便宜的に) Cn ≡ Pn+1 と定義すると, n = 1, 2, . . . に対する数
列 {Cn } は, 1, 2, 5, 14, 42, . . . となる. 数列 {Cn } の一般項を求めよ.
問題 15 木の独立点集合.
無向グラフ G = (V, E) における点の部分集合 S (⊆ V) が独立であるとは, ∀u, v ∈ S (u , v)
に対して {u, v} < E を満たすことであり, |S | が最大となる独立点集合 S を最大独立点集合
という.
いまグラフが木であるとき, 木の最大独立点集合を求めるアルゴリズムを設計せよ. ま
たそのアルゴリズムの時間計算量を解析せよ.
問題 16 頂点被覆. 特別な場合.
無向グラフ G = (V, E) における頂点被覆とは, 頂点の部分集合 S (⊆ V) で S ∩ {u, v} , ∅
(∀uv ∈ E) を満たすもののことであり, |S | が最小となる頂点被覆 S を最小頂点被覆 (集合)
という.
1. 入力となるグラフが木であるとき, 木の最小頂点被覆を求めるアルゴリズムを設計
せよ. またそのアルゴリズムの時間計算量を解析せよ.
2. 入力となるグラフの最大次数が 2 であるとき, その最小頂点被覆を求めるアルゴリズ
ムを設計せよ. またそのアルゴリズムの時間計算量を解析せよ.
問題 17 部分和．ナップサック問題などと同類．
部分和問題とは, 正整数 a1 , . . . , an と正整数 b を入力とし,
P
a j = b をみたす S ⊆
{1, . . . , n} が存在すれば yes, そうでなければ no と答える問題である.
この問題を解くアルゴリズムを設計せよ. またそのアルゴリズムの時間計算量を解析
せよ.
j∈S
問題 18 k-頂点被覆. 固定パラメータアルゴリズムの解析.
(1) k-頂点被覆問題に対するアルゴリズム Naive k-VC の最悪時間計算量を解析せよ. そ
の上で, Naive k-VC が固定パラメータアルゴリズムであるかどうかを議論せよ.
(2) k-頂点被覆問題に対するアルゴリズム Branch の最悪時間計算量を解析せよ. その上
で, Branch が固定パラメータアルゴリズムであるかどうかを議論せよ.
問題 19 MAX-SAT の乱択近似.
充足可能性 (SAT) とは, 与えられた命題論理式に対して, それを真にする各変数への真
理値割当てが存在するかを問う問題である. ただし, 論理式は和積標準形で与えられるも
のとする. たとえば, f = (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) は, x = 1, y = 1, z = 0 のときに f を真にす
る. MAX-SAT は SAT で真になる節の数を最大化する問題である.
いま MAX-SAT に対する次のアルゴリズムを考える: 「各変数に 0 か 1 を等確率で割当
てる」. このアルゴリズムが MAX-SAT に対する 1/2-近似アルゴリズムであることを証明
せよ.
問題 20 乱択, 重みなし版フライトスケジュール.
重みなし版フライトスケジュールで都市 1 から n へつねに右へと移動する問題で, 各都市
で次の移動都市を一様ランダムに選択するとする. このとき, 移動回数の期待値を求めよ.
問題 21 点彩色, 入力制限.
点彩色問題において, 入力を制限するアプローチでどのような研究結果があるかを調査
し報告せよ.

Download Report