練習問題

  1. 通常のチェスボード上に並べられた通常のチェスの駒の配置がルールに反していない場合に、どちらのプレイヤーが勝つかを判定する効率の良いアルゴリズムを説明、解析してください。両プレイヤーは完璧に駒を進めるものとします。[ヒント: 一行で書ける自明な答えがあります！]

  2. ❤

    1. 最初の \(n\) バースを歌うのに時間が \(\Theta(n^{3})\) かかる歌を見つけて (または作って) ください。

    2. 最初の \(n\) バースを歌うのに時間が \(\Theta(n \log n)\) かかる歌を見つけて (または作って) ください。

    3. 最初の \(n\) バースを歌うのにかかる時間が変な形で表される歌を見つけて (または作って) ください。

  3. 注意深い読者は、"\(n\) Bottles of Beer on the Wall" や "The \(n\) Days of Christmas" の解析が単純すぎると思うかもしれません。というのも、大きな数を歌うには小さい数よりも長い時間がかかるはずだからです。またある長さの単語は限られているので、単語を多く集めればその中には長い単語も含まれます1。歌に現れる単語の数ではなく音節の数を数えることで、歌唱時間をより正確に推定できるはずです。

    1. 整数 \(n\) を歌うのにどれだけ時間がかかりますか？

    2. "\(n\) Bottles of Beer on the Wall" を歌うのにどれだけ時間がかかりますか？

    3. "The \(n\) Days of Christmas" を歌うのにどれだけ時間がかかりますか？

    いつも通り、答えは適当な関数 \(f\) を使って \(O(f(n))\) という形で書いてください。

  4. "The Barley Mow" はブリテン諸島で何世紀にも渡って歌われている積み上げ歌です。この歌にはいくつもバージョンがありますが、デボンとコーンウォールで伝統的に歌われているバージョンの歌詞を次に示します。ここで \(\mathit{vessel}[i]\) は \(2^{i}\) オンスのビールが入ったグラスの名前を指します2。

    procedure \(\texttt{BarleyMow}\)(\(n\))

    "Here's a health to the barley-mow, my brave boys,"

    "Here's a health to the barley-mow!"

    \({}\)

    "We'll drink it out of the jolly brown bowl,"

    "Here's a health to the barley-mow!"

    "Here's a health to the barley-mow, my brave boys,"

    "Here's a health to the barley-mow!"

    for \(i \leftarrow 1\) to \(1\) do

    "We'll drink it out of the \(\mathit{vessel}[i]\), boys,"

    "Here's a health to the barley-mow!"

    for \(j \leftarrow i\) downto \(1\) do

    "The \(\mathit{vessel}[j]\)"

    "And the jolly brown bowl!"

    "Here's a health to the barley-mow!"

    "Here's a health to the barley-mow, my brave boys,"

    "Here's a health to the barley-mow!"

    図 0.6
    "The Barley Mow"

    1. \(\mathit{vessel}[i]\) が全て一単語であり、一秒間で四単語を歌うことができる場合、\(\textsc{BarleyMow}(n)\) を歌うのにどれだけ時間がかかりますか？ (厳密な漸近表記を示すこと)

    2. 任意の大きさの \(n\) に対してこの歌を歌う場合、グラスの名前を自分で付けていく必要があります。\(n\) を大きくしたときに同じ名前を使うのを避けるには、グラスの名前をだんだん長くしなければなりません。\(\mathit{vessel}[n]\) が \(\Theta(\log n)\) 音節を持っており、一秒間に 6 音節を歌えると仮定した場合、\(\textsc{BarleyMow}(n)\) を歌うのにどれだけ時間がかかりますか？ (厳密な漸近表記を示すこと)

    3. グラスの名前を言うたびに、実際にそれだけのビールを飲むとします。つまり "jolly brown bowl" と言ったときには 1 オンス飲み、\(\mathit{vessel}[i]\) と言ったときには \(2^{i}\) オンス飲むということです。問題の都合上あなたは 21 才以上だと仮定したとき、\(\textsc{BarleyMow}(n)\) を歌うと正確に何オンスのビールを飲むことになりますか？ (漸近表記ではなく正確な答えを出すこと)

  5. Huntington-Hill のアルゴリズム \(\textsc{ApportionCongress}\) の入力は \(P[1..n]\) と \(R\) であり、\(P[i]\) が \(i\) 番目の州の人口を、\(R\) が割り当てる議席数を表します。出力は \(r[1..n]\) であり、\(r[i]\) が \(i\) 番目の州に割り当てられた議席数を表します。

    Huntington-Hill のアルゴリズムは優先度付きキューを使わないで実装されることもあります。トップレベルのアルゴリズムは除数 (divisor) と呼ばれる正の整数 \(D\) を "推定" し、次のサブルーチンを使って配分を計算します。ここで変数 \(q\) が除数 \(D\) を使って計算した理想の議席配分を表します。このアルゴリズムで配分される議席数は常に \(\lceil q \rceil\) または \(\lfloor q \rfloor\) です。

    procedure \(\texttt{HHGuess}\)(\(\mathit{Pop}[1..n], R, D\))

    \(\mathit{reps} \leftarrow 0\)

    for \(i \leftarrow 1\) to \(n\) do

    \(q \leftarrow \mathit{Pop}[i]/D\)

    if \(q \cdot q < \lceil q \rceil \cdot \lfloor q \rfloor\) then

    \(Rep[i] \leftarrow \lfloor q \rfloor\)

    else

    \(Rep[i] \leftarrow \lceil q \rceil\)

    \(\mathit{reps} \leftarrow \mathit{reps} + Rep[i]\)

    return \(\mathit{reps}\)

    \(\textsc{HHGuess}\) の返り値 \(\mathit{reps}\) には三つの可能性があります。もし \(\mathit{reps} < R\) なら配分した議員の数が不足しており、(直感的には) \(D\) が小さすぎたことを意味します。もし \(\mathit{reps} > R\) なら配分した議員の数が過剰であり、(直感的には) \(D\) が大きすぎたことを意味します。そして \(\mathit{reps} = R\) なら \(R[1..n]\) が正しい議席配分となります。実用上は、素直に計算した除数 \(D = P / R\) の近くの整数に対して \(\textsc{HHGuess}\) を何回か呼べば正しい配分を計算できます。

    以降では \(n\) 個の州の人口の合計を \(P = \sum_{i=1}^{n} \mathit{Pop}[i]\) とし、\(n \leq R \leq P\) を仮定します。

    1. \(\textsc{HHGuess}\) に標準的な除数 \(D = P/R\) を入力したとしても正しい配分を計算できない場合があることを示してください。

    2. 異なる二つの除数 \(D, D^{\prime}\) に対して \(\textsc{HHGuess}\) が同じ \(\mathit{reps}\) を返したとします。このとき配分 \(Rep[1..n]\) も同じであることを示してください。

    3. \(\textsc{HHGuess}\) が正しい値 \(R\) を返したとします。このとき議席配分 \(Rep[1..n]\) が \(\textsc{ApportionCongress}\) アルゴリズムの出力と同じであることを示してください。

    4. "正しい" 除数 \(D\) が常に存在するとは限らないことを示してください！ つまり、入力 \(\mathit{Pop}[1..n]\) と \(R\) \((n \leq R \leq P)\) であって、全ての \(D > 0\) に対して \(\textsc{HHGuess}\) の返り値が \(R\) と異なるようなものを示してください。 [ヒント: \(\textsc{HHGuess}\) の四行目の \(<\) を \(\leq\) にするとどうなりますか？]

  1. Ja, das ist das Subatomarteilchenbeschleunigungsnaturmäßigkeitsuntersuchungsmaschine![return]

  2. グラスの名前は次の中から選ばれます: nipperkin, quarter-gill, half-a-gill, gill, quarter-pint, half-a-pint, pint, quart, pottle, gallon, half-anker, anker, firkin, half-barrel/kilderkin, barrel, hogshead, pipe/butt, tun, well, river, ocean。最後のいくつかの例外を除いて、各グラスの容量は一つ前のグラスの倍です。アイルランドとスコットランドで歌われているバージョンでは歌詞が少し違っており、"gallon" の後は人が続きます (barmaid, landlord, drayer など)。

    John Marston (ジョン・マーストン) によって 1600 年ごろに書かれた戯曲 Jack Drum's Entertainment (あるいは the Comedie of Pasquill and Katherine) には "Give us once a drink" という曲の古いバージョンが出てきます。("Giue vs once a drinke for and the black bole. Sing gentle Butler bally moy!") しかし、Marston が "high Dutch Song" を戯曲のために書いたのどうか、"bally moy" は "barley mow" の聞き間違い (mondegreen) なのかそれとも逆か、そもそも二つの曲が同じなのかどうか、学者の意見は一致しません。 これについて議論するなら \(n\) 本のビールと一緒にやるのが一番でしょう。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。