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

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

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

* 工学部情報学科 第1学年後期配当・火曜日第3限・工学部8号館共同2
* 文学部・文学研究科の講義「情報・史料学 特殊講義」
* 13時0分〜14時30分 (TAへの質問:12時30分〜12時55分)
* TA
池田 智志君 (奥乃研M1・音声対話グループ)
神田 尚君 (奥乃研M1・ロボットグループ)

* TAのページ (運用中)

* 同じ教科書を使用した他大学での講義・演習

講義予定・宿題

* 10月 2日: 第1回 教科書1.1節
宿題は, Ackermann関数, Ex.1.13
提出先は, 10号館1階事務室前レポート箱 (期限は10月9日12:00)
* 10月 9日: 第2回 TUT Scheme の使い方 平石君(湯淺研D3)
宿題は, factorial (recusive版, iterative 版) を実際に動かし, トレースを提出
提出先は, 10号館1階事務室前レポート箱 (期限は10月16日12:00)
* 10月16日:第3回 教科書1.1節, 1.2節
宿題は, Ex.1.5, 1.6, count-change 実際に動かし, 分割数を提出
提出先は, 10号館1階事務室前レポート箱 (期限は10月23日12:00)
* 10月23日:第4回 教科書1.2節, 1.3節

* 10月30日: 中間テスト (範囲は第4回まで)

* 11月 6日:第6回 教科書2.1節
予習をしてくること.

* 11月13日:第7回 教科書2.2.1節
* 11月20日:第8回 教科書2.2.2, 2.2.3節
* 11月27日:第9回 教科書2.2.4節
* 12月 4日:第10回 図形言語
* 12月11日:第11回 教科書2.3節
* 12月18日:第12回 教科書第2.4節, 2.5節 (2.5.2含 迄)
* 1月 8日:第13回 ソーティング
* 1月15日:第14回 ソーティング, ハッシュ技法
* 2月 5日:期末試験 (FYI)
8号館共同2, 共同5
(試験範囲は第5回から第14回)

課題

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

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

*【随意課題】  自由課題です.例えば, 下記のようなものが考えられます.
【随意課題1】   (提出期限2008年2月22日 奥乃の部屋まで)
Participate ACM Inter-University Programming Contest (H18年度1名参加)

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

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

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

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

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

【随意課題7】 (申請期限2008年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 講義関係のページ   2006年度アルゴリズムとデータ構造入門  2006年度TAのページ

Copyleft (C) 2007-2008. All wrongs reserved.
Last modified: Wed Oct 31 15:58:29 2007
奥乃博