シラバス参照

授業情報/Class Information

科目一覧へ戻る 2022/12/02 現在

基本情報/Basic Information

開講科目名
/Course
アルゴリズム特論/Advanced Algorithms
時間割コード
/Course Code
S221000040
ナンバリングコード
/Numbering Code
開講所属
/Course Offered by
理工学研究科/
曜日コマ
/Day, Period
木 2
開講区分
/Semester offered
前期/first semester
単位数
/Credits
2.0
学年
/Year
1,2
主担当教員
/Main Instructor
水田 智史/MIZUTA SATOSHI
科目区分
/Course Group
大学院(博士前期課程) 専門科目
教室
/Classroom
必修・選択
/Required/Elective
選択
授業形式
/Class Format
講義科目
メディア授業
/Media lecture

担当教員情報/Instructor Information

教員名
/Instructor
教員所属名
/Faculty/Department
水田 智史/MIZUTA SATOSHI 理工学研究科/
難易度(レベル)
/Level
レベル5
対応するDP
/DP
DP1・DP2・DP3
授業としての具体的到達目標
/Concrete arrival target as the class
○コンピュータで計算をするということの原理を理解すること
○問題を解くための適切で効率の良いアルゴリズムを選択・設計することができるようになること
授業の概要
/Summary of the class
Turing 機械の動作を通してアルゴリズムの概念を明確にし、アルゴリズムの解析により時間計算量について考察します。そして、問題が時間計算量によってクラスP、NP、NP完全などに分類されることを学びます。
授業の内容予定
/Contents plan of the class
1.Turing 機械と複雑さの測定
2.アルゴリズムの解析
3.モデル間の複雑さの関係
4.クラスP
5.Pに属する問題(1)―PATH問題
6.Pに属する問題(2)―Euclidのアルゴリズム
7.Pに属する問題(3)―文脈自由言語
8.クラスNP
9.NPに属する問題(1)―クリーク
10.NPに属する問題(2)―部分和問題
11.NP完全性
12.Cook-Levinの定理
13.NP完全問題(1)―充足可能性問題
14.NP完全問題(2)―頂点被覆問題とHamiltonパス問題
15.NP完全問題(3)―部分和問題
成績評価方法及び採点基準
/A scholastic evaluation method and marking standard
授業への参加度50%、期末レポート50%を合算して、総合的に評価します。
予習及び復習等の内容
/Contents such as preparations for lessons and the review
シラバスに記載された各回の授業内容に該当する配布資料の部分を授業実施時までに予習
し、授業実施後に復習を行ってください。(予習、復習は最低でも各1時間程度行う必要があります。)
教材・教科書
/The teaching materials, textbook
適宜プリントを配ります。
参考文献
/bibliography
Michael Sipser 著、阿部 正幸 他訳 「計算論の基礎」(共立出版)
丸岡 章 著 「計算理論とオートマトン言語理論」(サイエンス社)
留意点・予備知識
/Point to keep in mind, back ground
学部授業科目「アルゴリズム」および「プログラミング演習II」の内容を理解しておく必要があります。
授業内容に関する質問・疑義等
/Question, doubt about class contents
月曜日・17:30-18:30 で受け付けます。
研究室は理工学部1号館4階405室です。
Eメールアドレス・HPアドレス
/E-mail address, HP address
slmizu@hirosaki-u.ac.jp
学問分野1(主学問分野)
/Discipline 1
J60:情報科学、情報工学およびその関連分野
学問分野2(副学問分野)
/Discipline 2
J62:応用情報学およびその関連分野
学問分野3(副学問分野)
/Discipline 3
該当なし
地域志向科目
/Local intention subject
なし
授業形態・授業方法
/Class form, class method
順番を決めて輪講形式で進めます。
科目ナンバー
/The subject number
メディア授業による著作物利用の有無について
/Whether or not copyrighted works are used in media classes
有/Yes
その他
/Others
なし
No. 回(日時)
/Time (date and time)
主題と位置付け(担当)
/Subjects and instructor's position
学習方法と内容
/Methods and contents
備考
/Notes
該当するデータはありません

科目一覧へ戻る