English

年度	2024年度	開講部局	情報科学部
講義コード	KA110001	科目区分	専門教育科目
授業科目名	アルゴリズムとデータ構造
授業科目名 （フリガナ）	アルゴリズムトデータコウゾウ
英文授業科目名	Algorithms and Data Structures
担当教員名	藤田　聡
担当教員名 (フリガナ)	フジタ　サトシ
開講キャンパス	東広島	開設期	2年次生   後期   ３ターム
曜日・時限・講義室	(3T) 木1-4：工107
授業の方法	講義	授業の方法 【詳細情報】
			講義中心．ほぼ毎回演習を行う．オンラインで学習が完結するよう配慮しますが，質問や相談などのための時間も確保します．
単位	2.0	週時間		使用言語	B : 日本語・英語
学習の段階	2 : 初級レベル
学問分野（分野）	25 : 理工学
学問分野（分科）	02 : 情報科学
対象学生	情報科学部 令和5年度入学生
授業のキーワード	コンピュータプログラム，アルゴリズム，データ構造，効率化，システム設計
教職専門科目		教科専門科目
プログラムの中での この授業科目の位置づけ （学部生対象科目のみ）	ソフトウェア作成の基礎となるデータ構造やアルゴリズムの設計と解析について修得することができる．ソフトウェア作成に関する基礎知識全般が修得でき，プログラム作成さらにはシステム設計に関する能力向上に役立つ．これにより，ITを先導的に支える人材育成の一端を担う． 本授業科目は，コンピュータやプログラムに関連する内容を含む課題解決の基礎であり，研究や授業などにおいて現れる各種の課題について，コンピュータを利用して解決を図る場合の基礎となる．具体的には，以下のような研究や科目に応用がある：卒業論文（プログラム作成やシステム設計），コンピュータやプログラムに関連する内容を含む授業科目．
到達度評価 の評価項目 （学部生対象科目のみ）	電気システム情報プログラム （能力・技能） ・電気，システム，情報分野の基礎となる概念，知識および手法 ・電気，システム，情報分野の基礎概念，知識および手法を具体的・専門的な問題に応用する能力 電子システムプログラム （能力・技能） ・電子システム分野の基礎となる概念，知識および手法 ・電子システム分野の基礎概念，知識および手法を具体的・専門的な問題に応用する能力 計算機科学プログラム （能力・技能） ・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術． ・B. 新たな課題を自ら発見し，データに基づいた定量的かつ論理的な思考と，多角的視野と高度な情報処理・分析により，課題を解決する能力． （総合的な力） ・D2. 多様化，複雑化した情報社会における分野横断的な課題に対して，豊富な最先端情報技術に基づいて，最適なシステムソリューションを導く能力． データ科学プログラム （能力・技能） ・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術． ・B. 新たな課題を自ら発見し，データに基づいた定量的かつ論理的な思考と，多角的視野と高度な情報処理・分析により，課題を解決する能力． 知能科学プログラム （能力・技能） ・A. 情報基盤の開発技術，情報処理技術，データを分析して新しい付加価値を生む技術． ・B. 新たな課題を自ら発見し，データに基づいた定量的かつ論理的な思考と，多角的視野と高度な情報処理・分析により，課題を解決する能力． （総合的な力） ・D3. 複合的に絡み合う社会的ニーズや課題を俯瞰的に捉え，知能科学の幅広い知識に基づいた多角的視野と分析能力で課題を解決する能力．
授業の目標・概要等	本講義の受講により，ソフトウェア作成の基礎となるデータ構造，アルゴリズムの設計と解析に関する基礎知識全般が修得でき，プログラム作成さらにはシステム設計に関する能力向上に役立つ．具体的目標は以下の通りである： 1. データ構造とアルゴリズム設計に関する基礎知識全般を修得する． 2. アルゴリズムの効率（処理速度、メモリ使用量）解析のための基礎知識を修得する． 3. アルゴリズム効率化のためのデータ構造設計に関する基礎知識を修得する． 4. 効率的プログラムさらには効率的システムの設計に関する基礎知識を修得する．
授業計画	第1回 　講義の導入．アルゴリズムとは何か．予備知識． 第2回　文字列アルゴリズム（１），素朴な方法とKMP法 第3回　文字列アルゴリズム（２），KMP法におけるパターン照合テーブルの作成法とBM法 第4回　整列アルゴリズム（１），交換型アルゴリズム 第5回　整列アルゴリズム（２），分割統治型アルゴリズム 第6回　整列アルゴリズム（３），基数ソート 第7回　基本データ構造（１），スタック，キュー，二分探索木 第8回　基本データ構造（２），ヒープ 第9回　基本データ構造（３），素集合データ 第10回　最短経路アルゴリズム（１），ダイクストラ法 第11回　最短経路アルゴリズム（２），ベルマンフォード法 第12回　最短経路アルゴリズム（３），動的プログラミング，A*アルゴリズム 第13回　最小スパニング木アルゴリズム（１），グラフの探索 第14回　最小スパニング木アルゴリズム（２），クラスカル法 第15回　最小スパニング木アルゴリズム（３），プリム法 ほぼ毎回演習を行い，講義の最後に期末試験を行う．必要に応じて宿題を出す場合がある．
教科書・参考書等	藤田聡「アルゴリズムとデータ構造」数理工学社
授業で使用する メディア・機器等
	【詳細情報】	授業で使用するスライドのファイルは，もみじの該当ページから授業の前にダウンロードできるように手配する．
