集中講義 乱択と計算量

京都大学 人間環境学研究科・総合人間学部

(総合人間学部)5914001 数理科学特論II
(大学院人間環境学研究科)D015000 数理科学特論A

平成25年12月2日(月)〜6日(金)3限〜 京都大学総合人間学部棟4階1401数理科学セミナー室


賽の目の出方はランダム(無作為、出鱈目、不規則)であるという。しかし無作為とはそもそもどういうことか。また乱数はうまく使うと色々な計算の役に立つ(乱択算法)が、このために本当に無作為な乱数の代りに「出鱈目に見える」作られた数列で事足りるのか。これらは計算理論の根幹にある問の一つである。本講義では、前半で計算量の基礎事項を解説し、後半ではこのような乱択の本質に関する話題について最近の研究や未解決問題を含めて紹介する。

  1. 計算量理論入門(月・火・水)→演習問題.pdf
  2. 乱択と計算量(水・木・金)

評価方法:演習問題80点以上で優、1月7日(火)締切、レポート箱へ提出、黒板で解いた分は3倍

質問など歓迎します→kawamura@is.s.u-tokyo.ac.jpまで