Альфред Ахо

Альфред Вайно Ахо (родился 9 августа 1941 г.) - канадский ученый-компьютерщик, наиболее известный своими работами над языками программирования , компиляторами и связанными с ними алгоритмами, а также своими учебниками по искусству и науке компьютерного программирования. [2] [3] [4] Он и его давний соратник Джеффри Уллман являются лауреатами Премии Тьюринга 2020 года , которая обычно считается высшей наградой в области компьютерных наук . [5]

Альфред Ахо
AlfredAhoPortrait.jpg
Родившийся
Альфред Вайно Ахо

( 1941-08-09 )9 августа 1941 г. (79 лет)
Национальность Канадский
американец
Альма матер
Известен
Награды
Научная карьера
Поля Информатика
Учреждения Колумбийский университет
Тезис Индексированные грамматики: расширение контекстно-свободных грамматик  (1968)
Докторант Джон Хопкрофт [1]

Редактировать

Aho получил BASc. (1963) получил степень магистра инженерной физики в Университете Торонто , затем степень магистра (1965) и доктора философии. (1967) по специальности «Электротехника / информатика» в Принстонском университете . [6] Он проводил исследования в Bell Labs с 1967 по 1991 год, а затем с 1997 по 2002 год в качестве вице-президента Исследовательского центра компьютерных наук. [7] С 1995 года он занимал должность профессора Лоуренса Гассмана в области компьютерных наук в Колумбийском университете . Он занимал должность заведующего кафедрой с 1995 по 1997 год и снова весной 2003 года. [8]

В своей докторской диссертации Ахо создал индексированные грамматики [9] и автомат с вложенным стеком [10] как средства расширения возможностей контекстно-свободных языков , но сохранив многие из их свойств разрешимости и замкнутости. Одним из приложений индексированных грамматик является моделирование систем параллельной перезаписи [11], особенно в биологических приложениях. [12]

После окончания Принстона Ахо присоединился к Исследовательскому центру вычислительных наук в Bell Labs, где он разработал эффективные алгоритмы регулярного выражения и сопоставления строковых шаблонов, которые он реализовал в первых версиях инструментов Unixegrep и fgrep. fgrepАлгоритм стал известен как алгоритм Ахо-Corasick ; он используется несколькими библиографическими поисковыми системами, включая систему, разработанную Маргарет Дж. Корасик , и другими приложениями для поиска по строкам . [13]

В Bell Labs Ахо тесно сотрудничал со Стивом Джонсоном и Джеффри Уллманом над разработкой эффективных алгоритмов анализа и перевода языков программирования. [14] Стив Джонсон использовал восходящие алгоритмы синтаксического анализа LALR для создания генератора синтаксического анализатора yacc , [15] а Майкл Э. Леск и Эрик Шмидт использовали алгоритмы сопоставления с образцом регулярных выражений Ахо для создания генератора лексического анализатора lex. . [16] Инструменты lex и yacc и их производные использовались для разработки внешних интерфейсов многих современных компиляторов языков программирования. [17]

Ахо и Уллман написали серию учебников по методам компиляции, которые систематизировали теорию, относящуюся к проектированию компиляторов. Их учебник 1977 года « Принципы проектирования компиляторов» имел на обложке зеленый дракон и стал известен как «книга зеленого дракона». В 1986 году к Ахо и Уллману присоединился Рави Сетхи, чтобы создать новое издание, «книгу красного дракона» (которая была кратко показана в фильме 1995 года « Хакеры» ), а в 2006 году также Моника Лам для создания « книги фиолетового дракона ». Книги о драконах используются для университетских курсов, а также в качестве справочников по отрасли. [18]

В 1974 году Ахо, Джон Хопкрофт и Ульман написали « Дизайн и анализ компьютерных алгоритмов» , систематизируя некоторые из своих ранних исследований алгоритмов. Эта книга стала одной из самых цитируемых книг по информатике на несколько десятилетий и помогла стимулировать создание алгоритмов и структур данных в качестве центрального курса в учебной программе по информатике. [19]

Ахо также широко известен своим соавтором языка программирования AWK с Питером Дж. Вайнбергером и Брайаном Керниганом («А» означает «Ахо»). [20] По состоянию на 2010 г.Научные интересы Ахо включают языки программирования, компиляторы, алгоритмы и квантовые вычисления . Он является членом исследовательской группы «Язык и компиляторы» Колумбийского университета. [21]

В целом его работы были процитированы 81040 раз, а его индекс Хирша по состоянию на 8 мая 2019 г. составил 66. [22]

