すでにニュースでも伝えられている通り、12 月 1 日に第 7 回アルゴリズムイントロダクション輪講会がありました。今回の担当は私だったので、その発表資料を公開します。

1. 中央値と順序統計量 (その 1)
   1. 予定
   2. 順序統計量とは
   3. 選択問題とは
   4. 最小値と最大値
   5. 平均線形時間選択アルゴリズム
2. 中央値と順序統計量 (その 2)
   1. 最悪線形時間選択アルゴリズム
   2. 3 つずつのグループに分割した場合
   3. 7 つずつのグループに分割した場合
   4. 参考文献
3. 中央値と順序統計量 (補足)
   1. 4 つずつのグループに分割した場合
   2. 6 つずつのグループに分割した場合
   3. Lazy-Select[LINK]
   4. Randomized-Partition[LINK]
   5. スタッフロール

「どうせ後から Web で公開するんだから、PDF とか見るのに手間がかかるものは使ってられないよね。やっぱ時代は XML 複合文書でしょ!」と、数式を表現するのに MathML を使いまくったら、なぜか Firefox 以外ではまともに表示されなくなってしまいました。ホスト言語が XHTML なので、IE にいたっては地の文の表示すらできません。

とは言っても MathML の仕様書を斜め読みしただけなので、適切でないマークアップが結構含まれています。本当は図も SVG で表現したかったのですが、いろいろと余裕がなかったのであきらめました。資料が 3 つ (本番では補足を除く 2 つ) の文書に分かれているのは、Firefox で MathML の要素数が一定数を越えると、文字揃えが効かなくなるというバグに遭遇したためです。

なお、MathML の記述に当たっては以下を参考にしました。

• MathML 日本語情報
• 数学用マークアップ言語 (MathML) バージョン 2.0 日本語版