複雑さの理論

Theory of Complexity

9963314

63MAMAI305

入山　聖史

Satoshi Iriyama

2024年度前期

Semester

火曜3限

Tuesday 3rd

創域理工学部　情報計算科学科

Department of Information Sciences, Faculty of Science and Technology

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

現在“複雑さ”という名を付した研究が様々な分野で行なわれている．しかし，複雑さは取り扱う分野や対象によってその表現が異なっている．本講義では複雑さについて統一的に取り扱う数学的基礎について講義する．

本学科のディプロマポリシー「情報科学科の学問分野における幅広い基礎的知識をもとに，情報科学に関わる分野における原理と応用を体系的に身に付けている」を実現するために，幅広い応用分野を持つ複雑さについての数学的基礎を身に付ける．

微分方程式の解法の修得，力学系の基礎の理解，カオス現象についての理解，ロジスティック写像の定義の理解，カオス尺度の定義と求め方の理解，リアプノフ指数の定義と性質の理解，複雑さの応用分野についての知識の修得．

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

情報数学１Ｂ及び演習の内容を理解していることが望ましい．

小テストの実施　Quiz type test

-

授業準備と復習を合わせて週4時間を目安とします．
準備学習：
(全般)毎回，講義の参考書を事前に調べて講義の学習の準備をして下さい．
1. 身の回りにある複雑系(天体の運行，3体問題，ブラウン運動等)をwebで調べる
2. 原始関数の積分を求められるようにする
3. 1階の常微分方程式(変数分離形，同次形)の解を導出できるようにする
4. 1階の常微分方程式(線形)の解を導出できるようにする
5. 1階の常微分方程式(リッカチ形，ベルヌイ形)の解を導出できるようにする
6. 与えられた事象と生起確率から完全事象系をつくり，系のエントロピーを計算できるようにする
7. 条件付きエントロピーの定義を振り返り，ベイズの定理を証明する
8. ソート問題について異なるアルゴリズムで計算した場合の計算量を少なくとも3つ求める
9. フラクタル図形を生成するアルゴリズムを調べる
10. 円周率を求めるアルゴリズムの中で，最も短いものを調べる
11. 2人完全情報ゲームと囚人のジレンマについて調べる
12. 線形合同法のアルゴリズムを調べ，4ビット程度の初期値から求まる乱数列を導出する
13. 2階常微分方程式について解を求められるようにする
14. フラクタル次元について定義を調べる
15. これまでの内容についてノートを確認する
復習：
(全般)講義の内容が理解できているか，毎回復習して下さい．
1. 授業で触れたトピックについて，具体的な事例を調べる
2. 1階の常微分方程式の階が導出できるようにする
3. 差分方程式系から生成されるカオス軌道について具体的に求められうようにする
4. ロジスティック写像の分岐図をファイゲンバウム点との関係に注意しながら求める
5. 簡単な1次元写像についてリアプノフ指数を導出する
6. 状態遷移チャネルを用いて相互エントロピーを計算する
7. 状態力学と複雑さについての基本方程式の定義を覚える
8. クラスPとそこに属する問題についての基本的なアルゴリズムを確認する
9. フラクタル次元の定義を確認し，基本的なフラクタル図形について計算する
10. 計算可能性とゲーデル数，ランダム性についての定義を確認する
11. いくつかの例について，利得表から均衡点を求める
12. 完全守秘性の定義を確認し，いくつかの例で定義を満たしているか確認する
13. 2次元のカオス写像について周期を計算する
14. カオス尺度について定義を確認し，いくつかの写像についてm, nを決めた場合のカオス尺度を計算する
15. これまでの復習を行う

期末試験と授業内テスト(実施された場合)により評価する．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

大矢雅則　編著　情報数理入門　（サイエンス社）
ISBN-10: 4781909167
ISBN-13: 978-4781909165

1. 序論 複雑さとはなにか
2. カオスの数理(1) 力学系と微分方程式の基礎
3. カオスの数理(2) 差分方程式系のカオス
4. カオスの数理(3) 力学系における軌道
5. カオスの数理(4) リアプノフ指数と取り扱い
6. 情報における複雑さ(1) エントロピーとその数理
7. 情報における複雑さ(2) 様々なエントロピーと定理
8. 情報における複雑さ(3) 計算の複雑さ序論
9. 情報における複雑さ(4) 様々な複雑さと取り扱い
10. 応用(1) Kolmogorovの複雑量
11. 応用(2) ゲーム理論の数理と複雑さ
12. 応用(3) 暗号理論と複雑量
13. 先進的な話題 複雑さ理論における先進的な話題を紹介する
14. 総括 複雑さの数理について振り返り、理解を確認する
15. 演習 授業内容について演習を行う

情報セキュリティに関する企業での実務経験を生かし、情報セキュリティに関連する最新の理論や技術動向を適宜示しながら講義を行う。

-

-

なし

N

N