Ахо получил множество престижных наград, в том числе IEEE «S Джона фон Неймана медали и членство в Национальной академии наук . Он был избран членом в Американской академии искусств и наук в 2003 году [23] Он имеет почетные докторские из Университета Ватерлоо , [24] из Университета Хельсинки , [24] и из Университета Торонто . [25] Он является членом Американской ассоциации развития науки , ACM , Bell Labs и IEEE . [19]

Ахо дважды занимал пост председателя Консультативного комитета Управления компьютерных и информационных наук и инженерии Национального научного фонда. Он был бывшим президентом Специальной группы ACM по алгоритмам и теории вычислимости . [26] Ахо, Хопкрофт и Ульман были соучредителями премии C&C 2017, присужденной корпорацией NEC . [27] Он и Ульман были названы лауреатами Премии Тьюринга 2020 года 31 марта 2021 года. [5]

Редактировать

Ахо преподавал в Колумбийском университете в Нью-Йорке с 1995 года. В 2003 году он получил премию «Великий учитель» Общества выпускников Колумбии [28].

Редактировать

  • А.В. Ахо, Дж. Д. Ульман , Теория синтаксического анализа, перевода и компиляции, Vol. 1, Разбор. Прентис Холл, 1972. ISBN  0-13-914556-7
  • А.В. Ахо (ред.) Токи в теории вычислений. Прентис Холл, 1973. ISBN  0-13-195651-5 [29]
  • А.В. Ахо, Дж. Д. Ульман , Теория синтаксического анализа, перевода и компиляции, Vol. 2, Составление. Прентис-Холл, 1973. ISBN  978-0-13-914564-3
  • А. В. Ахо, Дж. Э. Хопкрофт , Дж. Д. Ульман , Разработка и анализ компьютерных алгоритмов. Аддисон-Уэсли, 1974. ISBN  0-201-00023-7
  • А. В. Ахо и Дж. Д. Ульман , Принципы проектирования компиляторов. Аддисон-Уэсли, 1977. ISBN  0-201-00022-9
  • А. В. Ахо, Дж. Э. Хопкрофт , Дж. Д. Ульман , Структуры данных и алгоритмы. Аддисон-Уэсли, 1983. ISBN  0-201-00023-7
  • А. В. Ахо, Р. Сетхи , Дж. Д. Уллман , Компиляторы: принципы, методы и инструменты . Аддисон-Уэсли, Рединг, Массачусетс, 1986. ISBN  0-201-10088-6
  • А. В. Ахо, Б. В. Керниган и П. Дж. Вайнбергер , Язык программирования AWK. Аддисон-Уэсли, 1988. ISBN  978-0-201-07981-4
  • А. В. Ахо, Дж. Д. Ульман , Основы компьютерных наук . WH Freeman / Computer Science Press, 1992. ISBN  978-0-7167-8233-9 [30] [31]
  • А. В. Ахо, М. С. Лам , Р. Сетхи и Дж. Д. Уллман , Компиляторы: принципы, методы и инструменты , второе издание. Аддисон-Уэсли, 2007. ISBN  978-0-321-48681-3

