Перейти до вмісту

Річард Ліптон

Матеріал з Вікіпедії — вільної енциклопедії.
Річард Ліптон
Народився6 вересня 1946(1946-09-06)[1] (79 років) Редагувати інформацію у Вікіданих
Місце проживанняАтланта Редагувати інформацію у Вікіданих
Країна США Редагувати інформацію у Вікіданих
Діяльністьінформатик, викладач університету, математик Редагувати інформацію у Вікіданих
Alma materКарнегі-Меллон
ЗакладТехнологічний інститут Джорджії Редагувати інформацію у Вікіданих
Науковий ступіньдокторський ступінь[2]
Науковий керівникDavid Parnasd Редагувати інформацію у Вікіданих
Аспіранти, докторантиАві Віґдерсон
Ден Боне
Vijaya Ramachandrand[3]
Chee-Keng Yapd[3]
Daniel Philip Loprestid[3]
Anastasios Viglasd[3]
Benjamin Brandon Gumd[3]
Arvin R. Parkd[3]
James Harold Shawd[3]
Тімоті Бадд[3]
Hana Galperind[3]
Gopalakrishnan Vijayand[3]
Stephen C. Northd[3]
Dimitrios Serpanosd[3]
Krishnaswamy Balasubramaniand[3]
Danupon Nanongkaid[3]
Shiva Kintalid[3]
Nisheeth K. Vishnoid Редагувати інформацію у Вікіданих
ЧленствоАмериканська академія мистецтв і наук
Національна інженерна академія США
Association for Computing Machinery[4] Редагувати інформацію у Вікіданих
Нагороди
Особ. сторінкаscs.gatech.edu/people/richard-lipton Редагувати інформацію у Вікіданих
У Вікіпедії є статті про інших людей із прізвищем Ліптон.

Річард Джей Ліптон (народився 6 вересня 1946 року) — американо-південноафриканський інформатик, який працює в галузі теорії комп'ютерних наук, криптографії та ДНК-комп'ютингу (обчислень). Р. Ліптон є заступником декана з наукових досліджень, професором та завідувачем кафедри обчислювальної техніки Фредеріка Дж. Стейрі у коледжі обчислювальної техніки Технологічного інституту штату Джорджія.

Теорема Карпа–Ліптона

[ред. | ред. код]

У 1980 році разом з Річардом М. Карпом, Ліптон довів, що якщо задача здійсненності булевих формул (SAT) може бути вирішена за допомогою логічних схем з поліноміальним числом логічних вентилів, то поліноміальна ієрархія зводиться до свого другого рівня.

Оцінка розміру запиту

[ред. | ред. код]

Ліптон та Дж. Ноутон представили адаптивний алгоритм випадкової вибірки для запитів до бази даних[5][6], який застосовується до будь-якого запиту, для якого відповіді на запит можуть бути розділені на несуміжні підмножини. На відміну від більшості алгоритмів оцінки вибірки, які статично визначають кількість необхідних вибірок, їх алгоритм визначає кількість вибірки на основі розмірів вибірки та прагне підтримувати постійний час роботи (на відміну від лінійного за кількістю вибірки).

Нагороди та почесні звання

[ред. | ред. код]

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]

Посилання

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. ↑ SNAC — 2010.
  2. ↑ Deutsche Nationalbibliothek Record #142572888 // Gemeinsame Normdatei — 2012—2016.
  3. ↑ а б в г д е ж и к л м н п р с Математичний генеалогічний проєкт — 1997.
  4. ↑ https://awards.acm.org/fellows/award-recipients
  5. ↑ Richard J. Lipton, Jeffrey F. Naughton (1990) «Query Size Estimation By Adaptive Sampling», «PODS '90: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems»
  6. ↑ Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider (1990) «SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data»
  7. ↑ ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory. Association for Computing Machinery. 15 вересня 2014. Архів оригіналу за вересень 20, 2014. Процитовано квітень 7, 2018.
Отримано з https://uk.wikipedia.org/w/index.php?title=Річард_Ліптон&oldid=43283040