Kniha v pamäti Shimon Even

Link: http://www.wisdom.weizmann.ac.il/~oded/even-book.html

8

Shimon Aj narodil v Izraeli na 15. júna 1935. Zomrel 1. Mája, 2004.
Okrem jeho priekopnícky výskum príspevkov (najmä na Grafe Algoritmy, Kryptografia), Shimon je známe, že bol veľmi vplyvný, pedagóg. Hral významnú úlohu pri vytváraní informatika vzdelávanie v Izraeli (napr., na Weizmann Institute a Technion). Pôsobil ako zdroj odborných inšpiráciou a vzorom pre generácie mladých študentov a výskumných pracovníkov.

Knihy pripomíname Shimon Aj bol zverejnený v Festschrift séria Springer to LNCS (napríklad Vol 3895, Marec 2006). Kniha obsahuje prínos do výskumu a prieskumy bývalých študentov a úzkej spolupracovníkov Shimon.

Názov: Teoretická informatika – Eseje v Pamäti Shimon Aj

Redakcie: Oded Goldreich, Arnold L. Rosenberg, Alan L. Selman

Krátke Zhrnutie: Tento objem pripomína Shimon Dokonca, jeden z otcov zakladateľov Počítačovej Vedy v Izraeli, ktorý zomrel 1. Mája 2004. Zväzok obsahuje výskumu príspevky, prieskumy a vzdelávacie eseje v teoretickej informatike, napísal bývalých študentov a úzkej spolupracovníkov Shimon. V súlade s Shimon štýl a zásady, eseje adresu prírodné výpočtové problémy a sú určené na to, aby boli prístupné väčšina výskumníkov v teoretickej informatike.

Knihy predslov (ktorý nasleduje) obsahuje krátke velebenie na Shimon a zoznam eseje zahrnuté v knihe.

Úvod

1. Mája 2004, svet teoretická informatika utrpel ohromujúci strata: Shimon Aj zomrel. Niekoľko počítač vedci mali tak dlho, trvalé, a vplyvný kariéru ako Shimon.

Shimon Dokonca sa narodil v Tel-Avive v roku 1935. Získal B. Sc. v odbore elektrotechnika z Technion v roku 1959, M. A. Matematiky na Univerzite v Severnej Karolíne v roku 1961, a Ph. D. v Aplikovanej Matematiky z Harvard University v roku 1963. Zastával pozície v Technion (1964-67 a 1974-2003), Harvard University (1967-69), Weizmann Institute (1969-74), a Tel-Aviv Akademického College (2003-04). Navštívil mnoho vysokých škôl a výskumných ústavov, vrátane Bell Laboratories, Boston University, Cornell, Duke, Lucent Technologies, MIT, Paderborn, Stanford, UC-Berkeley, USC a UT-Dallas.

Shimon Dokonca hral hlavnú úlohu pri vytváraní informatika vzdelávanie v Izraeli a led rozvoj akademických programov v dvoch hlavných inštitúcií: Weizmann Institute a Technion. V roku 1969 založil na Weizmann prvý informatika vzdelávacieho programu v Izraeli, a viedol tento program na päť rokov. V roku 1974 nastúpil novo vytvorené informatiky oddelenie na Technion a tvarované jeho akademický rozvoj niekoľko desaťročí. Tieto dve akademické programy sa ukázalo, že majú trvalý vplyv na vývoj počítačovej vedy v Izraeli.

Shimon Dokonca bol vynikajúci učiteľ a jeho kurzy hlboko ovplyvnil mnoho študentov navštevujúcich ich. Jeho prednášky, na mnohých medzinárodných workshopov a školy, inšpiroval veľký počet študentov a výskumných pracovníkov. Jeho knihy, najmä jeho oslavuje Graf Algoritmy, vykonáva jeho vzdelávacie správy aj na počítači vedcov, ktorí nemali to šťastie stretnúť sa s ním osobne. Ako mentor pre začínajúcich výskumných pracovníkov, Shimon bol takmer bez peer, rozvíjanie mnohých junior výskumníkov a poradenstvo mnoho postgraduálnych študentov, ktorí sa vydali na vlastné úspešnú kariéru vo výskume.

Shimon Dokonca bol priekopníkom v oblasti graf algoritmy, kryptografia a jeho prínos do výskumu v týchto oblastiach ovplyvnil priebeh ich vývoja. Shimon bol slávny nie zadržiavanie jeho záujmy na niekoľko tém, ale výbere skôr na prácu v takýchto rôznorodé oblasti, ako spínacie a automaty teória, teória kódovania, combinatorial algoritmy, zložitosť teória, distribuované výpočty, a okruh rozloženie. V každej z týchto oblastí, vyrábal vysoko kvalitné a inovatívne výskum na viac ako štyri desaťročia.

