データ構造とアルゴリズム論

Data Structure and Algorithm

専門教育科目

［−］

工学部

2年

HETBK2MCA1

2.00単位

講義 (Lecture)

2024年度後期

上浦 尚武

工学研究科

日本語

目標9

木曜10:40〜12:10・6202研究室
(メールによる事前連絡が必要)

kamiura@eng.u-hyogo.ac.jp

3◎／4◎／5◎

ー

1-1◎／4-1〇／4-2〇

ー

【講義目的】
プログラミングの基礎となるデータ構造とアルゴリズムの理論について学習する。適切なデータ構造とそれを処理するアルゴリズムを開発・選択することは、計算機プログラムを作成する際の基本的な要素であり、情報科学の基礎でもあるため、この知識を修得することが本講義の目的である。
【達成目標】
本講義の到達目標は、データ構造と基本的アルゴリズムの基本的事柄を認識した上で、１）各種学習したアルゴリズムについて性能を時間計算量の観点で評価できること、２）各アルゴリズム設計法を、実際の問題解決に利用できるプログラムの作成に活用できること、である。

サブタイトル：コンピュータサイエンスに不可欠なアルゴリズム設計手法とデータ構造解説
キーワード：時間計算量、配列、連結リスト、スタック、キュー、２分探索法、ハッシュ法、挿入ソート、ヒープソート、分割統治法、グリーディ法、動的計画法、分枝限定法、グラフ探索法、ダイクストラ法、多項式計算、行列連続積、文字列照合

【講義内容】
本講義では、アルゴリズムの評価基準および計算量評価についてまず論述し、その後、基本データ構造、基本概念、データ探索、ソートアルゴリズム、分割統治法、グリーディ法などの様々なアルゴリズム設計、グラフアルゴリズム、多項式計算、文字列照合などの紹介と説明を行う。同時にそれらの計算量に関して時間オーダーと領域オーダーの両面から詳説する。

【授業計画】
　１．アルゴリズムの基礎（テキスト第１章、キーワード：アルゴリズム、計算量漸近的評価、和集合）
　２．基本データ構造（テキスト第２章、キーワード：配列、連結リスト、スタック、キュー）
　３．アルゴリズムにおける基本概念（テキスト第３章、キーワード：木、再帰）
　４．データ探索（テキスト第４章、キーワード：探索アルゴリズム、２分探索法、ハッシュ法）
　５．ソートアルゴリズム（その１）（テキスト第５章、キーワード：基本ソート、挿入ソート、ヒープソート）
　６．ソートアルゴリズム（その２）（テキスト第６章、キーワード：クイックソート、ソート性能比較、ソートの安定性）
　７．アルゴリズム設計手法（その１）（テキスト第７章、キーワード：分割統治法）
　８．中間まとめ
　９．アルゴリズム設計手法（その２）（テキスト第８章、キーワード：グリーディ法、動的計画法）
１０．アルゴリズム設計手法（その３）（テキスト第９章、キーワード：バックトラック法、分枝限定法）
１１．グラフアルゴリズム（その１）（テキスト第10章、キーワード：グラフ、グラフ格納データ構造、幅優先探索）
１２．グラフアルゴリズム（その２）（テキスト第10章、キーワード：深さ幅優先探索、ダイクストラ法）
１３．多項式と行列（テキスト第11章、キーワード：多項式計算、行列積アルゴリズム、行列連続積）
１４．文字列照合アルゴリズム（テキスト第12章、キーワード：文字列照合、ホールスプールのアルゴリズム）
１５．アルゴリズムの限界（テキスト第12章、キーワード：問題のクラス階層、クラスP、クラスNP,　NP完全問題、NP困難問題）
 
生成系AIの利用：
生成系AIの利用については教員の指示に従うこと。生成系AIによる出力結果をそのまま課題レポートとして提出してはいけない。生成系AIによる出力をそのまま提出したことが判明した場合は単位を認定しない、又は認定を取り消すことがある。

藤原暁宏　アルゴリズムとデータ構造、森北出版株式会社（生協で購入する）

平田富夫　アルゴリズムとデータ構造(第3版)、森北出版

【予習】授業に際して指示するテキスト・オンデマンド教材の部分を事前読み込み（28ｈ）
【復習】講義内容の理解を深め定着させるためにテキストを読み直し（14ｈ）、配布プリントの解答（18h)

採用しない

【成績評価の基準】
　時間計算量、配列、連結リスト、スタック、キュー、２分探索法、ハッシュ法、挿入ソート、ヒープソートなどの基本的事項について理解し、より具体的なアルゴリズム設計法である分割統治法、グリーディ法、動的計画法、分枝限定法をグラフ探索、最短経路問題、多項式計算、行列連続積、文字列照合などに応用できる能力（知識、思考力、計算力）の到達度に基づき、S(90点以上)、A(80点以上)、B(70点以上)、C(60点以上)による成績評価のうえ、単位を付与する。
【成績評価の方法】
　授業計画の項目１から6について中間試験を11月中旬に行う。期末試験は２月上旬に行い、項目７から15を主な範囲として出題する。中間試験50%、期末試験50%を基準として、受講態度（プリント提出状況、積極的な質問等）を含めて総合的に評価する。

毎回講義時にプリントをユニバーサルパスポートのクラスプロファイル機能を使って公開し、その解答もクラスプロファイル機能を使って公開するとともに、講義内で解説する。
定期試験は、全体的な講評や模範解答をユニバーサルパスポートのクラスプロファイル機能を使って示す。

・先修科目の記載：プログラミング論Ⅰ、プログラミング論Ⅱ、以上の単位取得が望ましい。

該当しない

自然科学に基づいた専門分野の基礎力
電気、電子、情報分野の広い知識と特化した分野の知識