授業科目名(科目の英文名) 情報構造論(Information and Data

授業科目名(科目の英文名)
区分・分野・コア
情報構造論(Information and Data Structures)
必修
選択
単位
対象
年次
学
部
学
期
必修
2
2
工学部
前期
必修
曜・限
担当教員
中島 誠
内線
E-mail
7884
[email protected]
【授業のねらい】
アルゴリズム論はプログラミングのための理論的枠組みで，計算機科学を学ぶための基礎である。科目「アルゴリズム論」で学んだア
ルゴリズムより，より複雑な問題を解くための方法を学び，これらの特徴を修得し，応用のための基礎知識を身につける。
「アルゴリズム論」の後修科目として，実際の場面で使えるアルゴリズムについて学ぶ。現実の問題では，単純にそれを解くというだ
けでなく，与えられた種々の条件下で多くの解の中から最も良いものを，効率を重視しながら選ぶことが重要となる。これらの要求に応
じるには，内在する情報の構造を把握し，それに応じたアルゴリズムやデータ構造を使わなければならない。現在のノイマン型コンピュ
ータでは，待っている時間内に答が出ないような問題が多くある。解くのに非常に時間のかかる問題について，効率よく解を見つけるよ
うにするには，どのような方法を用いればよいかを講義する。内容の重要性に鑑み，プログラミングの演習科目「応用プログラミング演
習２」を併設してある。
○他の授業科目との関連
先修科目：アルゴリズム論
並修科目：応用プログラミング演習II
【具体的な到達目標】
（１）与えられた実用的な時間内では解けない問題（クラスNPの問題）の
存在を知り，クラスNPに属する問題とは何かを説明できる．
（２）クラスNPに属する問題であっても，実用的な時間内で解が見つけら
れる可能性が高くなるアルゴリズムの設計について説明できる。
（３）種々のアルゴリズムの設計法を理解したうえで，実際に活用・応用
ができるように動作をシミュレートできる。
【授業の内容】
【授業計画及び授業方法】
１．授業方法・進め方
「アルゴリズム論」で学んだ知識を前提に，次の計画で授業を進める。このとき授業毎に準備した課題を解くことで，力任せによる方
法ではなく洗練されたアルゴリズムを利用しなければ実用的でないことを実感してもらう。また，アルゴリズムを自身で理解した上で，
それを他の人に教えるような取組みも行なう。
２．授業計画
第１回 授業ガイダンス，および整列データの処理（１）
配列の併合，共通要素の抽出，２分探索
第２回 整列データの処理（２）
非減少連続関数の零点の発見，ニュートン法
第３回 分割統治法
マージソート，長大数の掛け算
第４回 動的計画法（１）
動的計画法の基礎，SUBSET-SUM問題と動的計画法
第５回 動的計画法（２）
配達スケジューリング問題
第６回 最適化問題（１）
最適化問題の定義，貪欲法と資源配分問題
第７回 最適化問題（２）
連続ナップサック問題と貪欲法，0-1ナップサック問題と動的計画法
第８回 グラフの問題（１）
グラフの表現（接続・隣接行列），最小木とプリムの方法
第９回 グラフの問題（２）
最短経路問題，最短経路木，ダイクストラの方法
第１０回 グラフの問題（３）
無向グラフの深さ優先探索，２重連結成分，関節点の検出
第１１回 文字列の照合（１）
素朴なアルゴリズム，クヌース‐モリス‐プラット法
第１２回 文字列の照合（２）
ボイヤー-ムーア法，ラビン-カーブ法
第１３回 計算幾何
凸包，ボロノイ図
第１４回 関係データベース
関係データベースの操作，マージスキャン法，ハッシュジョイン法
第１５回 問題のクラス
クラスＰとＮＰの定義，ＮＰ完全問題と問題の帰着
期末試験
【学生がより深く学ぶための工夫】
各回の授業中に理解度を確認するための演習問題を課す（成績にも反映させる）。複数人で問題に取り組むことも行い，相乗的により
理解を深められるようにする。併設する演習科目「応用プログラミング演習２」でアルゴリズム設計の実践を学ぶ。
【時間外学習】
授業を受ける前に，教科書の関連する章・節に目を通しておく必要がある。「応用ﾌﾟﾛｸﾞﾗﾐﾝｸﾞ演習II」でアルゴリズムの理解を深め，実
践に通じるプログラミング能力を養う｡
【教科書】
茨木俊秀：Cによるアルゴリズムとデータ構造，オーム社(2014)。
講義中に適宜プリントも配布する。
【参考書】
R.セジウィック著，野下浩平他 訳：アルゴリズムC；第2巻，近代科学社(1992)．
R.セジウィック著，野下浩平他 訳：アルゴリズムC・新版，近代科学社(2004)．
【成績評価の方法及び評価割合】
期末試験 ６０%，課題レポート ４０%
課題レポートは，各回の理解度と予習具合を測る重要な指標とする。
【注意事項】
【備考】
アルゴリズム論と並んで計算機科学を学ぶための基礎となります。
教員免許「情報」指定科目。JABEE「知能情報コース」学習・教育到達目標(A3), (d1)関連科目。