Редактировать

  1. Альфред Вайно Ахо в проекте « Математическая генеалогия»
  2. ^ Ахо, А .; Готтлоб, Г. (2014). «Место в первом ряду редакционной трансформации коммуникаций ». Коммуникации ACM . 57 (4): 5. DOI : 10,1145 / 2582611 . S2CID  21553189 .
  3. ^ Ахо, А.В. (1990). «Алгоритмы поиска паттернов в строках». Справочник по теоретической информатике . MIT Press. С. 255–300.
  4. Интервью Computerworld с Альфредом В. Ахо. Архивировано 29 мая 2008 г. в Wayback Machine.
  5. ^ a b Премия ACM Turing награждает новаторов, которые сформировали основы компиляторов языков программирования и алгоритмов . Проверено 31 марта 2021 года.
  6. ^ Создание надежных программ из ненадежных программистов [PDF], Excellentia
  7. ^ Фитчард, Кевин (31 марта 2021 г.). «Аль Ахо из Bell Labs и Джеффри Уллман удостоены престижной премии Тьюринга» . Nokia Bell Labs . Проверено 3 апреля 2021 года .
  8. ^ «Профиль и подробные достижения группы B, получивших приз C&C 2017» (PDF) . Фонд NEC C&C .
  9. ^ Ахо, А.В. (1968). «Индексированные грамматики --- расширение контекстно-свободных грамматик». Журнал ACM . 15 (4): 647–671. DOI : 10.1145 / 321479.321488 . S2CID  9539666 .
  10. ^ Ахо, А.В. (1969). «Вложенные автоматы стека». Журнал ACM . 16 (3): 383–406. DOI : 10.1145 / 321526.321529 . S2CID  685569 .
  11. ^ Рамбоу, Оуэн; Сатта, Джорджио (28 июля 1999 г.). «Независимый параллелизм в системах конечного копирования и параллельной перезаписи» . Теоретическая информатика . 223 (1–2): 87–120. DOI : 10.1016 / S0304-3975 (97) 00190-4 . ISSN  0304-3975 .
  12. ^ Кулик, Карел; Майбаум, TSE (1974). Loeckx, Жак (ред.). «Системы параллельной перезаписи на терминах» . Автоматы, языки и программирование . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 14 : 495–510. DOI : 10.1007 / 978-3-662-21545-6_38 . ISBN 978-3-662-21545-6.
  13. ^ Ахо, Альфред V .; Корасик, Маргарет Дж. (Июнь 1975 г.). «Эффективное сопоставление строк: помощь в библиографическом поиске». Коммуникации ACM . 18 (6): 333–340. DOI : 10.1145 / 360825.360855 . S2CID  207735784 .
  14. ^ Ахо, А.В.; Джонсон, Южная Каролина; Ульман, JD (1977). «Генерация кода для выражений с общими подвыражениями». Журнал ACM . 24 : 146–160. DOI : 10.1145 / 321992.322001 . S2CID  2614214 .
  15. ^ Моррис, Ричард (1 октября 2009 г.). «Стивен Кертис Джонсон: Компьютерщик недели» . Программное обеспечение Red Gate . Проверено 19 января 2018 года .
  16. ^ Lesk, ME; Шмидт, Э. «Лекс - генератор лексического анализатора» . Проверено 16 августа 2010 года .
  17. ^ Левин, Джон Р .; Мейсон, Тони; Браун, Дуг (1992). lex & yacc (2-е изд.). О'Рейли . pp.  1 â € «2. ISBN 1-56592-000-7.
  18. ^ "DYOL: Создайте свой собственный язык - корпус - Dragon Books - Purple Dragon" . slebok.github.io . Проверено 3 апреля 2021 года .
  19. ^ а б Ибараки, Стивен . «Джеффри Ульман и Альфред Ахо, обладатели премии ACM AMTuring 2020» . forbes.com . Проверено 3 апреля 2021 года . CS1 maint: обескураженный параметр ( ссылка )
  20. ^ Ахо, А.В.; Керниган, BW; Weinberger, PJ (1979). «Awk - язык сканирования и обработки шаблонов». Программное обеспечение: практика и опыт . 9 (4): 267. CiteSeerX  10.1.1.80.4787 . DOI : 10.1002 / spe.4380090403 . S2CID  29399630 .
  21. ^ http://landc.cs.columbia.edu/
  22. ^ "Google Scholar Record для Альфреда Ахо" .
  23. ^ "Книга членов, 1780-2010: Глава A" (PDF) . Американская академия искусств и наук. Архивировано 10 мая 2011 года (PDF) . Проверено 6 апреля 2011 года .
  24. ^ а б "DLS - Альфред Ахо" . Школа компьютерных наук Черитон . 16 февраля 2017 . Проверено 3 апреля 2021 года .
  25. ^ Сделай, Лиз. " ' Nobel Prize вычисления:' U Т Engineering выпускником Ахо получает AM Turing Award" . utoronto.ca . Проверено 3 апреля 2021 года .
  26. ^ «Краткое подавление в США доказательств возбуждает гнев» . Нью-Йорк Таймс . 17 февраля 1987 . Проверено 10 ноября 2015 г. - через Safari.
  27. ^ «Церемония награждения C&C 2017» . Фонд NEC C&C . Проверено 3 апреля 2021 года .
  28. ^ «Смотрите: компьютерный ученый Альфред Ахо» . Фонд Саймонса . 18 июля 2013 . Проверено 3 апреля 2021 года .
  29. ^ Токи в теории вычислений, под редакцией Альфреда В. Ахо. Соавторы: Рональд В. Книга [и другие] . worldcat.org . OCLC  976868524 . Проверено 1 апреля 2021 года .
  30. ^ Основы информатики . worldcat.org . OCLC  24669768 . Проверено 1 апреля 2021 года .
  31. ^ «Основы информатики» . worldcat.org . Проверено 1 апреля 2021 года .

Редактировать