シラバス参照

基本情報／Basic Information
詳細情報／Detailed Information
授業計画詳細情報／Class Schedule Details

基本情報/Basic Information

開講科目名／Course	アルゴリズム特論／Advanced Algorithms
時間割コード／Course Code	S241000043
ナンバリングコード／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	DP1･DP2･DP3
授業としての具体的到達目標／Concrete arrival target as the class	○コンピュータで計算をするということの原理を理解すること (DP1) ○問題を解くための適切で効率の良いアルゴリズムを選択・設計することができるようになること (DP2・DP3)
授業の概要／Summary of the class	Turing 機械の動作を通してアルゴリズムの概念を明確にし、アルゴリズムの解析により時間計算量について考察します。そして、問題が時間計算量によってクラスP、NP、NP完全などに分類されることを学びます。
授業の内容予定／Contents plan of the class	1. 4/11（木） Turing 機械と複雑さの測定 2. 4/18（木）アルゴリズムの解析 3. 4/25（木）モデル間の複雑さの関係 4. 5/ 9（木）クラスP 5. 5/16（木） Pに属する問題(1)―PATH問題 6. 5/23（木） Pに属する問題(2)―Euclidのアルゴリズム 7. 5/30（木） Pに属する問題(3)―文脈自由言語 8. 6/ 6（木）クラスNP 9. 6/13（木） NPに属する問題(1)―クリーク 10. 6/20（木） NPに属する問題(2)―部分和問題 11. 6/27（木） NP完全性 12. 7/ 4（木） Cook-Levinの定理 13. 7/11（木） NP完全問題(1)―充足可能性問題 14. 7/18（木） NP完全問題(2)―頂点被覆問題とHamiltonパス問題 15. 7/25（木） 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
該当するデータはありません

開講科目名／Course	アルゴリズム特論／Advanced Algorithms
時間割コード／Course Code	S241000043
ナンバリングコード／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	－

難易度（レベル）／Level	レベル5
対応するＤＰ／DP	DP1･DP2･DP3
授業としての具体的到達目標／Concrete arrival target as the class	○コンピュータで計算をするということの原理を理解すること (DP1) ○問題を解くための適切で効率の良いアルゴリズムを選択・設計することができるようになること (DP2・DP3)
授業の概要／Summary of the class	Turing 機械の動作を通してアルゴリズムの概念を明確にし、アルゴリズムの解析により時間計算量について考察します。そして、問題が時間計算量によってクラスP、NP、NP完全などに分類されることを学びます。
授業の内容予定／Contents plan of the class	1. 4/11（木） Turing 機械と複雑さの測定 2. 4/18（木）アルゴリズムの解析 3. 4/25（木）モデル間の複雑さの関係 4. 5/ 9（木）クラスP 5. 5/16（木） Pに属する問題(1)―PATH問題 6. 5/23（木） Pに属する問題(2)―Euclidのアルゴリズム 7. 5/30（木） Pに属する問題(3)―文脈自由言語 8. 6/ 6（木）クラスNP 9. 6/13（木） NPに属する問題(1)―クリーク 10. 6/20（木） NPに属する問題(2)―部分和問題 11. 6/27（木） NP完全性 12. 7/ 4（木） Cook-Levinの定理 13. 7/11（木） NP完全問題(1)―充足可能性問題 14. 7/18（木） NP完全問題(2)―頂点被覆問題とHamiltonパス問題 15. 7/25（木） 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	なし

授業情報／Class Information

基本情報/Basic Information

担当教員情報/Instructor Information