Shimon bol najčistejší z čistého theoreticians, po jeho nosa smerom k výskumu problémy, ktoré boli `vpravo”, tie v súčasnosti nie faddish ty. Jeho normy boli dokonalé, na mieste, kde by balk na zamestnávanie akýkoľvek výsledok, ktorého dôkaz nemal zvládol sám. Jeho integrity bol unimpeachable: on by šiel do veľkých dĺžok obhájiť akékoľvek zásady on veril v to.

Shimon mal veľkú vášeň pre počítačové vedy, ako aj veľkú vášeň pre pravdu. On oceňujú jednoduchosť, zodpovednosť vedy, prírodné otázky a starostlivo pripravený a výstav. Iba po jeho vlastným spôsobom, Shimon ovplyvnil mnohých výskumníkov, aby prijali jeho vášne a hodnoty. Dúfame, že to sa odráža v súčasnej hlasitosti.

Tento zväzok obsahuje prínos do výskumu a prieskumy bývalých študentov a úzkej spolupracovníkov Shimon. Sme veľmi radi, že Reuven Bar-Yehuda, Yefim Dinitz, Chlap, Aj, Richard Karp, Ami Litman, Yehoshua Perl, Sergio Rajsbaum, Adi Shamir a Yacov Yacobi dohodli na odosielanie príspevkov. V súlade s Shimon štýl a zásady, zameranie týchto príspevkov je na riešenie fyzických problémov, a že sú prístupné pre väčšinu výskumníkov v teoretickej informatike. Príspevky sú tri odlišné typy, odráža tri hlavné vedecké aktivity Shimon: pôvodný výskum, technické prieskumy a vzdelávacie eseje.

príspevkov

Príspevky boli písané bývalých študentov a úzkej spolupracovníkov Shimon. V niektorých prípadoch sa príspevky sú spoluautorom výskumníkov, ktorí nemali to šťastie byť v blízkosti Shimon, alebo dokonca, aby si ho poznal osobne. Nižšie sa budeme komentovať konkrétne aspekty každý príspevok, ktorý veríme Shimon by ocenil

Pôvodného výskumu

Je pochopiteľné, že každý má rád pôvodného výskumu, a Shimon nebola výnimkou. Veríme, že Shimon by boli spokojní s pokus, aby tieto výskumné príspevky prístupné pre širokú škálu výskumných pracovníkov (a nie len pre odborníkov v oblasti). Na podporu tohto cieľa, tieto príspevky boli preskúmané aj odborníkov i neodborníkov.

  • P. Fraigniaud, D. Ilcinkas, S. Rajsbaum a S. Tixeuil: Prehľad Priestor Dolnej Hranice pre Graf Prieskum cez Znížené Automaty. Shimon páčilo spojenie medzi oblastiach a oblastiach graf algoritmy a automaty teórie boli medzi jeho obľúbené.
  • O. Goldreich: “Concurrent” Zero-Knowledge S Načasovanie, Revisited. Shimon by žartujú na Oded je tendencia písať dlhé príspevky.
  • R. M. Karp: Spravodlivé Prideľovanie šírky Pásma Bez Per-Flow Štátnej. Shimon by sa ako skutočnosť, že východiskom tejto práce je praktický problém, a ktorý postupuje podľa destilačné jasné výpočtovej problém a riešenie je optimálne.
  • R. M. Karp, T. Nierhoff a T. Tantau: Optimálny Prietok Rozdelenie Medzi Viacerých Kanálov s Neznámou Kapacity. Tento papier má rovnakú príchuť ako predchádzajúce, a Shimon by sa to páčilo pre ten istý dôvod.
  • A. Litman: Parceling Butterfly a Batcher Triedenie Siete. Shimon by sa páčil pokúsi predložiť nové komplexnosti opatrení, ktoré lepšie odrážajú skutočné náklady implementácie.
  • Y. Perl, X. Zhou, J. Geller, a M. Halper: Aplikácie Križovatke Marketing Ontológia. Shimon by sa páčila skutočnosť, že jednoduché poznatky z teórie grafov sa používa na problém, ktorý je veľmi vzdialený od teórie grafov.
  • R. L. Rivest, A. Shamir a Y. Tauman: Ako Únik Tajomstvo – Teória a Aplikácia Krúžok Podpisy. Shimon by sa ako prírodné (`daily”) problém riešiť v tomto dokumente, ako aj elegantné riešenie, ktoré mu.
  • O. Yacobi s Y. Yacobi: Nový príslušné Hlásenie Útok na RSA. Shimon by mala vidieť otec a syn spoločne pracovať.

Technické prieskumy

Shimon oceňujú ochotu urobiť krok späť, pozrite sa na to, čo bolo vykonané (zo širšej perspektívy), a poskytujú lepší pohľad na to. Sme preto presvedčení, že on by bol rád, byť pripomínaný zväzku, ktorý obsahuje značný počet prieskumov.

  • R. Bar-Yehuda a D. Rawitz: Príbeh Dvoch Metód. Shimon rád príbehy, a on tiež páčil techniky opýtaných tu. Okrem toho, že by boli radi, aby sa dozvedeli, že tieto dve techniky sú v istom zmysle dve strany tej istej mince.
  • Y. Dinitz: Dinic Algoritmus – Pôvodnú Verziu a Aj Verzie. Shimon je údajne nesmierne teší Dinitz je prednáška, ktoré slúžili ako kostra tohto prieskumu.
  • C. Glasser, A. L. Selman, a L. Zhang: Survey of Disjoint NP-Páry a Vzťahy k Propositional Dôkaz Systémy. Tento prieskum sa zameriava na jednu z aplikácií sľub problémy, ktoré bolo určite neočakávané v roku 1984, keď Shimon Aj spolu s Alan Selman a Yacov Yacobi, zaviedol tento pojem.
  • O. Goldreich: Na Sľub Problémy. Tento prieskum stopy početné a rôznorodé aplikácie, ktoré pojem sľub problémy nájsť v dvoch desaťročí, ktoré uplynulo od vynálezu pojem.
  • G. Malewicz a A. L. Rosenberg: Kamienkovej Hry pre Internetové Počítačové. Shimon rád elegantné modely, a by bol záujem vidieť kamienkové hry používa na model Internet-vek problému.

Vzdelávacích eseje

Shimon rád opinionated diskusie a oceňujú nezávislí názory, ktoré spochybňujú tradičné dohovorov. Tak sme si istí, že by si si užil čítanie tieto eseje, a nám ľúto, že nemôžeme mať svoje reakcie na ne.

Pozrite si knihy TOC (a odkazy na všetky papiere).