Alfred Aho

Alfred Aho
Geboren
Alfred Vaino Aho

9. August 1941 (Alter 80))
Timmins, Ontario, Kanada
Staatsangehörigkeit kanadisch
amerikanisch
Alma Mater
Bekannt für
Auszeichnungen
Wissenschaftliche Karriere
Felder Informatik
Institutionen Universität von Columbia
These Indexierte Grammatiken: Eine Erweiterung kontextfreier Grammatiken (1968)
Doktorand John Hopcroft[1]
Doktorand Krysta SVore

Alfred Vaino Aho (Geboren am 9. August 1941) ist ein Kanadier Informatiker Am bekanntesten für seine Arbeit an Programmiersprachen, Compilerund verwandte Algorithmen und seine Lehrbücher zur Kunst und Wissenschaft der Computerprogrammierung.[2][3][4]

Aho wurde in die gewählt Nationale Akademie des Ingenieurwesens 1999 für seine Beiträge zu den Feldern von Algorithmen und Programmierwerkzeugen.

Er und sein langjähriger Mitarbeiter Jeffrey Ullman sind die Empfänger des 2020 Turing Award, allgemein als die höchste Unterscheidung in anerkannt Informatik.[5]

Karriere

AHO erhielt einen B.A.Sc. (1963) in technischer Physik aus dem Universität von Torontodann ein M.A. (1965) und Ph.D. (1967) in Elektrotechnik/Informatik aus Princeton Universität.[6] Er führte Forschungen an Bell Labs Von 1967 bis 1991 und erneut von 1997 bis 2002 als Vizepräsident des Computing Sciences Research Center.[7] Seit 1995 hielt er die Lawrence Gussman -Professur in der Professur in Informatik bei Universität von Columbia. Von 1995 bis 1997 und im Frühjahr 2003 war er Vorsitzender der Abteilung.[8]

In seiner Doktorarbeit erzeugt Aho erzeugt indizierte Grammatiken[9] und die Automatikschachtelstapel[10] als Fahrzeuge zur Ausweitung der Leistung von Kontextfreie Sprachen, aber viele ihrer Dekidabilitäts- und Verschlusseigenschaften beibehalten. Eine Anwendung indizierter Grammatik ist die Modellierung paralleler Umschreibungssysteme,[11] insbesondere in biologischen Anwendungen.[12]

Nach seinem Abschluss in Princeton trat AHO dem Forschungszentrum für Computer Sciences in Bell Labs bei, wo er effizient entwickelte regulären Ausdruck und String-Muster-Matching-Algorithmen, die er in den ersten Versionen der implementierten Unix Werkzeug Egrep und FGREP. Das FGREP Algorithmus ist als die bekannt geworden AHO-Corasick-Algorithmus; Es wird von mehreren bibliografischen Suchsystemen verwendet, darunter die von Margaret J. Corasick entwickelten und andere Suchanwendungen.[13]

In Bell Labs arbeitete AHO eng mit Steve Johnson und Jeffrey Ullman Entwicklung effizienter Algorithmen zur Analyse und Übersetzung von Programmiersprachen.[14] Steve Johnson verwendete die Bottom-up-LALR-Parsing-Algorithmen, um den Syntax-Analyzer-Generator zu erstellen yacc,[15] und Michael E. Lesk und Eric Schmidt Verwendete AHOs reguläre Expressions-Muster-Anpassungsalgorithmen, um den Lexikalanalysatorgenerator zu erstellen Lex.[16] Die Lex- und YACC -Tools und ihre Derivate wurden verwendet, um die vorderen Enden vieler der heutigen Programmiersprache zu entwickeln.[17]

Aho und Ullman schrieben eine Reihe von Lehrbüchern zum Zusammenstellen von Techniken, die die für das Compiler -Design relevante Theorie kodifizierten. Ihr Lehrbuch von 1977 Prinzipien des Compiler -Designs Hatte einen grünen Drachen auf der Titelseite und wurde als "The Green Dragon Book" bekannt. 1986 wurden Aho und Ullman von begleitet Ravi Sethi Um eine neue Ausgabe zu erstellen, "The Red Dragon Book" (das im Film von 1995 kurz gezeigt wurde Hacker) und 2006 auch von Monica Lam zu erstellen "die Lila Drachenbuch"Die Dragon -Bücher werden sowohl für Universitätskurse als auch für Branchenreferenzen verwendet.[18]

1974, Aho,, John Hopcroftund Ullman schrieb das Design und Analyse von Computeralgorithmeneinige ihrer frühen Forschungen zu Algorithmen. Dieses Buch wurde seit mehreren Jahrzehnten zu einem der am besten zitierten Bücher der Informatik und trug dazu bei, die Schaffung von Algorithmen und Datenstrukturen als zentraler Kurs im Lehrplan für Informatik zu fördern.[19]

