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

科目コード 91150
配当学年 1年
開講期 後期
曜時限 火曜・3時限
講義室 総合研究8号館講義室2
単位数 2
履修者制限
講義形態 講義・演習
言語
担当教員 吉井和佳, 馬谷誠二, 糸山克寿

講義概要

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

評価方法

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

最終目標

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

講義計画

項目 回数 内容説明
導入 1 ・ 講義の目標、抽象化とは
・ Scheme言語入門
1章 手続きによる抽象化 5 1.1章 プログラミングの要素
1.2章 手続きとその生成するプロセス
1.3章 抽象化の高階手続きによる形式化
2章 データによる抽象化 5 2.1章 データ抽象化とは
2.2章 階層データ構造と閉包性
2.3章 記号データ
2.4章 抽象データの多重表現
2.5章 汎用演算のシステム
ソーティング(整列)アルゴリズム 3 ・ 整列アルゴリズムの設計と解析
・ 挿入ソート・選択ソート・シェルソート
・ クイックソートとピボットの選択法
・ ヒープソート・・ マージソート
・ 辞書式順序・バケットソート・基数ソート
学習到達度の確認 1 ・期末試験
・必修課題2「図形言語」を使用した演習

教科書

・ ジェラルド・サスマン他著(和田英一訳): 『計算機プログラムの構造と解釈』 (ピアソン・エデュケーション)
・ 原著 "Structure and Interpretation of Computer Programs" (MIT Press) を薦めます
オンライン版フルテキスト (MIT Press 提供)

参考書

・ ジョン・ベントリー(小林健一郎訳): 『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』(ピアソン・エデュケーション) 
・ 原著 "Programming Pearls" (ACM Press) を薦めます .

予備知識

計算機科学概論(91130)
基礎情報処理演習 あるいは,学術情報メディアセンターでの編集などの基本操作ができること.

授業URL

講義情報は,Web page で公開します.TAのサポートページへのリンクもあります.
全講義情報 には過年度の情報(過去問を含む)を掲載してあります.
・ 古典力学に興味のある学生には,Gerald Jay Sussmanらの著書"Structure and Interpretation of Classical Mechanics"を本講義の続きとして独習することを勧めます.

その他

・ 受講生の理解度や進捗状況などに応じて一部省略や追加がありえます.
・ 図形言語による必修課題があります.過去の作品集をご覧ください.
・ やればやっただけ報われるシステムを採用しています.
・ 習熟度の早い学生に対しては,参考書を使ってより高度な随意課題を課す等の配慮を行います.
・3Dプリンタを使用して,図形言語で立体像を作成することもできます.希望者は申し出ること.