授業科目名	組込みプログラミングII
時間割番号	TJM219
担当教員名	西崎　博光
開講学期・曜日・時限	前期・金・IV	単位数	2
＜対象学生＞
(未登録)
＜授業の目的＞
「組込みプログラミングI」，「組込みプログラミングI演習」に引き続き，情報処理の幅広い場面で必要となる基本的なデータ構造である木構造とグラフに関するデータ構造とアルゴリズムを学ぶ。木構造やグラフは，様々なところで利用されている。たとえば，電子回路基板への最適な部品配置，ロボット動作のシュミレーション，効率的なルート探索などであり，木やグラフのデータ構造とアルゴリズムを学ぶことは，メカトロニクス技術者にとって非常に意義がある。 本授業では，木構造とグラフに関するデータ構造とアルゴリズムを理解し，C言語により実装ができる知識と技量を身につけることが大きな目標である。本授業を通して，データ構造の利用法，アルゴリズムの理解，より高度なプログラミング能力を習得する。
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部>メカトロニクス工学科向け 記号 コンピテンシー（能力・資質）   JM-A 専門 2.三分野での活躍を目指す技術者・研究者にとって必要な基礎知識と技術 C言語による基本的（データ型、制御構造、関数等）なプログラムが作成でき、組込み用マイコンの基本的なI/O制御プログラムをマイコンの概要と動作の理解の上で作成できる。 ○ JM-B 3.三分野のうち、一つ以上のより専門的な技術と知識。少なくとも一分野の技術と知識を十分に身につけ、さらに一つ以上の分野の技術と知識も身につける。 2.電気分野 動的変数、再帰関数などを用いた線形リスト、木構造、ソートのプログラムが書ける。 ◎ JM-C 3.情報分野 動的変数、再帰関数などを用いた線形リスト、木構造、ソートのプログラムが書ける。 ◎ JM-D 組込みシステムにおいて、ソフトウェアを開発することができる。 ○ JM-E 4.三分野の知識を利用した分野をまたがった活用 研究・開発の目的を十分理解した上で、その目的に応える問題解決ができる。 ○
＜到達目標＞  到達目標とは
目標NO 説明 コンピテンシーとの対応 JM 1 C言語の基本的なプログラミング技法を用いて，木構造，グラフを実現するプログラムが作成できること。 JM-A 2 データ構造の一種である木構造を理解し，説明ができ，木構造をC言語によるプログラムで実装できること。 JM-B 3 木構造の種類（二分木，二分探索木，算術木，ヒープ）を理解し，説明ができ，これらの木の生成や削除ができるプログラムを作成できること。 JM-C 4 グラフに関わる重要なアルゴリズム（最小全域木問題，最短経路問題）を理解し，説明ができること。 JM-D 5 木構造，グラフに対する各種アルゴリズム（数式と木の相互変換，ソート，最小全域木，最短経路探索）を実現するプログラムが作成できること。 JM-D 6 ルート探索（最短経路探索）などの実問題に近い課題において，木やグラフに関するアルゴリズムを通して課題を解決できること。 JM-E
＜成績評価の方法＞
目標No 割合 評価の観点 1 10% 演習課題で理解度ならびにプログラミングスキルを評価する。 2 10% 演習課題ならびに筆記試験で，理解度ならびにプログラミングスキルを評価する。 3 25% 演習課題ならびに筆記試験で，理解度ならびにプログラミングスキルを評価する。 4 25% 筆記試験で評価する。 5 20% 演習課題ならびに筆記試験で，理解度ならびにプログラミングスキルを評価する。 6 10% 演習課題ならびに筆記試験で理解度を評価する。 合計 100%
＜授業の方法＞
「組込みプログラミング」および「組込みプログラミングI演習」の単位を取得し，C言語の基礎を習得済みであることが前提で授業を進める。 教育方法・授業方法は次のとおりである。プログラミングを主とした，アクティブラーニングを全面的に導入している。 - 多くのサブトピックにおいて，座学とプログラミング演習のセットとなっている。そのため，臨機応変に2コマ連続で授業を実施することもある。 - 座学で説明した後，理解度の確認のための演習問題（筆記）に取り組み，実際にC言語でプログラムを書く。 - サブトピックによっては，事前学習用のビデオを用意することもある。 - 授業内容によっては，学生による発表を実施することもある。 - 中間評価と期末評価を実施するが，筆記によるペーパー試験を予定している（実技試験との混合試験にすることも否定はしない）。 - サブトピック毎に，プログラミング課題を課す。
＜受講に際して・学生へのメッセージ＞
本授業では，先行する「組込みプログラミング」および「組込みプログラミングI演習」で学習した内容を発展・応用するため，履修者は必ずこれら授業内容およびC言語プログラミングを復習をしておかなければならない。特に木構造については線形リスト，スタック・キュー，再帰呼び出しの応用となるため，履修前によく復習しておくこと。 なお，本授業では，教科書は用いずに，担当教員が作成したパワーポイントあるいはその説明ビデオを用いる。ただし，より深い内容に興味を持つ学生は，挙げてある参考書を購入し，学んでもよい。
＜テキスト＞
(未登録)
＜参考書＞
T. コルメン [ほか] 共著 ; 浅野哲夫 [ほか] 共訳, 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム 2 第3版, 近代科学社, ISBN:4764904071, (2012年出版 世界標準MIT教科書, . アルゴリズムイントロダクション)
＜授業計画の概要＞
1 タイトル 線形リストの復習と木構造 事前学習 事後学習 事前学習：先行科目の復習 事後学習：演習課題 授業内容 線形リストを構築する際に利用したポインタを用いた動的メモリ確保を復習する。また，木構造について理解を行う。木の走査方法（3種類の深さ優先探索）を理解し，正しく動作を説明できるようになることが達成目標である。 2 タイトル 二分木とそのプログラミング 事前学習 事後学習 事前学習：第1回目授業の復習 事後学習：演習課題，プログラミング演習課題 授業内容 木構造の一種である二分木について理解し，説明できるようになることが達成目標である。また，二分木を作成する方法を学び，実際にC言語で二分木実現するプログラムと木を探索するプログラムが書けるようになることも達成目標である。 3 タイトル 算術二分木と逆ポーランド記法ならびにそのプログラミング 事前学習 事後学習 事前学習：第2回目授業の復習，スタックの復習 事後学習：演習課題，プログラミング演習課題 授業内容 数式の表現方法（逆ポーランド記法，ポーランド記法，中置記法）について理解し，逆ポーランド記法から算術二分木を構築するアルゴリズムを理解し，説明できるようになることが達成目標である。加えて，このアルゴリズムをC言語で実装できるようになることも達成目標である。 4 タイトル 算術二分木を利用した数式からの四則演算とそのプログラミング 事前学習 事後学習 事前学習：第3回目授業の復習，スタックの復習 事後学習：演習課題，プログラミング演習課題 授業内容 逆ポーランド記法で表現されている数式を計算するアルゴリズムを理解し，説明できること，また，中置記法で表現されている数式から算術二分木を作成し，数式を計算するアルゴリズムを理解し，説明できることを達成目標とする。逆ポーランド記法で表現されている数式を計算するアルゴリズムについては，C言語で実装できることも達成目標とする。 5 タイトル 二分探索木 事前学習 事後学習 事前学習：第4回目までの授業の復習，再帰呼び出しの復習 事後学習：演習課題 授業内容 木構造でもっとも重要な二分探索木について理解し，二分探索木へのデータの追加・削除・探索の各アルゴリズムを理解し，説明できることが達成目標である。 6 タイトル 二分探索木のプログラミング 事前学習 事後学習 事前学習：第5回目までの授業の復習，再帰呼び出しの復習 事後学習：プログラミング演習課題 授業内容 二分探索木へのデータの追加・削除・探索の各アルゴリズムをC言語で実装できるようになることが達成目標である。 7 タイトル ヒープソート 事前学習 事後学習 事前学習：C言語の復習 事後学習：演習課題 授業内容 ヒープ（整列二分木）について理解し説明できること，またヒープを用いたソーティングアルゴリズムを理解し，説明できることが達成目標である。 8 タイトル ヒープソートのプログラミング 事前学習 事後学習 事前学習：第7回目の授業の復習 事後学習：プログラミング演習課題 授業内容 木をヒープに変換するためのアルゴリズム，ならびに，ヒープを用いたソーティングアルゴリズムを理解し，C言語で実装できることが達成目標である。 9 タイトル 中間の総括と中間試験 事前学習 事後学習 事前学習：中間試験のための試験勉強 事後学習：なし 授業内容 第1～8回目の授業内容に関しての理解度を問うための試験を実施する。試験をとおして，第1～8回目の授業内容についてさらに理解を深めることも達成目標である。 10 タイトル グラフ表現のためのデータ構造とそのプログラミング 事前学習 事後学習 事前学習：線形リストの復習 事後学習：プログラミング演習課題 授業内容 グラフをプログラムで実現するための方法として配列を用いる場合と線形リストを用いる場合の2通りの手法を理解し説明できること，またそれらをC言語で実装できるようになることが達成目標である。 11 タイトル 最小全域木 事前学習 事後学習 事前学習：第10回目の授業の復習 事後学習：演習課題 授業内容 グラフから最小全域木を抽出するクラスカル法というアルゴリズムを理解し，説明できることが達成目標である。 12 タイトル 最小全域木のプログラミング 事前学習 事後学習 事前学習：第11回目の授業の復習 事後学習：プログラミング演習課題 授業内容 最小全域木を抽出するクラスカル法をC言語で実装できるようになることが達成目標である。 13 タイトル 最短経路探索 事前学習 事後学習 事前学習：第10回目の授業の復習 事後学習：演習課題 授業内容 グラフの2点のノードを結ぶ最短経路を探索するダイクストラ法というアルゴリズムを理解し，説明できることが達成目標である。 14 タイトル 最短経路探索のプログラミング 事前学習 事後学習 事前学習：第13回目の授業の復習 事後学習：プログラミング演習課題 授業内容 最短経路探索を実現するダイクストラ法をC言語で実装できるようになることが達成目標である。 15 タイトル 総括と期末試験 事前学習 事後学習 事前学習：期末試験のための試験勉強 事後学習：なし 授業内容 第10～14回目の授業内容に関しての理解度を問うための試験を実施する。試験をとおして，第10～14回目の授業内容についてさらに理解を深めることも達成目標である。 16 タイトル 事前学習 事後学習 授業内容 17 タイトル 事前学習 事後学習 授業内容 18 タイトル 事前学習 事後学習 授業内容 19 タイトル 事前学習 事後学習 授業内容 20 タイトル 事前学習 事後学習 授業内容 21 タイトル 事前学習 事後学習 授業内容 22 タイトル 事前学習 事後学習 授業内容 23 タイトル 事前学習 事後学習 授業内容 24 タイトル 事前学習 事後学習 授業内容 25 タイトル 事前学習 事後学習 授業内容 26 タイトル 事前学習 事後学習 授業内容 27 タイトル 事前学習 事後学習 授業内容 28 タイトル 事前学習 事後学習 授業内容 29 タイトル 事前学習 事後学習 授業内容 30 タイトル 事前学習 事後学習 授業内容
＜備考＞
不正行為（他の履修生からのプログラムのコピーなど）は厳正に対処する。