授業で取り入れる 学習手法
予習・復習への アドバイス	第1回　以降の授業の基礎となる諸概念をきちんと理解すること．特にアルゴリズムの正しさと実行時間については，例題を通して理解を深めることが望ましい． 第2回　単純な文字列照合アルゴリズムの実行時間解析を自分自身で行ってみること． 第3回　KMP法の考え方を理解し，具体例を通して理解を深めること． 第4回　基本的な整列アルゴリズムの違いと長所・短所を理解すること． 第5回　分割統治に基づく整列アルゴリズムの考え方を理解すること．特に，再帰については注意が必要． 第6回　基数ソートで使われている考え方を理解すること．比較・交換だけが整列を行うための基本的な道具ではない． 第7回　キューやスタックなどの基本データ構造が実際のプログラムでどのように実現されるのかを理解すること． 第8回　キーバリューペアは，ウェブの検索などでも使われる重要な概念である．効率的な検索を行うための基本技術を理解すること． 第9回　ヒープや素集合データは，高速なアルゴリズムをつくる上で特に重要な役割を果たすデータ構造である．まずは基本的な考え方を理解し，例題を通して自分で使いこなせるようにした上で，なぜそのようにすればうまくいくのかまでを考えてほしい． 第10回　グラフの表現方法と最短経路問題の応用について理解する． 第11回　ダイクストラ法について理解する．アルゴリズムの動きを理解した上で，なぜその方法でうまくいくのかまでを考えてほしい． 第12回　ベルマンフォード法について理解する．アルゴリズムの動きを理解した上で，なぜその方法でうまくいくのかまでを考えてほしい． 第13回　最小生成木問題とその応用について理解する． 第14回　クラスカル法について理解する．アルゴリズムの動きを理解した上で，なぜその方法でうまくいくのかまでを考えてほしい． 第15回　プリム法について理解する．アルゴリズムの動きを理解した上で，なぜその方法でうまくいくのかまでを考えてほしい．
履修上の注意 受講条件等	原則としてすべての授業に出席すること． プログラミングに関する授業を履修しておくことが望ましい．
成績評価の基準等	演習の得点を50%，期末試験の得点を50%に換算して成績を評価する．
実務経験
実務経験の概要と それに基づく授業内容
メッセージ
その他
すべての授業科目において，授業改善アンケートを実施していますので，回答に協力してください。 回答に対しては教員からコメントを入力しており，今後の改善につなげていきます。