授業概要
- 首都大学東京 情報数理科学2(情報数理科学特論2) 集中講義
- 場所:首都大学東京(南大沢キャンパス)8号館6階610
- 時期:5月18日(木),5月25日(木),6月8日(木),6月15日(木)の14:40-17:50(途中休憩あり)
アルゴリズム的ランダムネスの理論では,科学の基本概念であるランダムについて,計算論を使って厳密な定義を与え,その性質を調べる。本講義では,計算論の再帰定理やTuring次数などの概念の復習から始める。その後,MLランダムネスの定義といくつかの性質を見る。特に,ランダムな列の構成技術に焦点を当てて解説する。
授業内容
- 5月18日(木):計算可能性理論(high, low, hyperimmune),Kolmogorov複雑性の定義
- 5月25日(木):Kolmogorov複雑性(KC定理,符号定理と計数定理)
- 6月8日(木):,MLランダムネス(圧縮不可能性,停止確率Ω,典型性,積分検定,予測不可能性による特徴付け),ランダム列の計算可能性(Kucera-Gacsの定理)
- 6月15日(木):Solovay還元とKucera-Slamanの定理
以下の講義ノートの中から,上記の話題の部分を取り出して,黒板に板書する形で進める.IDとパスワードは講義中に伝える.
講義ノート(2017年5月24日版)
レポート課題とその解答(2017年7月8日版)