比浏览器更快的访问！
28 关系: 博士，可判定性，复杂性类，字串搜尋演算法，希伯来大学，以色列，弗罗茨瓦夫，德国，哥伦比亚大学，哈佛大学，公开密钥加密，因式分解，图灵奖，理查德·卡普，第二次世界大战，米勒-拉宾检验，素数，非确定有限状态自动机，計算複雜性理論，魏瑪共和國，计算机科学，达纳·斯科特，電腦科學家，P/NP问题，波兰，整数，拉比，普林斯顿大学。
博士
博士是教育機構授予的最高一級學位。如某科系哲學博士、理學博士、文學博士、教育博士、工商管理博士、管理博士。日常生活中博士學位會與姓氏相結合而被稱為某博士。而博士英文同醫生一樣是Doctor。基本上博士論文必須包含該領域創新又有深度的內容，並通過同行學者審查方能取得博士學位。 然而，醫學博士及法律博士雖稱作「博士」，這不是一般所指的學術型「博士學位」，然而在美國與PhD博士學位具備同等地位（部分國家則視為類碩士學位）。 中国古代的“博士”指专门精通某一门学问或传授经学的官名（例如漢武帝時的五经博士）。 後來衍生為對特定的某一種專門職業精通的人，比如“茶博士”、“酒博士”等，類似近代對於服務業跟製造業師傅的稱呼。.
可判定性
没有描述。
新！!: 迈克尔·拉宾和可判定性 · 查看更多 »
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新！!: 迈克尔·拉宾和复杂性类 · 查看更多 »
字串搜尋演算法
字串搜尋演算法（String searching algorithms）又稱字串比對演算法（string matching algorithms）是一种搜索算法，是字串演算法中的一類，用以試圖在一長字符串或文章中，找出其是否包含某一個或多個字符串，以及其位置。 最直觀的解法是比對，如下例中，在字符串haystack中找出字符串needle char* haystack; char* needle; int hlen, nlen, found; int i,j,k; found.
新！!: 迈克尔·拉宾和字串搜尋演算法 · 查看更多 »
希伯来大学
#重定向 耶路撒冷希伯來大學.
新！!: 迈克尔·拉宾和希伯来大学 · 查看更多 »
以色列
以色列（יִשְׂרָאֵל；），正式名称是以色列国（help；دَوْلَة إِسْرَائِيل），是位於西亚的主权国家，坐落於地中海东南岸及红海亚喀巴湾北岸，北靠黎巴嫩，东北邻叙利亚，东与约旦接壤，巴勒斯坦领土（巴勒斯坦国对其宣称主权，但局部为以色列所控制）的约旦河西岸地区和加沙地带各居东西，西南则为埃及。其领土范围不大，但地形和气候相当多样。以色列的金融及科技创新中心為特拉维夫，而耶路撒冷則为其法定首都（美國承認）、各政府机构所在地（国防部除外）及其轄下的第一大城市（特拉维夫都会圈人口最多）。以色列对耶路撒冷的主权在国际上有爭議。美国東岸时间2017年12月6日下午1時，特朗普正式在白宫外交厅宣布美国承认耶路撒冷为以色列首都。 1947年11月29日，聯合國大會建議在巴勒斯坦托管地推行分治方案。這一方案規定了新的阿拉伯和猶太國家的國界，並指定耶路撒冷及其周邊地區將為聯合國進行國際管理Harris, J. (1998) The Journal of the Society for Textual Reasoning, Vol.
新！!: 迈克尔·拉宾和以色列 · 查看更多 »
弗罗茨瓦夫
弗罗茨瓦夫（波兰语：Wrocław；德语：Breslau，中文譯為布雷斯勞、布列斯勞、洛克勞；捷克语：Vratislav；拉丁语：Wratislavia 或 Vratislavia），是波兰城市，位于波兰西南部的奥得河畔，自1999年起是下西里西亚省的省会。该市人口约为637,075人（2016年），列波兰第四大城（次于华沙、克拉科夫和罗兹），同时也是波兰仅次于华沙的第二大金融中心，在经济、文化、交通等诸多方面都在波兰具有相当重要的地位。 弗罗茨瓦夫在其城市发展史上的大部分时期内，一直是一个以多民族、多元文化为特色的城市，德意志、波兰、捷克、犹太等民族均扮演过重要角色。而德语曾长期是占有优势地位的语言，该市的德语名称布雷斯勞（Breslau）的知名度一直很高，二战以前该市曾是德国重要的工商业与文化名城之一，城市规模居全德国第六位，那時人口已达60多万。在第二次世界大战以后的领土调整和民族大迁徙中，该市是德国在战后失去的最大城市，原有的德国居民被迫西迁，而波兰东部因為割让给苏联，大批波蘭人湧入這座城市導致弗罗茨瓦夫在人口构成上基本上成为一个纯粹的波兰城市，但由于保留下来的以及战后重建的大量普鲁士、奥地利乃至波希米亚风格的建筑，该市在波兰境内仍是一个颇为独特的城市。.
新！!: 迈克尔·拉宾和弗罗茨瓦夫 · 查看更多 »
德国
德意志联邦共和国（Bundesrepublik Deutschland／），简称德国（Deutschland），是位於中西歐的联邦议会共和制国家，由16个-zh-hans:联邦州; zh-hant:邦;-组成，首都与最大城市为柏林。其国土面积约35.7万平方公里，南北距离为876公里，东西相距640公里，从北部的北海与波罗的海延伸至南部的阿尔卑斯山。气候温和，季节分明。德国人口约8,180万，为欧洲联盟中人口最多的国家，也是世界第二大移民目的地，仅次于美国。 在50万年前的舊石器時代晚期，海德堡人及其後代尼安德特人生活在今德國中部。自古典時代以來各日耳曼部族開始定居於今日德國的北部地區。公元1世紀時，有羅馬人著作的關於“日耳曼尼亞”的歷史記載。在公元4到7世紀的民族遷徙期，日耳曼部族逐漸向歐洲南部擴張。自公元10世紀起，德意志領土組成神聖羅馬帝國的核心部分。16世紀時，德意志北部地區成為宗教改革中心。在神聖羅馬帝國滅亡後，萊茵邦聯和日耳曼邦聯先後建立，1871年，在普魯士王國主導之下，多數德意志邦國統一成為德意志帝國，「德意志」開始做為國名使用。在第一次世界大戰和1918-1919年德國革命後，德意志帝國解體，議會制的威瑪共和國取而代之。1933年納粹黨獲取政權並建立獨裁統治，最終導致第二次世界大戰及系統性種族滅絕的發生。在戰敗並經歷同盟國軍事佔領後，德國分裂为德意志聯邦共和國（西德）和德意志民主共和國（東德）。在1990年10月3日重新統一成為現在的德國。国家元首为联邦总统，政府首脑則为联邦总理。 德國是世界大國之一，其國内生產總值以國際匯率計居世界第四，以購買力評價計居世界第五。其諸多工業工程和科技部門位居世界前列，例如全球馳名的德國車廠、精密部件等，為世界第三大出口國。德國為發達國家，生活水平居世界前列。德國人也以熱愛大自然聞名，都市綠化率極高，也是歐洲再生能源大國，是可持續發展經濟的樣板，除了強調環境保護與自然生態保育，在人為飼養活體的態度十分嚴謹，不但獲得大量外匯和資訊優勢，其動物保護法律管束、生命教育水準也是首屈一指的，在高等教育方面並提供免費大學教育，並具備完善的社會保障制度和醫療體系，催生出拜爾等大藥廠。 德国为1993年欧洲联盟的创始成员国之一，为申根区一部分，并于1999年推动欧元区的建立。德国亦为联合国、北大西洋公约组织、八国集团、20国集团及经济合作与发展组织成员。其军事开支总额居世界第九。 德語是歐盟境内使用人數最多的母語。德國文化的豐富層次和對世界的影響表現在其建築和美術、音樂、哲學以及電影等等。德國的文化遺產主要以老城為代表。另外國家公園和自然公園共計有上百處。.
哥伦比亚大学
纽约市哥伦比亚大学（英文：Columbia University in the City of New York；通称：哥伦比亚大学），是一所坐落于纽约市曼哈顿上城晨边高地的私立研究型大学，常春藤联盟成员。她被视作世界上最具声望的大学之一。 哥伦比亚大学最初名为国王学院（King's College），于1754年根据英国国王乔治二世颁布的王室特许状成立。她是全美历史第五悠久及纽约州最古老的高等教育机构，也是九所美国独立宣言签署前成立的殖民地学院之一。美国独立战争之后，国王学院于1784年被重新命名为哥伦比亚学院（Columbia College）。一份1787年起草的章程将学校置于一个私人董事会的管理之下。1896年，她从麦迪逊大道搬迁至她现在位于晨边高地，占地32英亩的校址，并同时被赋予了一个新名称，即“哥伦比亚大学”。哥伦比亚大学是美国大学协会的十四个创立成员之一，并且是美国第一所授予医学博士学位的大学。 大学直辖二十所学院，包括哥伦比亚学院、傅氏基金工程和应用科学学院和通识教育学院 三所本科生院。同时，许多临近的机构也附属于哥伦比亚大学，包括教师学院、巴纳德学院、协和神学院。另外，学校还与美洲犹太教神学院、巴黎政治学院和朱利亚学院拥有本科联合教育项目 。大学同时在安曼、北京、伊斯坦布尔、巴黎、孟买、里约热内卢、圣地亚哥、亚松森和内罗毕建立了哥伦比亚大学全球中心。 哥伦比亚大学是每年一度的普利策奖的颁发机构，哥伦比亚大学——包括其前身国王学院——的著名校友包括五位美国开国元勋；九位美国最高法院法官；二十位在世的亿万富翁；二十九位奥斯卡奖获得者；以及二十九位各国元首，包括三位美国总统。九十五位校友、教职工或研究人员是诺贝尔奖获得者，数量在全球所有大学中名列第五。.
新！!: 迈克尔·拉宾和哥伦比亚大学 · 查看更多 »
哈佛大学
哈佛大學（Harvard University）為一所本部坐落於-zh-hans:麻省; zh-tw:麻薩諸塞州; zh-cn:马萨诸塞州; zh-hk:麻省-劍橋市的私立研究型大學。其因歷史、學術影響力、財富等因素而獲評為世上最享負盛名的學府之一。 哈佛於1636年由當地的殖民地立法機關立案成立，迄今為全美歷史最悠久的高等學府，並擁有北美最古老的校董委員會。 其最初稱之為「新學院」，該機構為了感謝一名年輕的牧師約翰·哈佛所作出的捐贈，而改名為「哈佛學院」。雖然從沒有與任何宗教派別有正式的聯繫，但早期的學院還是以培養公理會及一位論派神職者為主要職責。可是自18世紀起，其課程與學生群體的宗教性質漸漸淡化，而19世紀的哈佛則進一步成為了的文化起源地。美國南北戰爭後，當時的校長查爾斯·艾略特將哈佛各個學術機構綜合成了一所研究型大學，並增添了小班授課以及入學考試，而這些模式同時也影響了國家的中高等教育政策。此校亦為美國大學協會其中一個原始成員，並在經濟大蕭條及二次大戰後進一步修改了課程及收生政策。後與拉德克利夫學院合併成為了男女校。 校方目前共有十所學院及一所高等研究院。這些單位偏佈鄰近各區：其本部位於劍橋的；醫學、公共衛生及牙醫學院位於波士頓的長木醫學區；而包括哈佛體育場在內的大學體育設施以及商學院則在。哈佛同時擁有龐大的資產，每年所收到的捐款回贈數目長期位列全球教育機構之首。 哈佛大學為全美最難入讀的學府之一。 學校的研究生課程較為多元化，而本科教育則主要集中在文理學範疇。校方在2007年起實行了財政援助政策，家庭年收入低於一定數目的學生獲得不同程度的學費豁免。 哈佛擁有全美最古老的圖書館系統，這同時也是全球最具規模的私立及大學圖書館系統，館藏量逾1600萬冊。 其為常春藤盟校成員之一，現共有42支參與不同運動競賽的代表隊，屬全美大學體育協會甲組。除了體育，學生的課外生活還包括各個學會所舉辦的活動。哈佛校友涵蓋8名美國總統及多國領袖與政治要員；其亦培養了62名富豪企業家及335位羅德學者，人數均為全美最多；另也有150多名諾貝爾獎得主現在或曾經在哈佛學習或工作。.
新！!: 迈克尔·拉宾和哈佛大学 · 查看更多 »
公开密钥加密
公开密钥加密（Public-key cryptography），也称为非对称加密（asymmetric cryptography），是密碼學的一種演算法，它需要兩個密钥，一個是公開密鑰，另一個是私有密鑰；一個用作加密的時候，另一個則用作解密。使用其中一個密钥把明文加密后所得的密文，只能用相對應的另一個密钥才能解密得到原本的明文；甚至連最初用來加密的密鑰也不能用作解密。由於加密和解密需要兩個不同的密鑰，故被稱為非對稱加密；不同於加密和解密都使用同一個密鑰的對稱加密。雖然兩個密鑰在数学上相关，但如果知道了其中一个，并不能憑此计算出另外一个；因此其中一个可以公开，称为公钥，任意向外發佈；不公开的密钥为私钥，必須由用戶自行嚴格秘密保管，絕不透過任何途徑向任何人提供，也不會透露給要通訊的另一方，即使他被信任。 基於公開密鑰加密的特性，它還提供數位簽章的功能，使電子文件可以得到如同在紙本文件上親筆簽署的效果。 公開金鑰基礎建設透過信任数字证书认证机构的根证书、及其使用公开密钥加密作數位簽章核發的公開金鑰認證，形成信任鏈架構，已在TLS實作並在万维网的HTTP以HTTPS、在电子邮件的SMTP以STARTTLS引入。 另一方面，信任網絡則採用去中心化的概念，取代了依賴數字證書認證機構的公鑰基礎設施，因為每一張電子證書在信任鏈中最終只由一個根證書授權信任，信任網絡的公鑰則可以累積多個用戶的信任。PGP就是其中一個例子。.
新！!: 迈克尔·拉宾和公开密钥加密 · 查看更多 »
因式分解
因式分解（factorization，factorisation，或factoring），在數學中一般理解為把一個多項式分解為兩個或多個的因式（因式亦為多項式）的過程。在這個過後會得出一堆較原式簡單的多項式的積。例如多項式x^2 -4可被因式分解為\left(x+2 \right) \left(x-2 \right)。.
新！!: 迈克尔·拉宾和因式分解 · 查看更多 »
图灵奖
图灵奖（ACM A.M. Turing Award），又譯杜林獎、A.M.图灵奖，是计算机协会（ACM）于1966年设立的獎項，专门奖励对计算机事业作出重要贡献的个人。其名称取自世界计算机科学的先驱、英国科学家、曼徹斯特大学教授艾伦·图灵（A.M. Turing），这个奖设立目的之一是纪念这位現代计算机科學的奠基者。获奖者必须是在计算机领域具有持久而重大的先进性的技术贡献。大多数获奖者是计算机科学家。是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。 图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。2014年11月13日之前图灵奖由英特尔公司以及Google公司赞助，奖金为250,000美元。2014年11月13日，虽然英特尔退出赞助，Google反而将奖金提高到1,000,000美元，和诺贝尔奖奖金相近。 每年，美国计算机协会将要求提名人推荐本年度的图灵奖候选人，并附加一份200到500字的文章，说明被提名者为什么应获此奖。任何人都可成为提名人。美国计算机协会将组成评选委员会对被提名者进行严格的评审，并最终确定当年的获奖者。.
新！!: 迈克尔·拉宾和图灵奖 · 查看更多 »
理查德·卡普
查德·曼寧·卡普（Richard Manning Karp，），計算機科學家以及計算理論家。為柏克萊加州大學教授，在演算法理論方面有卓越的貢獻，因此獲得1985年的圖靈獎，2004年的本杰明·富兰克林奖章，2008年的京都賞（Kyoto Prize）。.
新！!: 迈克尔·拉宾和理查德·卡普 · 查看更多 »
第二次世界大战
二次世界大戰（又常簡稱二次大戰、二戰、WWII等；World War II；Seconde Guerre mondiale；Zweiter Weltkrieg；Вторая мировая война；第二次世界大戰）是一次自1939年至1945年所爆發的全球性軍事衝突，整場戰爭涉及到全球絕大多數的國家，包括所有的大國，并最終分成了兩個彼此對立的軍事同盟─同盟國和軸心國。這次戰爭是人類歷史上最大規模的戰爭，動員了1億多名軍人參與這次軍事衝突。主要的參戰國紛紛宣布進入總體戰狀態，幾乎將自身國家的全部經濟、工業和科學技術應用於戰爭之上，同時也將民用與軍用的資源合併以方便統籌規劃。包括有猶太人大屠殺、南京大屠殺、戰爭中日軍對中國軍民進行細菌戰、以及最终美國對日本首次使用原子彈等事件，使得第二次世界大戰也是自有紀錄以來涉及最多大規模民眾死亡案例的軍事衝突，全部總計便將近有5,000萬至7,000萬人因而死亡，這也讓第二次世界大戰成了人類歷史上死亡人數最多的戰爭。 儘管早在1931年9月，日本便侵佔了中國的滿洲，而後建立了傀儡國家滿洲國。至1937年7月盧溝橋事變後中日更爆發了全面戰爭。不過大多數人仍多把第二次世界大戰的爆發定為1939年9月1日德國入侵波蘭開始，這次入侵行動隨即導致英國與法國向德國宣戰。然而德國在入侵波蘭後開始著手嘗試在歐洲建立一個大帝國，自1939年末期到1941年初期為止，發動一連串戰爭並藉由條約的簽署使得德國幾乎佔領了歐洲絕大部分的地區，而名義上保持中立的蘇聯在和德國簽訂《德蘇互不侵犯條約》後，也跟進侵略潮流，陸續佔領或者吞併了其在歐洲邊界的鄰近6個國家，在這之中也包括第二次世界大戰爆發時所佔領的波蘭領土。英國以及大英國協的成員國則堅持持續與軸心國繼續作戰，並分別在北非和大西洋海上發生多次軍事衝突，而這也使得英國成了歐洲地區少數仍能繼續反抗德軍入侵的主要武力之一。1941年6月，歐洲的軸心國集團決定撕毀與蘇聯的合作約定，聯合入侵蘇聯領土，這次攻勢也開始了人類歷史上規模最大的地面戰爭爆發，但也在之後讓原本幾乎統轄整個歐洲地區的軸心國被迫投入大量軍力來維持作戰優勢。到了1941年12月，已經加入軸心國的大日本帝國為了能夠在亞洲及太平洋地區獲得領導地位，陸續襲擊位于太平洋的美國統轄地區和座落於與中南半島的歐洲殖民地，很快地於西太平洋和東亞戰區獲得了主導權。 到了1942年時日本開始在一系列的海戰中戰敗，位於歐洲的軸心國也陸續於北非戰役以及斯大林格勒戰役中節節敗退，這些都迫使軸心國停下進攻的腳步。1943年時，義大利法西斯政權在西西里島戰役中面對同盟國部隊嚴重失利，另一方面德軍在库尔斯克会战戰敗後失去對於東歐的領導地位，同時美國也在太平洋戰區中獲得了一連串的勝利，自此軸心國集團逐漸失去主導權並開始嘗試將佈署於各地的前線部隊進行戰略性的撤退。到了1944年時，盟軍決定登陸法國以開闢第二戰場，而蘇聯除了成功收復過去被佔領的領土外，也開始轉往進攻德國與其同盟國家的土地。在蘇聯和波蘭部隊共同攻入柏林後，第二次世界大戰歐洲戰區最終在1945年5月8日德國投降的情況下宣告結束。而另一方面美國在1944年和1945年成功擊敗了日本海軍部隊並陸續佔領了數個重要的西太平洋島嶼，這使得日本列島隨時面臨同盟國部隊入侵的危機。最後在美軍分別於廣島市和長崎市投下原子彈並造成大量日本平民死亡。1945年8月8日蘇聯進攻日本控制下的中國東北地區，8月14日日本跟進宣佈願意接受無條件投降的條件，而隨著亞洲戰事的停息也意味著第二次世界大戰正式結束。 1945年時第二次世界大戰以同盟國勝利宣告結束，然而二次大戰對世界影響極為深遠，改變了往後世界的政治版圖和社會結構，特別是戰敗的軸心國集團被迫接受同盟國的安排。1945年10月24日聯合國亦宣告成立，期望能夠促進各國合作並防止未來的軍事衝突；同時戰勝的盟軍各國，也紛紛在聯合國各個機構中擔任重要職位，特別是以美國、蘇聯、中國、英國和法國5個國家為首成立聯合國聯合國安全理事會的常任理事國，主導著世界的秩序.
新！!: 迈克尔·拉宾和第二次世界大战 · 查看更多 »
米勒-拉宾检验
米勒-拉賓質數判定法是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯來大學的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。.
新！!: 迈克尔·拉宾和米勒-拉宾检验 · 查看更多 »
素数
質--數（Prime number），又称素--数，指在大於1的自然数中，除了1和該数自身外，無法被其他自然数整除的数（也可定義為只有1與該數本身两个正因数的数）。大於1的自然數若不是質數，則稱之為合數。例如，5是個質數，因為其正因數只有1與5。而6則是個合數，因為除了1與6外，2與3也是其正因數。算術基本定理確立了質數於數論裡的核心地位：任何大於1的整數均可被表示成一串唯一質數之乘積。為了確保該定理的唯一性，1被定義為不是質數，因為在因式分解中可以有任意多個1（如3、1×3、1×1×3等都是3的有效因數分解）。 古希臘數學家歐幾里得於公元前300年前後證明有無限多個質數存在（欧几里得定理）。現時人們已發現多種驗證質數的方法。其中試除法比較簡單，但需時較長：設被測試的自然數為n，使用此方法者需逐一測試2與\sqrt之間的整數，確保它們無一能整除n。對於較大或一些具特別形式（如梅森數）的自然數，人們通常使用較有效率的演算法測試其是否為質數（例如277232917-1是直至2017年底為止已知最大的梅森質數）。雖然人們仍未發現可以完全區別質數與合數的公式，但已建構了質數的分佈模式（亦即質數在大數時的統計模式）。19世紀晚期得到證明的質數定理指出：一個任意自然數n為質數的機率反比於其數位（或n的對數）。 許多有關質數的問題依然未解，如哥德巴赫猜想（每個大於2的偶數可表示成兩個素數之和）及孿生質數猜想（存在無窮多對相差2的質數）。這些問題促進了數論各個分支的發展，主要在於數字的解析或代數方面。質數被用於資訊科技裡的幾個程序中，如公鑰加密利用了難以將大數分解成其質因數之類的性質。質數亦在其他數學領域裡形成了各種廣義化的質數概念，主要出現在代數裡，如質元素及質理想。.
非确定有限状态自动机
在计算理论中，非确定有限状态自动机或非确定有限自动机（NFA）是对每个状态和输入符号对可以有多个可能的下一个状态的有限状态自动机。这区别于确定有限状态自动机（DFA），它的下一个可能状态是唯一确定的。尽管DFA和NFA有不同的定义，在形式理论中可以证明它们是等价的；就是说，对于任何给定NFA，都可以构造一个等价的DFA，反之亦然：通过使用幂集构造。两种类型的自动机只识别正则语言。非确定有限自动机有时被称为有限类型的子移位（subshift）。非确定有限状态自动机可推广为概率自动机，它为每个状态转移指派概率。 非确定有限自动机是Michael O. Rabin和Dana Scott在1959年介入的，他们证明了它与确定自动机的等价性。.
新！!: 迈克尔·拉宾和非确定有限状态自动机 · 查看更多 »
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
新！!: 迈克尔·拉宾和計算複雜性理論 · 查看更多 »
魏瑪共和國
威瑪共和國（Weimarer Republik）指1918年至1933年採用共和憲政政体的德国，于德意志帝國在第一次世界大战中战败、霍亨索伦王朝崩溃后成立。由於這段時間施行的宪法（一般称之为《威瑪憲法》）是在憲法召开的国民议会上通过的，因而得此名稱。其使用的國名為「德意志國」（Deutsches Reich）。「威瑪共和」这一稱呼是后世历史学家的称呼，从来不是政府的正式用名。有如現在的法蘭西共和國算是第五共和國，共和是針對政權的說明。 威瑪共和是德国历史上第一次走向共和的嘗試，于德国十一月革命后而生，因阿道夫·希特勒及纳粹党在1933年上台执政而结束。虽然1919年的威瑪共和宪法在第二次世界大战结束前在法律上仍然有效，但納粹黨政府在1933年采取的一体化（Gleichschaltung）政策已经彻底破坏了共和国的民主制度，所以魏玛共和国在1933年已经名存实亡。.
新！!: 迈克尔·拉宾和魏瑪共和國 · 查看更多 »
计算机科学
计算机科学用于解决信息与计算的理论基础，以及实现和应用它们的实用技术。 计算机科学（computer science，有时缩写为CS）是系统性研究信息与计算的理论基础以及它们在计算机系统中如何与应用的实用技术的学科。 它通常被形容为对那些创造、描述以及转换信息的算法处理的系统研究。计算机科学包含很多分支领域；有些强调特定结果的计算，比如计算机图形学；而有些是探討计算问题的性质，比如计算复杂性理论；还有一些领域專注于怎样实现计算，比如程式語言理論是研究描述计算的方法，而程式设计是应用特定的程式語言解决特定的计算问题，人机交互则是專注于怎样使计算机和计算变得有用、好用，以及随时随地为人所用。 有时公众会误以为计算机科学就是解决计算机问题的事业（比如信息技术），或者只是与使用计算机的经验有关，如玩游戏、上网或者文字处理。其实计算机科学所关注的，不仅仅是去理解实现类似游戏、浏览器这些软件的程序的性质，更要通过现有的知识创造新的程序或者改进已有的程序。 尽管计算机科学（computer science）的名字里包含计算机这几个字，但实际上计算机科学相当数量的领域都不涉及计算机本身的研究。因此，一些新的名字被提议出来。某些重点大学的院系倾向于术语计算科学（computing science），以精确强调两者之间的不同。丹麦科学家Peter Naur建议使用术语"datalogy"，以反映这一事实，即科学学科是围绕着数据和数据处理，而不一定要涉及计算机。第一个使用这个术语的科学机构是哥本哈根大学Datalogy学院，该学院成立于1969年，Peter Naur便是第一任教授。这个术语主要被用于北欧国家。同时，在计算技术发展初期，《ACM通讯》建议了一些针对计算领域从业人员的术语：turingineer，turologist，flow-charts-man，applied meta-mathematician及applied epistemologist。 三个月后在同样的期刊上，comptologist被提出，第二年又变成了hypologist。 术语computics也曾经被提议过。在欧洲大陆，起源于信息（information）和数学或者自动（automatic）的名字比起源于计算机或者计算（computation）更常见，如informatique（法语），Informatik（德语），informatika（斯拉夫语族）。 著名计算机科学家Edsger Dijkstra曾经指出：“计算机科学并不只是关于计算机，就像天文学并不只是关于望远镜一样。”（"Computer science is no more about computers than astronomy is about telescopes."）设计、部署计算机和计算机系统通常被认为是非计算机科学学科的领域。例如，研究计算机硬件被看作是计算机工程的一部分，而对于商业计算机系统的研究和部署被称为信息技术或者信息系统。然而，现如今也越来越多地融合了各类计算机相关学科的思想。计算机科学研究也经常与其它学科交叉，比如心理学，认知科学，语言学，数学，物理学，统计学和经济学。 计算机科学被认为比其它科学学科与数学的联系更加密切，一些观察者说计算就是一门数学科学。 早期计算机科学受数学研究成果的影响很大，如Kurt Gödel和Alan Turing，这两个领域在某些学科，例如数理逻辑、范畴论、域理论和代数，也不断有有益的思想交流。.
新！!: 迈克尔·拉宾和计算机科学 · 查看更多 »
达纳·斯科特
达纳·斯图尔特·斯科特（Dana Stewart Scott，），美国科学家，研究领域涉及计算机科学、数学和哲学，1976年图灵奖得主。.
新！!: 迈克尔·拉宾和达纳·斯科特 · 查看更多 »
電腦科學家
電腦科學家（Computer scientist）是指一類具有資深電腦科學知識，並從事相關研究的人物。電腦科學家通常從事計算與資訊理論方面的研究，有時也關注這些理論在電腦系統中的應用。 與電腦工程師相對，電腦科學家通常對電腦系統的理論，而非實作，更加感興趣，儘管有時電腦科學家的工作也涉及到硬體系統。電腦科學家通常會對電腦科學的某一分支進行深入研究，但是這些分支都建立在對計算系統的理論研究上。.
新！!: 迈克尔·拉宾和電腦科學家 · 查看更多 »
P/NP问题
P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和相对独立地提出了下面的问题，即复杂度类P和NP是否是恒等的（P.
新！!: 迈克尔·拉宾和P/NP问题 · 查看更多 »
波兰
波兰共和国（Rzeczpospolita Polska），简称波兰，是位於中欧的共和制国家，北面濒临波罗的海，西面与德国接壤，南部与捷克和斯洛伐克为邻，乌克兰和白俄罗斯在东，东北部和立陶宛及俄罗斯加里宁格勒州接壤。面積312,679平方公里，位居歐洲第十；人口約3,863萬人，位居歐洲第九。目前為欧盟、北约、联合国、经济合作与发展组织、世贸组织等國際組織的成員。.
整数
整数，是序列中所有的数的统称，包括负整数、零（0）与正整数。和自然數一樣，整數也是一個可數的無限集合。這個集合在数学上通常表示粗體Z或\mathbb，源于德语单词Zahlen（意为“数”）的首字母。 在代數數論中，這些屬於有理數的一般整數會被稱為有理整數，用以和高斯整數等的概念加以區分。.
拉比
拉比（, Rabbi），有時也寫作辣彼，是猶太人的特別階層，主要為有学问的学者，是老師，也是智者的象徵。猶太人的拉比社會功能廣泛，尤其在宗教擔當重要角色，為許多猶太教儀式的主持。因此，拉比的社會地位十分尊崇，連君王也經常邀請拉比進宮教導。在猶太人的宗教經典《塔木德》，就經常提及拉比的事蹟。 拉比是老师的意思，是智者的象征，是「可以去请教的人」，他们经常与常人接触，解答他们的疑惑。他们是一群观察生活，思考生活从而获得智慧的人。.
普林斯顿大学
普林斯顿大学（Princeton University），又译普林斯敦大学，常被直接称为普林斯顿，是一所位於美国新泽西州普林斯顿的私立研究型大学，现为八所常春藤盟校之一。 普林斯顿历史悠久。它成立于1746年，是九所在美国革命前成立的殖民地学院之一，同时也是美国第四古老的高等教育机构。其在1747年移至纽瓦克，最终在1756年搬到了现在的普林斯顿，并于1896年正式改名为“普林斯顿大学”。虽然其旧校名是“新泽西学院”，但它与今天位于邻近的尤因镇（Ewing Township）的“新泽西学院”没有任何关联。此外虽然它最初是长老制的教育机构，但学校从没有跟任何宗教机构有直接的联系，而现在对学生亦无任何宗教上的要求。 普林斯顿现提供各种有关人文、自然科学、社会科学及工程学的本科及研究生课程；它并没有医学院、法学院、神学院及商学院，但能在政治及工程上提供专业课程。大学也与普林斯顿高等研究院及普林斯顿宗教学校有联谊。至今，已经有63位诺贝尔奖得主、17名美国国家科学奖章得主，14名菲尔兹奖得主，13名图灵奖得主，及3名美国国家人文奖章夺得人曾经或现为普林斯顿大学的毕业生或教职员。另外，普林斯顿也是获得最多捐款的学术机构之一。.
新！!: 迈克尔·拉宾和普林斯顿大学 · 查看更多 »
