ブラウザよりも高速アクセス！
27 関係: Association for Computing Machinery、多項式時間、一階述語論理、二階述語論理、ロシア、ロサンゼルス、トーマス・J・ワトソン研究所、パリ大学、ダートマス大学、アメリカ合衆国、アメリカ科学振興協会、オクラホマ州、オクラホマシティ、カリフォルニア大学バークレー校、カリフォルニア州、ゲーデル賞、サンノゼ、問い合わせ言語、非決定性チューリングマシン、複雑性クラス、関係の正規化、IBM、IEEE、NP、決定問題、有限モデル理論、情報科学研究所。
Association for Computing Machinery
Association for Computing Machinery (ACM) は、ニューヨークに本部のあるコンピュータ科学分野の国際学会。1947年設立。IEEEとともに、この分野で最も影響力の強い学会であり、IEEEがその名と由来や歴史からエレクトロニクスや通信分野の工学に強いのに対し、数学的な理論計算機科学のような分野もカバーする。日本語に訳して「計算機械学会」とされることもあるが、こんにちこの訳語が用いられることはほとんどなく、通常は単に"ACM"という略称で呼ばれるのがもっぱらである。ACMの「A」は Association (学会、団体) の頭文字であるが、アメリカ数学会 (AMS) と混同して「米国計算機学会」と誤訳されることがある。 数多くの国際会議を開催しており、人目を惹くデモ映像のSIGGRAPHやSIGMODなどはよく知られている。他の多くの学会と同様にすぐれた業績などへの表彰もおこなっているが、チューリング賞は、特にこの分野の最高の賞とみなされており、物理や化学といった分野におけるノーベル賞に匹敵するものと扱われることもある（他の賞についても時折「～のノーベル賞」といったような表現が使われることがあるが、この分野の全てを対象とした世界トップクラスの賞という位置づけにあるのはチューリング賞をおいて他にない）。.
新しい！!: ロナルド・フェイギンとAssociation for Computing Machinery · 続きを見る »
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: ロナルド・フェイギンと多項式時間 · 続きを見る »
一階述語論理
一階述語論理（いっかいじゅつごろんり、first-order predicate logic）とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理（にかいじゅつごろんり、second-order predicate logic）と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理（こうかいじゅつごろんり、higher-order predicate logic）という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。.
新しい！!: ロナルド・フェイギンと一階述語論理 · 続きを見る »
二階述語論理
二階述語論理（にかいじゅつごろんり、second-order predicate logic）あるいは単に二階論理（にかいろんり、second-order logic）は、一階述語論理を拡張した論理体系であり、一階述語論理自体も命題論理を拡張したものである。二階述語論理もさらに高階述語論理や型理論に拡張される。 一階述語論理と同様に議論領域（ドメイン）の考え方を使う。ドメインとは、量化可能な個々の元の集合である。一階述語論理では、そのドメインの個々の元が変項の値となり、量化される。例えば、一階の論理式 ∀x (x ≠ x + 1) では、変項 x は任意の個体を表す。二階述語論理は個体の集合を変項の値とし、量化することができる。例えば、二階の論理式 ∀S ∀x (x ∈ S ∨ x ∉ S) は、個体の全ての集合 S と全ての個体 x について、x が S に属するか、あるいは属さないかのどちらかであるということを主張している。最も一般化された二階述語論理は関数の量化をする変項も含んでいる（詳しくは後述）。.
新しい！!: ロナルド・フェイギンと二階述語論理 · 続きを見る »
ロシア
ア連邦（ロシアれんぽう、Российская Федерация）、またはロシア (Россия) は、ユーラシア大陸北部にある共和制及び連邦制国家。.
新しい！!: ロナルド・フェイギンとロシア · 続きを見る »
ロサンゼルス
ンゼルス（Los Angeles、スペイン語も同じ）は、アメリカ合衆国カリフォルニア州にある都市。同州最大の都市かつ全米有数の世界都市であり、国内ではニューヨークに次いで人口が多い（アメリカ合衆国国勢調査局）。.
新しい！!: ロナルド・フェイギンとロサンゼルス · 続きを見る »
トーマス・J・ワトソン研究所
トーマス・J・ワトソン研究所（トーマス・ジェイ・ワトソンけんきゅうじょ、Thomas J. Watson Research Center）は、IBMの研究部門の本部である。研究所の名称は、1915年から1971年までIBMを社長・CEOとして率いていた、トーマス・J ・ワトソン・シニアとその息子トーマス・J ・ワトソン・ジュニアの名前に因んだものである。 この研究所は三つの敷地に分かれて建っており、主要な研究所はニューヨーク市から北へ70kmほどに位置するニューヨーク州ヨークタウン・ハイツ（Yorktown Heights）にある。他の２つはニューヨーク州ホーソン（Hawthorne）とマサチューセッツ州ケンブリッジ（Cambridge）にそれぞれ位置している。 ここでの研究内容は、物理学や半導体技術などコンピュータ・ハードウェアに関するもの、ビジネスモデルやコンサルティング、経営などサービス業に関する研究、プログラミング言語やセキュリティ、データ管理などといったソフトウェアに関連するもの、OSやサーバといったシステム関連の研究と、多岐にわたる。 トーマス・J・ワトソン研究所は1945年、コロンビア大学のワトソン・サイエンティフィック・コンピューティング研究所（Watson Scientific Computing Laboratory）としてニューヨークに設立された。この施設は1953年に拡張され、1957年にはヨークタウン・ハイツに本部を移転し、1961年にはEero Saarinenによる設計の新しい研究所が完成した。1945年以来の施設は1970年に閉鎖、後にこの建物はコロンビア大学に譲渡され、現在ではCasa Hispanica（ヒスパニックの家の意）とワトソン・ホールとして知られている。更に1984年にはホーソンにも施設が拡張された。 この研究所で働いた著名な研究者には、数学者のブノワ・マンデルブロ、グレゴリー・チャイティン、Shmuel Winograd、物理学者の江崎玲於奈、発明家のRobert Dennard、コンピューター学者のジョン・コック、Stuart Feldman 、Irene Greifらがいる。.
新しい！!: ロナルド・フェイギンとトーマス・J・ワトソン研究所 · 続きを見る »
パリ大学
パリ大学（仏：Université de Paris）は、フランス共和国のパリ、クレテイユおよびヴェルサイユの3大学区にある13の大学の総称である。多くのノーベル賞受賞者を送り出している他、法学、政治学、科学、物理学、神学などの分野で優秀な学者を輩出している。また芸術の教育機関としても名高い。.
新しい！!: ロナルド・フェイギンとパリ大学 · 続きを見る »
ダートマス大学
アイビー・リーグのメンバーで、全米の大学の中で13番目に長い歴史を持ち、本校は9つあるアメリカ独立戦争以前に創立された「コロニアル・カレッジ」の1つでもある。.
新しい！!: ロナルド・フェイギンとダートマス大学 · 続きを見る »
アメリカ合衆国
アメリカ合衆国（アメリカがっしゅうこく、）、通称アメリカ、米国（べいこく）は、50の州および連邦区から成る連邦共和国である。アメリカ本土の48州およびワシントンD.C.は、カナダとメキシコの間の北アメリカ中央に位置する。アラスカ州は北アメリカ北西部の角に位置し、東ではカナダと、西ではベーリング海峡をはさんでロシアと国境を接している。ハワイ州は中部太平洋における島嶼群である。同国は、太平洋およびカリブに5つの有人の海外領土および9つの無人の海外領土を有する。985万平方キロメートル (km2) の総面積は世界第3位または第4位、3億1千7百万人の人口は世界第3位である。同国は世界で最も民族的に多様かつ多文化な国の1つであり、これは多くの国からの大規模な移住の産物とされているAdams, J.Q.;Strother-Adams, Pearlie (2001).
新しい！!: ロナルド・フェイギンとアメリカ合衆国 · 続きを見る »
アメリカ科学振興協会
ワシントンD.C.にあるオフィス アメリカ科学振興協会（アメリカかがくしんこうきょうかい、American Association for the Advancement of Science; AAAS）は、科学者間の協力を促進し、科学的自由を守り、科学界からの情報発信を奨励し、全人類の幸福のために科学教育をサポートする組織である。世界的にも最大級の学術団体で、有名な科学雑誌『サイエンス』の出版元としても知られている。.
新しい！!: ロナルド・フェイギンとアメリカ科学振興協会 · 続きを見る »
オクラホマ州
ラホマ州（State of Oklahoma、）は、アメリカ合衆国南中部にある州である。州の北はコロラド州とカンザス州に接し、東はミズーリ州とアーカンソー州、西はニューメキシコ州、南はテキサス州に接している。アメリカ合衆国50州の中で、面積では第20位、人口では第28位である。 州都および最大都市はオクラホマ市であり、タルサ市がそれに続く。 州名はチョクトー族インディアンの言葉でokla と hummaを合わせたものであり、「赤い人々」を意味する。1907年11月16日に元のインディアン準州とオクラホマ準州を合わせて合衆国46番目の州になっており、当初は全米のインディアン部族のほとんどを強制移住させる目的で作られた州である。そのため、他の州に比べ、インディアンの保留地（Reservation）が非常に多い。 オクラホマ州は天然ガス、石油および農業の生産高が高く、また航空機、エネルギー、通信およびバイオテクノロジーに経済の基盤がある。国内でも最大級に経済成長率が高く、一人当たり収入成長率と、州総生産の成長率では国内トップクラスである。オクラホマシティ市とタルサ市が州経済の中心となり、両都市圏に州人口の60%近くが住んでいる。.
新しい！!: ロナルド・フェイギンとオクラホマ州 · 続きを見る »
オクラホマシティ
ラホマシティ (Oklahoma City) は、アメリカ合衆国オクラホマ州中央部に位置する同州最大の都市にして州都。人口は約53万人（2004年）で、周辺の商業中心地として発展。一帯は肥沃な農地、牧草地が広がり、開拓時代に自営農地を求める約1万人の開拓民によって都市を創設。家畜置場や肉加工などの畜産関連工場、また綿花の集散地として発達する。1928年には油田が発見され、後に航空機、電器機械などの製造業も発展する。文化施設には州歴史博物館、カウボーイ博物館、オクラホマ州立動物園などがある。.
新しい！!: ロナルド・フェイギンとオクラホマシティ · 続きを見る »
カリフォルニア大学バークレー校
バークレー校はカリフォルニア大学 (University of California) の発祥地であり、10大学からなるカリフォルニア大学システム（UCシステム）の中で最も古い歴史を持つ。ハーバード大学など同国東部の名門私立大学群の集まりである「アイビーリーグ」に対し名門公立大学の集まりである「パブリック・アイビー」の一校である。アメリカの公立大学ランキングでは長期間にわたり1位を維持している。同じ米国西海岸サンフランシスコ近郊のベイエリアに位置するスタンフォード大学とはスポーツ分野を中心に長年ライバル関係にある。 シリコンバレーにも近く位置しておりIT系やコンピューター分野でも多数の大企業から出資を受け研究、開発を行っている。UNIXシステムの一つ、BSDもこの大学の研究室で開発された。元サン・マイクロシステムズ技術者のビル・ジョイは、UCバークレーの学生時代に、viエディタと Cシェル (csh) など様々な基本的なツール・ユーティリティを設計、実装している。 第二次世界大戦当時バークレー校の物理学部教授だったロバート・オッペンハイマーやノーベル化学賞受賞者のグレン・シーボーグを筆頭にバークレー校の多くの学者が原子爆弾開発計画であるマンハッタン計画に携わり、米国における原子力爆弾および水素爆弾の開発に大きく貢献した。現在（2014年）まで70人以上のノーベル賞受賞者を輩出している。化学に関する研究が世界的に有名で、周期表の元素のうち6つが本校で発見された。 現在、アメリカの公立大学においてランキング第1位である。.
新しい！!: ロナルド・フェイギンとカリフォルニア大学バークレー校 · 続きを見る »
カリフォルニア州
リフォルニア州（State of California、Estado de California、中:加利福尼亚州、加州）は、アメリカ合衆国西部、太平洋岸の州。アメリカ西海岸の大部分を占める。州都は、サクラメントである。.
新しい！!: ロナルド・フェイギンとカリフォルニア州 · 続きを見る »
ゲーデル賞
ーデル賞 (Gödel Prize) は、理論計算機科学分野で優れた功績を残した人に、ACM（国際計算機学会）のアルゴリズムと計算量理論に関する部会とEATCS（ヨーロッパ理論コンピュータ学会）が贈る賞である。受賞者には賞金5,000ドルが贈られる。論理学者クルト・ゲーデルに由来する。計算機科学分野ではチューリング賞と並んで権威を持つ賞である。.
新しい！!: ロナルド・フェイギンとゲーデル賞 · 続きを見る »
サンノゼ
ンノゼ（San José、San Jose）は、アメリカ合衆国カリフォルニア州にある都市。.
新しい！!: ロナルド・フェイギンとサンノゼ · 続きを見る »
問い合わせ言語
問い合わせ言語（といあわせげんご、query language:略記QL）とは、コンピュータのデータに対して問い合わせをするためのコンピュータ言語である。 データの構造（データモデル）によってさまざまである。たとえば、関係データベースに対する問い合わせ言語は、関係代数の集合演算、比較、ソートといった機能を持つものが多い。 なお、コンピュータのデータベースを扱うためのコンピュータ言語をデータベース言語という。 問い合わせ言語とデータベース言語は、概念的に重なる部分もあるが、同義ではない。.
新しい！!: ロナルド・フェイギンと問い合わせ言語 · 続きを見る »
非決定性チューリングマシン
非決定性チューリング機械（ひけっていせいチューリングきかい、Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。.
新しい！!: ロナルド・フェイギンと非決定性チューリングマシン · 続きを見る »
複雑性クラス
複雑性クラス（ふくざつせいクラス、Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えば'''FP'''）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.
新しい！!: ロナルド・フェイギンと複雑性クラス · 続きを見る »
関係の正規化
関係の正規化（かんけいのせいきか）は、関係データベース (リレーショナル・データベース) において、正規形と呼ばれる形式に関係（リレーション）を準拠させることにより、データの一貫性の維持と効率的なデータアクセスを可能にする関係設計を導くための方法である。正規形には様々なものが存在するが、いずれにせよ、正規化を行うことにより、データの冗長性と不整合が起きる機会を減らすことができる。 多くの関係データベース管理システム (RDBMS) は、論理的なデータベース設計とデータを格納する物理的な実装方法とが十分に分離されていないので、完全に正規化されたデータベースへのクエリ（検索質問）はパフォーマンスが良くないことがある。このような場合、パフォーマンスを向上させるためにデータの一貫性の低下と引き換えにあえて非正規化されることもある。.
新しい！!: ロナルド・フェイギンと関係の正規化 · 続きを見る »
IBM
IBM（アイビーエム、正式社名: International Business Machines Corporation）は、民間法人や公的機関を対象とするコンピュータ関連製品およびサービスを提供する企業である。本社はアメリカ合衆国ニューヨーク州アーモンクに所在する。世界170カ国以上で事業を展開している。.
新しい！!: ロナルド・フェイギンとIBM · 続きを見る »
IEEE
IEEE（アイ・トリプル・イー、The Institute of Electrical and Electronics Engineers, Inc.）は、アメリカ合衆国に本部を持つ電気工学・電子工学技術の学会である。.
新しい！!: ロナルド・フェイギンとIEEE · 続きを見る »
NP
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time（非決定性多項式時間）の略である（「Non-P」ないしは「Not-P」ではない）。.
新しい！!: ロナルド・フェイギンとNP · 続きを見る »
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
新しい！!: ロナルド・フェイギンと決定問題 · 続きを見る »
有限モデル理論
有限モデル理論（英: Finite model theory）とは、モデル理論の一種であり、一階述語論理などの論理言語を有限構造（有限群、グラフ、データベース、多くの計算模型など）に適用したときの属性に着目した理論である。論理言語と計算の関係に特に注目し、離散数学や計算複雑性理論やデータベース理論とも密接に関連する。 一階述語論理と古典モデル理論の重要な成果の多くは、有限構造に制限されると成り立たない。例えば、コンパクト性定理、クレイグの補間定理、レーヴェンハイム-スコーレムの定理、ゲーデルの完全性定理などである。このような文脈では、一階述語論理の表現能力が十分とは言えない点が根本的な問題である。このため、一階述語論理に推移閉包や最小不動点の作用素を追加したり、二階述語論理の一部を使ったりして、有限構造での属性を表現できる新たな論理体系を構築する。 有限モデル理論の一分野として重要な理論に記述計算量がある。これは、様々な抽象機械の能力と論理言語の表現能力を結びつけるものである。ある言語が一階述語論理に最小不動点作用素を追加したもので表せる場合、チューリングマシンにある文字列を与えたとき、その文字列がその言語に属するかどうかを判定するには多項式時間を要する（'''P'''）。記述計算量の考え方によって、計算複雑性理論と数理論理学の成果の交流が可能となり、標準的な複雑性クラスが「自然」なものであるという証拠も与える。Neil Immerman は、「数理論理学の歴史の中でも、有限構造に関する研究が最も興味深く…さらに言えば、コンピュータ上のオブジェクトは常に有限である。計算の研究には、有限構造の理論が必要である」と述べている。 また、有限モデル理論の重要な帰結の一つに、対象 x の性質 P(x) はほとんどの対象において当てはまるものであるか、ほとんどの対象において当てはまらないものであるかに分類されるという法則(Zero-One Law)がある。たとえば、サイズが n 以下のグラフの性質について考えるとき、対象が連結グラフである確率は n が無限大に近づくにつれて 1 に近づく。逆に、対象が孤立点を含んでいる確率は 0 に近づく。Zero-One Lawは、多項式時間でチェック可能な任意のグラフの性質について、性質を満たす対象の比率が 1 か 0 のどちらかに近づいていくことを主張する。この法則は、大規模な有限構造についての乱択アルゴリズムに影響を及ぼす。 有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を k 個に制限された一階述語論理などである。.
新しい！!: ロナルド・フェイギンと有限モデル理論 · 続きを見る »
情報科学研究所
Information Sciences Institute（ISI）は、アメリカ合衆国カリフォルニア州ロサンゼルス郊外のマリナ・デル・レイにある研究所。南カリフォルニア大学のキャンパス外研究施設として、1972年に創設された。 コンピュータ科学や情報通信・技術・工学の多面的で先進的な研究・開発で知られ、インターネットの原型であるアーパネット（ARPANET）の運営・管理を長く行った。ジョン・ポステルがコンピュータネットワークの研究を行った場所でもある。.
新しい！!: ロナルド・フェイギンと情報科学研究所 · 続きを見る »
