בשנת 1937 נולדה לו ולאיטה בת. הם קראו לה בשם אליעזרה (זמרת הקונטראלט והמתרגמת אליעזרה איג-זקוב), על שם אליעזר פקטורובסקי. באותה שנה הוזמן על ידי יצחק בן-צבי להעיד בפני ועדת פיל על יכולתה של הארץ לכלכל אוכלוסייה גדולה. בהמשך התבקש להכין מפה אשר תשמש את טיעוני הצד הציוני בזירה הבינלאומית. אולם, באותה תקופה היה כבר חולה בסרטן, מחלה שהכריעה אותו בשבת ב' באב תרצ"ח (1938) והוא בן פחות מ-44 שנים בלבד. הוא נקבר בבית הקברות בהר הזיתים ועל מצבתו נחרט "יוצר מדע הצמחים בישראל". בהלווייתו נשאו הספדים: משה שרת, הוגו ברגמן, יהודה לייב מאגנס ויצחק בן-צבי.
עבודתו.
הקמת הגן הבוטני הראשון בארץ ישראל.
גולת הכותרת של עבודתו המדעית והחינוכית של איג במשך כל חייו הייתה הקמת הגן הבוטני הלאומי בקמפוס האוניברסיטה העברית בהר הצופים שהיה הגן הבוטני הראשון בארץ ישראל וגם במזרח התיכון כולו. איג ביסס את הגן על הצומח של ארץ ישראל לפי בתי גידול. הוא הקים עם תלמידיו ועמיתיו דיונות זעירות, גדת נחל, חורש ים-תיכוני זעיר וכדומה, בהם שתלו צמחים מקומיים. הוא ליקט צמחים לגן גם בסוריה, טורקיה, עיראק ולבנון, ממנה הביא שתילי 350 ארזים. הגן המשיך לפעול גם לאורך 19 שנים שבהן היה הר הצופים מובלעת בשליטה ישראלית בתוך שטח ירדני.
כמו כן הקים בשנת 1920 את העשבייה (אוסף של צמחים מיובשים ומוגדרים, הממוינים ומסודרים על פי שיוך סיסטמטי ועל פי אזור גאוגרפי) של האוניברסיטה העברית
זיהוי צמחים ובתי גידול.
אחת מעבודותיו החלוציות של איג הייתה זיהוי בתי הגידול של ארץ ישראל והגדרת הצמחים הגדלים בהם. הוא נחשב לאבי תחום הפיטוגאוגרפיה של ארץ ישראל (חקר התפוצה הגאוגרפית של צמחים). בין היתר נתן את השם "בתה" לתצורת צומח המאופיינית בשיחים נמוכים.
בשנת 1931 יצא לאור המגדיר לצמחי ארץ ישראל, פרי עטו של איג, בסיועם של עוזריו זהרי ופיינברון. ספר זה היה המגדיר הראשון לצמחיית הארץ. איג עצמו העניק לצמחים רבים את שמם, כמו לאהרונסונית פקטורובסקי, הנקרא על שם שני הבוטנאים אליעזר פקטורובסקי, גיסו, ואהרן אהרנסון, או מושיובית גלילית, צמח שזוהה בשנת 1938 והוקדש לזכרו של גרשון מושיוב, בוטנאי מבטיח שנהרג בקריית ענבים שנתיים קודם לכן.
חלוץ שמירת הטבע.
אלכסנדר איג היה הראשון שקרא לשמירת הטבע בארץ המתחדשת. במאמרו "תוספת לידיעת הצמחייה בישראל" משנת 1926 כתב בין היתר:
הנצחה.
על שמו של איג נקראו מספר צמחים, ובהם זמזומית איג ("Bellevalia eigii"), מרוות איג ("Salvia eigii"), צלוקית אדום ("Stigmatella longistyla Eig") ונץ-החלב איג. כן נקרא על שמו רחוב בשכונת רמות אלון בירושלים.
אלגוריתם rho של פולרד
בתורת המספרים, אלגוריתם רו של פולרד (באנגלית: Pollard's rho algorithm) הוא אלגוריתם הסתברותי לפירוק מספר שלם לגורמים, שפותח ב-1975 על ידי ג'ון פולרד. האלגוריתם מוצא גורם ראשוני אחד, בדרך כלל את הקטן ביותר, וסיבוכיות הריצה שלו מסדר הגודל של שורש הגורם הראשוני. זאת בניגוד לאלגוריתם הפירוק הנאיבי מחד, שסיבוכיות הריצה שלו מסדר גודל של שורש המספר שאותו מבקשים לפרק, ולאלגוריתמים המודרניים לפירוק מאידך, שסיבוכיות הריצה שלהם תת-אקספוננציאלית בלוגריתם של המספר. ב-1981 שימש האלגוריתם (בגרסה משופרת שלו) לפירוק מספר פרמה השמיני (כ-77 ספרות עשרוניות), ונמצא שיש לו גורם ראשוני קטן.
חיפוש התנגשויות.
אלגוריתם rho של פולרד מבוסס על אלגוריתם פלויד למציאת מחזוריות, המטפל בפונקציה formula_1 מקבוצה סופית formula_2 אל עצמה. איבר התחלתי formula_3 מגדיר באינדוקציה את סדרת הערכים שהפונקציה מקבלת, formula_4. מכיוון שזו סדרה של ערכים בקבוצה סופית, היא מוכרחה לחזור על עצמה, והמסלול שהיא מתארת יהפוך למחזורי מאותו זמן והלאה. שיטת פולארד נקראת "שיטת formula_5", בגלל צורת האות היוונית הדומה לתיאור סכמתי של המחזור.
עקרון שובך היונים מבטיח חזרה בתוך formula_6 צעדים, ולא פחות; עם זאת, אם הפונקציה f אקראית, אז פרדוקס יום הולדת מביא לחזרה בתוך זמן קצר בהרבה - formula_7 צעדים, בתוחלת.
בעיית המחזוריות מבקשת למצוא התנגשות מפורשת; קרי, למצוא, ביעילות, אינדקסים formula_8 שעבורם formula_9. הדרך הנאיבית היא לאחסן את הרצף formula_10 בזיכרון (למשל באמצעות טבלת גיבוב) ולחפש בכל צעד כפילויות עם הערכים הקודמים. שיטה זו דורשת זיכרון מסדר הגודל של מספר הערכים שיתקבלו עד להתנגשות הראשונה, ובמקרים רבים זו דרישה בלתי מעשית.
ב-1960 פיתח רוברט פלויד אלגוריתם אלגנטי המוצא התנגשות תוך שימוש בזיכרון זניח בלבד: בחישוב סדרת הערכים, מחשבים במקביל גם את אותה סדרה במהירות כפולה. היינו, מתחילים בזוג ערכים formula_11, ובכל צעד מחליפים את הזוג formula_12 בזוג
formula_13, ומשווים את שני הרכיבים. ברגע שמתקבל השוויון formula_14, נמצאה התנגשות.
שימוש למציאת גורמים.
כדי למצוא גורם ראשוני של מספר נתון n, הציע פולארד לבחור פונקציה אריתמטית כמו formula_15, המחושבת מנקודת התחלה אקראית מודולו n. ההיוריסטיקה קובעת שפונקציה כזו מתנהגת כמו פונקציה אקראית. בהתאם לאלגוריתם של פלויד, מחשבים שני רצפים במקביל, לאורך אותם ערכים, כשהאחד נע במהירות כפולה מחברו. השוואת בני הזוג formula_16 אינה מתבצעת מודולו n, אלא על ידי חישוב המחלק המשותף המרבי של formula_17 ו-formula_18. הרעיון הוא שסדרת הערכים formula_10, המחושבת מודולו n, מוגדרת מודולו כל גורם ראשוני p של n (גם אם p אינו ידוע), ולכן היא מהווה גם סדרה של ערכים במרחב של p השאריות בחלוקה ל-p. התנגשות במרחב הקטן הזה, שאמורה להתרחש בתוך formula_20 צעדים, תזוהה מיד, מכיוון שההפרש באותו זמן יהיה 0 מודולו p, כך ש-p יחלק את המחלק המשותף המקסימלי formula_21. יש גם סיכוי לכך שההתנגשות תתרחש בו זמנית מודולו כל גורם (חזקת-)ראשוני של n, ואז המחלק המשותף המקסימלי יהיה n, והאלגוריתם נכשל.
האלגוריתם.
גרסה בסיסית של אלגוריתם rho עם הפונקציה: formula_15.
הערה: הסיכויים ש-formula_33 אינם גבוהים, אך אם בכל זאת האלגוריתם מסתיים כאשר formula_33 ישנן מספר אפשרויות. אחת היא לחזור על האלגוריתם עם ערכים התחלתיים שונים. השנייה היא לחזור על האלגוריתם עם פולינום אחר, בעל מקדם חופשי גבוה מ-1 למשל formula_35 אם formula_36.
בהנחה שהפונקציה formula_37 מתנהגת כפונקציה אקראית, זמן הריצה המשוער של האלגוריתם הוא formula_20 צעדים אריתמטיים (של כפל מודולרי) ועל כן הזמן המשוער למציאת גורם לא טריוויאלי של formula_18 הוא formula_40.
דוגמה במספרים קטנים.
הטבלה הבאה מציגה את הלולאה הראשית (שלב 2) באלגוריתם בפירוק המספר formula_41 :
נמצא ש-formula_42 הוא אחד הגורמים, למעשה הגורם הקטן ביותר של formula_43. יתר הגורמים הם formula_44 ו-formula_45.
גרסה משופרת של האלגוריתם.
ריצ'רד ברנט פרסם ב-1980 גרסה משופרת של אלגוריתם rho המכונה אלגוריתם פירוק לגורמים מונטה קרלו משופר, המציע שיפור של כ-36 אחוז במקרה הממוצע, ביחס לאלגוריתם המקורי. במקום להשתמש באלגוריתם מחזוריות של פלויד כפי שעושה האלגוריתם של פולרד, אלגוריתם ברנט משתמש בשיטה שונה הנקראת back-tracking (נסיגה) כדי לאתר את מחזוריות הרצף ולמנוע חזרה מיותרת.
קוד C של אלגוריתם מונטה קרלו של ברנט:
int BrentPollard(int n, int x0, int m)
int g, x, y = x0, ys, r = 1, q = 1;
x = y;
for(int i = 1; i &lt; r; i++)
y = f(y, n);
int k = 0;
ys = y;
for(int j = 1; j &lt; MIN(m, r-k); j++)
y = f(y, n);
q = (q * ABS(x-y)) % n;
g = gcd(q, n);
k += m;
} while( k &lt; r &amp;&amp; g &lt;= 1);
r «= 1;
} while(g &lt;= 1);
if(g == n)
ys = f(ys, n);
g = gcd(ABS(x - ys), n);
} while(g &lt;= 1);
if(g == n) return 0;
return g;
הקלט: formula_18 הוא המספר המיועד לפירוק, formula_47 מספר אקראי כלשהו הנמוך מ-formula_18, ו-formula_49 הוא ערך התחלתי כלשהו בדרך כלל 2. הפונקציה formula_50 אמורה להיות פונקציה אקראית כלשהי מודולו formula_18, כמו formula_52, המאקרו ABS מייצג ערך מוחלט והפונקציה gcd היא אלגוריתם אוקלידס.
יעילות.
אלגוריתם rho של פולרד מספק איזון הדדי בין זמן הריצה לבין סיכוי ההצלחה. במקרה הקשה כאשר המספר הוא כפולה של שני גורמים ראשוניים שווים בגודלם בערך, זמן ריצה משוער של formula_53 צעדים, יניב גורם ראשוני בסיכויים של חצי בהערכה גסה (אף על פי שזוהי הערכה היוריסטית בלבד). שאלת יעילות האלגוריתם המדויקת היא בעיה פתוחה.
אלגוריתם rho מהיר למדי עבור מספרים עם גורמים ראשוניים קטנים. למשל במחשב בינוני, יישום מעשי של האלגוריתם בפירוק מספר פרמה השישי (כעשרים ספרות עשרוניות) לוקח כמחצית שנייה. לעומת זאת לפירוק מספר בגודל זהה, שהוא כפולה של שני מספרים ראשוניים גדולים (לא בהכרח שונים) השווים בגודלם בקירוב, נדרשות כעשר שניות לפחות.
ההישג המשמעותי ביותר של האלגוריתם היה של גרסת ברנט המשופרת, איתה הצליחו ג'ון פולרד וריצ'רד ברנט לפרק את מספר פרמה השמיני formula_54 בזמן כולל של שעתיים על מחשב מרכזי מדגם UNIVAC.
פנחס ליטבינובסקי
פנחס ליטבינובסקי (נכתב גם ליטוינובסקי; 11 באוגוסט 1894; ט' באב תרנ"ד – 15 בספטמבר 1985; א' בתשרי תשמ"ו) היה צייר ישראלי. על יצירתו זכה בפרס ישראל לציור בשנת 1980.
ביוגרפיה.
פיוטר ולדימירוביץ ליטבינובסקי נולד לזאב וחוה ליטבינובסקי ב שבאוקראינה. אביו היה סוחר; פנחס התחנך בבית דתי ולמד בילדותו ב"חדר".