Введение
Альфред Вайно Ахо (родился 9 августа 1941 года) — канадский учёный в области компьютерных наук, наиболее известный своей работой над языками программирования, компиляторами и связанными с ними алгоритмами, а также своими учебниками по искусству и науке компьютерного программирования. Ахо был избран в Национальную академию инженерии в 1999 году за вклад в области алгоритмов и инструментов программирования. Он и его давний соавтор Джеффри Уллман являются лауреатами премии Тьюринга 2020 года, общепризнанной как высшая награда в области информатики. Он проводил исследования в Bell Labs с 1967 по 1991 год и вновь с 1997 по 2002 год в качестве вице-президента Научно-исследовательского центра вычислительных наук. С 1995 года он занимает должность профессора Лоуренса Гассмана в области компьютерных наук в Колумбийском университете. Он был председателем кафедры с 1995 по 1997 год и вновь весной 2003 года. В своей докторской диссертации Ахо разработал индексированные грамматики и автомат с вложенным стеком как средства расширения возможностей контекстно-свободных языков, сохраняя при этом многие их свойства разрешимости и замкнутости. Одним из применений индексированных грамматик является моделирование параллельных систем переписывания, особенно в биологических приложениях. После окончания Принстонского университета Ахо присоединился к Центру исследований вычислительных наук в Bell Labs, где разработал эффективные алгоритмы поиска регулярных выражений и сопоставления образцов строк, которые он реализовал в первых версиях Unix-утилит egrep и fgrep. Алгоритм fgrep стал известен как алгоритм Ахо-Корасика; он используется несколькими системами библиографического поиска, включая разработанную Маргарет Дж. Корасик, и другими приложениями поиска строк. В Bell Labs Ахо тесно сотрудничал со Стивом Джонсоном и Джеффри Уллманом в разработке эффективных алгоритмов для анализа и трансляции языков программирования. Стив Джонсон использовал алгоритмы восходящего разбора LALR для создания генератора синтаксического анализатора yacc, а Майкл Э. Леск и Эрик Шмидт использовали алгоритмы сопоставления образцов регулярных выражений Ахо для создания генератора лексического анализатора lex. Инструменты lex и yacc и их производные использовались для разработки фронт-эндов многих современных компиляторов языков программирования. Ахо и Уллман написали серию учебников по техникам компиляции, в которых систематизировали теорию, относящуюся к проектированию компиляторов. Их учебник 1977 года «Принципы построения компиляторов» имел изображение зеленого дракона на обложке и стал известен как «книга о зеленом драконе». В 1986 году к Ахо и Уллману присоединился Рави Сети для создания нового издания, «Книга о красном драконе» (которая ненадолго появляется в фильме 1995 года «Хакеры»), а в 2006 году — Моника Лам для создания «Книги о фиолетовом драконе». «Книги о драконах» используются как в университетских курсах, так и в качестве справочных материалов для специалистов. В 1974 году Ахо, Джон Хопкрофт и Уллман написали книгу «Проектирование и анализ компьютерных алгоритмов», в которой систематизировали некоторые из своих ранних исследований алгоритмов. Эта книга стала одной из наиболее цитируемых книг в области компьютерных наук на протяжении нескольких десятилетий и способствовала развитию алгоритмов и структур данных как центрального курса в учебной программе по информатике. Ахо также широко известен как соавтор языка программирования AWK вместе с Питером Вайнбергером и Брайаном Керниганом («A» обозначает «Aho»). По состоянию на 2010 год исследовательские интересы Ахо включают языки программирования, компиляторы, алгоритмы и квантовые вычисления. Он является частью исследовательской группы «Языки и компиляторы» в Колумбийском университете. В целом, его работы были процитированы 81 040 раз, а его индекс Хирша составляет 66 по состоянию на 8 мая 2019 года. Ахо получил множество престижных наград, в том числе медаль Джона фон Неймана IEEE и членство в Национальной инженерной академии. В 2003 году он был избран членом Американской академии искусств и наук. Он имеет почетные докторские степени Университета Ватерлоо и Университета Хельсинки, является членом Американской ассоциации содействия развитию науки, ACM, Bell Labs и IEEE. Ахо, Хопкрофт и Уллман были со-лауреатами премии C&C 2017 года, присуждаемой корпорацией NEC. Он и Уллман были названы лауреатами премии Тьюринга 2020 года 31 марта 2021 года.
Alfred Vaino Aho (born August 9, 1941) is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming. Aho was elected into the National Academy of Engineering in 1999 for his contributions to the fields of algorithms and programming tools. He and his long time collaborator Jeffrey Ullman are the recipients of the 2020 Turing Award, generally recognized as the highest distinction in computer science. He conducted research at Bell Labs from 1967 to 1991, and again from 1997 to 2002 as Vice President of the Computing Sciences Research Center. Since 1995, he has held the Lawrence Gussman Professorship in Computer Science at Columbia University. He served as chair of the department from 1995 to 1997, and again in the spring of 2003. In his PhD thesis Aho created indexed grammars and the nested stack automaton as vehicles for extending the power of context free languages, but retaining many of their decidability and closure properties. One application of indexed grammars is modelling parallel rewriting systems, particularly in biological applications. After graduating from Princeton, Aho joined the Computing Sciences Research Center at Bell Labs where he devised efficient regular expression and string pattern matching algorithms that he implemented in the first versions of the Unix tools egrep and fgrep. The fgrep algorithm has become known as the Aho–Corasick algorithm; it is used by several bibliographic search systems, including the one developed by Margaret J. Corasick, and by other string searching applications. At Bell Labs, Aho worked closely with Steve Johnson and Jeffrey Ullman to develop efficient algorithms for analyzing and translating programming languages. Steve Johnson used the bottom up LALR parsing algorithms to create the syntax analyzer generator yacc, and Michael E. Lesk and Eric Schmidt used Aho's regular expression pattern matching algorithms to create the lexical analyzer generator lex. The lex and yacc tools and their derivatives have been used to develop the front ends of many of today's programming language compilers. Aho and Ullman wrote a series of textbooks on compiling techniques that codified the theory relevant to compiler design. Their 1977 textbook Principles of Compiler Design had a green dragon on the front cover and became known as "the green dragon book". In 1986 Aho and Ullman were joined by Ravi Sethi to create a new edition, "the red dragon book" (which was briefly shown in the 1995 movie Hackers), and in 2006 also by Monica Lam to create "the purple dragon book". The dragon books are used for university courses as well as industry references. In 1974, Aho, John Hopcroft, and Ullman wrote The Design and Analysis of Computer Algorithms, codifying some of their early research on algorithms. This book became one of the most highly cited books in computer science for several decades and helped to stimulate the creation of algorithms and data structures as a central course in the computer science curriculum. Aho is also widely known for his co authorship of the AWK programming language with Peter J. Weinberger and Brian Kernighan (the "A" stands for "Aho"). as of 2010 Aho's research interests include programming languages, compilers, algorithms, and quantum computing. He is part of the Language and Compilers research group at Columbia University. Overall, his works have been cited 81,040 times and he has an h index of 66, as of May 8, 2019. Aho has received many prestigious honors, including the IEEE's John von Neumann Medal and membership in the National Academy of Engineering. He was elected a Fellow of the American Academy of Arts and Sciences in 2003. He holds honorary doctorates from the University of Waterloo, from the University of Helsinki, He is a Fellow of the American Association for the Advancement of Science, ACM, Bell Labs, and IEEE. Aho, Hopcroft, and Ullman were co recipients of the 2017 C&C Prize awarded by NEC Corporation. He and Ullman were named recipients of the 2020 Turing Award on March 31, 2021.
Преподавание
Ахо преподает в Колумбийском университете в Нью-Йорке с 1995 года. В 2003 году он был удостоен награды "Великий учитель" от Общества выпускников Колумбийского университета.