授業科目名	プログラミング応用
時間割番号	TCS105
担当教員名	鍋島　英知
開講学期・曜日・時限	後期・木・I	単位数	2
＜対象学生＞
(未登録)
＜授業の目的＞
プログラミング基礎および同演習で修得した内容を基にして，リストや木構造などのデータ構造と，探索，整列などのアルゴリズムの実現手法を C++言語によるプログラミングを通して学ぶ．また，C++言語によるクラスと継承を利用したオブジェクト指向プログラミングを身に付ける．同時開講するプログラミング応用演習において，その知識を活用するスキルの習得を行う．
＜本授業科目による獲得・涵養が特に期待されるコンピテンシー＞（能力・資質）
工学部>コンピュータ理工学科向け 記号 コンピテンシー（能力・資質）   CS-A 専門 6.情報科学、及び、数学や自然科学等の知識と手法を用いて、以下のことができる。 6c.各種のツールや手法に関する十分な知識をもち、それらをシステムの設計・開発・運用に応用できる。 ◎
＜到達目標＞  到達目標とは
目標NO 説明 コンピテンシーとの対応 CS 1 連結リスト，スタック，キュー，木構造等の基本的データが実現できること（レベル２） CS-A 2 探索，再帰，整列の基礎ならびにそれらの計算量を理解でき，プログラムとして実現できること（レベル２） CS-A 3 C++ 言語におけるクラスと継承を適切に用いたプログラミングができること（レベル１） CS-A
＜成績評価の方法＞
目標No 割合 評価の観点 1 40% レポートおよび中間期の試験により評価する 2 40% レポートおよび期末期の試験により評価する 3 20% レポートおよび中間・期末期の試験により評価する 合計 100%
＜授業の方法＞
* 本講義は，「プログラミング基礎」「プログラミング基礎演習」の修得を前提としている．また「プログラミング応用演習」を未修得の場合は履修しておくこと． * 授業は対面形式での実施を基本とする．ただし状況に応じてハイブリッド型・オンライン型の実施方法を併用する． * 本講義では理解を深めるためにほぼ毎回レポート課題を課す．レポートも評価の一部であるので必ず取り組み提出すること．
＜受講に際して・学生へのメッセージ＞
プログラミング言語を習得するためには，プログラムを自力で書き，コンパイルエラーを修正し，不具合があればそれも修正し，様々なテスト事例に対しても正しく動作するか確認するというサイクルを繰り返すことが非常に重要である．座学を受けているだけでは上達しないため，レポート課題などを通して，実際にプログラムを組み，その動作を確かめることが必要不可欠である．
＜テキスト＞
岩沼 宏治，美濃 英俊，鍋島 英知，山本 泰生, データ構造とアルゴリズム, コロナ社, ISBN:4339018236, (後継科目のアルゴリズムとデータ構造I, 同演習，アルゴリズムとデータ構造IIにおける教科書でもあります．)
＜参考書＞
高橋 麻奈, やさしいC++ 第5版, SBクリエイティブ, ISBN:4797392592 Cay Horstmann, Computing Concepts with C++ Essentials (3rd Edition), Wiley International, ISBN:0471164372 ハーバート・シルト (著), 神林 靖 (監修), トップスタジオ (翻訳), 独習C++ 第4版, 翔泳社, ISBN:4798119768
＜授業計画の概要＞
1 タイトル 値渡しと参照渡し，クラスとオブジェクト 事前学習 事後学習 事前学習：C++の制御構文，クラスの定義方法を復習しておくこと．また教科書１章を読んでおくこと 事後学習：間違ったプログラムについて「何がどのように間違っているのか」指摘できるようになること 授業内容 C++言語の復習を，「画面に図形を出力するプログラムの作成」や「間違ったプログラムの間違いを指摘」することを通して行う 2 タイトル ポインタと配列 事前学習 事後学習 事前学習：教科書２章～2.2.1節まで読んでおくこと．ポインタについて参考書「やさしいC++」で復習しておくこと 事後学習：講義で示したプログラムを実際に動作させ，ポインタの理解を深めること 授業内容 ポインタとは何か，ポインタの利用方法，ポインタと配列の関係を理解する 3 タイトル ポインタとメモリの動的割当，可変長配列 事前学習 事後学習 事前学習：教科書2.2.2節を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，メモリの動的割当の理解を深めること 授業内容 ポインタと参照の違い，メモリの動的確保，クラステンプレートを理解する 4 タイトル 連結リスト 事前学習 事後学習 事前学習：教科書2.3節を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，連結リストの理解を深めること 授業内容 アロー演算子，連結リストを理解する 5 タイトル 連結リストとスタック，キュー 事前学習 事後学習 事前学習：教科書2.4節（配列によるキューの実装の手前まで）を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，継承やスタック，キューについて理解を深めること 授業内容 スタックとキューとは何か，リストによるスタックとキューの実現方法を理解する　 6 タイトル 配列とスタック，キュー 事前学習 事後学習 事前学習：教科書2.4節（配列によるキューの実装以降）を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，継承やスタック，キュー（リングバッファ）について理解を深めること 授業内容 スタックとキュー（リングバッファ）の配列による実現方法を理解する 7 タイトル 木構造と木のなぞり 事前学習 事後学習 事前学習：教科書2.5節（[3] スタックとキューによる木のなぞりまで）を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，木構造とそのなぞりについて理解を深めること 授業内容 木構造とその実現方法，木のなぞり方を理解する 8 タイトル 中間評価（総括とまとめ） 事前学習 事後学習 事前学習：過去の試験問題を公開するのでそれに各自取り組み，解けるようになっておくこと 事後学習：自身の解答が適切であったかどうか，プログラムを実際に動作させるなどして検証すること 授業内容 講義前半の内容を総括し，その理解度を試験により評価する 9 タイトル 再帰呼び出し 事前学習 事後学習 事前学習：教科書2.5節（[4] 再帰呼び出しによる木のなぞり）を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，再帰呼び出しの動作について理解を深めること 授業内容 再帰呼び出しの概念を理解し，再帰呼び出しが実装できること 10 タイトル 再帰呼び出しによる木のなぞり 事前学習 事後学習 事前学習：教科書2.5節（[4] 再帰呼び出しによる木のなぞり）を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，再帰による木のなぞりや木に対する各種操作について理解を深めること 授業内容 再帰呼び出しが実装でき，再帰による木のなぞりの実装方法を理解する 11 タイトル 計算量 事前学習 事後学習 事前学習：教科書3.1節を読んでおくこと 事後学習：レポート課題を通して計算量の漸近的評価について理解を深めること 授業内容 計算量の概念を理解し，基本的なアルゴリズムの計算量を示すことができること 12 タイトル 線形探索と二分探索 事前学習 事後学習 事前学習：教科書3.2節, 3.3節を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，線形探索と二分探索の速度差について問題の大きさを変化させながら評価すること 授業内容 線形探索と二分探索の特徴，利点，欠点を理解する 13 タイトル 素朴な整列アルゴリズムと再帰的整列アルゴリズム 事前学習 事後学習 事前学習：教科書3.4節，3.5節を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，各ソートアルゴリズムについて理解を深めるとともに，問題の大きさを変化させながら速度差を評価すること 授業内容 選択ソート，挿入ソート，マージソート，クィックソート，外部ソートのアルゴリズムと，その利点・欠点を理解する 14 タイトル 空間を利用した整列アルゴリズム 事前学習 事後学習 事前学習：教科書3.6節を読んでおくこと 事後学習：講義で示したプログラムを実際に動作させ，各ソートアルゴリズムについて理解を深めるとともに，問題の大きさを変化させながら速度差を評価すること 授業内容 バケットソート，計数ソート，基数ソートのアルゴリズムと，その利点・欠点を理解する 15 タイトル 最終評価（総括とまとめ） 事前学習 事後学習 事前学習：過去の試験問題を公開するのでそれに各自取り組み，解けるようになっておくこと 事後学習：自身の解答が適切であったかどうか，プログラムを実際に動作させるなどして検証すること 授業内容 講義全体（主として後半）の内容を総括し，その理解度を試験により評価する 16 タイトル 事前学習 事後学習 授業内容 17 タイトル 事前学習 事後学習 授業内容 18 タイトル 事前学習 事後学習 授業内容 19 タイトル 事前学習 事後学習 授業内容 20 タイトル 事前学習 事後学習 授業内容 21 タイトル 事前学習 事後学習 授業内容 22 タイトル 事前学習 事後学習 授業内容 23 タイトル 事前学習 事後学習 授業内容 24 タイトル 事前学習 事後学習 授業内容 25 タイトル 事前学習 事後学習 授業内容 26 タイトル 事前学習 事後学習 授業内容 27 タイトル 事前学習 事後学習 授業内容 28 タイトル 事前学習 事後学習 授業内容 29 タイトル 事前学習 事後学習 授業内容 30 タイトル 事前学習 事後学習 授業内容
＜備考＞
・学生の理解度に合わせて，内容を変更する場合がある．