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

宿題は, Ex. 1.1, 1.2, 1.3, 1.4, Ackermann関数

提出先は, 10号館1階事務室前レポート箱 （期限は10月10日10:30）

レポート講評

10月10日： 第2回 TUT Scheme の使い方 平石君（湯淺研D2）

宿題は, Scheme (TUS, MIT-Scheme, Dr.Schemeなど）を使ってみること.

10月17日：第3回 教科書1.1節, 1.2節

宿題は, Ex.1.6, 1.8, 1.10, 両替のプログラムを動かし, $1と$3の両替が何通りあるかをレポート.

提出先は, 10号館1階事務室前レポート箱 （期限は10月23日17:30）

レポート講評

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

宿題は, Ex.1.11, 1.12, 1.13, 1.14, 1.16, 1.19

提出先は, 10号館1階事務室前レポート箱 （期限は10月30日17:30）

レポート講評

10月31日：第5回 教科書1.2

宿題は, Ex.1.21, 1.26, 1.27, 1.30, 1.32, 1.33

提出先は, 10号館1階事務室前レポート箱 （期限は11月6日17:30）

レポート講評

11月 7日：第6回 教科書1.2, 1.3節

宿題は, Ex.1.40, 1.41, 1.42, 1.43

提出先は, 10号館1階事務室前レポート箱 （期限は11月13日17:30）

レポート講評

11月14日：第7回 教科書2.1節

宿題は, Ex.2.1, 2.2, 2.4, 2.5, 2.6, 2.7

提出先は, 10号館1階事務室前レポート箱 （期限は11月20日17:30）

レポート講評

11月21日：第8回 教科書2.2.1, 2.2.2節

宿題は, なし （11月祭のため）

11月28日：第9回 教科書2.2.3節

宿題は, なし

12月 5日：第10回 中間試験

12月12日：第11回 教科書2.2.4節 図形言語 必修課題の説明を行うので, 出席すること.

宿題は, Ex.2.37, 2.38, 2.39, and 2.42

提出先は, 10号館1階事務室前レポート箱 （期限は12月18日17:30）

12月19日：第12回 教科書2.3節

宿題は, Ex.2.56, 2.57, 2.63, 2.64, 2.65

提出先は, 10号館1階事務室前レポート箱 （期限は1月9日12:00）

1月 9日：第13回 教科書第2.4節, 2.5節, ソーティング

宿題は, Ex.2.73, Ex.2.81 (必ずやること)

提出先は, 10号館1階事務室前レポート箱 （期限は1月15日17:30）

1月16日：第14回 ソーティング, ハッシュ技法 予習をしてくること

2月 6日：期末試験 (FYI)

8号館共同2, 共同3

(試験範囲は第11回から第14回)

課題

必修課題

【必修課題１】　 第２章までの宿題 （毎週提出）
〆切に遅れたり, 動作確認していないものは減点. Better later than never.

【必修課題２】　 図形言語の課題 (ソースプログラムは奥乃までメイルで送付すること)
提出先は, 10号館1階事務室前レポート箱 （期限は2月22日午後5時）
卒業する方は2月15日午後5時.

【随意課題】　 自由課題です．例えば, 下記のようなものが考えられます.

【随意課題１】　
Participate ACM Inter-University Programming Contest (H17年度1名参加)

【随意課題２】　（提出期限2007年3月15日 奥乃の部屋まで）
第２章までのすべての練習問題 （宿題分は改めて提出する必要なありません :-) ）
動作確認していないものは減点.

【随意課題３】　（提出期限2007年3月15日 奥乃の部屋まで）

• Scheme によるプログラム・アルゴリズムの動きの可視化 （例えば, 下記の例を参照）
• Fixed-Point 探索の過程をグラフに表示せよ. (H16年度2名)

【随意課題４】　　（提出期限2007年3月15日 奥乃の部屋まで）
これはすごいという抽象化を使った Scheme プログラム. (H17年度2名提出). 例えば,

• 整数論・群論・組合せ論
• 線形計画法・古典力学 (福嶋先生の講義の復習にもなります.)
• パズル解法・ゲーム・数独

【随意課題５】　　（提出期限2007年3月15日 奥乃の部屋までレポート・作品・プログラムを）
湯淺先生開発のLego Mindstoms 用 Lisp XSを 使って, 気のきいた挙動をする自律ロボットを作れ.

【随意課題６(難問)】　（提出期限2007年3月15日 奥乃の部屋まで）
図形言語の frame を円板にして, Escher の circle-limit を作成. (H17年度1名提出)

