2008 年度「計算数学１」

前期木曜４限（14 時 45 分から 16 時 15 分まで）です。 内容は先学期の「計算機基礎論３Ｂ」の続きです。 そのため、セクションや課題の番号は前からの続きになっています。

• 2008 年 04 月 10 日（木曜日） (1) ソートとは (§34-38)
  • §37 以降は次回にまわします。
• 2008 年 04 月 17 日（木曜日） (2) 素朴なソート (§39-44)
• 2008 年 04 月 24 日（木曜日） (3) 挿入ソート (§45-48) ［課題３］ 締め切りは 05 月 14 日（水曜日）
  • (48.2) で、ソートができたかどうかチェックするルーチンでは 「配列 a[ ] に 0 が代入されていないこと」をチェックすると書きましたが、 a[i] = rand(); のほうで初期化した場合には初期化の段階で 0 が代入されていることがありえるのでした。 （実際にはめったに起こりませんが。）
• 2008 年 05 月 01 日（木曜日） (4) プリントなし
• 2008 年 05 月 08 日（木曜日） (5) Shell ソート (§49-51) ［課題４］ 締め切りは 06 月 04 日（水曜日）
• 2008 年 05 月 15 日（木曜日） (6) プリントなし
• 2008 年 05 月 22 日（木曜日） (7) プリントなし
• 2008 年 05 月 29 日（木曜日） (8) ヒープソート (§52-54) ［課題５］ 締め切りは 07 月 02 日（水曜日）
• 2008 年 06 月 05 日（木曜日） (9) プリントなし
• 2008 年 06 月 12 日（木曜日） (10) マージソート (§55)　［オプション項目］
• 2008 年 06 月 19 日（木曜日） (11) 再帰 (§56-57)
  • 「ハノイの塔」のプログラムです。最初の二つは授業でやった範囲のＣ言語の知識で理解できるはずです。
    • hanoi.c 最も素朴に書いたもの。
    • hanoi2.c ほんの少し表示に凝りました。
    • hanoi2b.c 見た目は一つ上と同じですが、二重配列を使っています。
    • hanoi3.c 動画のように表示されます。円盤のまん中に棒あり。
    • hanoi3b.c 同上。円盤のまん中に棒なし。
    • hanoi4.c 中央の棒だけ上下逆に表示されるもの。枚数が多くても大丈夫。円盤のまん中に棒あり。
    • hanoi4b.c 同上。円盤のまん中に棒なし。
    • hanoi4c.c 同上。円盤のまん中に棒なし。円盤を二色で表示。
• 2008 年 06 月 26 日（木曜日） (12) クイックソート (§58-60) ［課題６］ 締め切りは 07 月 30 日（水曜日）
  • (58.2) の「N に比例する計算量」は「right-left+1 に比例する計算量」の間違いでした。
  • (58.3) あたりに、 「初めは left は 1, right は N でこの操作を行なう」 「やがて right-left+1 が 1 以下になるが、そのときは何もしなくてよい」 というような説明があるべきでした。
• 2008 年 07 月 03 日（木曜日） (13) （続き）
• 2008 年 07 月 10 日（木曜日） (14) （続き）
• 2008 年 07 月 17 日（木曜日） (15) 予定のところまで終わったので授業なし