ブラウザよりも高速アクセス！
33 関係: 停止性問題、実数、尤度関数、ペール・マルティン＝レーフ、マヌエル・ブラム、チャイティンの定数、チューリングマシン、ルベーグ測度、レイ・ソロモノフ、ブラムの公理、プログラム (コンピュータ)、データ構造、アルゴリズム的ランダムな無限列、アルゴリズム的確率、アンドレイ・コルモゴロフ、オークランド大学、グレゴリー・チャイティン、ゲーデルの不完全性定理、コルモゴロフ複雑性、ソフトウェア測定法、公理、級数、複雑性、計算理論、計算機科学、認識論、正規数、測度論、情報理論、情報科学、文字列、擬似乱数、整数。
停止性問題
計算可能性理論において停止(性)問題（ていしせいもんだい・ていしもんだい、halting problem）は、あるチューリング機械（≒コンピュータプログラム・アルゴリズム）が、そのテープのある初期状態（≒入力）に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。.
新しい！!: アルゴリズム情報理論と停止性問題 · 続きを見る »
実数
数学における実数（じっすう、 nombre réel, reelle Zahl, real number）は、様々な量の連続的な変化を表す数の体系である。実数全体の空間は、途切れのなさにあたる完備性とよばれる位相的な性質を持ち、代数的には加減乗除ができるという体の構造を持っている。幾何学や解析学ではこれらのよい性質を利用して様々な対象が定義され、研究されている。一方でその構成方法に自明でない手続きが含まれるため、実数の空間は数学基礎論の観点からも興味深い性質を持っている。また、自然科学における連続的なものの計測値を表すのに十分な数の体系だとも考えられている。 実数の概念は、その形式的な定義が19世紀に達成される前から数の体系として使われていた。「実数」という名前は複素数の概念が導入された後に「普通の数」を表現する言葉として導入されたものである。.
新しい！!: アルゴリズム情報理論と実数 · 続きを見る »
尤度関数
尤度関数（ゆうどかんすう、likelihood function）とは統計学において、ある前提条件に従って結果が出現する場合に、逆に観察結果からみて前提条件が「何々であった」と推測する尤もらしさ（もっともらしさ）を表す数値を、「何々」を変数とする関数として捉えたものである。また単に尤度ともいう。 その相対値に意味があり、最尤法、尤度比検定などで用いられる。.
新しい！!: アルゴリズム情報理論と尤度関数 · 続きを見る »
ペール・マルティン＝レーフ
ペール・マルティン＝レーフ (Per Martin-Löf, 1942年 -) はスウェーデンの論理学者、哲学者、数学者。の創案者として知られる。２００９年までストックホルム大学数学部および哲学部教授を務めた。.
新しい！!: アルゴリズム情報理論とペール・マルティン＝レーフ · 続きを見る »
マヌエル・ブラム
マヌエル・ブラム（Manuel Blum、1938年4月26日 - ）はベネズエラのカラカス出身の著名な計算機科学者。1995年、「計算複雑性理論の基礎的研究とその暗号およびプログラム検証への応用に関する貢献に対して」チューリング賞を授与された。.
新しい！!: アルゴリズム情報理論とマヌエル・ブラム · 続きを見る »
チャイティンの定数
チャイティンの定数（チャイティンのていすう、Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、Halting probability）とも。 停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。 個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。.
新しい！!: アルゴリズム情報理論とチャイティンの定数 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: アルゴリズム情報理論とチューリングマシン · 続きを見る »
ルベーグ測度
数学におけるルベーグ測度（ルベーグそくど、Lebesgue measure）は、ユークリッド空間上の長さ、面積、体積の概念を拡張したものである。名称はフランスの数学者アンリ・ルベーグにちなむ。体積には「互いに素な集合の体積は元の体積の和に等しい」という性質（加法性）がある。この性質を保ちながらより複雑な集合に対しても「体積」を定めることができるよう体積の概念を拡張できる。このような拡張は一意である。実解析、特にルベーグ積分で用いられる。体積と同様ルベーグ測度は値として をとりうる。解析学で普通に考えられるような集合に対してはルベーグ測度が与えられるものと考えてよいが、選択公理によって の部分集合でルベーグ測度を与えることができない（無理に与えると加法性が成り立たない）ものが存在することを証明できる。ルベーグ測度が与えられる集合はルベーグ可測であるという。以下の説明ではルベーグ可測な集合 の測度を で表す。.
新しい！!: アルゴリズム情報理論とルベーグ測度 · 続きを見る »
レイ・ソロモノフ
レイ・ソロモノフ（Ray Solomonoff、1926年7月25日 - 2009年12月7日）はアメリカの人工知能学者であり、アルゴリズム情報理論の創始者の1人。また、algorithmic probability を考案し、機械学習と予測と確率に基づく人工知能の分野を創始した。1956年、非意味論的機械学習についての論文を発表している。 1960年に algorithmic probability についてカリフォルニア工科大学での会議で発表し、同年2月には "A Preliminary Report on a General Theory of Inductive Inference" という論文を発表。1964年には "A Formal Theory of Inductive Inference" の第一部と第二部を発表し、さらに考え方を明確化した。そこからコルモゴロフ複雑性とアルゴリズム情報理論が発展した。 algorithmic probability は、オッカムの剃刀と多説明原理の組合せを数学的に定式化したものである。それは与えられた観察結果を説明するそれぞれの仮説（アルゴリズム、プログラム）に確率値を割り当てる機械に依存しない手法であり、最も単純な仮説が最も高い確率を割り当てられ、仮説が複雑になるほど割り当てる確率が低くなる。 他にも帰納推論の一般理論でも知られているが、確率的手法を用いて難しい問題を機械で解くという人工知能研究の過程で他にも様々な発見をしている。.
新しい！!: アルゴリズム情報理論とレイ・ソロモノフ · 続きを見る »
ブラムの公理
計算複雑性理論におけるブラムの公理（ブラムのこうり、Blum axioms）またはブラムの複雑性公理とは、計算可能関数の集合上の複雑性測度の満たすべき性質を述べた公理である。この公理はマヌエル・ブラムによって1967年に導入された。 重要な結果として、公理を満たす任意の複雑性測度でブラムの加速定理とギャップ定理が成り立つことが知られる。公理を満たす測度として最もよく知られているものとしては時間複雑性と空間複雑性がある。.
新しい！!: アルゴリズム情報理論とブラムの公理 · 続きを見る »
プログラム (コンピュータ)
ンピュータプログラム（英：computer programs）とは、コンピュータに対する命令（処理）を記述したものである。コンピュータが機能を実現するためには、CPUで実行するプログラムの命令が必要である。 コンピュータが、高度な処理を人間の手によらず遂行できているように見える場合でも、コンピュータは設計者の意図であるプログラムに従い、忠実に処理を行っている。実際には、外部からの割り込み、ノイズなどにより、設計者の意図しない動作をすることがある。また設計者が、外部からの割り込みの種類を網羅的に確認していない場合もある。.
新しい！!: アルゴリズム情報理論とプログラム (コンピュータ) · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
新しい！!: アルゴリズム情報理論とデータ構造 · 続きを見る »
アルゴリズム的ランダムな無限列
アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、Algorithmically random sequence）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。.
新しい！!: アルゴリズム情報理論とアルゴリズム的ランダムな無限列 · 続きを見る »
アルゴリズム的確率
アルゴリズム的情報理論において、ソロモノフのアルゴリズム的確率とはある観察にたいし事前確率を割り当てる数学的方法である。理論的には、その事前確率は普遍的である。帰納的推論の理論やアルゴリズムの解析などに使われている。計算可能ではなく、近似できるのみである。.
新しい！!: アルゴリズム情報理論とアルゴリズム的確率 · 続きを見る »
アンドレイ・コルモゴロフ
アンドレイ・ニコラエヴィッチ・コルモゴロフ（Андре́й Никола́евич Колмого́ров, Andrey Nikolaevich Kolmogorov, 1903年4月25日 - 1987年10月20日）はロシアの数学者であり、確率論および位相幾何学の大きな発展に寄与した。彼以前の確率論はラプラスによる「確率の解析的理論」に基づく古典的確率論が中心であったが、彼が「測度論に基づく確率論」「確率論の基礎概念（1933年）」で公理主義的確率論を立脚させ、現代確率論の始まりとなった。 初期には直観論理やフーリエ級数に関する研究を行っており、乱流や古典力学に関する研究成果もある。また彼はアルゴリズム情報理論の創始者でもある。なお、イズライル・ゲルファント、ウラジーミル・アーノルドをはじめ、コルモゴロフには数多くの弟子がいる。.
新しい！!: アルゴリズム情報理論とアンドレイ・コルモゴロフ · 続きを見る »
オークランド大学
ークランド大学（、Te Whare Wānanga o Tāmaki Makaurau）は、ニュージーランド北島オークランド市に所在するニュージーランドを代表する国立大学。.
新しい！!: アルゴリズム情報理論とオークランド大学 · 続きを見る »
グレゴリー・チャイティン
レゴリー・チャイティン（Gregory "Greg" J. Chaitin, 1947年 - ）は、アルゼンチン出身、アメリカ在住の数学者、コンピュータ科学者。 60年代に情報理論の分野に、ゲーデルの不完全性定理とよく似た現象を見いだす。つまり、その分野上での決定不可能な命題を発見し別種の不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能などのような理論においても、いかなる数であろうともcよりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 c が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。 1995年に、メイン大学から博士号を授与される。IBMのトーマス・J・ワトソン研究所に勤務した後、現在はリオデジャネイロ連邦大学に在籍。 幾つかの本を執筆しており、日本語に訳されている。.
新しい！!: アルゴリズム情報理論とグレゴリー・チャイティン · 続きを見る »
ゲーデルの不完全性定理
ーデルの不完全性定理（ゲーデルのふかんぜんせいていり、）又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明したものである。;第1不完全性定理: 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。;第2不完全性定理: 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。.
新しい！!: アルゴリズム情報理論とゲーデルの不完全性定理 · 続きを見る »
コルモゴロフ複雑性
ルモゴロフ複雑性（コルモゴロフふくざつせい、Kolmogorov complexity）とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ＝チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。 コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。.
新しい！!: アルゴリズム情報理論とコルモゴロフ複雑性 · 続きを見る »
ソフトウェア測定法
フトウェア測定法（ソフトウェアそくていほう）またはソフトウェアメトリック（英: Software metric ）とは、ソフトウェアやその仕様の属性の尺度である。 定量的手法の威力は他の分野で証明されていたことから、計算機科学の分野でも同様の手法をソフトウェア開発に持ち込もうとする努力が続けられてきた。Tom DeMarco は DeMarco, T. (1982) Controlling Software Projects: Management, Measurement & Estimation, Yourdon Press, New York, USA, p3 の中で「測定できないものは制御できない」と記している。.
新しい！!: アルゴリズム情報理論とソフトウェア測定法 · 続きを見る »
公理
公理（こうり、axiom）とは、その他の命題を導きだすための前提として導入される最も基本的な仮定のことである。一つの形式体系における議論の前提として置かれる一連の公理の集まりを (axiomatic system) という 。公理を前提として演繹手続きによって導きだされる命題は定理とよばれる。多くの文脈で「公理」と同じ概念をさすものとして仮定や前提という言葉も並列して用いられている。 公理とは他の結果を導きだすための議論の前提となるべき論理的に定式化された（形式的な）言明であるにすぎず、真実であることが明らかな自明の理が採用されるとは限らない。知の体系の公理化は、いくつかの基本的でよく知られた事柄からその体系の主張が導きだせることを示すためになされることが多い。 なお、ユークリッド原論などの古典的な数学観では、最も自明（絶対的）な前提を公理、それに準じて要請される前提を公準 (postulate) として区別していた。.
新しい！!: アルゴリズム情報理論と公理 · 続きを見る »
級数
数学における級数 (きゅうすう、series) とは、ひと口に言えば数や関数など互いに足すことのできる数学的対象の列について考えられる無限項の和のことである。ただし「無限の項の総和」が何を表しているのかということはしばしば解析学の言葉を用いて様々な場合に意味を与える（#級数の収束性の節を参照）ことができるが、そのようなことができない「発散する級数」もあれば、級数自体を新たな形式的対象としてとらえることもある。小さくなっていく実数を項とする級数の収束性については様々な判定条件が与えられている。 級数を表す記法として、和記号 を用いた表現 や三点リーダ を用いた表現 などがある。 有限個の項以外は とすることで有限個の対象の和を表すこともでき、無限項の和であることを特に強調する場合には無限級数とも言う。無限の項の和の形に表された級数が何を表しているかということは一見必ずしも明らかではないため、何らかの意味付けを与えなければならない。最もよく採用される理解の方法は、有限個の項の和が収束する先を無限級数の値とすることである。例えば、 より となる。このほかに、解析接続などの手法により、みかけ上発散している級数に対して のような等式が意味付けされることもある。.
新しい！!: アルゴリズム情報理論と級数 · 続きを見る »
複雑性
複雑性（ふくざつせい、complexity）という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという。.
新しい！!: アルゴリズム情報理論と複雑性 · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
新しい！!: アルゴリズム情報理論と計算理論 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: アルゴリズム情報理論と計算機科学 · 続きを見る »
認識論
認識論（にんしきろん、Erkenntnistheorie、Epistemology、Épistémologie）は、認識、知識や真理の性質・起源・範囲（人が理解できる限界など）について考察する、哲学の一部門である。存在論ないし形而上学と並ぶ哲学の主要な一部門とされ、知識論（theory of knowledge）とも呼ばれる。日本語の「認識論」は独語の訳語であり、日本ではヒト・人間を考慮した場合を主に扱う。英語と仏語の語源は「知」(epistēmē) + 「合理的な言説」(logos)。フランスでは「エピステモロジー」という分野があるが、20世紀にフランスで生まれた科学哲学の一つの方法論ないし理論であり、日本語では「科学認識論」と訳される。 哲学はアリストテレス以来その領域を諸科学によって置き換えられていったが、最後に狭い領域が残り、それが大きく認識論と存在論に大別され、現在もこの分類が生きている。認識論ではヒトの外の世界を諸々の感覚を通じていかに認識していくかが問題視される。認識という行為は、人間のあらゆる日常的、あるいは知的活動の根源にあり、認識の成立根拠と普遍妥当性を論ずることが存在論である。しかし、哲学における方法論は思弁に尽きるため、仮説を立て実験によって検証するという科学的方法論は長年取り入れられることはなかった。哲学論は基本的に仮設の羅列に過ぎず、単に主観的な主張であった。客観性の保証が全くない内観法が哲学者の主たる武器であった。19世紀末ごろ、認識論の一部が哲学の外に出て心理学という学問を成立させるが、初期にはもっぱら内観や内省を方法論とし、思弁哲学と大差はなかったため、のちにアームチェア心理学と呼ばれた。やがて、思弁を排し客観的、科学的方法論をもとに実験心理学が登場し、認識の一部は、心理学に取り込まれていった。錯覚現象などがその研究対象になった。実験心理学では、データの統計的処理では科学的であったが、なぜ錯覚が生まれるかというメカニズムの解明では、仮説を立て実験データとの照合を論じてはいたものの、その仮説自体はやはり思弁に過ぎなかった。それを嫌い人間の主観を排し、実験動物を用いた観察可能な行動のみを研究対象とする一派も存在したが、人間の認識は研究対象から外された。このため、認識論の問題は比較的最近まで客観科学化されずに哲学の領域にとどまり続けた。しかし、脳科学の進歩によって急速に、認識論と存在論の2つの世界は大きく浸食されつつある立花隆『脳を究める』（朝日新聞社 2001年3月1日）。.
新しい！!: アルゴリズム情報理論と認識論 · 続きを見る »
正規数
数学における正規数（せいきすう、normal number）とは、無限小数表示において数字が一様に分布しており、数字の列が現れる頻度に偏りがないという性質を持つ実数である。より正確な定義については「定義」の節を参照のこと。 ''r'' 進法での表示についてこの性質を持つ数を r 進正規数という。単に正規数と述べた場合は、2 以上の任意の整数 r に対して r 進正規数であることを意味する。 一般論として「ほとんど全ての」実数が正規数であることが知られているが、その証明は構成的でないため、正規数であることが判明している具体的な数は非常に限られている。例えば、2の平方根、円周率、ネイピア数はそれぞれ正規数だと信じられているが、その通りか否かは未だ謎である。.
新しい！!: アルゴリズム情報理論と正規数 · 続きを見る »
測度論
測度論（そくどろん、measure theory ）は、数学の実解析における一分野で、測度とそれに関連する概念（完全加法族、可測関数、積分等）を研究する。 ここで測度（そくど、measure ）とは面積、体積、個数といった「大きさ」に関する概念を精緻化・一般化したものである。 よく知られているように積分は面積と関係があるので、積分（厳密にはルベーグ積分）も測度論を基盤にして定式化・研究できる。 また、測度の概念は確率を数学的に定式化する際にも用いられるため（コルモゴロフの公理）、 確率論や統計学においても測度論は重要である。 たとえば「サイコロの目が偶数になる確率 」は目が 1,..., 6 になるという 6 つの事象の集合の中で、2, 4, 6 という 3 つ分の「大きさ」を持っている為、 測度の概念で記述できる。.
新しい！!: アルゴリズム情報理論と測度論 · 続きを見る »
情報理論
情報理論（じょうほうりろん、Information theory）は、情報・通信を数学的に論じる学問である。応用数学の中でもデータの定量化に関する分野であり、可能な限り多くのデータを媒体に格納したり通信路で送ったりすることを目的としている。情報エントロピーとして知られるデータの尺度は、データの格納や通信に必要とされる平均ビット数で表現される。例えば、日々の天気が3ビットのエントロピーで表されるなら、十分な日数の観測を経て、日々の天気を表現するには「平均で」約3ビット/日（各ビットの値は 0 か 1）と言うことができる。 情報理論の基本的な応用としては、ZIP形式（可逆圧縮）、MP3（非可逆圧縮）、DSL（伝送路符号化）などがある。この分野は、数学、統計学、計算機科学、物理学、神経科学、電子工学などの交差する学際領域でもある。その影響は、ボイジャー計画の深宇宙探査の成功、CDの発明、携帯電話の実現、インターネットの開発、言語学や人間の知覚の研究、ブラックホールの理解など様々な事象に及んでいる。.
新しい！!: アルゴリズム情報理論と情報理論 · 続きを見る »
情報科学
情報科学という語は日本語では多義的に用いられている。.
新しい！!: アルゴリズム情報理論と情報科学 · 続きを見る »
文字列
文字列（もじれつ）は、単語や文章のような、文字の連なったもの。ストリング (string)、テキスト (text) という場合もある。コンピュータ、特にプログラミングの分野で用いることが多い。.
新しい！!: アルゴリズム情報理論と文字列 · 続きを見る »
擬似乱数
擬似乱数（ぎじらんすう、pseudorandom numbers）は、乱数列のように見えるが、実際には確定的な計算によって求めている擬似乱数列による乱数。擬似乱数列を生成する機器を擬似乱数列生成器、生成アルゴリズムを擬似乱数列生成法と呼ぶ。 真の乱数列は本来、規則性も再現性もないものであるため、本来は確定的な計算によって求めることはできない（例：サイコロを振る時、今までに出た目から次に出る目を予測するのは不可能）。一方、擬似乱数列は確定的な計算によって作るので、その数列は確定的であるうえ、生成法と内部状態が既知であれば、予測可能でもある。 ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを検定と言い、各種の方法が提案されている。 しかし、特に暗号に使用する擬似乱数列については注意が必要であり、シミュレーション等には十分な擬似乱数列生成法であっても、暗号にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については暗号論的擬似乱数の節および暗号論的擬似乱数生成器の記事を参照。.
新しい！!: アルゴリズム情報理論と擬似乱数 · 続きを見る »
整数
数学における整数（せいすう、integer, whole number, Ganze Zahl, nombre entier, número entero）は、0 とそれに 1 ずつ加えていって得られる自然数 (1, 2, 3, 4, …) および 1 ずつ引いていって得られる数 (−1, −2, −3, −4, …) の総称である。 整数は数直線上の格子点として視覚化される 整数の全体からなる集合は普通、太字の Z または黒板太字の \mathbb Z で表す。これはドイツ語 Zahlen（「数」の意・複数形）に由来する。 抽象代数学、特に代数的整数論では、しばしば「代数体の整数環」の元という意味で代数的整数あるいは「整数」という言葉を用いる。有理数全体の成す体はそれ自身が代数体の最も簡単な例であり、有理数体の代数体としての整数環すなわち、「有理数の中で整なもの」の全体の成す環は、本項でいう意味での整数全体の成す環である。一般の「整数」との区別のためにここでいう意味の整数を有理整数 (rational integer) と呼ぶことがある接頭辞「有理（的）」(rational) はそもそも「整数比」であるという意味なので、この呼称は自己循環的にもみえる。しかし、有理整数と呼ぶ場合の「有理」は「有理数の中で」という程度の意味の単なる符牒であって、「整数比」という本来の意味合いに拘るのは徒労である。。.
新しい！!: アルゴリズム情報理論と整数 · 続きを見る »
