2004年度アルゴリズムとデータ構造入門

補足 図形言語機能付きの tustk の使い方

painter のプログラムは奥乃宛にメイルでも送付して下さい.
出力は下記の通りです.

(output-canvas 'foo.ps)

で foo.ps というポストスクリプトファイルが作成されますので, そのファイルをプリンタに出力して下さい.

TUT Scheme を使わずに, MIT Scheme を使う選択をされた方は, MIT-Scheme ではなく, MIT-Scheme-6001 をインストールして下さい.

また, コースウェアは ArtDigita University の コースウエア のページにある Problem Set 4 のプログラム ( go.scm, hend.scm, hutils.scm, prmpnt.scm ) を使用して下さい. (動作確認済み)

シラバス・ＴＡ

コンピュータ上で計算を行うプログラムはデータ構造とアルゴリズムから構成される． 本講義では，プログラミングについてコンピュータサイエンスの立場から 論じる。使用するプログラミング言語は Scheme であり、基本的なプログラミングの 概念について学ぶとともに、実際にプログラミングを経験することを通じて、 プログラミングの本質を習得することを狙う。

なお、本講義では教科書の前半の話題を取り上げ、後半は「プログラミング言語」 （湯淺先生, 第2学年前期配当, 90170）で取り上げる。

• 工学部シラバス　　PDF

• TA： 神田 直之君 （奥乃研M1）, 田崎 豪君 （奥乃研M1） 服部 祐哉君 （奥乃研M1）

教科書

• ジェラルド・サスマン他著（和田英一訳）: 『計算機プログラムの構造と解釈』 (ピアソン・エデュケーション）
  訳者のページ （東京大学名誉教授・ IIJ 研究所所長）
• 原著 "Structure and Interpretation of Computer Programs" (MIT Press) を薦める。
  オンライン版フルテキスト (MIT Press 提供)

参考書

• ジョン・ベントリー（小林健一郎訳): 『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』（ピアソン・エデュケーション）
• 原著 "Programming Pearls" (ACM Press) を薦める。

• Church Numeral とλ計算

誤解を恐れずに大雑把にいうと, λ計算ではScheme と違い, 名前つきのシンボル (名前付きの手続き) による再帰呼出しや special form が使えないので, 工夫が必要となります.

型付きλ計算では, このような処理がやさしくなります. 詳しくは, 佐藤先生の「計算と論理」で学んで下さい.

講義スケジュール・宿題

10月 5日： 第1回 教科書1.1節

宿題は、 Exercise 1.1, 1.2, 1.3. 提出先は、10号館1階事務室前レポート箱 （期限は10月18日午後5時）

10月12日： 第2回 TUT Scheme の使い方 平石君（湯淺研M２）場所は共同２

10月19日： 第3回 教科書1.1節

宿題は、 Exercise 1.4, 1.5, 1.6, 1.7, 1.8. 提出先は、10号館1階事務室前レポート箱 （期限は10月25日午後5時）

10月26日： 第4回 教科書1.2節

宿題は、 Exercise 1.9, 1.10, 1.11, 1.12, 1.13. 提出先は、10号館1階事務室前レポート箱 （期限は11月1日午後5時）

11月 2日： 第5回 教科書1.2 節

宿題は、 Exercise 1.14, 1.15, 1.16, 1.17, 1.18, 1.19, 1.20, 1.21, 1.22, 1.23, 1.24, 1.25, 1.26 提出先は、10号館1階事務室前レポート箱 （期限は11月8日午後5時）
問題1.23の runtime は (time 式) を使ってください。
例えば, (time (factorial 100)) や (time (fact 100)) のように
ただし, (time (factorial 3)) は瞬時に終わるので０が返ってくる可能性あり

11月 9日： 第6回 教科書1.3節

宿題は、 Exercise 1.29, 1.30, 1.31, 1.32, 1.33, 1.34 提出先は、10号館1階事務室前レポート箱 （期限は11月15日午後5時）

11月16日： 第7回 教科書1.3, 2.1節

宿題は、 Exercise 1.35, 1.36, 1.37, 1.38, 1.39, 1.40, 1.41, 1.42, 1.43 提出先は、10号館1階事務室前レポート箱 （期限は11月24日午後5時）

11月23日： 勤労感謝の日

11月30日： 第8回 教科書2.1, 2.2節

宿題は、 Exercise 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 2.8, 2.9, 2.10, 2.11, 2.12, 2.13, 2.14, 2.15, 2.16, 2.17, 2.18, 2.19, 2.20, 2.21, 2.22
提出先は、10号館1階事務室前レポート箱 （期限は12月6日午後5時）

12月 7日： 第9回 教科書2.2節

宿題は、 Exercise 2.23, 2.24, 2.25, 2.26, 2.27, 2.28, 2.29, 2.30, 2.31, 2.32, 2.33, 2.34, 2.35, 2.36, 2.37, 2.38, 2.39, 2.40, 2.411, 2.42, 2.43
提出先は、10号館1階事務室前レポート箱 （期限は12月13日午後5時）

12月14日： 第10回 教科書2.3節

宿題は、 Exercise 2.53, 2.54, 2.55, 2.56, 2.57, 2.58
提出先は、10号館1階事務室前レポート箱 （期限は12月13日午後5時）

12月21日： 第11回 教科書2.4節 (練習問題2-6の発展, 減算の定義 補足を参照のこと)

宿題は、 Exercise 2.59, 2.60, 2.61, 2.62, 2.63, 2.64, 2.65, 2.66, 2.67, 2.68, 2.69, 2.70, 2.71, 2.72, 2.73, 2.74, 2.75, 2.76
提出先は、10号館1階事務室前レポート箱 （期限は1月11日12時）

1月11日： 第12回 教科書2.3, 2.5節, sorting

宿題は、 Exercise 2.77, 2.78, 2.79, 2.80, 2.81, 2.82, 2.83, 2.84, 2.85, 2.86, 2.87, 2.88, 2.89, 2.90, 2.91, 2.92, 2.93, 2.94, 2.95, 2.96, 2.97, 2.98
提出先は、10号館1階事務室前レポート箱 （期限は1月17日17時）

1月18日： 第13回 教科書2.2節、図形言語 （予習をしてくること）

学術情報メディアセンターでの TUS/Tk の使い方

/staff/umatani/local/bin/{tustk,tustk2} TUS/TK本体

/staff/umatani/local/lib/tustk/demos サンプル (piclを含む)

デモ サンプル

宿題は、 Exercise 2.44, 2.45, 2.46, 2.47, 2.48, 2.49, 2.50, 2.51
提出先は、10号館1階事務室前レポート箱 （期限は1月15日17時）

2月1日： 期末テスト

(試験範囲は第1回から第13回)

• 【必修課題１】　 「コンピュータの歴史」について調査し、最低5枚のレポートとして提出。 分からない用語等は、用語集をつけること。（提出期限10月31日 10号館事務室へ）
  レポートの内容について、講義中に質問をし、理解度を確認することがある。 また、レベルの低いレポートは、再提出させる。

• 【必修課題２】　 第２章までのすべての練習問題 （毎週出していますので、改めて提出する必要なありません :-) ）
  動作確認していないものは減点。

  

