2025年度前期データ構造とアルゴリズム

曜日・時限 火曜日３時限 期別 前期 週時間数 2
ナンバリング HW230706
開講学科等 総合情報学部-デジタルゲーム学科
教員名 魚井　宏高
魚井　宏高
職務履歴

https://research.osakac.ac.jp/index.php?%e9%ad%9a%e4%ba%95%e3%80%80%e5%ae%8f%e9%ab%98

教員情報データベースに遷移します

目的

本科目では，リストや木構造，ハッシュといった典型的なデータ構造とそれを利用する様々なアルゴリズムやアプリケーションについて理解し，それらの効率を論じるための数学的な基礎知識について学習する．アプリケーションを構築していく上で必要となる，効率的なアルゴリズムを設計し，必要に応じて様々なデータ構造を適切に使用できる能力を獲得することを目的とする．
この科目を習得することで，デジタルゲームとエンタテインメントコンテンツ分野における基礎的な専門知識を包括的に有し，それらを適切に応用する能力を備えることができる．

授業計画

授業回 形式 学修内容 学修課題
1 AC 授業ガイダンス 事前学修 Visual Studio Codeの動作確認とシラバスをよく読んでおくこと(2時間)
事後学修 授業で指示した内容を元に，スライドの該当する箇所をチェックする(2時間)
2 AC 数学的予備知識の解説
各種アルゴリズムとオーダの考え方		 事前学修 二次関数と対数関数について復習しておくこと(2時間)
配布スライドを読んで計算量について予習してくる(2時間)
事後学修 授業内で出てきた各種数学のグラフを自分で書き直して，それぞれのグラフの性質をよく理解すること(2時間)
自分が書いた様々なプログラムに対して，オーダの考え方で計算量を算出してくる(2時間)
3 AC C++における標準ライブラリ(STL)に含まれるコレクション関連クラスの解説 事前学修 C++における配列の使い方を復習しておく(2時間)
事後学修 C++に用意されている主要なコレクションクラスについて，それぞれの役割を調べてまとめてくる(2時間)
4 AC 動的配列（vector） 事前学修 配布スライドを読んで動的配列について予習してくる(2時間)
事後学修 授業内で提示するvectorの演習課題を繰り返し解いて、その使い方をよく理解すること(2時間)
5 A,C遠隔 連結リスト（list） 事前学修 配布スライドを読んで連結リストについて予習してくる(2時間)
事後学修 授業内で提示するlistの演習課題を繰り返し解いて、その使い方をよく理解すること(2時間)
6 AC イテレータによる要素アクセス 事前学修 C++におけるvectorとlistの使い方について復習してくる(2時間)
事後学修 C++でforeachを用いた繰り返しと，そうでない繰り返しを行うプログラムを書いて，動作をよく理解しておく(2時間)
7 AC スタックとその応用(数式処理) 事前学修 配布スライドを読んでスタックについて予習してくる(2時間)
事後学修 数式処理の仕組みをよく理解すること(2時間)
8 AC キュー(待ち行列)とその応用(再帰呼び出しの逐次化) 事前学修 配布スライドを読んでキューについて予習してくる(2時間)
事後学修 再帰呼び出しの仕組みとキューを用いた逐次処理化についてよく理解すること(2時間)
9 AC 木構造(二分木・二分探索木) 事前学修 配布スライドを読んで二分木と二分探索木について予習してくる(2時間)
事後学修 教科書の該当箇所をよく読んでデータ構造の性質をよく理解すること(2時間)
10 AC 様々な探索木(AVL木 ほか) 事前学修 配布スライドを読んでAVL木について 予習してくる(2時間)
事後学修 授業内で提示するAVL木の演習課題を繰り返し解いて，一重回転と二重回転の使い方についてよく理解すること(2時間)
11 AC ハッシュ法（unordered_map）と ゲーム木探索（ゲーム木探索とその効率化） 事前学修 配布スライドを読んでハッシュ法について予習してくる(2時間)
配布スライドや授業内で提示する資料をよく読んで，ゲームプログラミングと木構造の関係について理解してくる(2時間)
事後学修 授業内で提示するunordered_mapの演習課題を繰り返し解いてよく理解すること(2時間)
格闘ゲームや思考ゲームなど，様々なゲームにおける木構造の使い方について調べてまとめる(2時間)
12 AC グラフ探索(最短経路問題ほか) 事前学修 配布スライドを読んで最短経路探索について予習してくる(2時間)
事後学修 グラフ探索の応用について考察すること(2時間)
13 AC まとめと総合的な演習 事前学修 ここまでの内容を配布スライドを読み返してよく復習しておくこと(2時間)
事後学修 復習した内容について再確認すること(2時間)

