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

(工学部情報学科第1学年後期配当・火曜日第3限・工学部8号館共同2)
13時00分〜14時30分 (TAへの質問:12時30分〜12時55分)


私の宿題の出し方が厳しいと思われるかも知れません。
しかし、真面目に取り組めば、報われることも多々ありますよ。

Err, and err, and err again,
but less, and less, and less.

by Donald Knuth

ACM Inter-Collegiate Programming Contestに参加しよう.
祝 京大チームACM/IPC2005世界大会出場

興味のある方は, 八杉先生まで連絡してください.

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

必修課題3を掲載しました. 〆切は2月22日17時です. (卒業される方は15日17時)

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 ) を使用して下さい. (動作確認済み)


シラバス・TA

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

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


教科書


参考書


補足 2005年 お年玉

誤解を恐れずに大雑把にいうと, λ計算では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 の使い方 平石君(湯淺研M2)場所は共同2
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)) は瞬時に終わるので0が返ってくる可能性あり
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回)

飛ばした練習問題を、自由課題として提出した場合には、プラスアルファとなります。

課題

随意課題を提出し、その内容があるレベルを越えており、さらに、 試験・レポートが最低合格点を満たしていた場合には、 最終成績を1ランクあるいは2ランク上げます。 ただし、上限は100点です。(教務で100点にされてしまいますー :-)


参考情報


2004年度受講生作品集


アルゴリズムの可視化


Back to 講義関係のページ   2004年度データ構造   2005年度本講義
Copyleft (C) 2004-2005. All wrongs reserved.
Last modified: Wed Feb 23 00:06:28 2005
奥乃博