Das Pumping-Lemma für kontextfreie Sprachen stellt eine grundlegende Entdeckung in der theoretischen Informatik dar, eine Entwicklung, die Eli Shamir zugeschrieben wird. Seine Karriere erstreckte sich über sieben Jahrzehnte und schlug eine Brücke zwischen strengen mathematischen Grundlagen und der praktischen Anwendung von Algorithmen, während er von seiner Basis in Jerusalem aus die Entwicklung der Computerlinguistik und der formalen Logik beeinflusste.
Frühes Leben und Dienst
Shamir wurde 1934 in Jerusalem geboren und besuchte die Tachkemoni-Schule sowie die Sekundarschule der Hebräischen Universität. Während des Arabisch-Israelischen Krieges von 1948 beteiligte er sich an den Verteidigungsvorbereitungen in Jerusalem. Sein akademischer Werdegang begann an der Hebräischen Universität Jerusalem, wo er sich dem Studium der Mathematik widmete und gleichzeitig als erster Operations-Research-Offizier der israelischen Luftwaffe im Rahmen des Atuda-Programms diente.
Akademische Entwicklung und Forschung
Im Jahr 1963 promovierte Shamir an der Hebräischen Universität unter der Betreuung von Shmuel Agmon. 1966 kehrte er an seine Alma Mater zurück und erreichte 1972 den Rang eines ordentlichen Professors. 1987 wurde er zum Jean-und-Helene-Alfassa-Professor emeritus für Informatik ernannt.
Beiträge zur theoretischen Informatik
Shamir leistete bedeutende Beiträge zu mehreren Fachgebieten, darunter Zufallsgraphen, Automatentheorie und computergestützte Lerntheorie. Zusammen mit Michael O. Rabin etablierte er das Informatikprogramm an der Hebräischen Universität. Seine Forschungsergebnisse waren umfangreich und reichten von den formalen Eigenschaften von Phrasenstrukturgrammatiken, die 1961 mit Y. Bar-Hillel und M. Perles entwickelt wurden, bis hin zur Untersuchung chromatischer Zahlen in Zufallsgraphen und selektiven Sampling-Algorithmen, die in den 1980er und 1990er Jahren veröffentlicht wurden.
Zwanzig Fragen, acht Minuten auf der Uhr und ein Perzentil, gemessen an allen bisherigen Teilnehmern. Ohne Anmeldung.
IQ-Test starten →Kurzfakten
- Geboren: 1934, Jerusalem - Gestorben: 2026, Jerusalem - Ausbildung: Hebräische Universität Jerusalem - Akademische Anstellungen: Northwestern University, University of California, Berkeley - Fachgebiet: Informatik und Mathematik - Hauptbereich: Graphentheorie - Auszeichnung: Jean-und-Helene-Alfassa-Professor emeritus - Hauptsprache: Hebräisch
Häufig gestellte Fragen
### Was ist die Hauptbedeutung der Arbeit von Eli Shamir?
Er ist für seine Rolle als einer der Entdecker des Pumping-Lemmas für kontextfreie Sprachen bekannt, einem wichtigen Konzept in der Automatentheorie.
### War Shamir an der Gründung von Informatikprogrammen beteiligt?
Ja, er und Michael O. Rabin waren für die Gründung des Informatikprogramms an der Hebräischen Universität Jerusalem verantwortlich.