ブラウザよりも高速アクセス！
36 関係: 停止性問題、可算集合、可逆圧縮、乱数列、平方剰余の相互法則、形式体系、チャイティンの定数、チューリングマシン、チューリング次数、レイ・ソロモノフ、プログラム (コンピュータ)、ビット、フェルマーの小定理、フェルマーの最終定理、ベリーのパラドックス、アルゴリズム、アルゴリズム的ランダムな無限列、アルゴリズム情報理論、アンドレイ・コルモゴロフ、エミュレータ、カオス理論、グレゴリー・チャイティン、ゲーデルの不完全性定理、ゲーデル数、円周率、C言語、非可算集合、複雑性、計算可能関数、計算理論、計算機科学、超越数、Perl、標準ストリーム、濃度 (数学)、擬似乱数。
停止性問題
計算可能性理論において停止(性)問題（ていしせいもんだい・ていしもんだい、halting problem）は、あるチューリング機械（≒コンピュータプログラム・アルゴリズム）が、そのテープのある初期状態（≒入力）に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。.
新しい！!: コルモゴロフ複雑性と停止性問題 · 続きを見る »
可算集合
可算集合（かさんしゅうごう、countable set 又は denumerable set）もしくは可付番集合とは、おおまかには、自然数全体と同じ程度多くの元を持つ集合のことである。各々の元に 1, 2, 3, … と番号を付けることのできる、すなわち元を全て数え上げることのできる無限集合と表現してもよい。 有限集合も、数え上げることができる集合という意味で、可算集合の一種とみなすことがある。そのため、はっきりと区別を付ける必要がある場合には、冒頭の意味での集合を可算無限集合と呼び、可算無限集合と有限集合を合わせて高々可算の集合と呼ぶ。可算でない無限集合を非可算集合という。非可算集合は可算集合よりも「多く」の元を持ち、全ての元に番号を付けることができない。そのような集合の存在は、カントールによって初めて示された。.
新しい！!: コルモゴロフ複雑性と可算集合 · 続きを見る »
可逆圧縮
可逆圧縮（かぎゃくあっしゅく）とは、圧縮前のデータと、圧縮・展開の処理を経たデータが完全に等しくなるデータ圧縮方法のこと。ロスレス圧縮とも呼ばれる。 アルゴリズムとしてはランレングス、ハフマン符号、LZWなどが有名。 コンピュータ上でよく扱われるLZH、ZIP、CABや、画像圧縮形式のPNG、GIF、動画圧縮形式のHuffyuv、音声圧縮形式のWindows Media Audio Lossless、Apple Lossless、ATRAC Advanced Lossless(AAL)、FLAC、TAK、TTA、Dolby TrueHD、DTS-HDマスターオーディオ、Meridian Lossless Packing、Monkey's Audio、Shorten、mp3HD、WavPack などが可逆圧縮である。.
新しい！!: コルモゴロフ複雑性と可逆圧縮 · 続きを見る »
乱数列
乱数列（らんすうれつ）とはランダムな数列のこと。 数学的に述べれば、今得られている数列 x1, x2,..., xn から次の数列の値 xn+1 が予測できない数列。乱数列の各要素を乱数という。.
新しい！!: コルモゴロフ複雑性と乱数列 · 続きを見る »
平方剰余の相互法則
整数論』（1801年）で平方剰余の相互法則の最初の証明を公開した。 （へいほうじょうよ、quadratic residue）とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則（へいほうじょうよのそうごほうそく、quadratic reciprocity）は、ある整数 が別の整数 の平方剰余であるか否かを判定する法則である。.
新しい！!: コルモゴロフ複雑性と平方剰余の相互法則 · 続きを見る »
形式体系
形式体系（けいしきたいけい、Formal System）は、数学のモデルに基づいた任意の well-defined な抽象思考体系と定義される。エウクレイデスの『原論』は史上初の形式体系とされることが多く、形式体系の特徴をよく表している。その論理的基盤による体系の命題と帰結の関係（論理包含）は、他の抽象モデルを何らかの基盤とする体系から形式体系を区別するものである。形式体系は大きな理論や分野（例えばユークリッド幾何学）の基盤またはそのものとなることが多く、現代数学では証明論やモデル理論などと同義に扱われる。ただし形式体系は必ずしも数学的である必然性はなく、例えばスピノザの『エチカ』はエウクレイデスの『原論』の形式を模倣した哲学（倫理学）書である。 形式体系には形式言語があり、その形式言語は基本的な記号（シンボル）で構成される。形式言語の文（式）は公理群を出発点として、所定の構成規則（推論規則）に従って発展する。従って形式体系は基本的な記号群の有限の組み合わせを通して構築された任意個の数式で構成され、その組み合わせは公理群と構成規則群から作り出される。 数学における形式体系は以下の要素から構成される.
新しい！!: コルモゴロフ複雑性と形式体系 · 続きを見る »
チャイティンの定数
チャイティンの定数（チャイティンのていすう、Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、非形式的に言えば無作為に選択されたプログラムが停止する確率を表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（ていしかくりつ、Halting probability）とも。 停止確率は無限に多数存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムを符号化する方式に依存するので、符号化方式を特定せずに議論する場合は Chaitin's construction と呼ぶことがある。 個々の停止確率は正規かつ超越的な実数であり、計算不可能である。つまりその各桁を列挙するアルゴリズムは存在しない。.
新しい！!: コルモゴロフ複雑性とチャイティンの定数 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: コルモゴロフ複雑性とチューリングマシン · 続きを見る »
チューリング次数
チューリング次数（～じすう、Turing degree, degree of unsolvability）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。 任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 X のチューリング次数が集合 Y のチューリング次数よりも小さいならば、ある数が Y に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が X に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。 チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。.
新しい！!: コルモゴロフ複雑性とチューリング次数 · 続きを見る »
レイ・ソロモノフ
レイ・ソロモノフ（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 は、オッカムの剃刀と多説明原理の組合せを数学的に定式化したものである。それは与えられた観察結果を説明するそれぞれの仮説（アルゴリズム、プログラム）に確率値を割り当てる機械に依存しない手法であり、最も単純な仮説が最も高い確率を割り当てられ、仮説が複雑になるほど割り当てる確率が低くなる。 他にも帰納推論の一般理論でも知られているが、確率的手法を用いて難しい問題を機械で解くという人工知能研究の過程で他にも様々な発見をしている。.
新しい！!: コルモゴロフ複雑性とレイ・ソロモノフ · 続きを見る »
プログラム (コンピュータ)
ンピュータプログラム（英：computer programs）とは、コンピュータに対する命令（処理）を記述したものである。コンピュータが機能を実現するためには、CPUで実行するプログラムの命令が必要である。 コンピュータが、高度な処理を人間の手によらず遂行できているように見える場合でも、コンピュータは設計者の意図であるプログラムに従い、忠実に処理を行っている。実際には、外部からの割り込み、ノイズなどにより、設計者の意図しない動作をすることがある。また設計者が、外部からの割り込みの種類を網羅的に確認していない場合もある。.
新しい！!: コルモゴロフ複雑性とプログラム (コンピュータ) · 続きを見る »
ビット
ビット (bit, b) は、ほとんどのデジタルコンピュータが扱うデータの最小単位。英語の binary digit （2進数字）の略であり、2進数の1けたのこと。量子情報科学においては古典ビットと呼ばれる。 1ビットを用いて2通りの状態を表現できる（二元符号）。これらの2状態は一般に"0"、"1"と表記される。 情報理論における選択情報およびエントロピーの単位も「ビット」と呼んでいるが、これらの単位は「シャノン」とも呼ばれる（詳細は情報量を参照）。 省略記法として、バイトの略記である大文字の B と区別するために、小文字の b と表記する。.
新しい！!: コルモゴロフ複雑性とビット · 続きを見る »
フェルマーの小定理
数論において、フェルマーの小定理（フェルマーのしょうていり、Fermat's little theorem）は素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。.
新しい！!: コルモゴロフ複雑性とフェルマーの小定理 · 続きを見る »
フェルマーの最終定理
算術』。 フェルマーの最終定理（フェルマーのさいしゅうていり、Fermat's Last Theorem）とは、 以上の自然数 について、 となる自然数の組 は存在しない、という定理のことである。フェルマーの大定理とも呼ばれる。フェルマーが驚くべき証明を得たと書き残したと伝えられ、長らく証明も反証もなされなかったことからフェルマー予想とも称されたが、360年後にアンドリュー・ワイルズによって完全に証明され、ワイルズの定理あるいはフェルマー・ワイルズの定理とも呼ばれるようになった。.
新しい！!: コルモゴロフ複雑性とフェルマーの最終定理 · 続きを見る »
ベリーのパラドックス
ベリーのパラドックス（ベリーの逆説）はパラドックスのひとつ。 「19文字以内で記述できない最小の自然数」という文を考える。自然数は可算無限に存在する一方で、日本語19文字で行える記述は有限通り（文字の種類の19乗）であるから、日本語19文字で表現できない自然数は必ず存在する。つまり、「19文字以内で記述できない最小の自然数」という文章は明確にある自然数を一意に定義している。しかしながら、実際に「19文字以内で記述できない最小の自然数」を求めてみると、「19文字以内で記述できない最小の自然数」であるにも関わらず、「19文字以内で記述できない最小の自然数」という19文字で表現が可能であり、「19文字以内で記述できない最小の自然数」という定義に合致しない。 ZFCなどの公理系は、上記のような非形式的な定義の方法を許可しないことでこのパラドックスを回避している。 「自然言語による数の定義」から生まれるパラドックスは他にリシャールのパラドックスが存在し、混同・同一視されることもある吉永良正『ゲーデル・不完全性定理―"理性の限界"の発見』 講談社ブルーバックス ISBN 4061329472など。矛盾を導くために実数を構成する必要がないぶんベリーのパラドックスの方が平易である。.
新しい！!: コルモゴロフ複雑性とベリーのパラドックス · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: コルモゴロフ複雑性とアルゴリズム · 続きを見る »
アルゴリズム的ランダムな無限列
アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、Algorithmically random sequence）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。.
新しい！!: コルモゴロフ複雑性とアルゴリズム的ランダムな無限列 · 続きを見る »
アルゴリズム情報理論
アルゴリズム情報理論（あるごりずむじょうほうりろん、Algorithmic information theory）は、情報理論と計算機科学の一分野であり、計算理論や情報科学とも関連がある。グレゴリー・チャイティンによれば、「シャノンの情報理論とチューリングの計算複雑性理論をシェイカーに入れて、力いっぱいシェイクしてできたもの」である。.
新しい！!: コルモゴロフ複雑性とアルゴリズム情報理論 · 続きを見る »
アンドレイ・コルモゴロフ
アンドレイ・ニコラエヴィッチ・コルモゴロフ（Андре́й Никола́евич Колмого́ров, Andrey Nikolaevich Kolmogorov, 1903年4月25日 - 1987年10月20日）はロシアの数学者であり、確率論および位相幾何学の大きな発展に寄与した。彼以前の確率論はラプラスによる「確率の解析的理論」に基づく古典的確率論が中心であったが、彼が「測度論に基づく確率論」「確率論の基礎概念（1933年）」で公理主義的確率論を立脚させ、現代確率論の始まりとなった。 初期には直観論理やフーリエ級数に関する研究を行っており、乱流や古典力学に関する研究成果もある。また彼はアルゴリズム情報理論の創始者でもある。なお、イズライル・ゲルファント、ウラジーミル・アーノルドをはじめ、コルモゴロフには数多くの弟子がいる。.
新しい！!: コルモゴロフ複雑性とアンドレイ・コルモゴロフ · 続きを見る »
エミュレータ
ミュレータ（Emulator）とは、コンピュータや機械の模倣装置あるいは模倣ソフトウェアのことである。.
新しい！!: コルモゴロフ複雑性とエミュレータ · 続きを見る »
カオス理論
論（カオスりろん、、、）は、力学系の一部に見られる、数的誤差により予測できないとされている複雑な様子を示す現象を扱う理論である。カオス力学ともいう。 ここで言う予測できないとは、決してランダムということではない。その振る舞いは決定論的法則に従うものの、積分法による解が得られないため、その未来（および過去）の振る舞いを知るには数値解析を用いざるを得ない。しかし、初期値鋭敏性ゆえに、ある時点における無限の精度の情報が必要であるうえ、（コンピューターでは無限桁を扱えないため必然的に発生する）数値解析の過程での誤差によっても、得られる値と真の値とのずれが増幅される。そのため予測が事実上不可能という意味である。.
新しい！!: コルモゴロフ複雑性とカオス理論 · 続きを見る »
グレゴリー・チャイティン
レゴリー・チャイティン（Gregory "Greg" J. Chaitin, 1947年 - ）は、アルゼンチン出身、アメリカ在住の数学者、コンピュータ科学者。 60年代に情報理論の分野に、ゲーデルの不完全性定理とよく似た現象を見いだす。つまり、その分野上での決定不可能な命題を発見し別種の不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能などのような理論においても、いかなる数であろうともcよりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 c が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。 1995年に、メイン大学から博士号を授与される。IBMのトーマス・J・ワトソン研究所に勤務した後、現在はリオデジャネイロ連邦大学に在籍。 幾つかの本を執筆しており、日本語に訳されている。.
新しい！!: コルモゴロフ複雑性とグレゴリー・チャイティン · 続きを見る »
ゲーデルの不完全性定理
ーデルの不完全性定理（ゲーデルのふかんぜんせいていり、）又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明したものである。;第1不完全性定理: 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。;第2不完全性定理: 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。.
新しい！!: コルモゴロフ複雑性とゲーデルの不完全性定理 · 続きを見る »
ゲーデル数
ーデル数（ゲーデルすう、Gödel number）は、数理論理学において何らかの形式言語のそれぞれの記号や整論理式に一意に割り振られる自然数である。クルト・ゲーデルが不完全性定理の証明に用いたことから、このように呼ばれている。また、ゲーデル数を割り振ることをゲーデル数化（Gödel numbering）と呼ぶ。 ゲーデル数のアイデアを暗に使っている例としては、コンピュータにおけるエンコードが挙げられる。 コンピュータでは何でも0と1で表し、「apple」のような文字列も0と1による数字で表す。 ゲーデル数化とは、このように文字列に数字を対応させる事を指す。 ゲーデル数化は、数式におけるシンボルに数を割り当てる符号化の一種でもあり、それによって生成された自然数の列が文字列を表現する。この自然数の列をさらに1つの自然数で表現することもでき、自然数についての形式的算術理論を適用可能となる。 ゲーデルの論文が発表された1931年以来、ゲーデル数はより広範囲な様々な数学的オブジェクトに自然数を割り振るのに使われるようになっていった。.
新しい！!: コルモゴロフ複雑性とゲーデル数 · 続きを見る »
円周率
円周率（えんしゅうりつ）は、円の周長の直径に対する比率として定義される数学定数である。通常、ギリシア文字 （パイ、ピー、ラテン文字表記: ）で表される。数学をはじめ、物理学、工学といった様々な科学分野に出現し、最も重要な数学定数とも言われる。 円周率は無理数であり、その小数展開は循環しない。円周率は、無理数であるのみならず、超越数でもある。 円周率の計算において功績のあったルドルフ・ファン・コーレンに因み、ルドルフ数とも呼ばれる。ルドルフは、小数点以下35桁までを計算した。小数点以下35桁までの値は次の通りである。.
新しい！!: コルモゴロフ複雑性と円周率 · 続きを見る »
C言語
C言語（シーげんご）は、1972年にAT&Tベル研究所のデニス・リッチーが主体となって開発したプログラミング言語である。英語圏では単に C と呼んでおり、日本でも文書や文脈によっては同様に C と呼ぶことがある。.
新しい！!: コルモゴロフ複雑性とC言語 · 続きを見る »
非可算集合
数学において、非可算集合（ひかさんしゅうごう）、あるいは非可算無限集合とは可算集合でない無限集合のことである。集合の非可算性は基数、濃度という概念と密接に関係している。集合は、その濃度が自然数全体の集合の濃度より大きいときに、非可算である。.
新しい！!: コルモゴロフ複雑性と非可算集合 · 続きを見る »
複雑性
複雑性（ふくざつせい、complexity）という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという。.
新しい！!: コルモゴロフ複雑性と複雑性 · 続きを見る »
計算可能関数
計算可能関数（けいさんかのうかんすう、Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。.
新しい！!: コルモゴロフ複雑性と計算可能関数 · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
新しい！!: コルモゴロフ複雑性と計算理論 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: コルモゴロフ複雑性と計算機科学 · 続きを見る »
超越数
超越数（ちょうえつすう、transcendental number）とは、代数的数でない数、すなわちどんな有理係数の代数方程式 のにもならないような複素数のことである。有理数は一次方程式の解であるから、超越的な実数はすべて無理数になるが、無理数 2 は の解であるから、逆は成り立たない。超越数論は、超越数について研究する数学の分野で、与えられた数の超越性の判定などが主な問題である。 よく知られた超越数にネイピア数（自然対数の底）や円周率がある。ただし超越性が示されている実数のクラスはほんの僅かであり、与えられた数が超越数であるかどうかを調べるのは難しい問題だとされている。例えば、ネイピア数と円周率はともに超越数であるにもかかわらず、それをただ足しただけの すら超越数かどうか分かっていない。 代数学の標準的な記号 \mathbb で有理数係数多項式全体を表し、代数的数全体の集合を、代数的数 algebraic number の頭文字を使って と書けば、超越数全体の集合は となる。 なお、本稿では を自然対数とする。.
新しい！!: コルモゴロフ複雑性と超越数 · 続きを見る »
Perl
Perl（パール）とは、ラリー・ウォールによって開発されたプログラミング言語である。実用性と多様性を重視しており、C言語やsed、awk、シェルスクリプトなど他のプログラミング言語の優れた機能を取り入れている。ウェブ・アプリケーション、システム管理、テキスト処理などのプログラムを書くのに広く用いられている。 言語処理系としてのperlはフリーソフトウェアである。Artistic LicenseおよびGPLのもとで配布されており、誰でもどちらかのライセンスを選択して利用することができる。UNIXやWindowsなど多くのプラットフォーム上で動作する。.
新しい！!: コルモゴロフ複雑性とPerl · 続きを見る »
標準ストリーム
標準ストリーム（入力、出力、エラー出力） 標準ストリーム（standard streams）とは、UNIXやUnix系オペレーティングシステム (OS) において、プログラムの活動実体であるプロセスとその実行環境（通常は端末）の間の接続として、（プロセスから見ると）あらかじめ確立されている入出力チャネル（パイプ (コンピュータ)）である。OSのカーネルではなくシェルで実装されている機能だが、広く使われているため標準化されている。UNIXやUnix系OSでは3つの入出力があり、標準入力（standard input）、標準出力（standard output）、標準エラー出力（standard error）である。 一部のプログラミング言語の実装では、UNIXやUnix系以外のシステムでもUnixと同様の使い勝手を提供するよう、これらを模擬するものがある。MS-DOSにはさらに、シリアルポートに対応する標準補助入出力 (stdaux)、プリンターに対応する標準プリンター出力 (stdprn) もあり、今でもWindowsでAUXやPRNという名前をファイルやコマンド等に使おうとすると問題を起こしたりするのは、これらに関してMS-DOSとの互換性を残しているためである。.
新しい！!: コルモゴロフ複雑性と標準ストリーム · 続きを見る »
濃度 (数学)
数学、とくに集合論において、濃度（のうど）あるいは基数（きすう）（cardinal number, cardinality, power）とは、集合の「元の個数」という概念を拡張したものである。有限集合については、濃度は「元の個数」の同意語に過ぎない。。。.
新しい！!: コルモゴロフ複雑性と濃度 (数学) · 続きを見る »
擬似乱数
擬似乱数（ぎじらんすう、pseudorandom numbers）は、乱数列のように見えるが、実際には確定的な計算によって求めている擬似乱数列による乱数。擬似乱数列を生成する機器を擬似乱数列生成器、生成アルゴリズムを擬似乱数列生成法と呼ぶ。 真の乱数列は本来、規則性も再現性もないものであるため、本来は確定的な計算によって求めることはできない（例：サイコロを振る時、今までに出た目から次に出る目を予測するのは不可能）。一方、擬似乱数列は確定的な計算によって作るので、その数列は確定的であるうえ、生成法と内部状態が既知であれば、予測可能でもある。 ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを検定と言い、各種の方法が提案されている。 しかし、特に暗号に使用する擬似乱数列については注意が必要であり、シミュレーション等には十分な擬似乱数列生成法であっても、暗号にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については暗号論的擬似乱数の節および暗号論的擬似乱数生成器の記事を参照。.
新しい！!: コルモゴロフ複雑性と擬似乱数 · 続きを見る »
