ブラウザよりも高速アクセス！
72 関係: Association for Computing Machinery、型理論、多項式時間、学問、並列計算、二進法、形式体系、形式的検証、形式科学、形式意味論、圏論、チューリングマシン、ユークリッドの互除法、ラムダ計算、ヘッブの法則、ブール代数、ブール論理、プログラミング言語、プログラム (コンピュータ)、プログラム意味論、ピーター・ショア、データベース、データ構造、ドナルド・ヘッブ、ニューラルネットワーク、分散コンピューティング、アラン・チューリング、アルゴリズム、アルゴリズム解析、アロンゾ・チャーチ、オートマトン、クルト・ゲーデル、クロード・シャノン、グラフ理論、ゲーデルの不完全性定理、コネクショニズム、コンピューティング、コンピュータ、コンピュータネットワーク、ゴットフリート・ライプニッツ、ジョージ・ブール、スティーヴン・コール・クリーネ、サブルーチン、公理、公開鍵暗号、符号理論、複雑性、計算可能性理論、計算幾何学、計算モデル、...、計算理論、計算生物学、計算複雑性理論、計算機、計算機科学、計算機科学の未解決問題、論理学、量子力学、量子コンピュータ、英語、通信の数学的理論、MITコンピュータ科学・人工知能研究所、暗号理論、機械学習、波動関数、最大公約数、情報理論、情報検索、数学、数理モデル、数理論理学、数論。 インデックスを展開 (22 もっと) »
Association for Computing Machinery
Association for Computing Machinery (ACM) は、ニューヨークに本部のあるコンピュータ科学分野の国際学会。1947年設立。IEEEとともに、この分野で最も影響力の強い学会であり、IEEEがその名と由来や歴史からエレクトロニクスや通信分野の工学に強いのに対し、数学的な理論計算機科学のような分野もカバーする。日本語に訳して「計算機械学会」とされることもあるが、こんにちこの訳語が用いられることはほとんどなく、通常は単に"ACM"という略称で呼ばれるのがもっぱらである。ACMの「A」は Association (学会、団体) の頭文字であるが、アメリカ数学会 (AMS) と混同して「米国計算機学会」と誤訳されることがある。 数多くの国際会議を開催しており、人目を惹くデモ映像のSIGGRAPHやSIGMODなどはよく知られている。他の多くの学会と同様にすぐれた業績などへの表彰もおこなっているが、チューリング賞は、特にこの分野の最高の賞とみなされており、物理や化学といった分野におけるノーベル賞に匹敵するものと扱われることもある（他の賞についても時折「～のノーベル賞」といったような表現が使われることがあるが、この分野の全てを対象とした世界トップクラスの賞という位置づけにあるのはチューリング賞をおいて他にない）。.
新しい！!: 理論計算機科学とAssociation for Computing Machinery · 続きを見る »
型理論
型理論（かたりろん、Type theory）は、数理論理学の一分野であり、「型」の階層を構築し、それぞれの型に数学的（あるいはそれ以外の）実体を割り当てるものである。階型理論（かいけいりろん、Theory of Types）とも。ある型のオブジェクトはその前提となる型のオブジェクトから構築される。この場合の「型」とは形而上的な意味での「型」である。バートランド・ラッセルは、彼が発見したラッセルのパラドックスにより素朴集合論の問題が明らかにされたことを受けて、型理論を構築した。型理論の詳細はホワイトヘッドとラッセルの 『プリンキピア・マテマティカ』にある。 型理論は、プログラミング言語の理論における型システムのベースにもなっている。「型システム」と「型理論」の語はほぼ同義として扱われることもあるが、ここでは、この記事では数理論理学の範囲を説明し、プログラミング言語の理論については型システムの記事で説明する。.
新しい！!: 理論計算機科学と型理論 · 続きを見る »
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: 理論計算機科学と多項式時間 · 続きを見る »
学問
学問（がくもん）とは、一定の理論に基づいて体系化された知識と方法であり、哲学や歴史学、心理学や言語学などの人文科学、政治学や法律学などの社会科学、物理学や化学などの自然科学などの総称。英語ではscience(s)であり、science(s)は普通、科学と訳す。なお、学問の専門家を一般に「学者」と呼ぶ。研究者、科学者と呼ばれる場合もある。.
新しい！!: 理論計算機科学と学問 · 続きを見る »
並列計算
並列計算（へいれつけいさん、parallel computing）は、コンピュータにおいて複数のプロセッサで1つのタスクを動作させること。並列コンピューティングや並列処理とも呼ばれる。問題を解く過程はより小さなタスクに分割できることが多い、という事実を利用して処理効率の向上を図る手法である。また、このために設計されたコンピュータを並列コンピュータという。ディープ・ブルーなどが有名。 関連する概念に並行計算（へいこうけいさん）があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。 特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。.
新しい！!: 理論計算機科学と並列計算 · 続きを見る »
二進法
二進法（にしんほう）とは、2 を底（てい、基（base）とも）とし、底の冪の和で数を表現する方法である。 英語でバイナリ (binary) という。binaryという語には「二進法」の他に「二個一組」「二個単位」といったような語義もある（例: バイナリ空間分割）。.
新しい！!: 理論計算機科学と二進法 · 続きを見る »
形式体系
形式体系（けいしきたいけい、Formal System）は、数学のモデルに基づいた任意の well-defined な抽象思考体系と定義される。エウクレイデスの『原論』は史上初の形式体系とされることが多く、形式体系の特徴をよく表している。その論理的基盤による体系の命題と帰結の関係（論理包含）は、他の抽象モデルを何らかの基盤とする体系から形式体系を区別するものである。形式体系は大きな理論や分野（例えばユークリッド幾何学）の基盤またはそのものとなることが多く、現代数学では証明論やモデル理論などと同義に扱われる。ただし形式体系は必ずしも数学的である必然性はなく、例えばスピノザの『エチカ』はエウクレイデスの『原論』の形式を模倣した哲学（倫理学）書である。 形式体系には形式言語があり、その形式言語は基本的な記号（シンボル）で構成される。形式言語の文（式）は公理群を出発点として、所定の構成規則（推論規則）に従って発展する。従って形式体系は基本的な記号群の有限の組み合わせを通して構築された任意個の数式で構成され、その組み合わせは公理群と構成規則群から作り出される。 数学における形式体系は以下の要素から構成される.
新しい！!: 理論計算機科学と形式体系 · 続きを見る »
形式的検証
形式的検証（けいしきてきけんしょう）とは、ハードウェアおよびソフトウェアのシステムにおいて形式手法や数学を利用し、何らかの形式仕様記述やプロパティに照らしてシステムが正しいことを証明したり、逆に正しくないことを証明することである。.
新しい！!: 理論計算機科学と形式的検証 · 続きを見る »
形式科学
形式科学（けいしきかがく、formal science）とは形式体系に関係する科学の総称である。論理学、数学、システム理論に加え、計算機科学、情報理論、ミクロ経済学、統計学、言語学などといった分野の理論ベースの細分野（たとえば計算機科学であれば理論計算機科学）がこれに含まれる。 形式科学で扱うのは記号システムによって記述される抽象的構造であり、結果は公理や理論上のアイデアから推論（純粋な思考の過程）のみによって導き出される。これは、自然科学が現実世界を扱い、観測・観察から得られた知識をもとに結果を導き出すのと対照的である。しかし、形式科学で扱う体系は現実世界のものをモチーフしたものが多い。また、形式科学の結果は自然科学において現実世界を簡潔に理解するための構造（モデル）をつくるのに応用されることが多い。 形式科学で扱う体系は純粋に理論的なものであるので、現実世界そのものではない。しかし、時として「理論的なモデルは現実世界を完全に描写することができる」とか、理論が「現実そのものである」などと信じられてしまうことがある。.
新しい！!: 理論計算機科学と形式科学 · 続きを見る »
形式意味論
形式意味論(formal semantics)とは、自然言語や、コンピュータプログラミング言語の意味論（プログラム意味論）において、その「意味」、たとえば自然言語であれば「全ての犬は黒い」「ある犬は黒い」「全ての犬は黒くない」「ある犬は黒くない」の各文にはそれぞれ対称的な意味があるわけだが、それを形式的（formal）にあらわさんとする、あるいはプログラミング言語においては、それで書かれたプログラムをコンピュータに実行させた結果どのようにコンピュータが動作するのか（「効果」などとも言う）を、形式的にあらわさんとしたものである。この記事では主として自然言語およびそれに近い分野のものについて述べる。プログラミング言語の意味論に関してはプログラム意味論の記事を参照のこと。 自然言語においては、自然言語を一種の形式的体系と捉え、文の意味はその構成要素から一定の手順に従って構成的に決定されると考える立場である。集合、論理記号など数学で用いる概念を理論に応用して自然言語の文の真理条件の規定や、前提・含意・矛盾などの論理的関係を記述することを目標とする。論理学者モンタギューの研究に端を発し、現在では多様な理論的枠組みが提案されている。自然言語処理にも応用されている。 形式意味論は、言語と外界との直接の結びつきを仮定し、実際に言語を用いる人間の認知活動を捨象しているため、主に認知意味論の研究者からの強い批判もある。ただし、批判の中には形式意味論の研究者によっても既に自覚されて、理論の改良が試みられているものもある。.
新しい！!: 理論計算機科学と形式意味論 · 続きを見る »
圏論
圏論（けんろん、category theory）は、数学的構造とその間の関係を抽象的に扱う数学理論の 1 つである。 考えている種類の「構造」を持った対象とその構造を反映するような対象間の射の集まりからなる圏が基本的な考察の対象になる。 数学の多くの分野、また計算機科学や数理物理学のいくつかの分野で導入される一連の対象は、しばしば適当な圏の対象たちだと考えることができる。圏論的な定式化によって同種のほかの対象たちとの、内部の構造に言及しないような形式的な関係性や、別の種類の数学的な対象への関連づけなどが統一的に記述される。.
新しい！!: 理論計算機科学と圏論 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: 理論計算機科学とチューリングマシン · 続きを見る »
ユークリッドの互除法
ユークリッドの互除法（ユークリッドのごじょほう、）は、2 つの自然数の最大公約数を求める手法の一つである。 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。.
新しい！!: 理論計算機科学とユークリッドの互除法 · 続きを見る »
ラムダ計算
ラムダ計算（ラムダけいさん、lambda calculus）は、計算模型のひとつで、計算の実行を関数への引数の評価（evaluation）と適用（application）としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。関数を表現する式に文字ラムダ (λ) を使うという慣習からその名がある。アロンゾ・チャーチとスティーヴン・コール・クリーネによって1930年代に考案された。1936年にチャーチはラムダ計算を用いて一階述語論理の決定可能性問題を（否定的に）解いた。ラムダ計算は「計算可能な関数」とはなにかを定義するために用いられることもある。計算の意味論や型理論など、計算機科学のいろいろなところで使われており、特にLISP、ML、Haskellといった関数型プログラミング言語の理論的基盤として、その誕生に大きな役割を果たした。 ラムダ計算は1つの変換規則（変数置換）と1つの関数定義規則のみを持つ、最小の（ユニバーサルな）プログラミング言語であるということもできる。ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。これは、ラムダ計算がチューリングマシンと等価な数理モデルであることを意味している。チューリングマシンがハードウェア的なモデル化であるのに対し、ラムダ計算はよりソフトウェア的なアプローチをとっている。 この記事ではチャーチが提唱した元来のいわゆる「型無しラムダ計算」について述べている。その後これを元にして「型付きラムダ計算」という体系も提唱されている。.
新しい！!: 理論計算機科学とラムダ計算 · 続きを見る »
ヘッブの法則
ヘッブの法則（ヘッブのほうそく）は、脳のシナプス可塑性についての法則である。ヘッブ則、ヘブ則とも呼ばれる。心理学者のドナルド・ヘッブによって提唱された。ニューロン間の接合部であるシナプスにおいて、シナプス前ニューロンの繰り返し発火によってシナプス後ニューロンに発火が起こると、そのシナプスの伝達効率が増強される。また逆に、発火が長期間起こらないと、そのシナプスの伝達効率は減退するというものである。.
新しい！!: 理論計算機科学とヘッブの法則 · 続きを見る »
ブール代数
ブール代数（ブールだいすう、boolean algebra）またはブール束（ブールそく、boolean lattice）とは、ジョージ・ブールが19世紀中頃に考案した代数系の一つである。ブール代数の研究は束の理論が築かれるひとつの契機ともなった。ブール論理の演算はブール代数の一例であり、現実の応用例としては、組み合わせ回路（論理回路#組み合わせ回路）はブール代数の式で表現できる。.
新しい！!: 理論計算機科学とブール代数 · 続きを見る »
ブール論理
ブール論理（ブールろんり、Boolean logic）は、古典論理のひとつで、その名称はブール代数ないしその形式化を示したジョージ・ブールに由来する。 リレーなどによる「スイッチング回路の理論」として1930年代に再発見され（論理回路#歴史を参照）、間もなくコンピュータに不可欠な理論として広まり、こんにちでは一般的に使われている。 本項目では、集合代数を用いて、集合、ブール演算、ベン図、真理値表などの基本的解説とブール論理の応用について解説する。ブール代数の記事ではブール論理の公理を満足する代数的構造の型を説明している。ブール論理はブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。.
新しい！!: 理論計算機科学とブール論理 · 続きを見る »
プログラミング言語
プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.
新しい！!: 理論計算機科学とプログラミング言語 · 続きを見る »
プログラム (コンピュータ)
ンピュータプログラム（英：computer programs）とは、コンピュータに対する命令（処理）を記述したものである。コンピュータが機能を実現するためには、CPUで実行するプログラムの命令が必要である。 コンピュータが、高度な処理を人間の手によらず遂行できているように見える場合でも、コンピュータは設計者の意図であるプログラムに従い、忠実に処理を行っている。実際には、外部からの割り込み、ノイズなどにより、設計者の意図しない動作をすることがある。また設計者が、外部からの割り込みの種類を網羅的に確認していない場合もある。.
新しい！!: 理論計算機科学とプログラム (コンピュータ) · 続きを見る »
プログラム意味論
プログラム意味論（program semantics）とは、計算機科学（特に理論計算機科学と分類されることもある）の一分野で、プログラミング言語の意味と計算モデルに関する分野である。形式的なものは、プログラミング言語の形式意味論とも呼ばれる。標準規格等では形式的でなく意味論を与えているものも多い。.
新しい！!: 理論計算機科学とプログラム意味論 · 続きを見る »
ピーター・ショア
ピーター・ショア（Peter Williston Shor, 1959年8月14日 -）は、アメリカ合衆国の理論計算機科学者、数学者。量子コンピュータの研究で知られ、特に従来不可能であった素因数分解を高速量子アルゴリズム（ショアのアルゴリズム）を用いて解決する方法を提唱した。 ニューヨーク出身。カリフォルニア工科大学卒業後、マサチューセッツ工科大学大学院で応用数学の博士号を取得した。現在はマサチューセッツ工科大学の教授である。 .
新しい！!: 理論計算機科学とピーター・ショア · 続きを見る »
データベース
データベース（database, DB）とは、検索や蓄積が容易にできるよう整理された情報の集まり。 通常はコンピュータによって実現されたものを指すが、紙の住所録などをデータベースと呼ぶ場合もある。コンピュータを使用したデータベース・システムでは、データベース管理用のソフトウェアであるデータベース管理システムを使用する場合も多い。.
新しい！!: 理論計算機科学とデータベース · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
新しい！!: 理論計算機科学とデータ構造 · 続きを見る »
ドナルド・ヘッブ
ドナルド・ヘッブ（Donald Olding Hebb、1904年7月22日 - 1985年8月20日）は、カナダの心理学者。神経心理学の開拓者の一人であり、ニューラルネットワーク研究の先駆者でもある。ヘッブの法則でその名を知られる。 神経生理学をもとに人間の学習を説明しようとした。 カナダのノバスコシア州チェスターに生まれる。医師であった両親のもとで英才教育を受ける。作家を志してダルハウジー大学に入学。さらにマギル大学の大学院に進み修士号を取得した。その後、母校の教員や農場労働者など職を転々とする中で、ウィリアム・ジェームズ、ジークムント・フロイト、ジョン・ワトソンらの著作に触れる。これをきっかけに心理学を志し、マギル大学の心理学教室を訪ねて、読むべき本、学ぶべき事柄について手ほどきを受ける。再び教職に戻り、モントリオールの学校で校長をしながらマギル大学の大学院生となる。1931年、大病を患い、病床でチャールズ・シェリントンやイワン・パブロフの著作に触れる。1933年には事故で妻を亡くし、校長をしていた学校も立ち行かなくなる。1934年、シカゴ大学のカール・ラシュレーの研究室に入り、翌年、ラシュレーの異動に伴いハーバード大学に移る。1936年、ハーバード大学にて博士号取得。フロリダのヤーキーズ霊長類研究所にて知覚や学習についての神経学的研究を行なう。1937年、再婚してモントリオールに戻り、モントリオール神経学研究所のワイルダー・ペンフィールドのもとで頭部損傷やロボトミーによる心理的影響の研究を行なう。1947年、マギル大学心理学教授。.
新しい！!: 理論計算機科学とドナルド・ヘッブ · 続きを見る »
ニューラルネットワーク
ニューラルネットワーク（神経回路網、neural network、略称: NN）は、脳機能に見られるいくつかの特性を計算機上のシミュレーションによって表現することを目指した数学モデルである。研究の源流は生体の脳のモデル化であるが、神経科学の知見の改定などにより次第に脳モデルとは乖離が著しくなり、生物学や神経科学との区別のため、人工ニューラルネットワーク（artificial neural network、ANN）とも呼ばれる。.
新しい！!: 理論計算機科学とニューラルネットワーク · 続きを見る »
分散コンピューティング
分散コンピューティング（ぶんさんコンピューティング、英: Distributed computing）とは、プログラムの個々の部分が同時並行的に複数のコンピュータ上で実行され、各々がネットワークを介して互いに通信を行いながら全体として処理が進行する計算手法のことである。複雑な計算などをネットワークを介して複数のコンピュータを利用して行うことで、一台のコンピュータで計算するよりスループットを上げようとする取り組み、またはそれを実現する為の仕組みである。分散処理（ぶんさんしょり）ともいう。並列コンピューティングの一形態に分類されるが、一般に並列コンピューティングと言えば、同時並行に実行する主体は同じコンピュータシステム内のCPU群である。ただし、どちらもプログラムの分割（同時に実行できる部分にプログラムを分けること）が必須である。分散コンピューティングではさらに、それぞれの部分が異なる環境でも動作できるようにしなければならない。例えば、2台の異なるハードウェアを使ったコンピュータで、それぞれ異なるファイルシステム構成であっても動作するよう配慮する必要がある。 問題を複数の部分問題に分けて各コンピュータに実行させるのが基本であり、素数探索や数多く試してみる以外に解決できない問題の対処として用いられているものが多い。分散コンピューティングの例としてBOINCがある。これは、大きな問題を多数の小さな問題に分割し、多数のコンピュータに分配するフレームワークである。その後、それぞれの結果を集めて大きな解を得る。一般的に処理を分散すると一台のコンピュータで計算する場合と比べ、問題データの分配、収集、集計するためのネットワークの負荷が増加し、問題解決の為のボトルネックとなるため、部分問題間の依存関係を減らすことが重要な課題となる。 分散コンピューティングは、コンピュータ同士をネットワーク接続し、効率的に通信できるよう努力した結果として自然に生まれた。しかし、分散コンピューティングはコンピュータネットワークと同義ではない。単にコンピュータネットワークと言った場合、複数のコンピュータが互いにやり取りするが、単一のプログラムの処理を共有することはない。World Wide Web はコンピュータネットワークの例であるが、分散コンピューティングの例ではない。 分散処理を構築するための様々な技術や標準が存在し、一部はその目的に特化して設計されている。例えば、遠隔手続き呼出し (RPC)、Java Remote Method Invocation (Java RMI)、.NET Remoting などがある。.
新しい！!: 理論計算機科学と分散コンピューティング · 続きを見る »
アラン・チューリング
アラン・マシスン・チューリング（Alan Mathieson Turing、〔テュァリング〕, 1912年6月23日 - 1954年6月7日）はイギリスの数学者、論理学者、暗号解読者、コンピュータ科学者。.
新しい！!: 理論計算機科学とアラン・チューリング · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: 理論計算機科学とアルゴリズム · 続きを見る »
アルゴリズム解析
アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース（時間や記憶領域）量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数（時間複雑性）や記憶領域サイズ（空間複雑性）への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的（asymptotic）な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数（hidden constant）と呼ぶ。 漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。.
新しい！!: 理論計算機科学とアルゴリズム解析 · 続きを見る »
アロンゾ・チャーチ
アロンゾ・チャーチ（Alonzo Church, 1903年6月14日 - 1995年8月11日）はアメリカの論理学者、数学者。ラムダ計算の創案者、「チャーチ＝チューリングのテーゼ」の提唱者として知られる。.
新しい！!: 理論計算機科学とアロンゾ・チャーチ · 続きを見る »
オートマトン
ートマトン (単数形: automaton, 複数形: オートマタ（automata ）) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトンなどの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。.
新しい！!: 理論計算機科学とオートマトン · 続きを見る »
クルト・ゲーデル
ルト・ゲーデル（Kurt Gödel, 1906年4月28日 - 1978年1月14日）は、オーストリア・ハンガリー二重帝国（現チェコ）のブルノ生まれの数学者・論理学者である。業績には、完全性定理及び不完全性定理、連続体仮説に関する研究が知られる。.
新しい！!: 理論計算機科学とクルト・ゲーデル · 続きを見る »
クロード・シャノン
ード・エルウッド・シャノン（Claude Elwood Shannon, 1916年4月30日 - 2001年2月24日）はアメリカ合衆国の電気工学者、数学者。20世紀科学史における、最も影響を与えた科学者の一人である。 情報理論の考案者であり、情報理論の父と呼ばれた。情報、通信、暗号、データ圧縮、符号化など今日の情報社会に必須の分野の先駆的研究を残した。アラン・チューリングやジョン・フォン・ノイマンらとともに今日のコンピュータ技術の基礎を作り上げた人物として、しばしば挙げられる。.
新しい！!: 理論計算機科学とクロード・シャノン · 続きを見る »
グラフ理論
ラフ理論（グラフりろん、graph theory）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。.
新しい！!: 理論計算機科学とグラフ理論 · 続きを見る »
ゲーデルの不完全性定理
ーデルの不完全性定理（ゲーデルのふかんぜんせいていり、）又は単に不完全性定理とは、数学基礎論における重要な定理で、クルト・ゲーデルが1930年に証明したものである。;第1不完全性定理: 自然数論を含む帰納的公理化可能な理論が、ω無矛盾であれば、証明も反証もできない命題が存在する。;第2不完全性定理: 自然数論を含む帰納的公理化可能な理論が、無矛盾であれば、自身の無矛盾性を証明できない。.
新しい！!: 理論計算機科学とゲーデルの不完全性定理 · 続きを見る »
コネクショニズム
ネクショニズム（connectionism）とは、人工知能研究においてニューラルネットワークモデルに基づいた知能体を実現・実装する立場のこと。あるいは認知科学・心理学において、同モデルでのシミュレーションなどの研究手法によって人間の認知や行動をモデル化しようとする立場のことである。コネクショニズムモデルに基づいた研究アプローチを取る研究者をコネクショニスト（connectionist）という。 例えば1980年代のデビッド・ラメルハートとジェームズ・マクレランドによるPDPモデル（並列分散処理）の研究はその代表的なものの１つである。.
新しい！!: 理論計算機科学とコネクショニズム · 続きを見る »
コンピューティング
階差機関。多項式関数の解を計算する機械 とある大学の計算機室 (2003) ウィキメディア財団のサーバ コンピューティング（computing）の古来の意味は「数えること」と「計算すること」であり、算術ないしは数学の計算を指した。現在は転じてコンピュータによる数値計算や、より広くデータ処理(data processing)や情報処理 (information processing) といったコンピュータを使う活動全般も指すことがある。 日本語ではどちらも「計算」と呼んでいるが、対応する英語にはcalculationとcomputationがある。条件分岐などを伴う複雑な計算がcalculationではなくcomputationである。.
新しい！!: 理論計算機科学とコンピューティング · 続きを見る »
コンピュータ
ンピュータ（Computer）とは、自動計算機、とくに計算開始後は人手を介さずに計算終了まで動作する電子式汎用計算機。実際の対象は文字の置き換えなど数値計算に限らず、情報処理やコンピューティングと呼ばれる幅広い分野で応用される。現代ではプログラム内蔵方式のディジタルコンピュータを指す場合が多く、特にパーソナルコンピュータやメインフレーム、スーパーコンピュータなどを含めた汎用的なシステムを指すことが多いが、ディジタルコンピュータは特定の機能を実現するために機械や装置等に組み込まれる組み込みシステムとしても広く用いられる。電卓・機械式計算機・アナログ計算機については各項を参照。.
新しい！!: 理論計算機科学とコンピュータ · 続きを見る »
コンピュータネットワーク
ンピュータネットワーク（computer network）は、複数のコンピュータを接続する技術。または、接続されたシステム全体。コンピュータシステムにおける「通信インフラ」自体、あるいは通信インフラによって実現される接続や通信の総体が（コンピュータ）ネットワークである、とも言える。.
新しい！!: 理論計算機科学とコンピュータネットワーク · 続きを見る »
ゴットフリート・ライプニッツ
ットフリート・ヴィルヘルム・ライプニッツ（Gottfried Wilhelm Leibniz、1646年7月1日（グレゴリオ暦）/6月21日（ユリウス暦） - 1716年11月14日）は、ドイツの哲学者、数学者。ライプツィヒ出身。なお Leibniz の発音は、（ライプニッツ）としているものと、（ライブニッツ）としているものとがある。ルネ・デカルトやバールーフ・デ・スピノザなどとともに近世の大陸合理主義を代表する哲学者である。主著は、『モナドロジー』、『形而上学叙説』、『人間知性新論』など。.
新しい！!: 理論計算機科学とゴットフリート・ライプニッツ · 続きを見る »
ジョージ・ブール
ョージ・ブール（George Boole, 1815年11月2日 - 1864年12月8日）は、イギリスの数学者・哲学者。多くの仕事があるが、こんにちのコンピュータ科学の分野の基礎的な理論のひとつであるブール代数（ブール論理）が現代では広く知られている。.
新しい！!: 理論計算機科学とジョージ・ブール · 続きを見る »
スティーヴン・コール・クリーネ
ティーヴン・コール・クリーネ（Stephen Cole Kleene, 1909年1月5日 - 1994年1月25日）は、アメリカの数学者。ウィスコンシン大学マディソン校に勤め、その業績は計算機科学の理論的な基礎を築くのに貢献した。クリーネは、正規表現の発明や、アロンゾ・チャーチ、クルト・ゲーデル、アラン・チューリング、エミール・ポストらと共に帰納的関数論という数理論理学の一分野を創始したことで知られる。クリーネ代数、クリーネ閉包、クリーネの再帰定理、クリーネ不動点定理の由来になっている。クリーネはまたライツェン・エヒベルトゥス・ヤン・ブラウワーが創始した数学的直観主義に貢献した。 クリーネは自分の姓をクレーニ（（IPA））と発音していた。英語圏ではクリーニ（）、クリーン（）などと誤読されることが多く、日本ではクリーネの表記が一般的になってしまっている。 その数理論理学における傑出した業績は、英語圏の論理学者の間に、"Cleanliness is next to godliness"「清潔さは信心深さに次ぐ」をもじって"Kleeneliness is next to Gödeliness"という格言があることにも表れている。.
新しい！!: 理論計算機科学とスティーヴン・コール・クリーネ · 続きを見る »
サブルーチン
ブルーチン（subroutine）は、コンピュータプログラミングにおいて、プログラム中で意味や内容がまとまっている作業をひとつの手続きとしたものである。繰り返し利用されるルーチン作業をモジュールとしてまとめたもので、呼び出す側の「主」となるもの（メインルーチン）と対比して「サブルーチン」と呼ばれる。サブプログラム (subprogram) と呼ばれることもある。また、「サブ」をつけずに「ルーチン」と呼ぶこともある。 プログラムのソース中で、繰り返し現れる作業をサブルーチン化することで、可読性や保守性を高く保つことができる。繰り返し現れる作業でなくても、意味的なまとまりを示すためにサブルーチン化することもある。また、キャッシュのような階層的メモリの設計を持つコンピュータ（現在のパソコンやワークステーションなどほぼすべて）では、よく使われるサブルーチンがキャッシュに格納されることで高速な動作を期待できる。.
新しい！!: 理論計算機科学とサブルーチン · 続きを見る »
公理
公理（こうり、axiom）とは、その他の命題を導きだすための前提として導入される最も基本的な仮定のことである。一つの形式体系における議論の前提として置かれる一連の公理の集まりを (axiomatic system) という 。公理を前提として演繹手続きによって導きだされる命題は定理とよばれる。多くの文脈で「公理」と同じ概念をさすものとして仮定や前提という言葉も並列して用いられている。 公理とは他の結果を導きだすための議論の前提となるべき論理的に定式化された（形式的な）言明であるにすぎず、真実であることが明らかな自明の理が採用されるとは限らない。知の体系の公理化は、いくつかの基本的でよく知られた事柄からその体系の主張が導きだせることを示すためになされることが多い。 なお、ユークリッド原論などの古典的な数学観では、最も自明（絶対的）な前提を公理、それに準じて要請される前提を公準 (postulate) として区別していた。.
新しい！!: 理論計算機科学と公理 · 続きを見る »
公開鍵暗号
公開鍵暗号（こうかいかぎあんごう、Public-key cryptography）とは、暗号化と復号に別個の鍵（手順）を用い、暗号化の鍵を公開すらできるようにした暗号方式である。 暗号は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いるための障害であった。この問題に対して、暗号化鍵の配送問題を解決したのが公開鍵暗号である。.
新しい！!: 理論計算機科学と公開鍵暗号 · 続きを見る »
符号理論
号理論（ふごうりろん、Coding theory）は、情報を符号化して通信を行う際の効率と信頼性についての理論である。符号は、データ圧縮・暗号化・誤り訂正・ネットワーキングのために使用される。符号理論は、効率的で信頼できるデータ伝送方法を設計するために、情報理論・電気工学・数学・言語学・計算機科学などの様々な分野で研究されている。通常、符号理論には、冗長性の除去と、送信されたデータの誤りの検出・訂正が含まれる。 符号化は、以下の4種類に分けられる。.
新しい！!: 理論計算機科学と符号理論 · 続きを見る »
複雑性
複雑性（ふくざつせい、complexity）という用語は、多数の部品が入り組んで配置された何らかのものを特徴付ける言葉として使われる。科学として複雑性を研究するアプローチはいくつか存在しており、本項目ではそれらを概説する。マサチューセッツ工科大学のセス・ロイドは、複雑性の定義を32種類集めてプレゼンテーションしたことがあるという。.
新しい！!: 理論計算機科学と複雑性 · 続きを見る »
計算可能性理論
計算可能性理論（けいさんかのうせいりろん、computability theory）では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。 計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。.
新しい！!: 理論計算機科学と計算可能性理論 · 続きを見る »
計算幾何学
計算幾何学（けいさんきかがく、英語：computational geometry）は、幾何学の言葉で述べることのできるアルゴリズムの研究をテーマとする計算機科学の一分野である。計算幾何学的アルゴリズムの研究から純幾何学的な問題が生じることもあり、またそのような問題は計算幾何学の一部であると考えられる。.
新しい！!: 理論計算機科学と計算幾何学 · 続きを見る »
計算モデル
計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.
新しい！!: 理論計算機科学と計算モデル · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
新しい！!: 理論計算機科学と計算理論 · 続きを見る »
計算生物学
計算生物学（けいさんせいぶつがく、computational biology）は、生物学の問題の解決に計算機科学、応用数学、統計学の手法を応用する学際研究分野。下記のような生物学の下位領域が含まれる。;バイオインフォマティクス;計算生物モデリング;計算ゲノミクス;分子モデリング;システム生物学;タンパク質構造予測と構造ゲノミクス;計算生化学と計算生物物理学.
新しい！!: 理論計算機科学と計算生物学 · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: 理論計算機科学と計算複雑性理論 · 続きを見る »
計算機
計算機（けいさんき）は、計算を機械的に、さらには自動的に行う装置である。人間が行う計算を援助するのみのものや、手動操作で自動的ではないものなどは計算器という文字表現をすることがある。.
新しい！!: 理論計算機科学と計算機 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: 理論計算機科学と計算機科学 · 続きを見る »
計算機科学の未解決問題
計算機科学の未解決問題（けいさんきかがくのみかいけつもんだい）とは計算機科学における未解決の問題のこと。.
新しい！!: 理論計算機科学と計算機科学の未解決問題 · 続きを見る »
論理学
論理学（ろんりがく、）とは、「論理」を成り立たせる論証の構成やその体系を研究する学問である。.
新しい！!: 理論計算機科学と論理学 · 続きを見る »
量子力学
量子力学（りょうしりきがく、quantum mechanics）は、一般相対性理論と同じく現代物理学の根幹を成す理論として知られ、主として分子や原子、あるいはそれを構成する電子など、微視的な物理現象を記述する力学である。 量子力学自身は前述のミクロな系における力学を記述する理論だが、取り扱う系をそうしたミクロな系の集まりとして解析することによって、ニュートン力学に代表される古典論では説明が困難であった巨視的な現象についても記述することができる。たとえば量子統計力学はそのような応用例の一つである。従って、生物や宇宙のようなあらゆる自然現象もその記述の対象となり得る。 代表的な量子力学の理論として、エルヴィン・シュレーディンガーによって創始された、シュレーディンガー方程式を基礎に置く波動力学と、ヴェルナー・ハイゼンベルク、マックス・ボルン、パスクアル・ヨルダンらによって構成された、ハイゼンベルクの運動方程式を基礎に置く行列力学がある。ただしこの二つは数学的に等価である。 基礎科学として重要で、現代の様々な科学や技術に必須な分野である。 たとえば科学分野について、太陽表面の黒点が磁石になっている現象は、量子力学によって初めて解明された。 技術分野について、半導体を利用する電子機器の設計など、微細な領域に関するテクノロジーのほとんどは量子力学を基礎として成り立っている。そのため量子力学の適用範囲の広さと現代生活への影響の大きさは非常に大きなものとなっている。一例として、パソコンや携帯電話、レーザーの発振器などは量子力学の応用で開発されている。工学において、電子工学や超伝導は量子力学を基礎として展開している。.
新しい！!: 理論計算機科学と量子力学 · 続きを見る »
量子コンピュータ
量子コンピュータ （りょうしコンピュータ、英語：quantum computer） は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。 いわゆる電子式など従来の一般的なコンピュータ（以下「古典コンピュータ」）の素子は、情報について、「0か1」などなんらかの2値をあらわすいずれかの状態しか持ち得ない「ビット」で扱う。量子コンピュータは「量子ビット」 (qubit; quantum bit、キュービット) により、重ね合わせ状態によって情報を扱う。 n量子ビットがあれば、2^nの状態を同時に計算できる。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現する。2^以下）で数千年かかっても解けないような計算でも、例えば数十秒といった短い時間でこなすことができる、とされている。--> 量子コンピュータの能力については、計算理論上の議論と、実際に実現されつつある現実の機械についての議論がある。#計算能力の節を参照。.
新しい！!: 理論計算機科学と量子コンピュータ · 続きを見る »
英語
アメリカ英語とイギリス英語は特徴がある 英語（えいご、）は、イ・ヨーロッパ語族のゲルマン語派に属し、イギリス・イングランド地方を発祥とする言語である。.
新しい！!: 理論計算機科学と英語 · 続きを見る »
通信の数学的理論
『通信の数学的理論』（つうしんのすうがくてきりろん、A Mathematical Theory of Communication）は、1948年に数学者クロード・シャノンが発表した、影響力のある論文である。後に書籍化される時に"The Mathematical Theory of Communication"に改題された。"A"を"The"にするという小さな変更だが、この論文の一般性を表現する重要な変更である（英語の冠詞も参照）。.
新しい！!: 理論計算機科学と通信の数学的理論 · 続きを見る »
MITコンピュータ科学・人工知能研究所
CSAILのある Stata Center MITコンピュータ科学・人工知能研究所（MIT Computer Science and Artificial Intelligence Laboratory、CSAIL）は、マサチューセッツ工科大学にある学際的研究所。2003年7月1日、MITコンピュータ科学研究所とMIT人工知能研究所の合併により創設された。CSAIL は研究領域においても研究員の人数においてもMIT最大の研究所である。所長は教授のロドニー・ブルックス。その建物はフランク・ゲーリーが設計した Stata Center である。.
新しい！!: 理論計算機科学とMITコンピュータ科学・人工知能研究所 · 続きを見る »
暗号理論
暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.
新しい！!: 理論計算機科学と暗号理論 · 続きを見る »
機械学習
機械学習（きかいがくしゅう、machine learning）とは、人工知能における研究課題の一つで、人間が自然に行っている学習能力と同様の機能をコンピュータで実現しようとする技術・手法のことである。.
新しい！!: 理論計算機科学と機械学習 · 続きを見る »
波動関数
波動関数（はどうかんすう、wave function）は、もともとは波動現象一般を表す関数のことだが、現在では量子状態（より正確には純粋状態）を表す複素数値関数のことを指すことがほとんどである。.
新しい！!: 理論計算機科学と波動関数 · 続きを見る »
最大公約数
40と15に関する次の要素が埋め込まれた図: 積(600)、 商と剰余(40÷15.
新しい！!: 理論計算機科学と最大公約数 · 続きを見る »
情報理論
情報理論（じょうほうりろん、Information theory）は、情報・通信を数学的に論じる学問である。応用数学の中でもデータの定量化に関する分野であり、可能な限り多くのデータを媒体に格納したり通信路で送ったりすることを目的としている。情報エントロピーとして知られるデータの尺度は、データの格納や通信に必要とされる平均ビット数で表現される。例えば、日々の天気が3ビットのエントロピーで表されるなら、十分な日数の観測を経て、日々の天気を表現するには「平均で」約3ビット/日（各ビットの値は 0 か 1）と言うことができる。 情報理論の基本的な応用としては、ZIP形式（可逆圧縮）、MP3（非可逆圧縮）、DSL（伝送路符号化）などがある。この分野は、数学、統計学、計算機科学、物理学、神経科学、電子工学などの交差する学際領域でもある。その影響は、ボイジャー計画の深宇宙探査の成功、CDの発明、携帯電話の実現、インターネットの開発、言語学や人間の知覚の研究、ブラックホールの理解など様々な事象に及んでいる。.
新しい！!: 理論計算機科学と情報理論 · 続きを見る »
情報検索
情報検索（じょうほうけんさく）とは、コンピュータを用いて大量のデータ群から目的に合致したものを取り出すこと。検索の対象となるデータには文書や画像、音声、映像、その他さまざまなメディアやその組み合わせとして記録されたデータなどが含まれる。インターネットの発達により検索はインターネットを介して行われることも多いが、ここでは情報を検索するためのコンピュータ側における仕組みを記述している。 情報検索に対するコンピュータ側における技術は情報を人間が直接管理するのに比べ、データの量的な制約やデータの取り扱いの一貫性を保つ困難さという制約を受けることなく、高速で安定なシステムにより利用者に適切なデータを提供する機能と位置付けることができる。.
新しい！!: 理論計算機科学と情報検索 · 続きを見る »
数学
数学（すうがく、μαθηματικά, mathematica, math）は、量（数）、構造、空間、変化について研究する学問である。数学の範囲と定義については、数学者や哲学者の間で様々な見解がある。.
新しい！!: 理論計算機科学と数学 · 続きを見る »
数理モデル
数理モデル（すうりモデル、mathematical model）とは、通常は、時間変化する現象の計測可能な主要な指標の動きを模倣する、微分方程式などの「数学の言葉で記述した系」のことを言う。モデルは「模型」と訳され「数理模型」と呼ばれることもある。元の現象を表現される複雑な現実とすれば、モデル（模型）はそれの特別な一面を簡略化した形で表現した「言語」（いまの場合は数学）で、より人間に理解しやすいものとして構築される。構築されたモデルが、元の現象を適切に記述しているか否かは、数学の外の問題で、原理的には論理的には真偽は判定不可能である。人間の直観によって判定するしかない。どこまで精緻にモデル化を行ったとしても、得た観察を近似する論理的な説明に過ぎない。 数理モデルは、対象とする現象や、定式化の抽象度などによって様々なものがある。.
新しい！!: 理論計算機科学と数理モデル · 続きを見る »
数理論理学
数理論理学（mathematische Logik、mathematical logic）は、論理学（形式論理学）の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。 数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学（とくに）における数理論理学の役割の詳細はこの記事には含まれていない。詳細はを参照。 この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか（逆数学のように）ということに焦点を当てている。.
新しい！!: 理論計算機科学と数理論理学 · 続きを見る »
数論
数論（すうろん、number theory）とは数、特に整数およびそれから派生する数の体系（代数体、局所体など）の性質について研究する数学の一分野である。整数論とも言う。ふつうは代数学の一分野とみなされることが多い。おおむね次の四つに分けられる。;初等整数論;代数的整数論;解析的整数論;数論幾何学 フェルマーの最終定理のように、数論のいくつかの問題については、他の数学の分野に比して問題そのものを理解するのは簡単である。しかし、使われる手法は多岐に渡り、また非常に高度であることが多い。 ガウスは次のような言葉を残している。.
新しい！!: 理論計算機科学と数論 · 続きを見る »
