アルゴリズムとプログラム設計 -Algorithms and Program Design-

担当教員・研究室 配当年次 学期 種別 単位数 授業形態 開講年度 ナンバリングコード
穴田 有一 852研究室
2年 後期 選択 2 単位
講義（対面）
2021 SCM215
アクティブラーニング
はい
授業概要
　データ構造とアルゴリズムの基礎を修得し，それらをプログラム設計に役立てる方法を学びます。データ構造とアルゴリズムの構成法は，プログラミングの習得に必要なだけでなく，プログラム設計にも欠かすことのできない基礎知識です。講義では，データ構造の作り方によってアルゴリズムの良否，複雑さが大きく影響されることへの理解も深めます。題材としては，計算量の他に，アルゴリズムの表現法，データ構造，探索法，整列法（ソート）などをとりあげます。また,データ構造とアルゴリズムを表現する言語には原則としてJavaを用います。この科目は情報科学の基礎的科目の一つであることを自覚して学習を進めてください。
　授業の進め方について，できるだけ例題を多くして，データとアルゴリズムが相まって各ステップで状態がどのように変化していくか視覚的にとらえやすいような説明を考えていきます。また，毎回の授業の最初に，前回授業の知識定着を確認するための演習問題を行います。その際には，自分自身で解答したあと，その内容について他の学生とディスカッションを行います。授業の途中では，ピアインストラクション（解答投票-ディスカッション-解答投票）による理解度の確認を行います。
授業における学修の到達目標
１．基本的なアルゴリズムの計算量を評価することができる。
２．適切な方法でアルゴリズムを表現することができる。
３．基本的なデータ構造を理解しデータの操作ができる。
４．基本的な整列法を理解しデータの整列ができる。
授業計画
回数 授業、事前・事後学習 時間
1 事前学習 シラバスをよく読み，授業の趣旨・目的をよく考える．また，教科書の1.1.1節をよく読んでおく． 2.0
授業 データ構造とアルゴリズムの基本
事後学習 授業内容をまとめる． 2.0
2 事前学習 教科書の1.1.2～1.1.3節をよく読んで，疑問点をメモしておく． 2.0
授業 アルゴリズムと計算量
事後学習 教科書の問題1.1，問題1.2，問題1.3を学習する． 2.0
3 事前学習 事前配布資料をよく読んでおく． 2.0
授業 構造化プログラミング
前回学習範囲の演習問題（アルゴリズムと計算量）を学習する．
事後学習 DijkstraのACMチューリング賞受賞記念講演抜粋の要点をまとめ，感想を書く． 2.0
4 事前学習 教科書の2.1節をよく読んでおく． 2.0
授業 配列を使った基本操作
事後学習 宿題1aを学習し，POLITE2（Moodle）にアップロードする． 2.0
5 事前学習 教科書の2.2.1～2.2.2節をよく読んで，疑問点をメモしておく． 2.0
授業 連結リスト
前回学習範囲の演習問題（配列の基本操作）を学習する．
事後学習 宿題1bを学習し，POLITE2（Moodle）にアップロードする． 2.0
6 事前学習 教科書の2.2.3節をよく読んで，疑問点をメモしておく． 2.0
授業 連結リストの基本操作
前回学習範囲の演習問題（連結リスト）を学習する．
事後学習 宿題1cを学習し，POLITE2（Moodle）にアップロードする． 2.0
7 事前学習 教科書の2.3.1～2.2.3節をよく読んで，疑問点をメモしておく． 2.0
授業 スタックと逆ポーランド記法
前回学習範囲の演習問題（連結リストの基本操作）を学習する．
事後学習 教科書の問題2.1，問題2.2，問題2.3を学習する．
宿題1dを学習し，POLITE2（Moodle）にアップロードする．		 2.0
8 事前学習 教科書の2.3.4～2.3.6節をよく読んで，疑問点をメモしておく． 2.0
授業 キュー
前回学習範囲の演習問題（スタック）を学習する．
事後学習 教科書の問題2.4を学習する．
宿題2を学習し，POLITE2（Moodle）にアップロードする．		 2.0
9 事前学習 教科書の2.4.1節をよく読んで，疑問点をメモしておく． 2.0
授業 木構造の基本
前回学習範囲の演習問題（キュー）を学習する．
事後学習 教科書の問題2.5，問題2.6，問題2.7を学習する． 2.0
10 事前学習 教科書の2.4.2～2.4.3節をよく読んで，疑問点をメモしておく． 2.0
授業 木の走査
前回学習範囲の演習問題（木構造の基本）を学習する．
事後学習 教科書の問題2.8，問題2.9，問題2.10を学習する． 2.0
11 事前学習 教科書の3.1節をよく読んで，疑問点をメモしておく． 2.0
授業 2分探索木
前回学習範囲の演習問題（木の走査）を学習する．
事後学習 教科書の問題3.1，問題3.2を学習する． 2.0
12 事前学習 教科書の3.3節をよく読んで，疑問点をメモしておく． 2.0
授業 ハッシュ法
前回学習範囲の演習問題（2分探索木）を学習する．
事後学習 教科書の問題3.3を学習する． 2.0
13 事前学習 教科書の4.1節をよく読んで，疑問点をメモしておく． 2.0
授業 単純な整列アルゴリズム（バブルソート，選択ソート，挿入ソート）
前回学習範囲の演習問題（ハッシュ法）を学習する．
事後学習 教科書の問題4.1，問題4.2，問題4.3を学習する． 2.0
14 事前学習 教科書の4.3節をよく読んで，疑問点をメモしておく． 2.0
授業 ヒープソート
前回学習範囲の演習問題（単純な整列アルゴリズム）を学習する．
事後学習 教科書の問題4.5を学習する． 2.0
15 事前学習 教科書の4.4節をよく読んで，疑問点をメモしておく． 2.0
授業 クイックソート
前回学習範囲の演習問題（ヒープソート）を学習する．
事後学習 教科書の問題4.6を学習する． 2.0
成績評価の方法およびその基準
次項の項目及び割合で標準評価基準に基づき総合評価する。
■試験：　70%　■レポート：10%　■演習課題・宿題：　20%　
課題(試験やレポート等)に対するフィードバック方法
・演習問題の結果：その場で自己採点しますが，自己採点の結果は，各自POLITE3（Moodle）にアップロードします．
教科書
  • 書名:基礎から学ぶ　データ構造とアルゴリズム ,　著者名:穴田有一・林雄二 ,　出版社:共立出版
参考書・Webサイト
河西朝雄「Javaによるはじめてのアルゴリズム入門」技術評論社，２００１
Robert Lafore「Javaで学ぶアルゴリズムとデータ構造」ソフトバンク，２００１
R.セジウィック「アルゴリズム」（第１巻，第２巻，第３巻）近代科学社，１９９７
杉山行浩「Cで学ぶデータ構造とアルゴリズム」東京電機大学出版局，１９９５
近藤嘉雪「定本Cプログラマのためのアルゴリズムとデータ構造」ソフトバンク，１９９８
単位習得が望ましい科目
プログラミング入門，プログラミング基礎
備考
なし
担当教員の実務経験
1981年から1982年にかけて，石油化学企業に勤務し，プロジェクトチームのメンバーとして研究開発に従事した経験から，基礎知識と学問の方法論を学習することの重要性を伝えるとともに，他者とコミュニケーションを十分にとりながら協調することの重要性を伝えます．
close閉じる