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

曜日・時限	水曜日２時限	期別	前期	週時間数	2
ナンバリング	HT330404
開講学科等	総合情報学部-情報学科
教員名	渡邊　郁渡邊　郁職務履歴 https://research.osakac.ac.jp/index.php?%e6%b8%a1%e9%82%8a%e3%80%80%e9%83%81 教員情報データベースに遷移します

目的

2年前期の「アルゴリズムとデータ構造１」の授業では、リスト、スタック、キューなど基本的なデータ構造およびソーティング等の基本的なアルゴリズムを学んだ。本授業でそれを基礎とし、もっと複雑なグラフ及びネットワーク等のデータ構造やアルゴリズムを学ぶ。本科目はディプロマポリシー(1)知識・理解「情報学の基礎知識とそれを応用し実践する能力を有する。」【DP-T-1-1】を達成するために重要な科目である。

授業計画

授業回	形式	学修内容	学修課題
1	A	グラフのデータ表現	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
1	A	グラフのデータ表現	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(２.7時間)
2	A	グラフ探索(幅優先探索)	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
2	A	グラフ探索(幅優先探索)	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(２.7時間)
3	A	グラフ探索(深さ優先探索)	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
3	A	グラフ探索(深さ優先探索)	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
4	A	最短経路問題	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
4	A	最短経路問題	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
5	A	総合演習1	事前学修	第1~4回目の授業内容をよく復習しておくこと(２時間)
5	A	総合演習1	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
6	A	中間テストとmoodleでの解答確認による振り返り	事前学修	第1~5回目の授業内容をよく復習しておくこと(２.7時間)
6	A	中間テストとmoodleでの解答確認による振り返り	事後学修	中間テストで解けなかった問題は授業資料をよく読んで再度解いてみること。(2時間)
7	A	文字列照合(力押し法、KMP法)	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
7	A	文字列照合(力押し法、KMP法)	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
8	A	文字列照合(BM法)	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
8	A	文字列照合(BM法)	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
9	A	二分木とそのなぞり	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
9	A	二分木とそのなぞり	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
10	A	二分探索木	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
10	A	二分探索木	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
11	A	ハッシュ表	事前学修	moodleにアップロードする授業資料を事前に読み十分予習しておくこと。(２時間)
11	A	ハッシュ表	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
12	A	総合演習2	事前学修	第7~11回目の授業内容をよく復習しておくこと(２時間)
12	A	総合演習2	事後学修	当日の授業内容を確認しておくこと。とくに授業中に出題された課題のやり残しは自分でできる限りやっておくこと。(2.7時間)
13	A	最終テストとmoodleでの解答確認による振り返り	事前学修	第7~12回目の授業内容をよく復習しておくこと(２.7時間)
13	A	最終テストとmoodleでの解答確認による振り返り	事後学修	最終テストで解けなかった問題は授業資料をよく読んで再度解いてみること。(2時間)

授業形式記号

A:一斉授業（通常の講義）
B:問題発見・解決学習、プロジェクト学習
C:体験、実験、実習、演習など

D:調査分析、解析など
E:ものづくり、作品制作
F:グループワーク（ディスカッション・ディベートを含む）

G:プレゼンテーション
H:地域・企業　連携型学習
I:その他

到達目標

＜修得する資質・能力(ディプロマポリシー)＞
- 知識・理解力、応用力【DP-T-1-1】
＜JABEE学習･教育到達目標 : C＞
(1)二分木及び二分探索木のデータ構造とそれに関連するアルゴリズムを理解している。[JABEE番号:C5]
(2)グラフの表現方法と代表的なグラフ・ネットワークアルゴリムを理解している。[JABEE番号:C6]
(3)文字列照合アルゴリズムを理解している。[JABEE番号:C7]

先修が望まれる科目:アルゴリズムとデータ構造1、情報数学１・２、C++プログラミング演習1・2・3
関連科目: なし

＜評価項目と基準＞以下の評価項目の配点に従い100点満点で60点以上を合格とする。
評価項目 (対応する授業目標)[配点]…評価基準
-グラフのデータ構造(2)[15]…隣接行列、接続行列、隣接リストについて理解している。
-グラフ探索(2)[15]…BFS、DFSを理解している。
-ネットワークアルゴリズム(2)[15]…最短経路問題とダイクストラのアルゴリズムを理解している。
-文字列照合(3)[15]…KMP法、ボイヤー-ムーア法を理解していること。
-二分木(1)[15]…二分木のデータ構造とそのなぞりアルゴリズムを理解している。
-二分探索木(1)[10]…二分探索木とその挿入、削除アルゴリズムを理解している。
-ハッシュ法[15]…ハッシュ法を理解している。

評価方法と評価観点

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

教科書・参考書

教科書:アルゴリズム論、ITTextシリーズ、浅野、増沢、和田著、オーム社、 ISBN:4274132781　(授業資料を適宜配布するので購入は必須でないが、授業をより正確に理解するために購入することを薦める)
参考書:アルゴリズムC++、R.セジウィック著、近代科学社、ISBN4-7649-0222-2

オフィスアワー

毎週火曜日12:40-13:30　11-304室
なるべく事前に予約してください。

その他

注意事項
(1)以下の場合は不合格(E)になるので注意すること。
- 欠席回数が４回以上の場合
- 小テストが一つでも未受験の場合
(2) 毎回授業でmoodleで課題小テストを行う。これは成績評価に含まれないが，この課題小テストの取り組み状況が悪いまたは未受験の場合，当日は欠席とする。

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

戻る