授業形式記号

  • A:一斉授業（通常の講義）
  • B:問題発見・解決学習、プロジェクト学習
  • C:体験、実験、実習、演習など
  • D:調査 分析、解析など
  • E:ものづくり、作品制作
  • F:グループワーク（ディスカッション・ディベートを含む）
  • G:プレゼンテーション
  • H:地域・企業　連携型学習
  • I:その他

到達目標

・プログラムの実行効率の計算ができるようになること
・数学的な基礎知識に基づき，目的に応じて，C++において用意されている各種のコレクション関連クラスを適切に選択し利用できるようになること

科目に関連するディプロマポリシー項目
〇2024年度以降入学生
下記、記載のカリキュラムマップを参照。
https://www.osakac.ac.jp/about/policy/faculty/
※各学科/専攻名称のカリキュラムポリシー下段の
　「カリキュラムマップ」よりご確認ください。

　　〇 202３年度以前の入学生
　　　　修得する資質・能力:知識・理解【DP-W-1-1】

評価方法と評価観点

評価方法 配点合計知識・理解力応用力コミュニケーション力態度・志向性創造力 合計
定期試験またはレポート試験 60% 70% 30% 100%
小テスト、小論文 10% 50% 50% 100%
グループワーク 0%
プレゼンテーション 0%
レポート、宿題 30% 60% 40% 100%
授業での姿勢（ノート、質疑など） 0%
作品、パフォーマンス（実技、実演） 0%
その他1(具体的に： 0%
その他2(具体的に： 0%
100% 65% 35% 0% 0% 0% 100%

教科書・参考書

教科書は用いず，授業前にはその時間で行う内容をまとめたスライドファイルを配布するので，必ずダウンロードして目を通しておくこと．

参考書： 電子書籍のみ
「アルゴリズムを学ぼう」川中真耶、杵渕朋彦、椎名俊輔著　アスキー・メディアワークス　ISBN978-4048861281
　参考書としておくが，教科書的に参照することもある．ただし，本書で取り扱われている言語はJava言語であり，C++言語とは少し異なる．具体的なC++プログラム(すなわち実装)については，講義内で示す．

「定本Cプログラマのためのアルゴリズムとデータ構造」　近藤嘉雪著　ソフトバンククリエイティブ　ISBN978-4797304954
　こちらもC言語による解説書ではあるが，基本的には同じである．ただし，少し古いのでサンプルプログラムについては修正する必要があるものもある．

オフィスアワー

前期火曜4限 10-306室まで，できるだけ授業後に申し出て下さい．
学内外の用務のため、オフィスアワーでも教員が教員室に不在の可能性があります．
事前予約の場合はできるだけ対応します．
電子メールでの相談はuoi@oecu.jpに送ってください(ただし，成績に関する問い合わせには返答できません)．
授業内容に関する質問については，Moodleの授業掲示板(質問室)で行ってもらう方が望ましいです．
遠隔(ビデオ会議)でも対応しますが，時間調整のために事前にメールで予約してください.

その他

欠格条件：
宿題もしくは授業内レポートがほぼ毎回あるが，合わせて未提出が5回以上で，定期試験の成績にかかわらず，最終成績を0点とする．
また，両方のレポート提出が0回かつ定期試験未受験の場合は，最終成績は評価不能(E)とし，卒業再試験の資格を失うので注意すること．

注意事項：
授業計画および，講義でとり上げる題材は，進行度合いに応じて変更される可能性があります．
1年で使用した開発環境Visual Studio Codeを使用するので，各自が受講前に動作確認をしておくこと．問題があればサポートデスクで対応してもらってください．

Moodleを用いて，資料・教材の配布，小テスト，レポート提出を行います．
毎回ノートPCを用いるので，忘れないように．故障などの場合にはサポートデスクで代替機を借りておくように．

紙での課題提出は行わない(PDF化して提出)が不適切なサイズの用紙の場合には減点する．
宿題・レポートは返却しないが，回答例を示したり，一部を取り上げての評価は講義中に行う．

実務経験のある教員による授業科目

戻る