|
授業科目名
|
担当教官
|
|||||
|
アルゴリズムとデータ構造
|
岩沼 宏治
|
|||||
|
時間割番号
|
単位数
|
コース
|
履修年次
|
期別
|
曜日
|
時限
|
| 263610 | 2 | Ｇ | 2 | 前期 | 金 | I |
| ［概要］ | ||||||
| 本講義では，種々の情報処理技術の根幹を成すアルゴリズムとデータ構造に関する種々の基本的理論と技術を学ぶ．具体的な講義内容としては，IEEE/ACMが設定するモデルカリキュラムCC2001の内容を（先行科目のプログラミングII，同演習と併せて）カバーする題材を取り上げる．情報処理技術教育の基幹科目として，十分な幅と深みをもった題材を取り上げ， 学生に十分な素養を持たせることを目標としている． カリキュラム中での位置付け：Gコースのカリキュラム |
||||||
| ［具体的な達成目標］ | ||||||
| 本講義では，大きく分けて以下の３つの項目について取り上げ，その基本的な理解を達成目標とする． （１） 個々の具体的な問題における代表的なアルゴリズム， （２） アルゴリズムの設計において汎用的に用いられる理論と技法 （３） 問題の持つ本質的な難しさとそれに起因する計算効率化の限界 また比較的長い英文を課題として出題し，その内容理解を問うテストを通して英語教育の一部を担うことを目標としている．（１）から（３）で取り上げる具体的な内容は，IEEE/ACM CC2001での必修項目を全て取り上げるように配慮してある（下記の講義の達成状況の欄を参照のこと）．本講義と同時開講される「アルゴリズムとデータ構造演習」と協力して，情報処理技術者としての十分な素養を持たせることを目標としている． |
||||||
| ［必要知識・準備］ | ||||||
| プログラミング I, II，および同演習，計算機アーキテクチャをしっかり復習されたい．またＣ言語の知識とプログラミング技術が必須である． | ||||||
| ［評価基準］ | ||||||
| 評価は、中間試験（35点）と期末試験(55点)を総合して行う．また講義の進行あわせて適宜レポートと英文リーディング試験（合わせて10点）を課す．総合60点以上が合格である． | ||||||
| ［教科書］ | ||||||
| ［参考書］ | ||||||
| (未登録) | ||||||
| ［講義項目］ | ||||||
| １．序論：コンピュータサイエンス的数字と天文学的数字ではどちらが大きいのか？ ２．ヒープソート： 選択ソートの改良，完全2分木の埋め込みによるヒープの実現 ３．比較によるソート法の時間計算量の下界（本質的に必要な計算量）と その空間的克服：バケットソート、基底ソート ４．簡単な最適化問題： 資源配分問題、連続ナップザック問題 ５．文字列照合その１： 素朴なアルゴリズムとKMP法 ６．文字列照合その２： Boyer-Moore法 ７．グラフ問題その１： 木とグラフの定義，最小全域木， クラスカルのアルゴリズム，プリムのアルゴリズム ８．グラフ問題その２： 最短経路問題， ダイクストラのアルゴリズム．ワーシャルフロイドのアルゴリズム ９． 中間試験 １０．計算不可能性原理、計算量の無限階層、ＮＰ完全問題 １１．分割統治法： 長大数の乗算、点集合の凸包 １２．動的計画法： 部分和問題、０−１ナップザック問題 １３．分岐限定法： ０−１ナップザック問題 １４．近似解法： 貪欲算法、ランダム法、局所探索法、緩和法 進んだ話題： 分散アルゴリズム，確率的アルゴリズム １５．期末試験 |
||||||
| ［教育方法］ | ||||||
| • 全ての講義資料をPowerPointを利用して電子的に作成し，ホームページから配布する • 適宜，自主勉強用の演習問題プリントを配布する． • 中間試験の答案用紙の採点結果を返却する予定である．これにより自己の実力の確認を行なってもらいたい． |
||||||
| ［JABEEプログラムの学習・教育目標との対応］ | ||||||
| ・教育目標（A)に対して情報処理技術の全ての基本であるアルゴリズムとデータ構造の基本的知識と問題解決能力および応用能力を習得させる． ・教育目標（C)に対して，理科的内容の英文プリントを配布し，リーディング能力を訓練する．小テストなどを通して理解力の向上を図る． ・教育目標（D)に対して，演習問題を配り，自主的な勉強を誘導・推奨する． ・教育目標（E)に対して，講義の中で，各問題や技術と，現実の問題・アプリケーションにおける要求との関連について解説し，問題意識を常に持たせる |
||||||
| ［その他］ | ||||||
| オフィスアワー：月曜４時限目 | ||||||