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

Data Structure and Algorithm

専門教育科目

［−］

工学部

2年

HETBK2MCA1

2.00単位

講義 (Lecture)

2026年度後期

(Fall semester)

上浦 尚武

工学研究科

日本語

目標9

オフィスアワー：随時、ただし、mailによる事前連絡要（上浦）
場所：書写6202（上浦）

kamiura@eng.u-hyogo.ac.jp (上浦)

2◎／1〇／4〇

ー

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

ー

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

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

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

【授業計画】
　１．アルゴリズムの基礎（テキスト第１章、キーワード：アルゴリズム、計算量漸近的評価、和集合）
　２．基本データ構造（テキスト第２章、キーワード：配列、連結リスト、スタック、キュー）
　３．アルゴリズムにおける基本概念（テキスト第３章、キーワード：木、再帰）
　４．データ探索（テキスト第４章、キーワード：探索アルゴリズム、２分探索法、ハッシュ法）
　５．ソートアルゴリズム（その１）（テキスト第５章、キーワード：基本ソート、挿入ソート、ヒープソート）
　６．ソートアルゴリズム（その２）（テキスト第６章、キーワード：クイックソート、ソート性能比較、ソートの安定性）
　７．効率的なアルゴリズム設計⼿法（テキスト第７章、キーワード：分割統治法）
　8．中間まとめ
　9．組み合わせ最適化手法（その１）（テキスト第８章、キーワード：グリーディ法、動的計画法）
１０．組み合わせ最適化手法（その２）（テキスト第９章、キーワード：バックトラック法、分枝限定法）
１１．グラフアルゴリズム（その１）（テキスト第10章、キーワード：グラフ、グラフ格納データ構造、幅優先探索）
１２．グラフアルゴリズム（その２）（テキスト第10章、キーワード：深さ幅優先探索、ダイクストラ法）
１３．多項式と行列（テキスト第11章、キーワード：多項式計算、行列積アルゴリズム、行列連続積）
１４．文字列照合アルゴリズム（テキスト第12章、キーワード：文字列照合、ホールスプールのアルゴリズム）
１５．アルゴリズムの限界（テキスト第13章、キーワード：問題のクラス階層、クラスP、クラスNP,　NP完全問題、NP困難問題）
定期試験

対面

利用する場面を限定し許可

「生成ＡＩの利用にあたっては『本学の教育における生成ＡＩの取扱いについて（学生向け）』の記載内容について留意すること。この講義
においては、以下の範囲において、生成ＡＩの利用を許可し、これ以外の範囲での利用は禁止する。生成ＡＩの利用については担当教員の指
示に従うこと。教員が認める範囲を超えて生成ＡＩを利用したことが判明した場合は、単位を認定しない、または認定を取り消すことがあ
る。生成ＡＩの出力した内容について、事実関係の確認や出典・参考文献を確認・追記することが重要である。また、生成ＡＩによる出力結
果をそのまま課題・レポートとして提出してはならない。さらに，担当教員の許可なく講義資料の全部または一部を電子ファイルまたは画像
等として生成ＡＩに入力することを禁止する。
(利用可の範囲)
利用許容範囲については、担当教員より提示される条件に従うものとする。

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

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

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

採用しない

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

【成績評価の方法】
　授業計画の項目１から6について中間試験を11月中旬に行う。期末試験は２月上旬に行い、項目７から15を主な範囲として出題する。中間試験50%、期末試験50%を基準として、総合的に評価する。

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

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

該当しない

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