ブラウザよりも高速アクセス！
70 関係: 合成数、多項式時間、帰納言語、乱択アルゴリズム、二階述語論理、ミラー–ラビン素数判定法、マサチューセッツ工科大学、チューリング賞、ハーバード大学、ハーヴェイ賞、ハイファ、ポーランド、ラビ、ラビン-カープ文字列検索アルゴリズム、ラビンオートマトン、リチャード・カープ、リーマン予想、レナード・クラインロック、ヴロツワフ、ヘブライ大学、プリンストン大学、パリティゲーム、テルアビブ大学、デイナ・スコット、ドイツ、ニューヨーク州、ベル研究所、アリーヤー、アロンゾ・チャーチ、アドルフ・フレンケル、イギリス委任統治領パレスチナ、イスラエル賞、ウエストチェスター郡 (ニューヨーク州)、エルサレム、コロンビア大学、ゴードン・ムーア、ジョン・マッカーシー、スティーヴン・コール・クリーネ、サハロン・シェラハ、公開鍵暗号、王立協会、科学アカデミー (フランス)、第一次中東戦争、米国科学アカデミー、素因数分解、素数、素数判定、紛失通信プロトコル、鍵 (暗号)、非決定性有限オートマトン、...、計算複雑性理論、計算機科学、IBM、P≠NP予想、Rabin暗号、RSA暗号、暗号理論、暗号解読、暗号文、正規言語、文字列探索、数理論理学、1931年、1956年、1959年、1975年、1976年、1979年、1981年、1987年。 インデックスを展開 (20 もっと) »
合成数
合成数（ごうせいすう、Composite number）は、自然数で、1とその数自身以外の約数を持つ数である。2つ以上の素数の積で表すことのできる自然数と定義してもよい。たとえば15は1と15自身以外に3と5を約数に持つ（または 3×5 と素数の積で表される）ので合成数である。9や25など素数を2乗した数は1つしか素因数をもたないが、9.
新しい！!: マイケル・ラビンと合成数 · 続きを見る »
多項式時間
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい！!: マイケル・ラビンと多項式時間 · 続きを見る »
帰納言語
帰納言語（きのうげんご、Recursive language）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。.
新しい！!: マイケル・ラビンと帰納言語 · 続きを見る »
乱択アルゴリズム
乱択アルゴリズム（らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム）または確率的アルゴリズム（かくりつてき-、Probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.
新しい！!: マイケル・ラビンと乱択アルゴリズム · 続きを見る »
二階述語論理
二階述語論理（にかいじゅつごろんり、second-order predicate logic）あるいは単に二階論理（にかいろんり、second-order logic）は、一階述語論理を拡張した論理体系であり、一階述語論理自体も命題論理を拡張したものである。二階述語論理もさらに高階述語論理や型理論に拡張される。 一階述語論理と同様に議論領域（ドメイン）の考え方を使う。ドメインとは、量化可能な個々の元の集合である。一階述語論理では、そのドメインの個々の元が変項の値となり、量化される。例えば、一階の論理式 ∀x (x ≠ x + 1) では、変項 x は任意の個体を表す。二階述語論理は個体の集合を変項の値とし、量化することができる。例えば、二階の論理式 ∀S ∀x (x ∈ S ∨ x ∉ S) は、個体の全ての集合 S と全ての個体 x について、x が S に属するか、あるいは属さないかのどちらかであるということを主張している。最も一般化された二階述語論理は関数の量化をする変項も含んでいる（詳しくは後述）。.
新しい！!: マイケル・ラビンと二階述語論理 · 続きを見る »
ミラー–ラビン素数判定法
ミラー–ラビン素数判定法（Miller–Rabin primality test）またはラビン–ミラー素数判定法（Rabin–Miller primality test）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンはこれを無条件の確率的アルゴリズムに修正した。.
新しい！!: マイケル・ラビンとミラー–ラビン素数判定法 · 続きを見る »
マサチューセッツ工科大学
マサチューセッツ工科大学（英語: Massachusetts Institute of Technology）は、アメリカ合衆国マサチューセッツ州ケンブリッジに本部を置く私立工科大学である。1865年に設置された。通称はMIT（エム・アイ・ティー。「ミット」は誤用で主に日本、欧州の極めて一部で用いられる）。 全米屈指のエリート名門校の1つとされ、ノーベル賞受賞者を多数（2014年までの間に1年以上在籍しMITが公式発表したノーベル賞受賞者は81名で、この数はハーバード大学の公式発表受賞者48名を上回る）輩出している。最も古く権威ある世界大学評価機関の英国Quacquarelli Symonds（QS）による世界大学ランキングでは、2012年以来2017年まで、ハーバード大学及びケンブリッジ大学を抑えて6年連続で世界第一位である。 同じくケンブリッジ市にあるハーバード大学とはライバル校であるが、学生達がそれぞれの学校の授業を卒業単位に組み込める単位互換制度（Cross-registration system）が確立されている。このため、ケンブリッジ市は「世界最高の学びのテーマパーク」とさえも称されている。物理学や生物学などの共同研究組織を立ち上げるなど、ハーバード大学との共同研究も盛んである。 MITはランドグラント大学でもある。1865年から1900年の間に約19万4千ドル(これは2008年時点の生活水準でいうところの380万ドルに相当)のグラントを得、また同時期にマサチューセッツ州から更なる約36万ドル（2008年時点の生活水準で換算して700万ドルに相当）の資金を獲得しているD.
新しい！!: マイケル・ラビンとマサチューセッツ工科大学 · 続きを見る »
チューリング賞
ACMチューリング賞(ACM A.M. Turing Award)は、計算機科学分野で革新的な功績を残した人物に年に1度、ACMから贈られる賞であり世界最高の権威を持つ賞とされている。その功績は長く影響が続くもので、コンピュータ業界で技術的にも重要なものとされている。計算機科学におけるノーベル賞と広く認識されており、事実、受賞者にはハーバート・サイモンなどノーベル賞受賞者が存在している。 「チューリング」の名は、現代計算機科学の父の1人とされるアラン・チューリングの名にちなむ。2014年11月3日、Googleの後援により受賞者には100万ドルが贈られると発表された。 1966年の最初の受賞者はカーネギーメロン大学のアラン・パリスだった。初の女性受賞者は、2006年のフランシス・E・アレン（IBM）である。2008年には再び女性であるバーバラ・リスコフが受賞している。.
新しい！!: マイケル・ラビンとチューリング賞 · 続きを見る »
ハーバード大学
ハーバード大学（英語: Harvard University）は、アメリカ合衆国の研究型私立大学であり、アイビー・リーグの一校。イギリス植民地時代の1636年に設置された、アメリカ合衆国内において、最も学術的起源の古い高等教育機関である。.
新しい！!: マイケル・ラビンとハーバード大学 · 続きを見る »
ハーヴェイ賞
ハーヴェイ賞 (Harvey Prize)は、ハイファのイスラエル工科大学が主催する賞。科学技術の進展、人類の健康福祉の増進、中東和平への貢献に対して、毎年原則として2人ずつに授与され、賞金は各75,000ドル。 選考時点で既にノーベル賞やウルフ賞を受賞している者は対象から除外されるが、本賞受賞後にそれらを受賞した者は少なくない。.
新しい！!: マイケル・ラビンとハーヴェイ賞 · 続きを見る »
ハイファ
ハイファ（、、Ḥefa、Haifa）は、イスラエルハイファ地区にある都市である。.
新しい！!: マイケル・ラビンとハイファ · 続きを見る »
ポーランド
ポーランド共和国（ポーランドきょうわこく、Rzeczpospolita Polska）、通称ポーランドは、中央ヨーロッパに位置する共和制国家。欧州連合 (EU)、北大西洋条約機構 (NATO) の加盟国。通貨はズウォティ。首都はワルシャワ。 北はバルト海に面し、北東はロシアの飛地カリーニングラード州とリトアニア、東はベラルーシとウクライナ、南はチェコとスロバキア、西はドイツと国境を接する。 10世紀に国家として認知され、16世紀から17世紀にかけヨーロッパで広大な国の1つであったポーランド・リトアニア共和国を形成。18世紀、4度にわたり国土が隣国によって分割され消滅。 第一次世界大戦後、1918年に独立を回復したが、第二次世界大戦時、ナチス・ドイツとソビエト連邦からの事前交渉を拒否し両国に侵略され、再び国土が分割された。戦後1952年、ポーランド人民共和国として国家主権を復活、1989年、民主化により共和国となった。冷戦時代は、ソ連の影響下に傀儡政権の社会主義国とし最大で最も重要なソ連の衛星国の一国となり、政治的にも東側諸国の一員となった。国内及び東側諸国の民主化とソ連の崩壊と東欧革命を経て、「中欧」または「中東欧」として再び分類されるようになっている。.
新しい！!: マイケル・ラビンとポーランド · 続きを見る »
ラビ
ラビ（英語・ラテン語 rabbi, ドイツ語 Rabbi, ギリシア語 rhabbi, アラム語 rabbin(複数形), ヘブライ語 rabbi / セファルディ・ミズラヒ圏 chakham, イディッシュ語 rebbe）とは、ユダヤ教に於いての宗教的指導者であり、学者でもあるような存在。 複数形はラッビーイーム。 英語圏（主に米国）ではラバイと発音する（Ra-Byのような発音になる） ヘブライ語ラッビー rabbi とはラブ rabh「師」の派生語であり、「わが師」という形である。イツハク・ラビンやラビノヴィチ Rabinowicz というような姓にある「ラッビーン」はアラム語の複数形である。 また、アラム語ラッバーン rabban「チーフ・ラビ」は、サンヘドリン長に与えられた、ラビよりも上の称号である。 ヘブライ語 ／ラブ私の我々の ／rabhrabbīrabbēnū 複数形rabbānīmrabbī’īm アラム語 ／ラブ私の我々の ／rabhrabbān 複数形rabbīn ラビを呼ぶときは「ラビ・○○」というように姓の前にラビを付けて敬意を表す。 「ラッベーヌー」となると「我々のラブ（師）」で、特にラッベーヌーという場合はモーセなどをさす。 アラム語の対応形が「ラッバーン、ラバン」で、古代のサンヘドリン長のことである。 ラディーノ語のハハム chakham はアラビア語のハキームに対応し、イスラム圏での学者や医者もやはり「賢者」と呼ばれた。なお、アラビア語でハーキムとなると知事を意味する。.
新しい！!: マイケル・ラビンとラビ · 続きを見る »
ラビン-カープ文字列検索アルゴリズム
ラビン-カープ文字列検索アルゴリズム（Rabin-Karp string search algorithm）は、マイケル・ラビンとリチャード・カープが開発した、ハッシュ関数を利用してテキストからパターン（サブ文字列）を探す文字列検索アルゴリズムの一種。1つのパターンの検索にはあまり用いられないが、理論的には重要であり、複数パターンの検索には効果的である。テキストの文字数が n、パターンの文字数が m とした場合、平均および最良の実行時間はO(n)だが、ごくまれに最悪性能として O(nm)となる（広く用いられないのはそのため）。しかし、k個の文字列のいずれかにマッチする部分を検索するのに要する時間は k によらず平均で O(n) となるという独特の利点を持つ。以下、単にラビン-カープまたはラビン-カープ法と略記することがある。 ラビン-カープの単純な応用例として、盗作の検出がある。例えば、学生が『白鯨』に関する英語の論文を書いたとしよう。賢い教授は『白鯨』に関する様々な資料を集め、それらの全文を自動的に抽出するものとする。そこで、ラビン-カープを使えば学生の論文の任意の文がそれら資料からの丸写しかどうかを判定できる。微妙な修正で盗作を判定できなくなるのを防ぐには、大文字・小文字の別を無視し、句読点を無視すればよい。この場合の検索文字列数 k は膨大なので、単一文字列検索アルゴリズムは非現実的である。.
新しい！!: マイケル・ラビンとラビン-カープ文字列検索アルゴリズム · 続きを見る »
ラビンオートマトン
ラビンオートマトン（Rabin Automaton）は、無限長の文字列を扱う有限オートマトンの一種。その形式は \mathcal.
新しい！!: マイケル・ラビンとラビンオートマトン · 続きを見る »
リチャード・カープ
リチャード・マニング・カープ（Richard Manning Karp、1935年1月3日 - ）は、計算機科学者にして計算理論家であり、計算理論の研究で知られている。カリフォルニア大学バークレー校に在籍。.
新しい！!: マイケル・ラビンとリチャード・カープ · 続きを見る »
リーマン予想
1.
新しい！!: マイケル・ラビンとリーマン予想 · 続きを見る »
レナード・クラインロック
レナード・クラインロック（英語: Leonard Kleinrock、1934年6月13日 -）は、アメリカの技術者で計算機科学者。UCLAの計算機科学の教授で、コンピュータネットワークの分野の中でも理論面で数々の重要な貢献を行った。インターネットの原型であるARPANETの開発で重要な役割を担った。.
新しい！!: マイケル・ラビンとレナード・クラインロック · 続きを見る »
ヴロツワフ
ヴロツワフ（ポーランド語: 、 ブレスラウ、 ボロスロー）は、ポーランド西部にある第4の都市で、ドルヌィ・シロンスク県の県都。歴史的にシロンスク地方の中心都市で、ポーランドの中でも最も古い都市のひとつである。市内にはオドラ川とその支流が流れ、200以上の橋が架かっている。 ヴロツワフは歴史上、様々な国（ポーランド王国、オーストリア帝国、ドイツ、ハンガリー、プロイセン、ボヘミア）の1部となっていたが、1945年(第二次世界大戦後)にポーランド領となった。 ヴロツワフは、UEFA欧州選手権2012 のホストである。2016年の欧州文化首都になることが決まっており、またワールドゲームズ2017の開催地にも決定した。.
新しい！!: マイケル・ラビンとヴロツワフ · 続きを見る »
ヘブライ大学
ヘブライ大学（ヘブライ語：האוניברסיטה העברית בירושלים - Hebrew University of Jerusalem）は、イスラエルの国立大学である。.
新しい！!: マイケル・ラビンとヘブライ大学 · 続きを見る »
プリンストン大学
プリンストン大学（英語: Princeton University）は、アメリカ合衆国ニュージャージー州プリンストンに本部を置くアメリカ合衆国の私立大学である。1746年に設置された。 学生数は学部生約4800名、大学院生約2000名である。アイビー・リーグ（Ivy League）の大学8校のうちの1校であることや、2名の大統領を輩出していること、アメリカ全土で8番目に古いことなどで有名な大学である。41人のノーベル賞受賞者、14人のフィールズ賞受賞者、5人のアーベル賞受賞者、10人のチューリング賞受賞者、209人のローズ奨学生、126人のを輩出している。2016年度の受験サイクルでは全受験者の6.5%が入学を許可された。.
新しい！!: マイケル・ラビンとプリンストン大学 · 続きを見る »
パリティゲーム
パリティゲームの例。 円形のノードはプレイヤー0に、正方形のノードはプレイヤー1に属する。 左側の青い領域はプレイヤー0の勝利領域で、右側の赤い領域はプレイヤー1の勝利領域である。 パリティゲーム (parity games) は彩色された有向グラフ上でプレイされる理論上のゲームである。各ノードは優先度と呼ばれる(通常は有限種類の)自然数で彩色されている。このゲームはプレイヤー0とプレイヤー1の二名によってプレイされる。各プレイヤーは、ゲーム上に一個だけある駒をグラフの辺にそって動かす。手番は、その駒の現在地によって決められている。この操作を繰り返し(場合によっては無限回)行うことにより、プレイと呼ばれるパスが定まる。 有限長のプレイの場合、駒を動かせなくなったプレイヤーが敗者で、敗者でない側が勝者となる。無限長のプレイの勝者は、プレイ中に現れる優先度の値によって決定される。プレイ中に無限回現れた優先度のうち、最大の値が偶数ならばプレイヤー0の勝利、奇数ならばプレイヤー1の勝利となる。(偶奇が逆だったり、最大値のかわりに最小値を使う場合もある。) この偶奇性が「パリティ」の由来であろう。 パリティゲームはボレル階層の3層目に属する。したがってパリティゲームは決定的である。 n後者演算に関する二階の理論の決定可能性に関するラビンの証明では、パリティゲームに類似のゲームが暗黙的に使われ、該当ゲームの決定性も証明されている。 ナスター-タルスキの定理を使えば、パリティゲームの決定性に対するより単純な証明を与えることもできる。E.
新しい！!: マイケル・ラビンとパリティゲーム · 続きを見る »
テルアビブ大学
ャンパス テルアビブ大学（テルアビブだいがく、、جامعة تل أبيب）は、イスラエルのテルアビブにある大学。1954年に前身となるユダヤ研究機関が創立され、1956年に現在の大学に組織変更された。なお、同大学のキャンパスの内部にはディアスポラ博物館が設置されており、同大学の教職員や学生ではない一般の観光客でもディアスポラ博物館を訪問することは可能である。.
新しい！!: マイケル・ラビンとテルアビブ大学 · 続きを見る »
デイナ・スコット
デイナ・スチュアート・スコット (Dana Stewart Scott, 1932年-) はアメリカの計算機科学者、数学者、論理学者。数学的に難しい問題についての素養に基づき、非形式的だが厳格な方法で計算機科学・論理学・哲学にまたがる領域の根本的概念を明確化させてきた。オートマトン理論についての業績により1976年にチューリング賞を受賞。1970年代にはクリストファー・ストレイチーと共同でプログラム意味論への新たなアプローチを基礎付けた。様相論理、位相幾何学、圏論などでも業績を残している。 2012年現在は、カーネギーメロン大学で計算機科学と哲学と数理論理学の名誉教授を務めている。事実上引退しており、カリフォルニア州バークレー在住。2005年に創刊した学術誌 Logical Methods in Computer Science の編集長を務めている。.
新しい！!: マイケル・ラビンとデイナ・スコット · 続きを見る »
ドイツ
ドイツ連邦共和国（ドイツれんぽうきょうわこく、Bundesrepublik Deutschland）、通称ドイツ（Deutschland）は、ヨーロッパ中西部に位置する連邦制共和国である。もともと「ドイツ連邦共和国」という国は西欧に分類されているが、東ドイツ（ドイツ民主共和国）の民主化と東西ドイツの統一により、「中欧」または「中西欧」として再び分類されるようになっている。.
新しい！!: マイケル・ラビンとドイツ · 続きを見る »
ニューヨーク州
ニューヨーク州（State of New York）は、アメリカ合衆国大西洋岸中部にあり、本土アメリカ合衆国では北東部地域に位置する州。面積では第27位の州である。かつては50州で最も人口が多かったが、2010年の国勢調査現在は、カリフォルニア州、テキサス州、フロリダ州に次ぐ4位である。 南州境はニュージャージー州とペンシルベニア州、東州境はコネチカット州、マサチューセッツ州およびバーモント州に接する。西はカナダとの国境に接し、名所のナイアガラの滝がある。東南端に、アメリカ最大の都市であるニューヨーク市があり、州南部は近郊の大都市圏となっている。一方で、州北部の五大湖湖畔には古くからの工業都市であるバッファローとロチェスターがある。州都は、人口10万人足らずのオールバニである。2011年以降、州知事は民主党のアンドリュー・クオモ。.
新しい！!: マイケル・ラビンとニューヨーク州 · 続きを見る »
ベル研究所
ベル研究所（ベルけんきゅうじょ、Bell Laboratories）はもともとBell System社の研究開発部門として設立された研究所であり、現在はノキアの子会社である。「ベル電話研究所」、略して「ベル研」とも。.
新しい！!: マイケル・ラビンとベル研究所 · 続きを見る »
アリーヤー
アリーヤーもしくはアリヤー（עלייה、『上ること』の意味）は、ユダヤ人によるエレツ・イスラエル（:en:Eretz Israelイスラエルの地）への移民を言う。アリヤーはシオニズム思想の根本的な教義である。 反対に、ユダヤ人がイスラエルから移民することをイェリダー（ירידה.、『下ること』の意味）という。.
新しい！!: マイケル・ラビンとアリーヤー · 続きを見る »
アロンゾ・チャーチ
アロンゾ・チャーチ（Alonzo Church, 1903年6月14日 - 1995年8月11日）はアメリカの論理学者、数学者。ラムダ計算の創案者、「チャーチ＝チューリングのテーゼ」の提唱者として知られる。.
新しい！!: マイケル・ラビンとアロンゾ・チャーチ · 続きを見る »
アドルフ・フレンケル
アドルフ・フレンケル アドルフ・アブラハム・ハレヴィ・フレンケル（Adolf Abraham Halevi Fraenkel, 1891年2月17日 - 1965年10月15日）はドイツ出身でイスラエルに移住したユダヤ系の数学者。.
新しい！!: マイケル・ラビンとアドルフ・フレンケル · 続きを見る »
イギリス委任統治領パレスチナ
イギリス委任統治領パレスチナ（イギリスいにんとうちりょうパレスチナ、British Mandate for Palestine、الانتداب البريطاني على فلسطين、המנדט הבריטי על פלשתינה א"י）は、国際連盟によりパレスチナに創設された、イギリスが統治を行う委任統治領である。パレスチナは、16世紀以来この地を治めていたオスマン帝国から、第一次世界大戦後にイギリス帝国の委任統治下に入った領土である。イギリスは1918年にこの地の占領統治を開始し、1920年から高等弁務官による民政を開始して実質的に植民統治を開始していた。 委任統治領パレスチナの決議案は1922年7月24日に国際連盟理事会で公式に承認され、1923年9月26日に発効した.
新しい！!: マイケル・ラビンとイギリス委任統治領パレスチナ · 続きを見る »
イスラエル賞
イスラエル賞（פרס ישראל）は、イスラエル国が授与する賞であり、同国最高の栄誉ある賞とされている。 毎年、独立記念日（5月14日）にエルサレムで受賞式典が行われ、大統領、首相、クネセト（イスラエルの議会）議長、最高裁判所長官が出席する。1953年、当時の文部大臣 Ben-Zion Dinor の発案で創設され、彼自身も1958年と1973年に受賞している。.
新しい！!: マイケル・ラビンとイスラエル賞 · 続きを見る »
ウエストチェスター郡 (ニューヨーク州)
ウエストチェスター郡（Westchester County）は、アメリカ合衆国ニューヨーク州の郊外にある郡の一つ。 .
新しい！!: マイケル・ラビンとウエストチェスター郡 (ニューヨーク州) · 続きを見る »
エルサレム
ルサレムまたはイェルサレムは、イスラエルおよびパレスチナ自治区にある都市。 イスラエルはエルサレムが自国の「首都」であると宣言しているものの、国際連合など国際社会はこれを認めておらず、イスラエルの首都はテルアビブであるとみなしている。したがって、イスラエルと国交を持つ諸国も、大使館や領事館はエルサレムでなくテルアビブに置いてきた。ただし、2017年になってアメリカ合衆国のドナルド・トランプ大統領はエルサレムをイスラエルの首都であると明言し、さらにアメリカ大使館をテルアビブからエルサレムに移転する方針を明らかにした。.
新しい！!: マイケル・ラビンとエルサレム · 続きを見る »
コロンビア大学
ンビア大学（英語: Columbia University）は、米国ニューヨーク州ニューヨーク市マンハッタン区に本部を置く、アイビー・リーグに属する私立大学。正式名称は、Columbia University in the City of New York。イギリス植民地時代（1754年）に英国国王ジョージ2世の勅許によりキングスカレッジとして創立され、全米で5番目に古い。 世界屈指の名門大学としてノーベル賞受賞者を101名輩出するなど全世界から多くの優秀な研究者、留学生が集まっている。卒業生はあらゆる分野の第一線で活躍しており、これまで34名の各国の大統領・首相や28名のアカデミー賞受賞者等を輩出している。最近の著名な卒業生は米第44代大統領バラク・オバマ。 大学のモットーは、"In Thy light shall we see the light"（"In lumine Tuo videbimus lumen"）。旧約聖書・詩編36編9節（Psalm 36:9）の"in thy light shall we see light"（我らは汝の光によりて光を見ん。）を元にしている。.
新しい！!: マイケル・ラビンとコロンビア大学 · 続きを見る »
ゴードン・ムーア
魚釣りを楽しむゴードン・ムーア(2005年ごろ) ゴードン・ムーア（Gordon E. Moore, 1929年1月3日 - ）は、Intel Corporation（インテル）の設立者の一人であり、現名誉会長である（2005年現在）。.
新しい！!: マイケル・ラビンとゴードン・ムーア · 続きを見る »
ジョン・マッカーシー
ョン・マッカーシー（John McCarthy, 1927年9月4日 - 2011年10月24日）は、アメリカ合衆国の計算機科学者で認知科学者。マービン・ミンスキーとならぶ初期の人工知能研究の第一人者。「人工知能; Artificial Intelligence」という用語は彼が1956年のダートマス会議のために1955年に出した提案書で初めて使用された。また、ALGOL言語の設計に触発され、LISPというプログラミング言語を開発し、タイムシェアリングの概念を一般化させた。.
新しい！!: マイケル・ラビンとジョン・マッカーシー · 続きを見る »
スティーヴン・コール・クリーネ
ティーヴン・コール・クリーネ（Stephen Cole Kleene, 1909年1月5日 - 1994年1月25日）は、アメリカの数学者。ウィスコンシン大学マディソン校に勤め、その業績は計算機科学の理論的な基礎を築くのに貢献した。クリーネは、正規表現の発明や、アロンゾ・チャーチ、クルト・ゲーデル、アラン・チューリング、エミール・ポストらと共に帰納的関数論という数理論理学の一分野を創始したことで知られる。クリーネ代数、クリーネ閉包、クリーネの再帰定理、クリーネ不動点定理の由来になっている。クリーネはまたライツェン・エヒベルトゥス・ヤン・ブラウワーが創始した数学的直観主義に貢献した。 クリーネは自分の姓をクレーニ（（IPA））と発音していた。英語圏ではクリーニ（）、クリーン（）などと誤読されることが多く、日本ではクリーネの表記が一般的になってしまっている。 その数理論理学における傑出した業績は、英語圏の論理学者の間に、"Cleanliness is next to godliness"「清潔さは信心深さに次ぐ」をもじって"Kleeneliness is next to Gödeliness"という格言があることにも表れている。.
新しい！!: マイケル・ラビンとスティーヴン・コール・クリーネ · 続きを見る »
サハロン・シェラハ
ハロン・シェラハ（ヘブライ語名：、英語名：Saharon Shelah, 1945年7月3日 - ）は、イスラエルの数学者、論理学者。エルサレム出身。日本では「シェラー」あるいは「シェラーハ」と表記されることもある。 専門は数理論理学、とくにモデル論および公理的集合論。その他にブール代数や実関数論、集合論的位相空間論に関する仕事もある。.
新しい！!: マイケル・ラビンとサハロン・シェラハ · 続きを見る »
公開鍵暗号
公開鍵暗号（こうかいかぎあんごう、Public-key cryptography）とは、暗号化と復号に別個の鍵（手順）を用い、暗号化の鍵を公開すらできるようにした暗号方式である。 暗号は通信の秘匿性を高めるための手段だが、それに必須の鍵もまた情報なので、鍵を受け渡す過程で盗聴されてしまうというリスクがあった。共通鍵を秘匿して受け渡すには（特使が運搬するというような）コストもかかり、一般人が暗号を用いるための障害であった。この問題に対して、暗号化鍵の配送問題を解決したのが公開鍵暗号である。.
新しい！!: マイケル・ラビンと公開鍵暗号 · 続きを見る »
王立協会
イヤル・ソサイエティ（Royal Society）は、現存する最も古い科学学会。1660年に国王チャールズ2世の勅許を得て設立された。正式名称は"The President, Council, and Fellows of the Royal Society of London for Improving Natural Knowledge"（自然知識を促進するためのロンドン王立協会）。日本語訳ではロンドン王立協会（-おうりつきょうかい）、王立学会（おうりつがっかい）など。 この会は任意団体ではあるが、イギリスの事実上の学士院（アカデミー）としてイギリスにおける科学者の団体の頂点にあたる。また、科学審議会（Science Council）の一翼をになうことによって、イギリスの科学の運営および行政にも大いに影響をもっている。1782年創立の王立アイルランドアカデミーと密接な関係があり、1783年創立のエジンバラ王立協会とは関係が薄い。.
新しい！!: マイケル・ラビンと王立協会 · 続きを見る »
科学アカデミー (フランス)
科学アカデミー（かがくアカデミー、仏:Académie des sciences）は、フランス国立の学術団体で、フランス学士院を構成する団体の一つ。フランス科学アカデミー。アカデミー・デ・シアンス。.
新しい！!: マイケル・ラビンと科学アカデミー (フランス) · 続きを見る »
第一次中東戦争
一次中東戦争（だいいちじちゅうとうせんそう、מלחמת העצמאות、حرب 1948）は、1948年から1949年にかけて行われたアラブ諸国とイスラエルとの戦争のこと。パレスチナ戦争ともいう。イスラエル側の呼称は「独立戦争」（ヘブライ語：מלחמת העצמאות）で、アラブ側の呼称は「アン・ナクバ（大災害）」（アラビア語：النكبة.）である。イスラエルはこの戦争に勝利し、独立国としての地位を固めた。.
新しい！!: マイケル・ラビンと第一次中東戦争 · 続きを見る »
米国科学アカデミー
米国科学アカデミー（べいこくかがくアカデミー、、）は、アメリカ合衆国の科学アカデミーであり、民間非営利団体に位置づけられる。全米アカデミーズの一員である。 アカデミー会員は、米国における科学、技術、医学におけるプロボノとしての活動を行っている。機関誌として『米国科学アカデミー紀要』を発行する。.
新しい！!: マイケル・ラビンと米国科学アカデミー · 続きを見る »
素因数分解
素因数分解 (そいんすうぶんかい、prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。 素因数分解には次のような性質がある。.
新しい！!: マイケル・ラビンと素因数分解 · 続きを見る »
素数
素数（そすう、prime number）とは、 より大きい自然数で、正の約数が と自分自身のみであるもののことである。正の約数の個数が である自然数と言い換えることもできる。 より大きい自然数で素数でないものは合成数と呼ばれる。 一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 \mathbb Z での素数は有理素数（ゆうりそすう、rational prime）と呼ばれることもある。 最小の素数は である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。 素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。 自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。 分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2018年1月現在で知られている最大の素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2324万9425桁に及ぶ。.
新しい！!: マイケル・ラビンと素数 · 続きを見る »
素数判定
素数判定（そすうはんてい）とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。しかし多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。.
新しい！!: マイケル・ラビンと素数判定 · 続きを見る »
紛失通信プロトコル
暗号理論において、紛失通信（ふんしつつうしん、Oblivious Transfer、以下OTと記す）とは、暗号プロトコルの一種で、送信者が送信したデータのうち、受信者がどれを受信したのか、送信者が知ることができないようなプロトコルである。忘却送信ということもある。1981年にマイケル・ラビンが提案したRabin-OTが最初のOTである。 落とし戸置換(厳密には、enhanced trapdoor permutation)が存在すれば、OTが存在することが示されている。.
新しい！!: マイケル・ラビンと紛失通信プロトコル · 続きを見る »
鍵 (暗号)
暗号技術において、鍵（かぎ、key）とは、暗号アルゴリズムの手順を制御するためのデータである。 鍵は、同じ暗号方式を使用しながら利用者毎に暗号化の手順を異なるものにするために考え出されたものであるが、暗号だけではなく、デジタル署名やメッセージ認証コード（Keyed-hashなど）でも使用される。擬似乱数で用いられるシード（種）も鍵の一種である。 アルゴリズムが公開されている現代暗号においては、鍵が第三者に渡ることは、暗号文の秘匿性などが失われることを意味するので、鍵は非常に重要な役割を果たしている。.
新しい！!: マイケル・ラビンと鍵 (暗号) · 続きを見る »
非決定性有限オートマトン
非決定性有限オートマトン（）または非決定性有限状態機械（）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。.
新しい！!: マイケル・ラビンと非決定性有限オートマトン · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: マイケル・ラビンと計算複雑性理論 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
新しい！!: マイケル・ラビンと計算機科学 · 続きを見る »
IBM
IBM（アイビーエム、正式社名: International Business Machines Corporation）は、民間法人や公的機関を対象とするコンピュータ関連製品およびサービスを提供する企業である。本社はアメリカ合衆国ニューヨーク州アーモンクに所在する。世界170カ国以上で事業を展開している。.
新しい！!: マイケル・ラビンとIBM · 続きを見る »
P≠NP予想
P≠NP予想（P≠NPよそう、）は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想である。P対NP問題（PたいNPもんだい、）と呼ばれることもある。 理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年にクレイ数学研究所のミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。.
新しい！!: マイケル・ラビンとP≠NP予想 · 続きを見る »
Rabin暗号
Rabin暗号（:en:Rabin cryptosystem）とは、1979年にマイケル・ラビンが発表した公開鍵暗号である。選択平文攻撃で解読することと素因数分解問題を解くことが等価であることが証明された初の暗号である。.
新しい！!: マイケル・ラビンとRabin暗号 · 続きを見る »
RSA暗号
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。 暗号とデジタル署名を実現できる方式として最初に公開されたものである。.
新しい！!: マイケル・ラビンとRSA暗号 · 続きを見る »
暗号理論
暗号理論（あんごうりろん）の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.
新しい！!: マイケル・ラビンと暗号理論 · 続きを見る »
暗号解読
暗号解読（あんごうかいどく、Cryptanalysis）とは、暗号を解読すること、あるいは解読法に関する研究を指す。 暗号の解読とは、暗号文を作成するのに用いた秘密情報（秘密の表記法や秘密の鍵など）にアクセスすることなく、暗号文を平文に戻すことである。これに対して、秘密情報を用いて暗号文を平文に戻すことは復号といい、解読と復号は区別することが多い。但し英語の"decryption"は両者の意味を持ち区別されない（以下、秘密情報のことを"鍵"と記す）。 他人に知られたくない情報を秘匿する手段として暗号が生まれるのと同時に、秘密を暴くための暗号解読も生まれたと考えられる。 研究としての暗号解読には、暗号 (Cipher) の解読だけではなく、デジタル署名の偽造、ハッシュ関数のコリジョン探索、あるいは暗号プロトコルの解読なども含まれる。.
新しい！!: マイケル・ラビンと暗号解読 · 続きを見る »
暗号文
暗号文（あんごうぶん、ciphertext）とは、暗号化アルゴリズムの出力で、判読不能な状態になった情報のことである。復号するともとの平文になる。.
新しい！!: マイケル・ラビンと暗号文 · 続きを見る »
正規言語
正規言語（せいきげんご）または正則言語（せいそくげんご）は、以下に示す性質（いずれも等価）を満たす形式言語である。.
新しい！!: マイケル・ラビンと正規言語 · 続きを見る »
文字列探索
文字列探索 (もじれつたんさく) とは、ある文字列の中から、別のある文字列を探索することである。テキストエディタ等で必須の機能であり、これまでさまざまなアルゴリズムが考案されている。 ここでいう文字列とは、ある定まった文字集合の要素を任意に並べた系列のことである。通常、文字はアルファベット等の言語に依拠した文字セットを指すことが多いが、生物情報学における染色体の塩基配列A, T, G, Cの4文字を対象とするもののように、特定の領域に特化した応用も行われている。 正規表現にマッチする文字列の探索、と類似した問題だが、正規表現で可能なパターンに比べ検索対象を絞ることで、より高速に探索するものとして研究されている（ユーザの使うプログラムでは、検索するパターンに応じて、アルゴリズムを切り替えるものもある）。正規表現による探索については正規表現の記事を参照のこと。 近年は、暗号化された文字列を復号せずに探索する秘匿検索、圧縮テキスト中の文字列探索の研究、多国語文字列のバイト列表現に対する探索の研究、なども行われている。.
新しい！!: マイケル・ラビンと文字列探索 · 続きを見る »
数理論理学
数理論理学（mathematische Logik、mathematical logic）は、論理学（形式論理学）の数学への応用の探求ないしは論理学の数学的な解析を主たる目的とする、数学の関連分野である。局所的には数理論理学は超数学、数学基礎論、理論計算機科学などと密接に関係している。数理論理学の共通な課題としては形式体系の表現力や形式証明系の演繹の能力の研究が含まれる。 数理論理学はしばしば集合論、モデル理論、再帰理論、証明論の4つの領域に分類される。これらの領域はロジックのとくに一階述語論理や定義可能性に関する結果を共有している。計算機科学（とくに）における数理論理学の役割の詳細はこの記事には含まれていない。詳細はを参照。 この分野が始まって以来、数理論理学は数学基礎論の研究に貢献し、また逆に動機付けられてきた。数学基礎論は幾何学、算術、解析学に対する公理的な枠組みの開発とともに19世紀末に始まった。20世紀初頭、数学基礎論は、ヒルベルトのプログラムによって、数学の基礎理論の無矛盾性を証明するものとして形成された。クルト・ゲーデルとゲルハルト・ゲンツェンによる結果やその他は、プログラムの部分的な解決を提供しつつ、無矛盾性の証明に伴う問題点を明らかにした。集合論における仕事は殆ど全ての通常の数学を集合の言葉で形式化できることを示した。しかしながら、集合論に共通の公理からは証明することができない幾つかの命題が存在することも知られた。むしろ現代の数学基礎論では、全ての数学を展開できる公理系を見つけるよりも、数学の一部がどのような特定の形式的体系で形式化することが可能であるか（逆数学のように）ということに焦点を当てている。.
新しい！!: マイケル・ラビンと数理論理学 · 続きを見る »
1931年
記載なし。
新しい！!: マイケル・ラビンと1931年 · 続きを見る »
1956年
記載なし。
新しい！!: マイケル・ラビンと1956年 · 続きを見る »
1959年
記載なし。
新しい！!: マイケル・ラビンと1959年 · 続きを見る »
1975年
記載なし。
新しい！!: マイケル・ラビンと1975年 · 続きを見る »
1976年
記載なし。
新しい！!: マイケル・ラビンと1976年 · 続きを見る »
1979年
記載なし。
新しい！!: マイケル・ラビンと1979年 · 続きを見る »
1981年
この項目では、国際的な視点に基づいた1981年について記載する。.
新しい！!: マイケル・ラビンと1981年 · 続きを見る »
1987年
この項目では、国際的な視点に基づいた1987年について記載する。.
新しい！!: マイケル・ラビンと1987年 · 続きを見る »