• 【必修課題３】　図形言語（1月23日確定）
  締め切りは2月22日 (卒業される方は2月15日).
  1. 気のきいた painter を1種類作れ。（painter λ のプログラム）
  2. 空間充填曲線を1種類作れ。（例. 右図のHilbert curve, Peano curve）
  3. フラクタルを1種類作れ。（例. Koch curve, Snowflake, Sierpinski's Gasket）
  • tustk2 の使い方
  • 必修課題３のヒント
  • 作品集 (New)

  ---

• 【随意課題１】　（2004年度は終了）
  Participate ACM Inter-University Programming Contest

• 【随意課題２】　（提出期限2005年3月15日 奥乃の部屋まで）
  Fixed-Point 探索の過程をグラフに表示せよ. 1名提出 (正月明け)

• 【随意課題３】　　（提出期限2005年3月15日 奥乃の部屋まで）
  これはすごいという抽象化を使った Scheme プログラム。例えば、
  • 整数論・群論・組合せ論
  • 線形計画法・古典力学 1名提出 (1月下旬)
  • パズル解法・ゲーム
  

• 【随意課題４】　　（提出期限2005年3月15日 奥乃の部屋まで）
  図形言語の frame を円板にして, Escher の circle-limit を作成。

参考情報

• TUT Scheme （湯淺先生小宮先生開発）を使用して講義を進める。
• 当該年度の授業回数などに応じて一部省略、追加がありうる。
• 2〜3回のプログラム演習・レポートを課す。中間テストを行う場合もある。

• 習熟度の早い学生に対しては，参考書を使ってより高度な随意課題を課す等の配慮を行う。

• 古典力学に興味のある学生には、 Gerald Jay Sussmanらの著書 "Structure and Interpretation of Classical Mechanics" (MIT Press, 2001) を本講義の続きとして 独習することを勧める。
• オンライン版フルテキスト (MIT Press 提供)

• "Chaotic Evolution of the Solar System", Gerald Jay Sussman and Jack Sisdom, Science, 257, July 1992.
  The evolution of the entire planetary system has been numerically integrated for a time span of nearly 100 million years. This calculation confirms that the evolution of the solar system as a whole is chaotic, with a time scale of exponential divergence of about 4 million years. Additional numerical experiments indicate that the Jovian planet subsystem is chaotic, although some small variations in the model can yield quasiperiodic motion. The motion of Pluto is independently and robustly chaotic. HTML

２００４年度受講生作品集

アルゴリズムの可視化

• AVL木 by 村瀬 昌満君 (2002年度情報学科計算機科学コース2回生, 「データ構造」受講生).

• 各種ソーティングの比較デモ by 桐生 幸歩君 (2003年度理学研究科修士課程, 「データ構造」受講生).

• 各種ソーティングのデモ by 横山 憲司君 (2000年度東京理科大学理工学部情報科学科3年生) 他.

• ナップザック問題 by 浅水 太一君 (2004年度情報学科計算機科学コース2回生, 「データ構造」受講生).

• ハノイの塔 by 北原 鉄朗君 (2000年度東京理科大学理工学部情報科学科3年生, 現奥乃研D1).

• スタックによるポーランド記法の式の実行 by 北原鉄朗君 (2000年度東京理科大学理工学部情報科学科3年生, 現奥乃研D1).

• 木の走査 by 横山 憲司君 (2000年度東京理科大学理工学部情報科学科3年生).