2025年度前期アルゴリズム設計論

曜日・時限	月曜日３時限	期別	前期	週時間数	2
ナンバリング	GP331204
開講学科等	情報通信工学部-情報工学科
教員名	上嶋　章宏上嶋　章宏職務履歴 https://research.osakac.ac.jp/index.php?%e4%b8%8a%e5%b6%8b%e3%80%80%e7%ab%a0%e5%ae%8f 教員情報データベースに遷移します

目的

与えられた問題をコンピュータで解くためにはそのためのプログラムが必要となる。プログラムの元になる計算手続きをアルゴリズムと言い，これは良いプログラムを書くために理解しておかなければならない必須知識である。本講義では，アルゴリズム基礎論に引き続き，アルゴリズムについて学ぶ。
基礎的なデータ構造の実現方法を理解し，効率的なアルゴリズムの重要性を認識するために，アルゴリズムの計算効率の客観的な評価法について基本的な概念を学び，重要ないくつかのデータ構造を理解し，代表的ないくつかのアルゴリズムを題材にアルゴリズムの客観的な評価手法を理解できるようになる。

授業計画

授業回	形式	学修内容	学修課題
1	A,C	アルゴリズムと計算量	事前学修	シラバスを読んで，関連科目を復習してくる（2時間）
1	A,C	アルゴリズムと計算量	事後学修	計算量の捉え方を整理し復習する（3時間）
2	A,C	グラフ，木，２分木	事前学修	グラフ，木などの基本的なデータ構造を調べておく（2時間）
2	A,C	グラフ，木，２分木	事後学修	ノートを整理し復習する（3時間）
3	A,C	ヒープ（データ構造と木の深さ）	事前学修	ヒープの定義とサポートする操作を調査してくる（2時間）
3	A,C	ヒープ（データ構造と木の深さ）	事後学修	ヒープの構造を整理し復習する（3時間）
4	A,C	ヒープ（各種操作の実現と計算量）	事前学修	ヒープでの各種操作に実現方法を調査してくる（2時間）
4	A,C	ヒープ（各種操作の実現と計算量）	事後学修	講義中に課した問題を解いて復習する（3時間）
5	A,C	代表的な整列アルゴリズムとその解析	事前学修	整列アルゴリズムについて調べておく（2時間）
5	A,C	代表的な整列アルゴリズムとその解析	事後学修	ヒープソートについてノートを整理し復習する（3時間）
6	A,C	整列の下界と線形時間での整列	事前学修	決定木について調べておく（2時間）
6	A,C	整列の下界と線形時間での整列	事後学修	計算量の下界についてノートを整理し復習する（3時間）
7	A,C	２分探索木（データ構造）	事前学修	連結リストでの操作の実現方法を調べておく（2時間）
7	A,C	２分探索木（データ構造）	事後学修	２分探索木の構造についてノートを整理し復習する（3時間）
8	A,C	２分探索木（各種操作の実現と計算量）	事前学修	２分探索木の実装について調べておく（2時間）
8	A,C	２分探索木（各種操作の実現と計算量）	事後学修	講義中に課した問題を解いて復習する（3時間）
9	A,C	平衡探索木（ＡＶＬ木，２色木）	事前学修	２色木以外の平衡探索木を調べておく（2時間）
9	A,C	平衡探索木（ＡＶＬ木，２色木）	事後学修	２色木の平衡条件を復習しておく（2時間）
10	A,C	平衡探索木（２色木でのINSERT操作手順）	事前学修	２色木でのINSERT操作の手順を予習してくる（2時間）
10	A,C	平衡探索木（２色木でのINSERT操作手順）	事後学修	講義中に課した問題を解いて復習する（2時間）
11	A,C	平衡探索木（２色木でのDELETE操作手順，代表的な操作の計算量）	事前学修	２色木でのDELETE操作の手順を予習してくる（2時間）
11	A,C	平衡探索木（２色木でのDELETE操作手順，代表的な操作の計算量）	事後学修	講義中に課した問題を解いて復習する（2時間）
12	A,C	グラフ・ネットワークに関する問題	事前学修	最小木，最短路木，マッチング，ネットワークフローなどについて予習してくる（2時間）
12	A,C	グラフ・ネットワークに関する問題	事後学修	紹介したグラフ問題の解法についてノートを整理し復習する（2時間）
13	I	学習到達度の最終確認	事前学修	アルゴリズム設計に関して学んできた内容を総合的に復習してくる（2時間）
13	I	学習到達度の最終確認	事後学修	分からなかったところをしっかり復習し，学修到達の不充分な点に取り組む（2時間）

授業形式記号

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

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

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

到達目標

到達目標は次の通りである。

○修得する資質・能力：知識・理解力【DP-P-1-1】
　・漸近計算量を概算できる
　・グラフ上で定める各概念を理解できる
　・２分木にまつわるデータ構造を区別でき，操作の実現手順を理解できる
　
○修得する資質・能力：応用力【DP-P-2-2】
　・データ構造やアルゴリズムの正当性を理解し応用できる
　・アルゴリズムの計算量の見積り方を理解し応用できる
　・問題解決に適したデータ構造を選定し，アルゴリズム設計に適用できる

評価方法と評価観点

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

教科書・参考書

参考書：「アルゴリズムイントロダクション第１巻」，T.コルメン，C.ライザーソン，R.リベスト共著，浅野，岩野，梅尾，山下，和田共訳近代科学社
参考書：「Ｃによるアルゴリズムとデータ構造」，茨木俊秀，昭晃堂

オフィスアワー

研究室を訪問する場合は，電子メールなどで事前にアポイントを取ることが望ましい。
前期月曜5限（A号館2階教員室15）

なお，学内外の用務のため，オフィスアワーでも教員が教員室に不在の可能性がある。

その他

事後学修の内容をレポートや宿題の形で応用力や学習進度を確認するので，授業中の指示を聞き洩らさない。
授業内外の課題について，解答あるいは考え方を適宜解説する。

本講義は，2年次開講「知能情報科学基礎」の授業内容をある程度理解していることを前提とする。3年次前期開講の「離散数学」も合わせて履修していることが望ましい。

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

戻る