SortExercise

Uselessness

問い †

• ソート(並び替え)の仕様(説明)を書きなさい。
  • "How to SORT"(手続き)でなく、"What we can call SORT"(仕様)を書くこと。
  • あなたがプログラミング演習で「ソート」プログラムを書けない(例示などでは納得できない)物分りの悪い学生に、ソートとは何か０から説明する先生になったつもりで。

• ただし、以下のような回答だと不正解とする。
  • 例示を含む(ソートの手続き(プログラム)は例示とみなす。)
  • 同語反復 (e.g. ソートとは並べることである)
  • 冗長
  • 用語の定義が曖昧(未定義の基礎概念の使用は最小にとどめ、その概念の出典などを明示すること。)
  • ソート以外を含む不要に一般的すぎる定義 (e.g., ソートはチューリングマシンである)
  • 「空間」・「配置」・「順序」・「配列」とかの概念を定義せず使う(この概念より簡潔に解答可能なので、冗長)

背景・出題意図 †

• Marr (1982)の"計算理論"レベルの説明の含意を理解するのは難しい。計算理論レベルとは、計算を手続き(アルゴリズム)と独立に説明するレベルであり、いわゆるプログラムの仕様である。

• プログラムの良し悪し(バグ)は、この仕様に適した計算手続きとなっているかで判断されるため、手続きとは独立に説明されていなければならない。

• この基礎的概念を理解するための演習として上記の問題を考えよう。

誤解答例 (この解答例は、雑談メンバーから寄せられたものです。ご協力ありがとうございます。) †

• ソート（並び替え）とは，任意の要素列を「昇順に並んだ」要素列へ変換する手続きをいう．
  • 半順序ではない/ 同語反復(並んだ)

• 「3, 1, 2」を「1, 2, 3」にするのが、「ソート」です。
  • 例示からの帰納推論を前提にするは不可

• 集合 A の要素を一列に重なりなく配置して作られた「列」を考える．仮に，列の一方の端を「小」，他方の端を「大」と呼ぶ．
  • 「列」とは何か未定義。同様に「端」も未定義。

• ある記号列を個々の記号がもつ意味（性質）と定められた規則にしたがい，停止判定されるまで繰り返し操作すること。
  • 一般的すぎて、ソート以外の計算を含む。物分りの悪い学生が「ソートとして"1+1->2"というプログラムを書いて、停止判定される事を確認しました。これで課題達成ですね。」と主張しても文句を言えない。

• 有限集合 X，その部分集合 X_1, X_2, …, X_n \subset X，および X_i (i = 1, …, n) に対して定義された全順序関係 R_i が与えられたとき，全ての i について，部分集合 X_i の全ての元を R_i を満たすように順番に出力して停止する．
  • これは手続きの記述である。手続きとは独立に説明すること。

• ソートとは「配列内の要素の位置を表す2つの添字 i, j が i < j のとき、 (i番目の要素) <= (j番目の要素)が常に成り立つように配列の要素を並べ替えること」
  • 「配列」という用語をもう少し噛み砕いて説明しよう。「配列」はある概念を特定の計算機実装で表現したものです。

模範解答 †

日高までご連絡をください。