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

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

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

Follow-up授業として試験の一解答案を公開します(Feb. 11, 2014)

随意課題を提出する方は okuno＠nue.org に送ってください．(Feb. 18, 2014)

* 工学部情報学科 第1学年後期配当・火曜日第3限・場所は総合研究８号館講義室２
* 文学部・文学研究科の講義「情報・史料学 特殊講義」
* 13時0分〜14時30分 （TAへの質問：12時40分〜12時55分） No Student Left Behind
*担当教員: 奥乃 博 教授
馬谷 誠二助教 糸山 克寿助教
*TA
池宮 由楽君 （奥乃研M1・音楽情報処理グループ）
坂東 宜昭君 （奥乃研M1・ロボット聴覚グループグループ）
古川 孝太郎君 （奥乃研M1・ロボット聴覚グループ, KMC）

* TAのページ
* 京都大学教務情報システム KULAISIS もたまには見て下さい. (仕分けの対象になってしまいます)

* JAKLD Java版組み込み用Scheme (湯淺先生作成) を使用します.
* レポートは LaTeX で作成すること. (学術情報メディアセンターには完備)
* レポートは Emacs で作成すること. (学術情報メディアセンターには完備)
  • コマンドは，連想式（Cntlは文字単位，Metaは単語単位，C-MはＳ式単位）
  • .emacs に (setq scheme-program-name "java -jar d:/java/Scheme/jakld.jar") を入れておくと，emacs の中からM-X run-scheme でJAKLDが起動できる．
  • Emacs は Emacs-Lisp で作成 (初代 Emacs は，Emacs-TECO)
  • Emacs はプログラミング環境 （奥乃： エディタ：論説：マン・マシン・インタフェースとしてのエディタ, 情報処理, Vol.25, No.8 (Aug. 1984) pp.865-868, 情報処理学会. PDF)

講義予定・宿題

* 10月 1日： 第1回 オリエンテーション，Scheme入門 先生（助教, 五十嵐研）
Slides
教科書を1-1-1 〜 1-1-3を読む
PDFのファイル名は "学生番号-姓名-回数.pdf" とすること (例: 1029234567-AkiAmano-1.pdf)
提出先は, sicp-1 at zeus.kuis.kyoto-u.ac.jp （期限は10月7日24:00）
優秀なレポート提出者（敬称略） 　
  • 鈴木善樹 　　
  • 枡井啓貴 (pdf ) 　　
  • 山田淳二 (pdf )
  • 奥野僚介
  • 小池拓矢
  • 嶋 隼輝
  • 秋田大空
  • 磯西市路
* 10月 8日： 第2回 教科書1.1節, 1.2節
Slides, Handout
宿題: 再帰型階乗，教科書 1-1-4 〜 1-2-2 をレポート
PDFのファイル名は "学生番号-姓名-回数.pdf" とすること (例: 1029234567-AkiAmano-2.pdf)
提出先は, sicp-2 at zeus.kuis.kyoto-u.ac.jp （期限は10月14日24:00）
優秀なレポート提出者（敬称略）
  • 中井 裕介
  • 枡井啓貴
  • 山田淳二
  • 大家理和
  • 小池拓矢
  • 勝見久央
  • 柴田健太郎
  • 立松美雪
* 10月22日： 第3回
Slides, Handout
宿題: 反復型階乗，教科書 1-2-3 〜 1-3-1 をレポート
PDFのファイル名は "学生番号-姓名-回数.pdf" とすること (例: 1029234567-HarukoAmano-3.pdf)
提出先は, sicp-3 at zeus.kuis.kyoto-u.ac.jp （期限は10月28日24:00）
優秀なレポート提出者（敬称略）
  • 鈴木善樹 (2)
  • 枡井啓貴 (3)
  • 山田淳二 (3)
  • 大家理和 (2)
  • 伊藤海斗
  • 奥野僚介 (2)
  • 磯西市路 (2)
  • 高山勉
  • 津島啓晃
* 10月29日：第4回 教科書1.2節
Slides
宿題: Fibonacci number, 教科書 1-3-2 〜 1-3-4 をレポート
PDFのファイル名は "学生番号-姓名-4.pdf" とすること (例: 1029234567-HarukoAmano-4.pdf)
提出先は, sicp-4 at zeus.kuis.kyoto-u.ac.jp （期限は11月4日24:00）
優秀なレポート提出者（敬称略）
  • 枡井啓貴 (4)
  • 山田淳二 (4)
  • 横山悠
  • 遠藤ルッカス良
  • 奥野僚介 (3)
  • 延田和磨
  • 伊藤博典
  • 加田昇
  • 高山勉 (2)
