アルゴリズム情報理論と個々のオブジェクトのランダム性

20世紀半ばのエントロピーの概念は、 クロードシャノンによって導入されました。 「ランダム変数の1つの値に含まれる情報の平均ビット数」として直感的に説明できます。 ただし、個々のオブジェクト（たとえば、小説やDNAのテキスト）に適用することはできません。多くの同種のオブジェクトのアンサンブルがない場合、ランダム変数はありません。







1960年代半ばに、さまざまな人々（コルモゴロフ、ソロモン、レビン、チャイティン）に、個々のオブジェクトの情報量（複雑さ）を、このオブジェクトが生成するプログラムの最小長として（プログラミング言語の自然な制限の下で）決定できることが明らかになりました。 情報のアルゴリズム理論が生まれ、それはさまざまな分野に関連していることが判明しました：確率理論の基礎の哲学的質問（いつ統計的仮説を棄却しますか？）から組み合わせ論（集合のサイズとその射影を結ぶ不等式）および計算可能性理論まで。



今日あなたのために選んだ講義は、HSEコンピュータサイエンス学部の有名な数学者Alexander Shenによって行われました。 かつて、コルモゴロフの学生であるウラジミール・ウスペンスキーの指導の下で、彼は「エントロピー概念のアルゴリズム的変種」という論文を擁護した。



講義では、基本的な定義といくつかの基本的な結果について説明します。 アレクサンダー・シェンはモスクワ州立大学を卒業しました。 現在彼は、情報伝達問題研究所の従業員です。 A.A. ハルケビッチRASおよびフランス科学研究センターの研究所。 研究対象：アルゴリズム、コルモゴロフの複雑さ、論理、情報理論。 Alexander Hanievichが数学とプログラミングについて書いたほとんどすべての本は、パブリックドメインにあります 。