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