|| 英語(English)
学習支援計画書(シラバス) 検索システム
専門教育課程 情報工学科
授業科目区分 科目名 単位数 科目コード 開講時期 履修方法
専門教育課程
専門科目
専門
アルゴリズムデザイン
Algorithm Design
2 E525-01 2023年度
4期(後学期)
修学規程第4条を参照
担当教員名
*印は、実務経験のある教員を示しています。
授業科目の学習・教育目標
キーワード 学習・教育目標
1.グラフ理論 2.アルゴリズム設計手法 3.決定不能性 4.計算困難性 5.計算困難問題へのアプローチ 複雑な問題に対する効率的なアルゴリズムを設計できるようになるため,様々なアルゴリズ ム設計技法を身に付ける.また,計算困難な問題に関する知識や,そのような問題に対する アルゴリズム設計アプローチも身に付ける.
授業の概要および学習上の助言
様々なアルゴリズム設計技法を学ぶ.具体的には,次の手法を学ぶ ・貪欲法 ・分割統治法 ・動的計画法 また,コンピュータで解けない問題があるという決定不能性の基礎を学ぶ.一方,コンピュータで解ける問題の中にも,現実 的な時間で計算できることが知られていない「計算困難問題」があることも学ぶ. そのうえで,計算困難な問題であっても,あきらめずに様々なアプローチで解決を図る方法について学ぶ. 抽象的でメタな議論が多いので,意味をしっかりと理解し,演習問題等で自分で問題を解くことで表面的な理解に留まらない ことが重要である.
教科書および参考書・リザーブドブック
教科書:アルゴリズム理論の基礎[森北出版] 参考書:アルゴリズムとデータ構造[森北出版] リザーブドブック:指定なし
履修に必要な予備知識や技能
「データ構造とアルゴリズム」を履修していることが望ましい.
学生が達成すべき行動目標
No. 学科教育目標
(記号表記)
L,M 貪欲法を用いたアルゴリズムを説明できる
L,M 分割統治法を用いたアルゴリズムを説明できる
L,M 局所探索法を用いたアルゴリズムを説明できる
L,M 動的計画法を用いたアルゴリズムを説明できる
L,M NP完全性について説明できる
L,M 計算困難問題に対する各種アプローチを説明できる
達成度評価
評価方法
試験 クイズ
小テスト
レポート 成果発表
(口頭・実技)
作品 ポートフォリオ その他 合計
総合評価割合 40 0 60 0 0 0 0 100
指標と評価割合 総合評価割合 40 0 60 0 0 0 0 100
総合力指標 知識を取り込む力 10 0 20 0 0 0 0 30
思考・推論・創造する力 20 0 20 0 0 0 0 40
コラボレーションと
リーダーシップ
0 0 0 0 0 0 0 0
発表・表現・伝達する力 10 0 20 0 0 0 0 30
学習に取組む姿勢・意欲 0 0 0 0 0 0 0 0
※総合力指標で示す数値内訳、授業運営上のおおよその目安を示したものです。
評価の要点
評価方法 行動目標 評価の実施方法と注意点
試験 おおむね学期末に実施する.試験範囲はその都度指定する.
クイズ
小テスト
レポート 不定期に実施する.範囲はその都度指定する.
成果発表
(口頭・実技)
作品
ポートフォリオ
その他
具体的な達成の目安
理想的な達成レベルの目安 標準的な達成レベルの目安
適切な設計手法を用いたアルゴリズムを設計できる 様々なアルゴリズム設計手法の考え方を説明できる
CLIP学習プロセスについて
一般に、授業あるいは課外での学習では:「知識などを取り込む」→「知識などをいろいろな角度から、場合によってはチーム活動として、考え、推論し、創造する」→「修得した内容を表現、発表、伝達する」→「総合的に評価を受ける、GoodWork!」:のようなプロセス(一部あるいは全体)を繰り返し行いながら、応用力のある知識やスキルを身につけていくことが重要です。このような学習プロセスを大事に行動してください。
※学習課題の時間欄には、指定された学習課題に要する標準的な時間を記載してあります。日々の自学自習時間全体としては、各授業に応じた時間(例えば2単位科目の場合、予習2時間・復習2時間/週)を取るよう努めてください。詳しくは教員の指導に従って下さい。
授業明細
回数 学習内容 授業の運営方法 学習課題 予習・復習 時間:分※
1週 アルゴリズム解析の基礎 講義・演習と質疑応答,自己 点検 予習:教科書第1章を読む 復習:教科書第1章の章末問題を 解く 60 60
2週 グラフ 講義・演習と質疑応答,自己 点検 予習:教科書第2章を読む 復習:教科書第2章の章末問題を 解く 60 60
3週 分割統治法 講義・演習と質疑応答,自己 点検 予習:教科書第3章を読む 復習:教科書第3章の章末問題を 解く 60 60
4週 貪欲法 講義・演習と質疑応答,自己 点検 予習:教科書第4章を読む 復習:教科書第4章の章末問題を 解く 60
5週 総合演習 講義・演習と質疑応答,自己 点検 予習:第4回までの内容を振り返 る 60
6週 局所探索法 講義・演習と質疑応答,自己 点検 予習:教科書第5章を読む 復習:教科書第5章の章末問題を 解く 60 60
7週 動的計画法 講義・演習と質疑応答,自己 点検 予習:教科書第6章を読む 復習:教科書第6章の章末問題を 解く 60 60
8週 総合演習 講義・演習と質疑応答,自己 点検 予習:第7回までの内容を振り返 る 60
9週 計算可能性 講義・演習と質疑応答,自己 点検 復習:講義資料を見返す 60
10週 計算困難性と計算量クラス 講義・演習と質疑応答,自己 点検 予習:教科書第7章を読む 復習:教科書第7章の章末問題を 解く 60 60
11週 計算困難問題へのアプローチ(近似) 講義・演習と質疑応答,自己 点検 予習:教科書第8章を読む 復習:教科書第8章の章末問題を 解く 60 60
12週 計算困難問題へのアプローチ(乱択) 講義・演習と質疑応答,自己 点検 予習:教科書第9章を読む 復習:教科書第9章の章末問題を 解く 60 60
13週 計算困難問題へのアプローチ(決定性アプローチ,ヒ ューリスティックス) 講義・演習と質疑応答,自己 点検 予習:教科書第5章を読む 復習:教科書第5章の章末問題を 解く 60 60
14週 総合演習 講義・演習と質疑応答,自己 点検 予習:第13回までの内容を振り返 る
15週 試験 自己点検 試験 自己点検 予習:試験に向けた勉強 120