* 11月 5日： 第5回 教科書1.3節 糸山先生
宿題: EX1.29, 1.31, 教科書 2 〜 2-1-2 をレポート
PDFのファイル名は "学生番号-姓名-5.pdf" とすること (例: 1029234567-HarukoAmano-5.pdf)
提出先は, sicp-5 at zeus.kuis.kyoto-u.ac.jp （期限は11月11日24:00）
優秀なレポート提出者（敬称略）
  • 枡井啓貴 (5)
  • 山田淳二 (5)
  • 横山悠 (2)
  • 三鼓悠
  • 大家理和 (3)
  • 紫藤佑介
  • 柴田健太郎(2)
  • 嶋隼輝(2)
  • 磯西市路 (3)
* 11月12日：第6回 教科書1.3節
宿題: 教科書 2-1-3 〜 2-2-2 をレポート, Ex.2.17~2.28
PDFのファイル名は "学生番号-姓名-6.pdf" とすること (例: 1029234567-HarukoAmano-6.pdf)
提出先は, sicp-6 at zeus.kuis.kyoto-u.ac.jp （期限は11月18日24:00）
優秀なレポート提出者（敬称略）
  • 枡井啓貴 (6)
  • 山田淳二 (6)
  • 横山悠 (3)
  • 三鼓悠 (2)
  • 大家理和 (4)
  • 柴田健太郎(3)
  • 津島啓晃 (2)
* 11月19日：第7回 教科書2.1節, 2.2節
宿題: 友達をいっぱい作ること．
11月祭自主的協賛のため提出の必要はありません．
* 11月26日：第8回 教科書2.3節
宿題: 教科書 2-2-3 〜 2-2-4 をレポート，EX2.33〜2.42を解く
PDFのファイル名は "学生番号-姓名-8.pdf" とすること (例: 1029234567-HiromiSuzuka-8.pdf)
提出先は, sicp-8 at zeus.kuis.kyoto-u.ac.jp （期限は12月2日24:00）
優秀なレポート提出者（敬称略）
  • 山田淳二 (7)
  • 枡井啓貴 (7)
  • 五十嵐 雄
  • 藤原 紳
  • 三鼓悠 　(3)
  • 大家理和 (5)
  • 清水一浩
  • 柴田健太郎(4)
  • 津島啓晃 (3)
* 12月 3日：第9回　　図形言語 必修課題説明のため必ず出席すること
図形言語の種々のファイル
宿題: 図形言語の動作確認．
PDFのファイル名は "学生番号-姓名-9.pdf" とすること (例: 1029234567-MaedaAtsuko-9.pdf)
提出先は, sicp-9 at zeus.kuis.kyoto-u.ac.jp （期限は12月9日24:00）
優秀なレポート提出者（敬称略）
  • 鈴木 善樹(3)
  • 藤原 紳(2)
  • 中井 裕介(2)
  • 奥野 僚介(3)
  • 中村 玄貴
  • 柴田健太郎(5)
  • 若林慶

* 12月10日：第10回 教科書2.2, 2.3節 3D 図形言語
宿題: 微分システムを完成．
PDFのファイル名は "学生番号-姓名-10.pdf" とすること (例: 1029234567-HiromiSuzuka-10.pdf)
提出先は, sicp-10 at zeus.kuis.kyoto-u.ac.jp （期限は12月16日24:00）
優秀なレポート提出者（敬称略）
  • 鈴木 善樹(3)
  • 藤原 紳(2)
  • 中井 裕介(2)
  • 奥野 僚介(3)
  • 中村 玄貴
  • 柴田健太郎(5)
  • 若林慶

* 12月17日：第11回
宿題: 教科書 2-3 〜 2-5-2 をレポート
PDFのファイル名は "学生番号-姓名-11.pdf" とすること (例: 1029234567-HiromiSuzuka-11.pdf)
提出先は, sicp-11 at zeus.kuis.kyoto-u.ac.jp （期限は1月6日24:00）
優秀なレポート提出者（敬称略）
  • 横山 悠
  • 山田 淳二
  • 枡井 啓貴
  • 内藤純平
  • 三鼓悠
  • 勝見久央
  • 柴田健太郎(6)

