授業科目名 （英文名）
データ構造とアルゴリズム論 (Data St ructure and Algorithm)
科目区分 対象学生 ※ 単位数 2.00 開講年次・ 学期 ２年次・後期 担当教員 上浦 尚武 所属 工学研究科 ｵﾌｨｽｱﾜｰ・場所 ※ 連絡先 ※ 講義目的及び到達目標 プログラミングの基礎となるデータ構造とアルゴリズムの理論について述べる。適切 なデータ構造とそれを処理するアルゴリズムを開発・選択することは、計算機プログ ラムを作成する際の基本的な要素であり、情報科学の基礎でもあるため、この知識を 得ることが本講義の目的である。 本講義の到達目標は、データ構造と基本的アルゴリズムの基本的事柄を認識した上で 、各種学習したプログラムでなぜ高速化できるのかを数学的に理解することである。 講義内容・授業計画 講義内容 本講義では、アルゴリズムの評価基準および計算量評価についてまず口述し、その後 、基本データ構造、基本概念、データ探索、ソートアルゴリズム、分割統治法、グリ ーディ法などの様々なアルゴリズム設計、グラフアルゴリズム、多項式計算、文字列 照合などの紹介と説明を行う。同時にそれらの計算量に関して時間オーダーと領域オ ーダーの両面から詳説する。 授業計画 １．アルゴリズムの基礎 ２．基本データ構造 ３．木、再帰などの基本概念 ４．データ探索 ５．ソートアルゴリズム１（挿入ソート、ヒープソート） ６．ソートアルゴリズム２（クイックソート、ソート性能比較） ７．アルゴリズム設計１（分割統治法） ８．中間試験 ９．アルゴリズム設計２（グリーディ法、動的計画法） １０．アルゴリズム設計３（バックトラック法、分枝限定法） １１．グラフアルゴリズム １２．多項式と行列 １３．文字列照合アルゴリズム １４．P-, NP-, NP-完全問題について １５．全体のまとめ テキスト 藤原暁宏 アルゴリズムとデータ構造、森北出版株式会社（生協で購入する） 参考文献 特になし 成績評価の基準・方法 講義目的・到達目標に記載する事項について十分習得した者に単位を授与する。同事 項に関する到達度に応じてSからCまで成績を与える。 授業計画の項目１から7について中間試験を行う。期末試験は、項目9から15を主な範 囲として出題する。中間試験50%、期末試験50%を基準として、受講態度（積極的な質 問等）を含めて総合的に評価する。 履修上の注意・履修要件 ・先修科目の記載：プログラミング論Ⅰ、プログラミング論Ⅱ、以上の単位取得が望 ましい。 ＜新型コロナウィルス感染症に伴う特例措置に基づく遠隔授業＞ 当授業は、原則全ての授業を対面で実施する予定ですが、履修者人数によっては、新 型コロナウィルス感染症対策として、履修者を複数の教室に分けて教室間をオンライ ンで繋ぐ方法や、対面授業と自宅でのオンライン授業を隔週実施する方法とする場合 があり、自宅等でオンライン授業の受講を視聴できる通信環境(PC・タブレット等の端 末やWi-Fi環境)が必要となる場合があります。最終的な授業方法は履修登録後に決定・ 連絡します。
実践的教育 該当しない
備考 自然科学に基づいた専門分野の基礎力
