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

アルゴリズムとデータ構造入門では, 『計算機プログラムの構造と解釈』 (SICP) の第1章と第2章をTUT-Scheme を使って習得するとともに, ソーティング, 探索, ハッシュについても学びます.

謹賀新年 2007年元旦
* 工学部情報学科 第1学年後期配当・火曜日第3限・工学部8号館共同2
* 文学部・文学研究科の講義「情報・史料学 特殊講義」
* 13時0分〜14時30分 (TAへの質問:12時30分〜12時55分)
* TA
糸山克寿君 (奥乃研M1・音楽グループ)
武田 龍君 (奥乃研M1・聖徳太子グループ)
福林雄一朗君 (奥乃研M1・音声対話グループ)

* TAのページ (質問はこちらに, New)

12月5日(火)の中間試験を病欠した人は教務掛に申し出て下さい.

[ 講義予定・宿題 | 課題 | シラバス | 評価 | 教科書 | TUT Scheme | 参考書 | 可視化 | 講義資料トップ ]

講義予定・宿題

* 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回)

課題

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

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

*【随意課題】  自由課題です.例えば, 下記のようなものが考えられます.
【随意課題1】 
Participate ACM Inter-University Programming Contest (H17年度1名参加)

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

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

【随意課題4】  (提出期限2007年3月15日 奥乃の部屋まで)
これはすごいという抽象化を使った Scheme プログラム. (H17年度2名提出). 例えば,
  • 整数論・群論・組合せ論
  • 線形計画法・古典力学 (福嶋先生の講義の復習にもなります.)
  • パズル解法・ゲーム・数独

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

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

【随意課題7】 (申請期限2007年2月22日 奥乃の部屋まで)
本講義で, 困っている友人の援助をし, TAの手助けをする.
  • 毎回の宿題・レポートで誰の援助をしたかを, 提出レポートの中に明記すること.
  • できれば, 友人が困っていたことをできるだけ詳細にレポートすること.

シラバス

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

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

評価方法

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

教科書

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

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)) で描画.

参考書・自習の助け

アルゴリズムの可視化

Amazon なか見検索  

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

Copyleft (C) 2006-2007. All wrongs reserved.
Last modified: Tue Jan 9 17:06:39 2007
奥乃博