AHO ist auch allgemein bekannt für seine Mitautorschaft der Awk Programmiersprache mit Peter J. Weinberger und Brian Kernighan (Das "a" steht für "Aho").[20] Ab 2010 Zu den Forschungsinteressen von AHO gehören Programmiersprachen, Compiler, Algorithmen und Quanten-Computing. Er ist Teil der Sprach- und Compiler-Forschungsgruppe an der Columbia University.[21]

Insgesamt wurden seine Werke 81.040 Mal zitiert und er hat eine H-Index von 66, ab dem 8. Mai 2019.[22]

Aho hat viele prestigeträchtige Ehrungen erhalten, einschließlich der IEEE's John von Neumann -Medaille und Mitgliedschaft in der Nationale Akademie des Ingenieurwesens. Er wurde zum Stipendiaten der Amerikanische Akademie für Kunst und Wissenschaften in 2003.[23] Er hält Ehrendoktoranden aus dem Universität von Waterloo,[24] von dem Universität von Helsinki,[24] und von der Universität von Toronto.[25] Er ist ein Stipendiat der American Association for the Advancement of Science, ACM, Bell Labs, und IEEE.[19]

AHO war zweimal Vorsitzender des Beirats für die Direktion für Computer- und Informationswissenschaft und Ingenieurwesen der National Science Foundation. Er ist ein früherer Präsident der ACM -Spezialinteressengruppe für Algorithmen und Berechnungsfähigkeitstheorie.[26] Aho, Hopcroft und Ullman waren Mitreviente des Jahres 2017 C & C -Preis verliehen NEC Konzern.[27] Er und Ullman wurden zum Empfänger der 2020 ernannt Turing Award am 31. März 2021.[5]

Lehren

AHO unterrichtet seit 1995 an der Columbia University in New York City. Er gewann 2003 den Great Teacher Award von der Society of Columbia -Absolventen.[28]

Bücher

  • A. V. Aho und J. D. Ullman, Die Theorie des Parsens, der Übersetzung und des Kompilierens, Vol. 1, Parsen. Prentice Hall, 1972. ISBN0-13-914556-7
  • A. V. Aho (Hrsg.) Strömungen in der Computertheorie. Prentice Hall, 1973. ISBN0-13-195651-5[29]
  • A. V. Aho und J. D. Ullman, Die Theorie des Parsens, der Übersetzung und des Kompilierens, Vol. 2, zusammenstellen. Prentice-Hall, 1973. ISBN978-0-13-914564-3
  • A. V. Aho, J. E. Hopcroft, J. D. Ullman, Das Design und die Analyse von Computeralgorithmen. Addison-Wesley, 1974. ISBN0-201-00023-7
  • A. V. Aho und J. D. Ullman, Prinzipien des Compiler -Designs. Addison-Wesley, 1977. ISBN0-201-00022-9
  • A. V. Aho, J. E. Hopcroft, J. D. Ullman, Datenstrukturen und Algorithmen. Addison-Wesley, 1983. ISBN0-201-00023-7
  • A. V. Aho, R. Sethi, J. D. Ullman, Compiler: Prinzipien, Techniken und Werkzeuge. Addison-Wesley, Reading MA 1986. ISBN0-201-10088-6
  • A. V. Aho, B. W. Kernighan, und P. J. Weinberger, Die awk -Programmiersprache. Addison-Wesley, 1988. ISBN978-0-201-07981-4
  • A. V. Aho und J. D. Ullman, Grundlagen der Informatik. W. H. Freeman/Computer Science Press, 1992. ISBN978-0-7167-8233-9[30][31]
    • A. V. Aho und J. D. Ullman, Grundlagen der Informatik, C Edition. W. H. Freeman, 1995. ISBN978-0-7167-8284-1
  • A. V. Aho, M. S. Lam, R. Sethi, und J. D. Ullman, Compiler: Prinzipien, Techniken und Werkzeuge, Zweite Ausgabe. Addison-Wesley, 2007. ISBN978-0-321-48681-3

