科目名 : アルゴリズムとデータ構造入門

科目コード 91150
配当学年 1学年
開講期 後期
曜時限 火曜・3時限
講義室 共同2
単位数 2
履修者制限
講義形態 講義・演習
言語
担当教員 奥乃 博

講義概要

コンピュータ上で計算を行うプログラムはデータ構造とアルゴリズムから構成されます. 本講義では, プログラミングの概念についてコンピュータサイエンスの立場から学びます. 使用するプログラミング言語は Scheme です. 基本的なプログラミングの概念について学ぶとともに, 実際にプログラミングを経験することを通じて, プログラミングの本質である手続き抽象化とデータ抽象化を習得します.
本講義では教科書の前半の話題を取り上げ, 後半は「プログラミング言語」(90170)(湯淺先生, 第2学年前期配当, 90170)で取り上げます.本講義の到達目標は, 教科書の第2章まですべての練習問題も含めて理解することです.

評価方法

試験80%
課題20%
  課題1: ほぼ毎回の宿題をレポート形式で提出
  課題2: 図形言語を使用して,painter, 空間充填曲線,フラクタルを作成
随意課題を提出した場合,合格点に達していれば,さらにプラスアルファをする

最終目標

1)手続きの抽象化とデータの抽象化の概念を習得
2)アルゴリズムやデータ構造の概念をSchemeを使ってプログラミングする能力を習得
3)図形言語を使用し,複雑な図形をスマートに描画する手法を学修

講義計画

項目 回数 内容説明
導入 2 ・ 講義の目標、抽象化とは
・ 計算機の歴史
・ Java版Scheme (jakld) の使い方
1章 手続きによる抽象化 4 1.1章 プログラミングの要素
1.2章 手続きとその生成するプロセス
1.3章 抽象化の高階手続きによる形式化
2章 データによる抽象化 5 2.1章 データ抽象化とは
2.2章 階層データ構造と閉包性
2.3章 記号データ
2.4章 抽象データの多重表現
2.5章 汎用演算のシステム
ソーティング(整列)アルゴリズム 2 ・ 整列アルゴリズムの設計と解析
・ 挿入ソート・選択ソート・シェルソート
・ クイックソートとピボットの選択法
・ ヒープソート・・ マージソート
・ 辞書式順序・バケットソート・基数ソート

教科書

・ ジェラルド・サスマン他著(和田英一訳): 『計算機プログラムの構造と解釈』("http://www.amazon.co.jp/exec/obidos/ASIN/489471163X/photoinfo-22";) (ピアソン・エデュケーション)
・ 原著 "Structure and Interpretation of Computer Programs" (http://www.amazon.co.jp/exec/obidos/ASIN/0262510871/photoinfo-22) (MIT Press) を薦めます
・ オンライン版フルテキスト(http://mitpress.mit.edu/sicp/) (MIT Press 提供).

参考書

・ ジョン・ベントリー(小林健一郎訳): <a href="http://www.amazon.co.jp/exec/obidos/ASIN/4894712369/photoinfo-22";>『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』</a>(http://www.amazon.co.jp/exec/obidos/ASIN/4894712369/photoinfo-22)(ピアソン・エデュケーション)
・ 原著 "Programming Pearls" (ACM Press) を薦めます.

予備知識

・ 基礎情報処理演習(23015)
・ あるいは, 学術情報メディアセンターでの編集などの基本操作ができること. bfテスト

授業URL

・ 講義情報(http://winnie.kuis.kyoto-u.ac.jp/~okuno/Lecture/09/IntroAlgDs/)は, Web page で公開します. TAのサポートページへのリンクもあります.
・ 昨年度の講義は, 京都大学オープンコースウェア(OCW)(http://ocw.kyoto-u.ac.jp/jp/engineering/course07/index.htm) にも掲載されています. 奥乃の講義情報(http://winnie.kuis.kyoto-u.ac.jp/~okuno/Lecture/) には過年度の情報(過去問を含む)を掲載してあります.
・ 古典力学に興味のある学生には、Gerald Jay Sussmanらの著書Structure and Interpretation of Classical Mechanics(http://mitpress.mit.edu/SICM/)を本講義の続きとして独習することを勧めます.

その他

・ Java版Scheme, jakld (湯淺先生開発)を使用して講義を進めます. メディアセンターで提供されています.
・ 毎回, 一部の練習問題を宿題として出しますので, 翌週の火曜日正午までに情報学科レポート提出箱に提出してください.
・ 受講生の理解度や進捗状況などに応じて一部省略や追加がありえます.
・ 図形言語による必修課題があります. 過去の作品集(http://winnie.kuis.kyoto-u.ac.jp/~okuno/Lecture/Gallery/)をご覧ください.
・ やればやっただけ報われるシステムを採用しています.
・ 習熟度の早い学生に対しては, 参考書を使ってより高度な随意課題を課す等の配慮を行います.
・ 計算機科学コース実験4では, XS-Lisp(http://www.xslisp.com/) を用いたLego Mindstom による「ロボットプログラミング」も開講しています.
・ 講義のページは http://winnie.kuis.kyoto-u.ac.jp/members/okuno/Lecture/ です.