【随意課題７】　（申請期限2007年2月22日 奥乃の部屋まで）
本講義で, 困っている友人の援助をし, ＴＡの手助けをする.

• 毎回の宿題・レポートで誰の援助をしたかを, 提出レポートの中に明記すること.
• できれば, 友人が困っていたことをできるだけ詳細にレポートすること.

シラバス

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

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

• 工学部シラバス　　 PDF

• TAのページ

評価方法

• 試験： ８０点 (中間試験・期末試験)

• 必修課題： ２０点 (課題は２つ)

• 随意課題をどれか１題提出し, その内容があるレベルを越えており, さらに, 試験・必修課題が最低合格点を満たしていた場合には, 最終成績を１ランクあるいは２ランク上げます. ただし, 上限は１００点です. （教務で１００点にされてしまいますー :-)

本講義を最後まで受け，試験を受け，さらに，必修課題を提出した人の成績の 平均は過去２年間７５点を越えています．

教科書

• ジェラルド・サスマン他著（和田英一訳）: 『計算機プログラムの構造と解釈』 (ピアソン・エデュケーション）

• 訳者のページ （東京大学名誉教授・ IIJ 研究所所長）

• 原著 "Structure and Interpretation of Computer Programs" (MIT Press) を薦めます.

• オンライン版フルテキスト (MIT Press 提供, ただ！)

• SICP in Texinfo format (Emacs 用フォーマット)

本講義は「教科書は持っているもの」として進めます.

Schemeの使い方

Schemeの処理系

2005年度TAの村瀬君による Schemeの処理系いろいろ

TUT Scheme

TUT Scheme （湯淺先生小宮先生開発）を使用して講義を進める.

マニュアル

ダウンロード

cygwin 版 TUT-Scheme には random が入っていません. この定義をお使い下さい.

小宮先生提供ファイル. (なお, tus2, tustk2 には入っています. )

TUS2 + HTML/Javascrip の組合せも使えます. Windows native で. (cygwin 不要)

詳細は小宮先生のページにあります.

Cygwin 上で tustk/tustk2 を使用していて, file を読ませるとうまく動かない人は, 改行が"nl (¥n)"であることを確認して下さい.

1. od -a ファイル | more で改行が "cr nl" か"nl"だけかをチェック.

2. もし "cr nl" ならば, tr '¥r' ' ' < 古いファイル > 新しいファイル名 で, nl" に変換.

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

TUS/TK本体： /usr/local/bin/{tustk,tustk2}

サンプル (piclを含む)： /usr/local/lib/tustk/demos

サンプル： デモ

前田君による cygwin の下での TUT Schemeの使い方 TUT Scheme under cygwin

MIT Scheme

伊奈君による MIT Schemeの使い方

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

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

(setup) で3つの window が出現.

(paint g1 wave), (paint g2 (square-limit orida-sensei 2)) で描画.

参考書・自習の助け

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

• 和田先生のページ （東京大学名誉教授・ IIJ 研究所所長）
• Video Lecture by Hal Abelson and Gerald J. Sussman (MIT)
• 6.001 SICP（MIT OpenCourseWare）
• Course Ware (京都大学オープンコースウェア)
  2004年度「アルゴリズムとデータ構造」公開中.
• Course Ware (Art Digital University)

• Google with SICP (練習問題の解答を見るのは自分で解いてからにしてください！)
• LispやScheme本

• 古典力学に興味のある学生には, 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回生, 「データ構造」受講生, 現奥乃研M2).
• 各種ソーティングの比較デモ by 桐生 幸歩君 (2003年度理学研究科修士課程, 「データ構造」受講生).
• 各種ソーティングのデモ by 横山 憲司君 (2000年度東京理科大学理工学部情報科学科3年生) 他.
• ナップザック問題 by 浅水 太一君 (2004年度情報学科計算機科学コース2回生, 「データ構造」受講生).
• ハノイの塔 by 北原 鉄朗君 (2000年度東京理科大学理工学部情報科学科3年生, 現奥乃研D3).
• スタックによるポーランド記法の式の実行 by 北原鉄朗君 (2000年度東京理科大学理工学部情報科学科3年生, 現奥乃研D3).
• 木の走査 by 横山 憲司君 (2000年度東京理科大学理工学部情報科学科3年生).

Amazon なか見検索

Back to 講義関係のページ　　　2005年度アルゴリズムとデータ構造入門