* 1月 7日：第12回　教科書2.4節・ソーティング （教科書終了）
宿題:
PDFのファイル名は "学生番号-姓名-12.pdf" とすること (例: 1029234567-NatsuAmano-12.pdf)
提出先は, sicp-12 at zeus.kuis.kyoto-u.ac.jp （期限は1月13日24:00）
優秀なレポート提出者（敬称略）
  • 枡井 啓貴
  • 鈴木 善樹
  • 中井 裕介
  • 三鼓悠
  • 勝見久央
  • 清水一浩
  • 津島啓晃

* 1月17日：第13回 ソーティング
宿題:
PDFのファイル名は "学生番号-姓名-13.pdf" とすること (例: 1029234567-NatsuAmano-13.pdf)
提出先は, sicp-13 at zeus.kuis.kyoto-u.ac.jp （期限は1月23日24:00）
優秀なレポート提出者（敬称略）
  • 山田 淳二
  • 枡井 啓貴
  • 鈴木善樹
  • 三鼓悠
  • 野口拓馬
  • 柴田健太郎
  • 津島啓晃
* 1月21日：第14回 ソーティング・ハッシング
宿題はありません．復習をしっかり行なって試験に臨んで下さい．

*1月28日, 8号館NSホール： 期末試験 (2012, 2011, 2010, 2009)

Follow-up授業として試験の一解答案 を公開します (Feb. 11, 2014)

課題

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

レポートを書くためのスタイルファイル・例
このdirectoryにあります.

【必修課題２】　 図形言語の課題 (ソースプログラムは奥乃までメイルで送付すること)
提出先は, メイルで （期限は2月9日午後4時）

卒業する方は2月3日午後4時.

レポートには, 工夫した点やアルゴリズムを明記して下さい.

*【随意課題】　 自由課題です．例えば, 下記のようなものが考えられます.
【随意課題１】　　　（提出期限2014年2月15日 奥乃 okuno at nue.org まで）
Participate ACM Inter-University Programming Contest (H18〜21年度毎年1名参加)

【随意課題２】　（提出期限2014年2月15日 奥乃 okuno at nue.org まで）
第２章までのすべての練習問題 （宿題分は改めて提出する必要なありません :-) ）
動作確認していないものは減点. (毎年複数名)

【随意課題３】　（提出期限2014年2月15日 奥乃 okuno at nue.org まで）

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

【随意課題５】　　（提出期限2014年2月15日 奥乃 okuno at nue.org まで）
湯淺先生開発のLego Mindstoms 用 Lisp XSを 使って, 気のきいた挙動をする自律ロボットを作れ. (H18年度1名)

【随意課題６(難問)】　（提出期限2014年2月15日 奥乃 okuno at nue.org まで）
図形言語の frame を円板にして, Escher の circle-limit を作成. (H17年度, H19年度1名, H20, H21年度2名提出)

【随意課題７】　（申請期限2014年2月15日 奥乃 okuno at nue.org まで）
本講義で, 困っている友人の援助をし, ＴＡの手助けをする. (H19年度複数名, H20年度〜 2桁の方)
  • 毎回の宿題・レポートで誰の援助をしたかを, 提出レポートの中に明記すること.
  • できれば, 友人が困っていたことをできるだけ詳細にレポートすること.

シラバス

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

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

評価方法

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

2013年度も随意課題の＋α　を除いた時点で超えています．(Feb.15,2014)

教科書

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

Schemeの使い方

JAKLD Scheme (Java版組み込み用Scheme)

* Java 版 組み込み用Scheme (湯淺先生作成) を使用して講義を進める.
  • 図形言語 (& 末尾再帰) もサポート.
  • MIDI音源もサポート. マニュアル

  • Windows のコマンドプロンプトで実行可能.
    cygwin や Linux を使えば rlwrap (コマンドエディタ)が使えます.

  • java -jar jakld.jar で実行
    java -jar パス\jakld.jar (jakld.jar が違うdirectory/folder にある場合)

    (load "factorial.scm")
    (factorial 10)

  • 末尾再帰サポート有り・無しの2つの版がある. (有りの jalkd.jar を使用して下さい)

  • Android JALKD あり（2010年度受講生坂東 宜昭君開発）

その他のSchemeの処理系 (御使用の場合は自己責任で)

* 2005年度TAの村瀬君による 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の使い方

* 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

* TAのページ (運用中)

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

アルゴリズムの可視化

Amazon なか見検索  

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

(C) 2010-2015. All wrongs reserved.
Last modified: Tue Feb 18 6:07:01 JST 2014 奥乃博 No Student Left Behind