Verweise

  1. ^ Alfred Vaino Aho Bei der Mathematik Genealogie -Projekt
  2. ^ Aho, A.; Gottlob, G. (2014). "Ein Sitz in der ersten Reihe zu Kommunikation'redaktionelle Transformation'. Kommunikation der ACM. 57 (4): 5. doi:10.1145/2582611. S2CID 21553189.
  3. ^ Aho, A.V. (1990). "Algorithmen zum Auffinden von Mustern in Saiten". Handbuch der theoretischen Informatik. MIT Press. S. 255–300.
  4. ^ Computerworld -Interview mit Alfred V. Aho Archiviert 29. Mai 2008 bei der Wayback -Maschine
  5. ^ a b ACM Turing Award ehrt Innovatoren, die die Grundlagen von Programmiersprachkompilern und Algorithmen geprägt haben. Abgerufen am 31. März 2021.
  6. ^ "Erstellen zuverlässiger Programme von unzuverlässigen Programmierern" (PDF). Ausgezeichnet.
  7. ^ Fitchard, Kevin (31. März 2021). "Al Aho und Jeffrey Ullman von Bell Labs geehrt mit dem prestigeträchtigen Turing Award". Nokia Bell Labs. Archiviert vom Original am 1. April 2021. Abgerufen 3. April, 2021.
  8. ^ "Profil und detaillierte Erfolge der Empfänger der Gruppe B des C & C -Preises 2017" (PDF). Das NEC C & C Foundation. Archiviert (PDF) Aus dem Original am 20. Januar 2022.
  9. ^ A. V. (1968). "Indexierte Grammatiken-eine Erweiterung kontextfreier Grammatiken". Journal of the ACM. 15 (4): 647–671. doi:10.1145/321479.321488. S2CID 9539666.
  10. ^ A. V. (1969). "Verschachtelte Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529. S2CID 685569.
  11. ^ Rambow, Owen; Satta, Giorgio (28. Juli 1999). "Unabhängige Parallelität beim endlichen Kopieren paralleler Umschreibungssysteme". Theoretische Informatik. 223 (1–2): 87–120. doi:10.1016/s0304-3975 (97) 00190-4. ISSN 0304-3975.
  12. ^ Culik, Karel; Maibaum, T. S. E. (1974). Loeckx, Jacques (Hrsg.). "Parallele Umschreibungssysteme zu Begriffen". Automaten, Sprachen und Programmierung. Vorlesungsnotizen in Informatik. Berlin, Heidelberg: Springer. 14: 495–510. doi:10.1007/978-3-662-21545-6_38. ISBN 978-3-662-21545-6.
  13. ^ Aho, Alfred V.; Corasick, Margaret J. (Juni 1975). "Effiziente String -Matching: Eine Hilfe für die bibliografische Suche". Kommunikation der ACM. 18 (6): 333–340. doi:10.1145/360825.360855. S2CID 207735784.
  14. ^ Aho, A. V.; Johnson, S. C.; Ullman, J. D. (1977). "Codegenerierung für Ausdrücke mit gemeinsamen Subtimpressionen". Journal of the ACM. 24: 146–160. doi:10.1145/321992.322001. S2CID 2614214.
  15. ^ Morris, Richard (1. Oktober 2009). "Stephen Curtis Johnson: Geek der Woche". Rote Gate -Software. Abgerufen 19. Januar, 2018.
  16. ^ Lesk, M.E.; Schmidt, E. "Lex - ein Lexikalanalysatorgenerator". Abgerufen 16. August, 2010.
  17. ^ Levine, John R.; Mason, Tony; Brown, Doug (1992). Lex & Yacc (2 ed.). O'Reilly. pp.1–2. ISBN 1-56592-000-7.
  18. ^ "Dyol: Entwerfen Sie Ihre eigene Sprache - Corpus - Dragon Books - Purple Dragon". Slebok.github.io. Abgerufen 3. April, 2021.
  19. ^ a b Ibaraki, Stephen. "Jeffrey Ullman und Alfred Aho, 2020 ACM A.M.Turing Award -Empfänger". Forbes.com. Abgerufen 3. April, 2021.
  20. ^ Aho, A. V.; Kernighan, B. W.; Weinberger, P. J. (1979). "Awk - ein Muster -Scan- und Verarbeitungssprache". Software: Übung und Erfahrung. 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 -Datensatz für Alfred Aho".
  23. ^ "Buch der Mitglieder, 1780–2010: Kapitel A" (PDF). Amerikanische Akademie für Kunst und Wissenschaften. Archiviert (PDF) Aus dem Original am 10. Mai 2011. Abgerufen 6. April, 2011.
  24. ^ a b "DLS - Alfred Aho". Cheriton School of Computer Science. 16. Februar 2017. Abgerufen 3. April, 2021.
  25. ^ Do, Liz. "'Nobelpreis des Computers:' U des Technikalumnus Alfred Aho erhält A.M. Turing Award ". Utoronto.ca. Abgerufen 3. April, 2021.
  26. ^ "Die kurze Unterdrückung von Beweisen in den USA rührt Ärger". Die New York Times. 17. Februar 1987. Abgerufen 10. November, 2015 - über Safari.
  27. ^ "2017 C & C -Preiszeremonie". NEC C & C Foundation. Archiviert Aus dem Original am 10. Juli 2018. Abgerufen 3. April, 2021.
  28. ^ "Uhr: Informatiker Alfred Aho". Simons Foundation. 18. Juli 2013. Abgerufen 3. April, 2021.
  29. ^ Ströme in der Computertheorie, herausgegeben von Alfred V. Aho. Autoren beitragen: Ronald V. Buch [und andere]. Worldcat.org. OCLC 976868524. Abgerufen 1. April, 2021.
  30. ^ Grundlagen der Informatik. Worldcat.org. OCLC 24669768. Abgerufen 1. April, 2021.
  31. ^ "Grundlagen der Informatik". Worldcat.org. Abgerufen 1. April, 2021.

Externe Links