tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
בעיית k השרתים (K-Server problem) היא אחת מהבעיות הידועות באלגוריתמים מקוונים והוצגה לראשונה ב-1988. בבעיה זו ישנם k שרתים מפוזרים במרחב מטרי סופי (מעין "חדר").
הבעיה מוגדרת כך: בהינתן k שרתים הנמצאים בנקודות במישור, ובקשות שמגיעות מנקודות שונות באופן מקוון, צריך להחליט לכל בקשה איזה שרת להזיז לנקודה שלה כדי לטפל בה.
המטרה היא להזיז את השרתים במרחק הכולל (על פי המרחב המטרי) הקטן ביותר האפשרי.
השערה רווחת היא כי יחס התחרותיות של בעיית k-השרתים הוא k.
ידוע כי k הוא הערך הטוב ביותר האפשרי וכי לבעיית 2 השרתים ידוע אלגוריתם 2-תחרותי.
לערכים גדולים יותר היחס הטוב ביותר הידוע הוא 2k-1.
אלגוריתם קני הוא אלגוריתם רב-שלבי בתחום עיבוד תמונה שמטרתו היא זיהוי קצוות בתמונה.
האלגוריתם פותח על ידי ג'ון קני ב-1986.
האלגוריתם מקבל כקלט תמונה בגווני-אפור (אם התמונה היא צבעונית ניתן להמיר אותה לגווני-אפור) ומוציא כפלט תמונה בשחור-לבן בעלת ממדים זהים שבה הקצוות מסומנים בצבע לבן ושאר התמונה בצבע שחור.
באופן פשוט "קצה" מוגדר להיות מעבר חד בין גוונים.
לבד מהתמונה עצמה האלגוריתם מקבל שני פרמטרים נוספים עיקריים: סף עליון וסף תחתון.
האלגוריתם משמש לתחום של עיבוד תמונה וראייה ממוחשבת .
תיאור כללי של שלבי האלגוריתם:
חישוב פונקציית הגרדיאנט- מציאת נגזרות חלקיות של פונקציית הגוון, עבור כל נקודה בתמונה מתקבל וקטור נגזרת.
מציאת גודלו וכיוונו של וקטור הנגזרת.
הנקודות שבהן גודל וקטור הנגזרת קטן מהסף-התחתון נפסלות מייד לשמש כקצוות ואלו שבהן הוא גדול מהסף העליון מייד מסומנות כקצוות.
הכיוון של וקטור-הנגזרת של כל נקודה מהנקודות שנותרו מקורב לאחד מארבעה כיוונים בדידים: אופקי, אנכי או אלכסוני (אחד משני הכיוונים האלכסוניים).
הנקודות שעוזרות ליצור רצף של נקודות בעלות אותו כיוון-נגזרת עם נקודות שכבר סומנו כקצה, מסומנות גם הן כקצוות.
אלגוריתם השכן הקרוב או k-Nearest Neighbors algorithm (או בקיצור k-NN) הוא אלגוריתם חסר פרמטרים לסיווג ולרגרסיה מקומית שפותח לראשונה על ידי אוולין פיקס וג'וזף הודג'ס ב 1951. בשני המקרים הקלט תלוי ב־k התצפיות הקרובות במרחב התכונות.
k-NN יכול לשמש לסיווג או לרגרסיה:
k-NN לסיווג – בהינתן קלט של דוגמה חדשה, האלגוריתם משייכה לקבוצה.
הדוגמה משויכת למחלקה הנפוצה ביותר בקרב k השכנים הקרובים (כאשר k מוגדר כמספר חיובי שלם, בדרך כלל מספר קטן).
אם k=1 האובייקט משויך למחלקה של השכן הבודד הקרוב ביותר.
k-NN לרגרסיה – בהינתן דוגמה חדשה, האלגוריתם מחזיר ערך מאפיין לדוגמה.
ערך זה הוא ממוצע ערכים של ערכי k השכנים הקרובים ביותר.
k-NN הוא אלגוריתם לימוד מבוסס מופעים, או למידה עצלה, שבו הפונקציה מקורבת באופן מקומי בלבד וכל החישובים נדחים עד סיווגה.
אלגוריתם k-NN הוא מבין האלגוריתמים הפשוטים ביותר בתחום למידת המכונה.
שקלול תרומתם של השכנים יכול להיות שימושי גם במקרה של סיווג וגם במקרה של רגרסיה, כך שמשקל השכנים הקרובים תורם יותר לממוצע מהשכנים הרחוקים יותר.
לדוגמה שיטת שקלול נפוצה מורכבת כך שנותנים לכל שכן משקל של , כאשר d הוא המרחק לאותו שכן.
השכנים נלקחים מתוך סדרת אובייקטים של מחלקה (עבור k-NN לסיווג) או אפיון הערך (עבור k-NN לרגרסיה) ידועים.
חיסרון בולט של האלגוריתם הוא רגישותו למבנה המקומי של הנתונים.
הקלט לשלב האימון של האלגוריתם הוא דוגמאות אימון, וקטורי תכונות במרחב רב ממדי כל אחד עם תווית סיווג (למשל עבור וקטור תכונות של d ממדים ושתי מחלקות סיווג).
שלב האימון מתבסס רק על אחסון תכונת הווקטור ותווית הסיווג של דוגמאות האימון במבנה נתונים שיאפשר בהמשך חיפוש מהיר בהם, כדוגמת עץ kd.
הקלט לשלב הסיווג הוא וקטור ללא תווית (למשל ).
בשלב הסיווג k מוגדר כקבוע, והמסווג קובע את תווית הסיווג על פי התווית השכיחה ביותר בקרב k דוגמאות האימון הקרובות לדוגמה הנבדקת.
מטריקה מקובלת למדידת מרחק בין משתנים רציפים היא מרחק אוקלידי.
עבור משתנים בדידים, כגון בבעיית סיווג טקסט, ניתן להשתמש במטריקה אחרת, כגון מרחק המינג.
לעיתים קרובות, דיוק הסיווג של k-NN ניתן לשיפור באופן משמעותי אם המטריקה שבשימוש נלמדת באמצעות אלגוריתמים מיוחדים כמו "Large margin nearest neighbor" או "Neighbourhood components analysis".
חיסרון משמעותי של סיווג כזה, לפי השכיח המקומי, הוא כאשר התפלגות המחלקות מוטה, כלומר: מספר דוגמאות האימון באחת המחלקות גדול בהרבה ממספר דוגמאות האימון במחלקות האחרות.
במקרה כזה, רוב הדוגמאות החדשות יסווגו למחלקה זו, כי בשל מספרן הגדול, דוגמאות האימון ממחלקה זו נוטות להיות נפוצות בקרב k השכנים הקרובים לדוגמה החדשה.
דרך אחת להתמודדות עם בעיה זו היא הקצאת משקל לסיווג, שייקבע לפי מרחק הדוגמה מ־k השכנים הקרובים.
הסיווג (או הערך, במקרה של בעיית רגרסיה) של כל אחת מ־k הנקודות הקרובות יוכפל במשקל הפרופורציונלי להופכי של המרחק מנקודת האימון לנקודה הנוכחית.
דרך אחרת כדי להתגבר על סטיות במדידה היא הפשטה בייצוג נתונים.
לדוגמה, ברשת קוהונן, כל צומת מייצגת מרכז של קבוצת נקודות דומות, ללא קשר לצפיפותן בנתוני האימון המקוריים.
הבחירה הטובה ביותר של k תלויה בנתונים; בדרך כלל, ערכים גבוהים יותר של k גורמים לצמצום ההשפעה של הרעש על סיווג, אבל גורמים לגבולות בין מחלקות להיות פחות מובהקים.
k טוב יכול להיבחר באמצעות מספר שיטות.
במקרה המיוחד בו נחזתה מראש סוג המחלקה כמחלקה הקרובה ביותר לנקודות האימון (כלומר כאשר k=1) נקרא אלגוריתם השכן הקרוב ביותר.
הדיוק של אלגוריתם k-NN יכול להיפגע קשות על ידי נוכחות של רעש או תכונות לא רלוונטיות, או אם סקלת התכונה אינה עקבית עם חשיבותה.
מאמצי מחקר רבים הושקעו עבור בחירת תכונות או דירוג תכונות לשיפור סיווגם.
בסיווג בינארי (דו־ערכי; כאשר יש שתי מחלקות), כדאי לבחור את k להיות מספר אי־זוגי כדי להימנע ממצבי תיקו.
דרך אחת פופולרית לבחירת k אופטימלי באופן אמפירי למצב זה היא באמצעות שיטת אתחול .
k-NN הוא מקרה פרטי של הערכת צפיפות משתני קרנל, של הערכת רוחב פס משתנים ושל הערכת צפיפות קרנל "בלון" עם אחידות סטטיסטית בקרנל.
בצורתו הפשוטה של האלגוריתם הוא נדרש לחשב המרחקים בין הדוגמה לסיווג לכל דוגמאות האימון, אך גישה נאיבית כזו דורשת חישובים רבים כאשר יש דוגמאות אימון רבות.
עם זאת שימוש באלגוריתם יעיל לחיפוש שכן קרוב מאפשר להשתמש ב־k-NN גם עבור דוגמאות רבות.
במהלך השנים הוצעו מספר רב של אלגוריתמי חיפוש לשכן הקרוב; בכלל ניסו אלגוריתמים אלה לצמצם את מספר הערכות המרחק שמבוצעות בפועל.
כאשר מספר הדוגמאות שואף לאינסוף, לאלגוריתם מובטח שיעור שגיאה מרבי לא יותר מפעמיים שיעור השגיאה של בייס (השגיאה המינימלית הניתן להשגה בהתחשב בהתפלגות הנתונים).
עבור נתונים רב־ממדיים (לדוגמה, אם מספר ממדים גדול מ־10), הפחתת ממדים מבוצעת בדרך כלל לפני הפעלת k-NN על הנתונים, כדי למנוע את ההשפעות של קללת הממד (Curse of dimensionality).
משמעותה של קללת הממד, בהקשר של k-NN, היא שהמרחק האוקלידי אינו מדד יעיל למרחק במרחב מממד גבוה, כיוון שכל הווקטורים הם שווי מרחק ביחס לווקטור הנבדק (דמיינו מספר נקודות מונחות פחות או יותר על עיגול שלם עם נקודת שאילתה במרכז; המרחק בין נקודות השאילתה לכל נקודות המידע הוא כמעט זהה).
ניתן לשלב בפעולה אחת חילוץ תכונות והורדת ממד באמצעות שיטות ניתוח גורמים ראשיים (PCA), ניתוח הבחנה ליניארי (LDA) או ניתוח מתאם קנוני (CCA) כשלב טרום עיבודי, ולאחר מכן יצירת אשכולות על ידי k-NN בשיכון במרחב בממד נמוך יותר (embedding).
הורדת ממד יכולה להיעשות גם באמצעות הורדת ממד אקראית.
כללי השכן הקרוב ביותר למעשה מחשבים במרומז את גבול ההחלטה.
כמו כן ניתן לחשב את גבול ההחלטה באופן מפורש, כדי לעשות זאת באופן יעיל כך שמורכבות החישוביות היא פונקציה של מורכבות הגבול.
צמצום נתונים היא אחת הבעיות החשובות ביותר בבעיות עם מספר דוגמאות רב.
בדרך כלל, לסיווג מדויק דרושות רק כמה נקודות, או "אבות טיפוס" וניתן למצוא אותן כך:
בחירת "Class-outliers", כלומר, דוגמאות שסווגו לא נכון על ידי k-NN עבור k נתון.
יש להפריד את שאר הנתונים לתוך שתי קבוצות: (א) אבות הטיפוס המשמשים לסיווג (ב) "הנקודות הנבלעות" – נקודות ש־k-NN יכול לתקן את סיווגן באמצעות אבות הטיפוס, ונקודות אלו ניתן להסיר ממדגם האימון.
דוגמאות האימון המוקפות בדוגמאות של מחלקות אחרות נקראות Class outlier.
הגורמים של Class outliers כוללים:
לא מספיק דוגמאות אימון במחלקה זו (קיימת דוגמה בודדת במקום מקבץ דוגמאות)
חוסר בתכונות חשובות (המחלקות מופרדות בממדים שונים לא ידועים)
ריבוי דוגמאות ממחלקות אחרות (מחלקות לא מאוזנות) אשר יוצרות רקע עוין למחלקה הקטנה
בשילוב עם k-NN מייצר רעשים.
הרעשים יכולים להיות מזוהים ומופרדים לצורך ניתוח עתידי.
בהינתן שני מספרים טבעיים, k>r>0, דוגמת אימון נקראת k,r-NN class-outlier, אם k שכנים קרובים כוללים יותר מ־r דוגמאות של מחלקות אחרות.
CNN עבור צמצום כמות הנתונים
אלגוריתם ממוקד לשכן הקרוב ביותר (Condensed Nearest Neighbor, CNN, מכונה גם אלגוריתם הארט) הוא אלגוריתם שנועד לצמצם את מספר הדוגמאות לסיווג k-NN.
אלגוריתם זה בוחר את אבות הטיפוס U מתוך דוגמאות האימון, כך ש־1NN יכול לסווג את U כמעט במדויק, כפי ש־1NN מסווג את כל הנתונים.
CNN עובד באופן איטרטיבי, בהינתן מדגם אימון:
סרוק את כל האיברים ב־X, וחפש רכיב x שיש לו תווית שונה מאב הטיפוס הקרוב אליו (מקרב U).
הסר את x מ־X, והוסף אותו ל־U.
סרוק שוב, עד שלא יתווספו עוד אבות טיפוס ל־U.
השתמש ב־U במקום ב־X לשם הסיווג.
הדוגמאות שאינן אבות טיפוס נקראות נקודות בלועות.
לשם שיפור יעילות הסריקה של CNN, נגדיר את יחס הגבול לדוגמת אימון x:
כאשר ||x-y|| הוא המרחק הקרוב ביותר לדוגמה y בעלת תווית שונה מאשר x, והמרחק ||x'-y|| הוא המרחק בין y לדוגמה הקרובה ביותר אליה 'x, המסווגת כמו x.יחס הגבול הוא בין 0 ל־1, היות שערכו של ||x'-y|| לעולם אינו גדול יותר מערכו של ||x-y||.
סדר זה מעניק עדיפות לגבולות המחלקות לשם הכללתם בקבוצת אבות־הטיפוס U.
נקודה בעלת תווית שונה מאשר x נקראת נקודה חיצונית ל־x.
חישוב יחס הגבול מודגם באיור משמאל.
הנתונים מסומנים בצבעים: נקודת הפתיחה היא x, והיא מסומנת באדום.
הנקודות החיצוניות הן כחולות וירוקות.
הנקודה החיצונית הקרובה ביותר ל־x היא הנקודה y.
הנקודה האדומה הקרובה ביותר ל־y היא הנקודה 'x.
יחס הגבול a(X) הוא תכונה של נקודת הפתיחה x.
בעזרת יחס הגבול, ניתן לייעל את סריקת דגימות האימון ב-CNN, אם הסריקה מבוצעת בסדר יורד של a(x).
להלן המחשה של CNN על קבוצת דוגמאות אימון המחולקות לשלוש מחלקות: אדום, ירוק וכחול.
איור 1 מראה את המצב ההתחלתי, שבו יש 60 נקודות בכל מחלקה.
איור 2 מציג את מפת הסיווג 1NN: כל פיקסל מסווג על ידי 1NN באמצעות כל הנתונים.
איור 3 מציג את מפת הסיווג 5NN.
אזורים לבנים תואמים את האזורים הלא מסווגים, שבהם היה תיקו בין מחלקות (למשל, אם יש שתי נקודות ירוקות, שתי נקודות אדומות ונקודה אחת כחולה מקרב חמשת השכנים הקרובים ביותר).
איור 4 מציג את מקבץ הדוגמאות המצומצם.
ה־xים הם Class-outliers שנבחרו על ידי כלל (3,2)NN (כל שלושת השכנים הקרובים ביותר של מקרים אלה שייכים למחלקות אחרות); הריבועים הם אבות־הטיפוס, והעיגולים הריקים הם הנקודות הבלועות.
בצד שמאל למטה מוצגים מספרי ה־class-outlier, אבות־הטיפוס והנקודות הבלועות לכל אחת משלוש המחלקות.
מספר אבות־הטיפוס נע בין 15% ל־20% עבור מחלקות שונות בדוגמה זו.
איור 5 מראה שמפת הסיווג 1NN עם אבות־הטיפוס דומה מאוד למפה עם הנתונים הראשוניים.
האיורים נוצרו בעזרת היישומון של מירקס.
אלגוריתם K-NN משמש להערכת משתנים רציפים.
אלגוריתם לדוגמה עשוי להשתמש בממוצע משוקלל של K השכנים הקרובים ביותר, משוקללים לפי ההופכי של מרחקם.
חשב את המרחק האוקלידי או מרחק מהלנוביס (Mahalanobis) מהנקודה הנבדקת לנקודות האימון המתויגות.
סדר את הנקודות המתויגות לפי מרחק עולה.
מצא k אופטימלי לאלגוריתם, על סמך שורש הטעות הריבועית הממוצעת.
חשב ממוצע משוקלל לפי המרחק ההופכי מ־k שכנים קרובים.
אלגוריתם מיקסום התוחלת הוא שיטה איטרטיבית לאמידה של פרמטרים, במודלים סטטיסטיים שבהם משולבים משתנים מקריים סמויים שאין עבורם תצפיות.
מודל איטרציה זה עובר בין שני שלבים:
התוחלת (שלב ה-E), אשר יוצר פונקציה של הפרמטרים לאמידה - תוחלת של לוג הנראות (של כל הנתונים, כולל הסמויים) כאשר מניחים כי למשתנים הסמויים יש התפלגות שנסמכת על האומדן הנוכחי עבור הפרמטרים.
שלב המיקסום (שלב ה-M), אשר מוצא עבור הפרמטרים את האומדנים אשר מביאים למקסימום את הפונקציה שחושבה בשלב התוחלת.
לאחר שלב המיקסום חוזרים חוזרים לשלב התוחלת עם האומדנים שנמצאו בשלב המיקסום וכן הלאה.
אלגוריתם EM קיבל את שמו לראשונה בשנת 1977 במאמר מאת ארתור דמפסטר, נאן ליירד, ודונלד רובין.
במאמר זה ציינו החוקרים כי בעבר השיטה כבר הועלתה על הכתב בידי מחברים אחרים.
דמפסטר-ליירד-רובין הגדירו את שיטת מיקסום התוחלת ככלי חשוב לפתרון מגוון רחב של בעיות.
עם זאת, ניתוח ההתכנסות של דמפסטר-ליירד-רובין היה שגוי.
ניתוח מתוקן פורסם על ידי ס.פ ג'ף וו ב-1983.
אלגוריתם EM משמש תחליף לאומד נראות מקסימלית במודלים סטטיסטיים שבהם קיים קושי הנובע מקיומם של משתנים מקריים סמויים או נתונים חסרים.
במודלים אלו קשה מבחינה טכנית למצוא מקסימום לפונקציית הנראות.
אלגוריתם EM מתחיל עם אומדן התחלתי לפרמטרים (אפשר לקבלו באמצעות שיטות אמידה פחות מדויקות).
מתוך האומדן הראשוני מקבלים את ההתפלגות עבור הנתונים החסרים ואת תוחלת ההתפלגות של לוג הנראות עבור נתונים מלאים.
זו עדיין פונקציה של הפרמטרים, כי האומדן משמש אותנו רק כדי לקבל את ההתפלגות לנתונים החסרים.
עתה ניתן להשתמש ב- במקום בפונקציית לוג הנראות, , שבה משתמשים בשיטה של אומד נראות מקסימלי.
האומדן החדש לפרמטרים יהיה זה המביא למקסימום .
בניגוד למקרה של אומד נראות מקסימלי, האומדן שקיבלנו עדיין לא אופטימלי ועלינו להציבו שוב כדי לקבל התפלגות משופרת לנתונים החסרים.
כך ממשיכים עם האיטרציות עד אשר מגיעים למצב שבו איטרציות נוספות אינן משנות את האומדנים באופן שהוא משמעותי.
בהינתן מודל סטטיסטי המורכב ממדידות , משתנים סמויים שאינם נראים או נתונים חסרים (משתנה מקרי), פרמטרים θ אותם מעוניינים לאמוד ופונקציית הצפיפות בהינתן הנתונים המלאים.
פונקציית הצפיפות השולית של הנתונים הקיימים היא ולכן לוג הנראות בהינתן הנתונים הנראים היא .
כאשר אומדים בשיטת הנראות המקסימלית, בדרך כלל, מוצאים שיביא למקסימום את .
אולם בדרך כלל במקרים של נתונים חסרים בדרך כלל מדובר בבעיה טכנית קשה יחסית.
בתנאים מסוימים, אלגוריתם EM מאפשר לעשות זאת על ידי יישום איטרטיבי של שני הצעדים הבאים:
שלב התוחלת (שלב ה-): חישוב תוחלת הלוג של פונקציית הנראות לנתונים המלאים, ביחס להתפלגות של של הנתונים החסרים, בהינתן סדרת התצפיות והאומדן הנוכחי של הפרמטרים :
שלב המיקסום (שלב ה-): מציאת ה- אשר מביא למקסימום את הפונקציה שחושבה בצעד הראשון:
מתחילים עם אומדן ראשוני, (שיכול להתקבל באמצעות שיטה אחרת, פחות מדויקת), ואז חוזרים שוב ושוב על שלב התוחלת ושלב המיקסום ומקבלים סדרה של אומדנים שבתנאים מסוימים הולכים ומשתפרים.
ג'ף וו הוכיח את משפט ההתכנסות הבא:
הוא תת-קבוצה של המרחב האוקלידי ה- ממדי ,
רציפה על וגזירה בפנים של ,
הפונקציה רציפה גם ב- וגם ב-;
אז כל נקודות הגבול של סדרה הן נקודות קריטיות של (נקודה בה הנגזרת מתאפסת או לא מוגדרת) והסדרה מתכנסת באופן מונוטוני ל- עבור נקודה , שהיא אחת מהנקודות הקריטיות של .
אם נניח בנוסף לכך את ההנחות הבאות:
לפונקציה יש נקודה קריטית יחידה שבה מתקבל מקסימום גלובלי,
וקטור הנגזרות החלקיות של רציף גם ב- וגם ב-;
התפלגות תערובת של שתי התפלגויות רב-נורמליות
נתון מדגם של ווקטורי תצפיות בלתי תלויים מתערובת של שתי התפלגויות רב-נורמליות ממימד , ונניח שקיימים משתנים מקריים סמויים אשר קובעים מאיזה מרכיב של התערובת מגיעה כל תצפית.
המטרה היא לאמוד את המשקלים של הצירוף הקמור בין שתי ההתפלגויות המרכיבות ואת התוחלות והשונויות של כל אחד מהם:
פונקציית הנראות עבור הנתונים המלאים הכוללים וקטור תצפיות :
כאשר הן פונקציות צפיפות של התפלגויות רב-נורמליות.
הלוג של פונקציית הנראות הוא:
מאחר ש- מבטא נתונים חסרים נציב במקומו משתנים מקריים:
בהינתן האומדן , ההתפלגות המותנה של נקבעת על ידי חוק בייס:
בשלב זה מקבלים אומדנים חדשים לפרמטרים, כאלה אשר מביאים את למקסימום.
נעשה זאת, במקרה המסוים הזה, על ידי גזירה(חלקית) לפי הפרמטרים והשוואה ל-0,
עבור , מציאת האומדנים החדשים של ו- ,
ניתן להכליל את האלגוריתם המודגם לעיל עבור תערובות של יותר משתי התפלגויות רב-נורמליות.
אלגוריתם קורי העכביש (COBWEB) משמש עבור מערכת גדלה שבה קיימת היררכיה של קיבוץ קונספטואלי (conceptual clustering).
שיטת קורי העכביש הומצאה על ידי פרופסור דאגלס.
פישר, אשר נכון לשנת 2017 עובד באוניברסיטת ואנדרבילט.
אלגוריתם קורי העכביש מארגן תצפיות באופן הדרגתי לתוך עץ מסווג (classification tree).
כל צומת סיווג בעץ מייצג מחלקה אשר מאופיינת על ידי חישוב הסתברותי.
החישוב ההסתברותי מסכם את ההתפלגויות המותנות בתכונות של האובייקטים המסווגים תחת אותה צומת.
עץ מסווג זה יכול לשמש כדי לחזות תכונות חסרות או את המחלקה של אובייקט חדש.
ישנן ארבע פעולות בסיסיות שאלגוריתם קורי העכביש משתמש בהן כדי לבנות אשכולות מסווגים.
כל תהליך שנבחר תלוי בקטגוריית השירות (Category of utility) של הסיווג, המושגת על ידי יישום אלגוריתם זה.
מיזוג שני צמתים: החלפת שני צמתים בצומת חדש, אשר צומתי המשנה שלו הם איחוד של הצמתים המקוריים, אשר מסכם את ההתפלגויות המותנות בתכונות של כל האובייקטים המסווגים תחת אותם צמתים.
פיצול צומת: צומת מפוצל על ידי החלפתו עם צומתי המשנה שלו.
הוספת צומת חדש: נוצר צומת חדש המתאים לאובייקט אשר מוכנס לתוך העץ.
העברת אובייקט למטה בסדר ההיררכי: קורא ביעילות את אלגוריתם קורי העכביש של האובייקט ואת עץ המשנה המושרש בתוך הצומת.
אלגוריתם צ'ודנובסקי הוא אלגוריתם מהיר לחישוב הספרות של פאי (מספר).
האלגוריתם פורסם בשנת 1989 על ידי האחים דויד וגריגורי וולפוביץ' צ'ודנובסקי.
סיבוכיות האלגוריתם כדי לחשב ספרות היא .
האלגוריתם מבוסס על הטור האינסופי:
יישנם שלושה ביטויים מסוגים שונים, שהם סדרות בקצבים שונים וקבוע: בקצב פולינומי Mk, בקצב ליניארי Lk, בקצב אקספוננציאלי Xk, והקבוע C, שעל בסיסם ניתנת הנוסחה שהיא:
ניתן אף לשפר את הנוסחה על ידי הצבה של:
דוגמת קוד בפייתון של האלגוריתם
במדעי המחשב, אלגוריתם מונטה קרלו הוא אלגוריתם אקראי שהפלט שלו עשוי להיות שגוי בהסתברות מסוימת (בדרך כלל קטנה).
שתי דוגמאות לאלגוריתמים כאלה הן אלגוריתם קרגר ואלגוריתם מונטה קרלו עבור בעיית FAS מינימלית .
השם מתייחס לקזינו במונטה קרלו שבנסיכות מונקו, אשר ידוע ברחבי העולם כסמל להימורים.
המחלקה הקשורה של אלגוריתמים מסוג לאס וגאס היא אקראית גם כן, אבל בדרך אחרת: זמן הריצה שלהם משתנה באופן אקראי, אך הם תמיד מחזירים את התשובה הנכונה.
ניתן להמיר אלגוריתם מונטה קרלו לאלגוריתם לאס וגאס במקרים בהם קיימת פרוצדורה שיכולה לוודא כי הפלט הניתן על ידי אלגוריתם הוא אכן נכון.
אם המצב הוא כזה, אז האלגוריתם מסוג לאס וגאס שמתקבל הוא רק להריץ את האלגוריתם מסוג מונטה קרלו שוב ושוב עד שאחת הריצות מייצרת פלט שניתן לוודא שהוא נכון.
בעוד התשובה המוחזרת על ידי אלגוריתם דטרמיניסטי צפויה להיות נכונה תמיד, זה לא המצב באלגוריתם מונטה קרלו.
עבור בעיות הכרעה, אלגוריתמים אלו מסווגים בדרך כלל ל"נוטה ל-לא" או "נוטה ל-כן".
אלגוריתם מונטה קרלו הנוטה ל-לא צודק תמיד כשהוא מחזיר לא; אלגוריתם נוטה ל-כן צודק תמיד כשהוא מחזיר כן.
החלוקה מתארת אלגוריתמים עם שגיאה חד-צדדית, אך לאלגוריתמים אחרים ייתכן שלא תהיה נטייה לאחד הצדדים; לאלגוריתמים אלו נאמר שיש שגיאה דו-צדדית.
התשובה שהם מספקים (או כן או לא) תהיה נכונה או לא נכונה, בהסתברות חסומה כלשהי.
למשל, בדיקת הראשוניות של Solovay–Strassen משמשת כדי לקבוע אם מספר נתון הוא מספר ראשוני.
היא תמיד עונה כן עבור קלט שהוא מספר ראשוני; עבור מספר פריק, היא מחזירה לא בהסתברות לפחות ½ .
לפיכך, תשובה לא מהאלגוריתם היא נכונה בוודאות, ואילו תשובה כן נשארת בספק; לכן זהו אלגוריתם ½ נכון-נוטה-ללא.
עבור אלגוריתם מונטה קרלו עם שגיאה חד-צדדית, ניתן להקטין את ההסתברות לכישלון (ולהגביר את הסתברות ההצלחה) על ידי הרצת האלגוריתם k פעמים.
נקח לדוגמה שוב את אלגוריתם Solovay–Strassen שהוא ½ נכון-נוטה-ללא.
ניתן להריץ את האלגוריתם מספר פעמים ולהחזיר כתשובה לא אם קיבלנו תשובת לא אחת תוך k איטרציות, אחרת נחזיר כן.
לכן, אם המספר הוא ראשוני, אז התשובה תמיד נכונה, ואם המספר הוא פריק אז התשובה נכונה בהסתברות לפחות .
עבור אלגוריתם מונטה קרלו עם שגיאה דו-צדדית, גם כן ניתן להפחית את ההסתברות לכישלון על ידי הפעלת האלגוריתם k פעמים, והחזרת פונקציית רוב (majority) על התשובות.
לעומת זאת, מחלקת הסיבוכיות ZPP מתארת בעיות פתירות על ידי אלגוריתם לאס וגאס שתוחלת הזמן שלהם פולינומית.
ZPP ⊆ RP ⊆ BPP, אך לא ידוע אם מחלקה כלשהי מהן נבדלת מהאחרות; זאת אומרת, ייתכן שלאלגוריתמים מסוג מונטה קרלו יש יותר כח חישובי מאשר לאלגוריתמים מסוג לאס וגאס, אך זה לא הוכח.
מחלקת סיבוכיות נוספת, PP, מתארת בעיות הכרעה להן קיים אלגוריתם מונטה קרלו עם זמן פולינומי, שהוא מדויק יותר מאשר הטלת מטבע אך שלא ניתן בהכרח לחסום בהן את הסתברות השגיאה כקטנה ממש מ- ½ .
אלגוריתמים ידועים מסוג מונטה קרלו כוללים את בדיקת הראשוניות של Solovay–Strassen, בדיקת הראשוניות Baillie-PSW, בדיקת הראשוניות של מילר–רבין, וכמה גרסאות מהירות מסוימות של אלגוריתם Schreier–Sims בתורת הקבוצות החישובית.
אלגוריתם לָאנְצוֹשׁ (Lánczos) הוא אלגוריתם שפיתח המתמטיקאי ופיזיקאי ההונגרי-יהודי-אמריקאי קורנל לאנצוש ב-1950. האלגוריתם מוצא חלק (או את כל) הערכים עצמיים והווקטורים העצמיים של מטריצה הרמיטית (או סימטרית) בגודל במספר מוגבל של פעולות.
כמות הפעולות הנדרשת למציאת כל הערכים העצמיים והווקטורים העצמיים של מטריצה היא , אבל בעזרת אלגוריתם לאנצוש ניתן למצוא חלק מהערכים העצמיים בפחות פעולות.
למרות שהאלגוריתם יעיל חישובית, השיטה בהצגה המקורית שלה הייתה לא מועילה, מאחר שסבלה מחוסר יציבות נומרית.
ב-1970 הראו איביו וניומן איך לייצב את השיטה ויישמו זאת כדי לפתור מערכות הנדסיות גדולות מאוד.
בעבודה המקורית שלהם, הם הציעו שיטה לבחירת וקטור התחלתי.
מעט אחר כך ביצע כריסטופר פייג' אנליזה לשגיאה.
קלט: מטריצה הרמיטית בגודל , ומספר איטרציות (בשביל לקבל את כל הערכים העצמיים והווקטורים העצמיים במדויק, יש לבחור ).
למעשה, האלגוריתם לא צריך לקבל את המטריצה, אלא את היכולת להפעיל אותה על וקטורים.
פלט: מטריצה בגודל עם עמודות אורתונורמליות ומטריצה תלת-אלכסונית בגודל .
הערכים העצמיים של המטריצה "קרובים" לחלק מהערכים העצמיים של המטריצה המקורית .
בשביל לקבל את הערכים העצמיים של אפשר להשתמש למשל באלגוריתם QR.
מכיוון שהמטריצה היא מטריצה תלת-אלכסונית, הערכים העצמיים שלה מחושבים ב פעולות.
יהי וקטור שרירותי עם נורמה אוקלידית .
אחרת בחר את להיות וקטור שרירותי עם נורמה אוקלידית שיהיה אורתוגונלי לכל .
תהי המטריצה עם עמודות .
אחד המימושים המקובלים לאלגוריתם נמצא בחבילה ARPACK.
לדוגמה, המימוש באוקטבה (Octave) מתבסס על מימוש זה.
צעדת ג'רוויס או אלגוריתם עטיפת המתנה הוא אלגוריתם למציאת הקמור של נקודות במישור.
האלגוריתם נקרא על שם ריי ג'רוויס שפרסם את האלגוריתם בשנת 1973, אף על פי שהאלגוריתם התגלה במקביל בתקופה זו על ידי מספר חוקרים.
סיבוכיות זמן הריצה של האלגוריתם היא (O(nh כאשר n הוא מספר הנקודות הכולל ו-h הוא מספר הנקודות שירכיבו את הקמור בסופו של דבר.
האלגוריתם מוצלח במיוחד כאשר הקמור מורכב מנקודות מועטות יחסית, אך כאשר הקמור מורכב במיוחד יש להעדיף את הסריקה של גראהם.
קיים גם אלגוריתם המשלב בין יתרונותיהם של השניים ומשיג סיבוכיות משופרת.
ניתן להשתמש באלגוריתם גם עבור מספר רב של ממדים.
בתורת המספרים ובקריפטוגרפיה, אלגוריתם רו של פולרד ללוגריתם הבדיד הוא אלגוריתם הסתברותי לחישוב לוגריתם בדיד בחבורה ציקלית סופית מסדר ראשוני עם זמן ריצה דומה לשיטת כוח גס גנרית הנקראת אלגוריתם צעד-קטן צעד-גדול אך עם צריכת זיכרון שולית ביחס אליה.
האלגוריתם פותר את בעיית הלוגריתם הבדיד בהסתברות גבוהה, בסיבוכיות בסדר גודל של כאשר הוא סדר החבורה.
לצורך אלגוריתם פולרד ההנחה היא שסדר החבורה הוא מספר ראשוני, שאם לא כן, אפשר בשילוב עם אלגוריתם פוליג-הלמן לפתור את בעיית הלוגריתם הבדיד בזמן ריצה שהוא בסדר גודל כאשר הוא הגורם הראשוני הגדול ביותר של .
הרעיון של פולרד ניתן להרחבה לכל סוג של חבורה ציקלית, כמו חבורה אבלית מעל עקום אליפטי הידועה בפופולריות שלה בהצפנה המודרנית ולמעשה לא ידוע על אלגוריתם שמציג סיבוכיות טובה יותר לפתרון בעיית הלוגריתם הבדיד בעקום אליפטי.
בחבורה ציקלית מעל מספר ראשוני קיים אלגוריתם תחשיב אינדקסים עם זמן ריצה תת-מעריכי והוא נחשב ליעיל ביותר הידוע כיום למספרים גדולים אך אינו בר ביצוע בעקום אליפטי.
ב-1980 פיתח ריצ'רד ברנט גרסה משופרת יותר של אלגוריתם רו של פולרד לפירוק לגורמים שניתן ליישום גם לפתרון בעיית הלוגריתם הבדיד ומציע שיפור בפקטור של רבע ביעילותו לעומת הגרסה של פולרד.
מאוחר יותר פולרד וברנט פיתחו ושיפרו את האלגוריתם אף יותר.
ביטחון מערכות הצפנה מודרניות רבות מסתמך על ההשערה שקשה לפתור את בעיית הלוגריתם הבדיד (דיסקרטי) בחבורות מסוימות.
בהסתמך על בעיה זו ניתן להכין פונקציה חד-כיוונית שהיא הבסיס להצפנה אסימטרית.
הדוגמאות אולי החשובות ביותר הן פרוטוקול דיפי-הלמן וחתימה דיגיטלית DSA הפופולריים שמסתמכים על השערה זו, למרות שלא קיימת הוכחה מתמטית.
בעיית הלוגריתם הבדיד המסומנת בקיצור DLP היא כדלקמן:
נתונה חבורה ציקלית סופית מסדר המסומנת ונתון יוצר של החבורה ויהי אלמנט כלשהו.
מצא את הלוגריתם הבדיד של בבסיס בקיצור שהוא אלמנט יחיד בטווח המקיים: .
בעיית דיפי-הלמן בקיצור DHP, היא בעיה דומה שהועלתה לראשונה על ידי ויטפילד דיפי ומרטין הלמן במאמר המפורסם שלהם שבו הציגו לראשונה את הצפנת מפתח ציבורי ופרוטוקול שיתוף מפתח המבוסס על הבעיה הבאה: נתון המספר הראשוני ויוצר של החבורה וכן נתונים ו- (מודולו ).
בעיה זו נחשבת גם היא לבעיה קשה אם כי לא הוכח האם היא קשה לפחות כבעיית הלוגריתם הבדיד.
מאידך, כל דרך לפתרון בעיית הלוגריתם הדיקסרטי יכולה לשמש לפתרון בעיית דיפי-הלמן.
לדוגמה אם נתון המספר הראשוני החבורה היא חבורה ציקלית מסדר .
יוצר אפשרי אחד של חבורה זו יכול להיות .
(קל לראות שאם מעלים את 5 בחזקת כל המספרים מ-1 עד 96 (מודולו 97) מתקבלים כל האלמנטים של החבורה בלי יוצא מן הכלל לא בהכרח לפי סדר עולה).
אם נבחר בחשבון פשוט מתקבל לכן בחבורה .
אם נתונים האלמנטים ו- (מודולו 97) בעיית דיפי-הלמן היא לגלות את (כשהאלמנטים ו- אינם ידועים).
הבעיה נקראת לוגריתם בדיד כיוון שהיא עוסקת בקבוצה סופית מודולו שלם כלשהו הנקרא מודולוס.
ראוי לציין שאף-על-פי שקל לחשב לוגריתמים באופן כללי, אין הדבר נכון לגבי לוגריתם בדיד מכיוון שהתנהגות התוצאה נראית אקראית על פניה ולא ניתן לבצע קירוב.
הסיבה שהבסיס הוא יוצר היא כדי שהחבורה תהיה ציקלית כך שכל אלמנט בחבורה ניתן לייצוג כחזקה של היוצר.
הדרישה שהחבורה תהיה ציקלית אינה הכרחית, הגדרה כללית יותר של הבעיה, הנקראת בקיצור GDLP, היא מציאת אלמנט המקיים , בהנחה שקיים, עבור האלמנטים (כאשר אינו בהכרח יוצר).
החבורה החיבורית הנוצרת על ידי עקום אליפטי כאשר הפעולה היא חיבור נקודות בעקום היא דוגמה לחבורה שבה בעיית הלוגריתם הבדיד קשה.
אחת הדרכים לפתור את הבעיה היא בעצם חישוב איזומורפיזם בין חבורות.
אפילו אם שתי חבורות איזומורפיות זו לזו, אלגוריתם יעיל לפתרון בעיית הלוגריתם הבדיד בחבורה אחת, אינו בהכרח יעיל בחבורה השנייה.
למשל כל חבורה כפלית ציקלית מסדר איזומורפית לחבורה החיבורית הציקלית .
על כל פנים, בעוד שקיים אלגוריתם יעיל לחישוב לוגריתמים בחבורה החיבורית מעל המספרים השלמים מודולו מספר ראשוני, כלומר מציאת שלם המקיים , לא ניתן ליישמו לפתרון הלוגריתם הבדיד בחבורה הכפלית.
הדרך הישירה והפשוטה ביותר לפתרון בעיית הלוגריתם הבדיד היא שיטת כוח גס, סריקת כל החזקות של בזה אחר זה מ-1 עד עד שמתקבל וסיבוכיותה היא מסדר גודל .
היא אינה יעילה מהיבט קריפטוגרפי כיוון שאם גדול (נניח באורך סיביות) התקפה כזו אינה פרקטית.
שיטה מעט יותר טובה נקראת "צעד-קטן צעד-גדול" והיא מבוססת על העובדה שאם אפשר לכתוב את בצורה: (לפי כלל החילוק המודולרי) כאשר ו-.
לכן לאחר העברת אגפים מתקבל .
מהאמור עולה שאם מכינים טבלה המכילה את הזוגות () עבור כל המספרים מ-1 עד , הממויינת לפי האלמנט השני, מובטח שיימצא אלמנט אחד (אם קיים פתרון) השווה ל-.
היות שהטבלה היא בסדר גודל של השורש הריבועי של סדר החבורה וחיפוש בטבלה ממויינת אינו קשה, יוצא שסיבוכיות השיטה היא אך היא דורשת סיבוכיות מקום בסדר גודל של ועל כן אם גדול מאוד (נניח ) היא אינה פרקטית.
אלגוריתם רו של פולרד מנסה לייצר "סדרה פסידו-אקראית" של אלמנטים מהחבורה בהתבסס על רעיון מונטה קרלו וחיפוש אחר התנגשויות, כלומר שני אלמנטים זהים בסדרה.
אם נמצאה התנגשות הדבר מוביל לפתרון בעיית הלוגריתם הבדיד בהסתברות גבוהה.
שני רעיונות מרכזיים של פולרד הם פונקציה איטרטיבית אקראית קלה לחישוב, איתה מכינים את הסדרה הפסאודו-אקראית ואלגוריתם מציאת מחזוריות שמנסה למצוא בה התנגשות בזמן הקצר ביותר ללא שימוש בטבלאות.
לצורך הפשטות נניח שנתונה חבורה ציקלית מסדר ראשוני.
תחילה מחלקים את לשלוש קבוצות בגודל זהה בקירוב , בחלוקה לוגית בהתבסס על כלל מנחה קל לבדיקה.
אפשר למשל לחלק לפי משקלו של כל אלמנט באופן הבא הקבוצה תכיל את כל האלמנטים: , הקבוצה את האלמנטים והשלישית .
דרך אחרת יותר יעילה היא לחלק לפי הערך של הסיביות הכי פחות משמעותיות של כל כאשר תלוי במספר החלוקות (במקרה זה מספיק לבחון את שתי הסיביות האחרונות).
מספר החלוקות שרירותי וניתן לשינוי, אך יש צורך לשים לב לכמה היבטים חשובים בנוגע לחלוקה למשל .
מחשבים סדרה פסידו-אקראית של אלמנטים מהחבורה לפי הכלל הבא.
בוחרים אלמנט התחלתי ועבור כל מחשבים:
בנוסף מתוך הסדרה האמורה מכינים שתי רשימות של שלמים וכן כאשר ו- ועבור כל מחשבים את
הערכים של ו- מחושבים כך שעבור כל מתקיים .
אם כאשר זה אומר שנמצאה "התנגשות".
כדי למצוא התנגשות ביעילות האלגוריתם מנצל טכניקה המיוחסת לרוברט פלויד (לפי דונלד קנות') שנקראת מציאת מחזוריות או "שיטת הצב והארנב" שהיא שיטה יעילה לאיתור מחזוריות של פונקציה איטרטיבית אקראית על עצמה מהצורה .
מנסים באופן רקורסיבי לאתר את הנקודה בה הסדרה מתחילה לחזור על עצמה.
מבצעים בכל איטרציה שתי הליכות, הליכה איטית והליכה מהירה.
בהליכה איטית מחשבים מתוך הערכים מהאיטרציה הקודמת את השלשה החדשה () ובהליכה מהירה את ומשווים בין ל-, אם הם שווים אותרה מחזוריות הפונקציה וזה אומר שמנקודה זו ואילך המסלול יחזור על עצמו במעגל אין סופי.
סיבוכיות הטכניקה הזו זהה לשיטה הישירה המסתמכת על חיפוש בטבלאות ומבזבזת זיכרון רב.
אם נמצאה התאמה המשמעות היא ש- ולכן .
אם לוקחים לוגריתם בבסיס של שני האגפים במשוואה האחרונה מתקבל
בהנחה ש-, שבכל מקרה עלול לקרות בהסתברות מאוד זניחה.
מתוך המשוואה האחרונה אפשר לחלץ את על ידי הכפלה בהופכי הכפלי של .
קלט: החבורה מסדר , יוצר והאלמנט .
מחשבים את הערכים של מתוך הערכים הקודמים וכן לפי הנוסחאות המתוארות לעיל.
אם אלגוריתם מסתיים בכישלון אחרת מחזירים את .
במקרה הנדיר שהאלגוריתם מסתיים בכישלון מגרילים אחרים ומתחילים מההתחלה כאשר .
נתונה תת-חבורה של החבורה מסדר עם היוצר ונתון .
חלוקת האלמנטים של לשלוש קבוצות מתבצעת לפי הכלל הבא: מחשבים את , אם השארית 1 הוא שייך ל-, אם השארית היא 0 הוא שייך ל- ואילו אם השארית היא 2 הוא שייך ל-.
הטבלה הבאה מסכמת את מהלכי האלגוריתם והערכים של וכן לאחר כל איטרציה.
באיטרציה ה-14 נמצאה התנגשות כי .
לכן מחשבים את וההופכי שלו ולכן והפתרון הוא מודולו 191.
אלגוריתם רו של פולרד בעקום אליפטי
עקום אליפטי הוא כלי מתמטי פופולרי המצוי בשימוש נרחב בהצפנה מודרנית בשל העובדה שהוא מאפשר פרמטרים קטנים יותר בפקטור של עשר בקירוב לעומת אלגוריתם כמו RSA.
עם עקום אליפטי אפשר ליישם פונקציה חד-כיוונית ואיתה לממש הצפנה אסימטרית המבוססת על בעיה מתמטית כמו בעיית הלוגריתם הבדיד בעקום אליפטי.
בעיית הלוגריתם הבדיד בעקום אליפטי מקבילה לבעיה הכללית והיא כדלהלן:
נתון עקום אליפטי המוגדר מעל השדה , נתונה נקודה מסדר ונקודה , מצא שלם בטווח המקיים .
השלם נקרא הלוגריתם הבדיד של הנקודה בבסיס הנקודה או בקיצור .
אם הפרמטרים של העקום נבחרו בזהירות כדי להבטיח שלא יהיו קיצורי דרך לפתרון הבעיה בעקום זה, הדרך הטובה ביותר לפתרונה היא באמצעות אלגוריתם רו של פולרד בסיבוכיות של .
הסימון מייצג את כל הנקודות שהן כפולות של .
(כגון וכן הלאה עד ).
במילים אחרות, הנקודה היא תוצאה של חיבור הנקודה בעצמה (הנקראת בקיצור POINT_DBL) בדיוק פעמים והבעיה היא לגלות כמה פעמים בוצע החיבור, קרי לגלות את ערכו של .
לא קיימת דרך פשוטה לבצע זאת כי המסלול של הנקודות נראה אקראי.
שיטת כוח גס אינה מעשית משום שבמקרה הממוצע יש צורך לבדוק לפחות מחצית מהנקודות עד שנמצא .
אם כוח גס אינו מעשי.
כמובן שיש לשים לב של- יש לפחות גורם ראשוני אחד גדול דיו.
שאם לא כן אפשר לנצל את אלגוריתם פוליג-הלמן בזמן שהוא ביחס ישיר לגודל הגורמים הראשוניים שלו.
למעשה ככל שהגורם הראשוני שלו (לפחות אחד מהם) גדול יותר סיבוכיות ההתקפה תהיה גבוהה יותר.
כמו בחבורה ציקלית, הרעיון של אלגוריתם רו בעקום אליפטי הוא למצוא שני זוגות שלמים () וכן () מודולו המקיימים:
מזה נובע שאפשר לחשב את על ידי .
הדרך הישירה למצוא זוגות המקיימים את המשוואה האמורה היא על ידי בחירה אקראית ואחסון בטבלה.
אם מכינים טבלה המכילה את כל השלשות: () וממיינים לפי הערך השלישי, מובטח שבסופו של דבר הערך הזה יופיע פעם נוספת מה שיאפשר לגלות את הלוגריתם הבדיד כאמור.
תופעה שבה הערך השלישי מופיע פעמיים כאשר הערכים האחרים שונים נקראת "התנגשות".
לפי פרדוקס יום ההולדת מספר הניסיונות הצפוי לפני שתופיע התנגשות הוא בערך שזה בערך .
אולם החסרון בשיטה זו הוא שיש צורך בזיכרון רב, ליתר דיוק שלשות.
אלגוריתם רו מנסה להימנע משימוש בזיכרון על ידי שיטת הצב והארנב.
מגדירים פונקציה איטרטיבית אקראית כך שבהינתן והערכים ו- כך שמתקיים יהיה קל לחשב את ואת כך שמתקיים .
לדוגמה, אם מחלקים את החבורה הציקלית ל- רשימות בגודל זהה בקירוב (למשל ), מציבים כל נקודה ברשימה המתאימה אם הערך של 5 הסיביות הכי פחות משעותיות של הקואורדינטה של הנקודה הוא .
נניח ששיטת חלוקה זו תסומן ב- ונניח שהערכים ו- הם שלמים אקראיים כלשהם הנמוכים מ- כאשר מתפרס על פני כל הרשימות של , במקרה זה פונקציה אקראית איטרטיבית יכולה להיות:
ולכן אם אז הפונקציה האקראית היא כאשר וכן .
כל נקודה התחלתית מגדירה סדרה אחרת של נקודות כאשר כל נקודה מחושבת על ידי הנקודה הקודמת, .
היות שהחבורה הזו סופית בהכרח שתיגרם התנגשות, כלומר ערך של כלשהו יופיע שוב ומנקודה זו ואילך הסדרה תחזור על עצמה במעגל אין סופי.
כלומר יופיע האינדקס הקטן ביותר המקיים עבור כלשהו ומכאן ואילך עבור כל .
כאן הוא אורך השובל ו- הוא היקף מעגל במונחים של מספר האיטרציות של הפונקציה האיטרטיבית האקראית.
אם היא פונקציה אקראית אז ההתנגשות הראשונה צפויה לקרות לאחר צעדים בקירוב.
אורך השובל הוא ואורך המעגל צריך להיות בקירוב.
התנגשות היא מצב שבו כאשר ואותה אפשר למצוא ללא צורך בזיכרון באמצעות שיטת פלויד או שיטת הצב והארנב.
בשיטה זו מחשבים בכל צעד את הנקודות ו- ומנסים למצוא התאמה.
מספר הזוגות הצפוי שיש לבדוק הוא לכל הפחות זוגות ולכל היותר זוגות, עד שתמצא התנגשות.
ליתר דיוק בהנחה ש- אקראית מספר הזוגות הצפוי שצריך לבדוק עד שתמצא התנגשות הוא .
מספר החישובים שיש לבצע בעקום האליפטי הוא בערך פעולות חיבור נקודות.
אלגוריתם רו של פולרד לחישוב לוגריתם בדיד בעקום אליפטי.
תחילה בוחרים את מספר הענפים או רשימות ואת פונקציית החלוקה שמציבה כל נקודה ברשימה המתאימה לפי הכלל .
מגרילים שני שלמים ומחשבים את .
מגרילים זוג שלמים נוספים ומחשבים את .
אם האלגוריתם הסתיים בכישלון, אחרת מחזירים את .
נתון העקום עם המשוואה .
נקודה היא מסדר ראשוני .
כדי למצוא את מגדירים תחילה ובוחרים פונקציית חלוקה לפי הכלל:
הטבלה הבאה מציגה את השלשות () ו-() המתקבלות לאחר הצעד הרביעי באלגוריתם עבור המקרה .
אפשר לראות בשורה האחרונה בטבלה שהאלגוריתם מצא התנגשות כי:
בגלל הפופולריות של עקומים אליפטיים בקריפטוגרפיה, נעשה מאמץ לשפר את אלגוריתם רו של פולרד בין היתר על ידי עיבוד מקבילי.
נניח שזמינים מחשבים לצורך פתרון הבעיה.
הדרך הנאיבית היא להריץ את האלגוריתם על כל מחשב בנפרד עם נקודות התחלה אקראיות שונות, עד שאחד מהם יגלה התנגשות.
שיטה זו אינה מנצלת את פוטנציאל המקביליות כי השיפור בביצועים הוא בפקטור לכל היותר.
פול ואן-אורשוט ומייקל ויינר הציעו גרסה מקבילית של אלגוריתם רו שמניבה שיפור בביצועים בפקטור של .
הרעיון הוא לאפשר לכל הסדרות של כל המעבדים להתנגש אחת עם השנייה.
ביתר פירוט, כל מעבד בוחר לעצמו נקודת התחלה באופן אקראי בנפרד מהאחרים, אולם כל המעבדים משתמשים באותה פונקציה איטרטיבית כדי לחשב את האלמנט הבא בסדרה .
לכן, אם נוצרת התנגשות בין שתי סדרות, כל הנקודות של שתי הסדרות החל בנקודה שבה הופיעה התנגשות תהיינה זהות.
כדי להתאים את אלגוריתם פלויד למציאת מחזוריות בין סדרות נפרדות שנוצרות על ידי מעבדים שונים, נוקטים באסטרטגיה הבאה, בוחרים מאפיין ייחודי קל לזיהוי המשמש כ"נקודה מובחנת" (Distinguished Point).
נקודה מובחנת יכולה להיות כזו המכילה למשל רצף של אפסים מובילים בקואורדינטה שלה.
בכל פעם שמעבד נתקל בנקודה מובחנת כזו הוא משדר את הנקודה לשרת מרכזי שאוסף את כל הנקודות המובחנות מכל המעבדים וממיין אותם בזיכרון.
אם השרת מקבל בשלב כלשהו נקודה מובחנת שכבר התקבלה קודם לכן, הוא מחשב את הלוגריתם הבדיד ומסיים בהצלחה.
אם הפרופורציה של הנקודות המובחנות ב- היא הסיכויים לקבל התנגשות הם בערך לכן מספר פעולות כפל נקודות בעקום הצפוי מכל מעבד עד שמתקבלת התנגשות אחת הוא
בכך מושגת האצה ליניארית במהירות הביצוע של האלגוריתם ביחס למספר המעבדים הזמינים.
ההתקשרות עם השרת המרכזי היא מינימלית וכן אין צורך בתקשורת כלשהי של המחשבים בינם לבין עצמם מלבד עם השרת.
אפשר לשלוט בכמות הזיכרון הנדרשת בשרת המרכזי על ידי בחירה נכונה של תכונת ההבחנה באופן כזה שמצד אחד לא תהיה נדירה ויהיה קשה למצוא נקודה כזו אך מצד שני שלא תהיה תדירה מדי ואז כמות הזיכרון עלולה להיות מופרזת.
דרך נוספת לשפר ביצועים היא על ידי שימוש באוטומורפיזם.
יהי אוטומורפיזם של חבורה, כאשר היא נקודה בעקום מסדר .
בהנחה שקל לחשב את והיא מסדר .
כלומר הוא השלם הקטן ביותר כך ש- עבור כל ב-.
מגדירים יחס שקילות על המסומן על ידי
אם ורק אם עבור בטווח .
כאשר הוא המחלק הקטן ביותר של המקיים .
הרעיון בהאצת האלגוריתם הוא לשנות את פונקציית האיטרציה שתהיה מעל מחלקת השקילות .
כדי לעשות זאת מגדירים הצגה קנונית של של כל מחלקת שקילות .
למשל יכולה להיות הנקודה ב- שהקואורדינטה שלה היא השלם הקטן ביותר.
או למשל העתקת השלילה .
שאז אפשר להגדיר את פונקציית האיטרציה על ידי
אם נניח שקיים שלם המקיים אז, היות ש- היא אוטומורפית מתקבל עבור כל .
אם מוצאים שני שלמים המקיימים אז אפשר לחשב בקלות את השלמים המקיימים .
הפונקציה כאן משמשת כפונקציה איטרטיבית באלגוריתם רו בגרסה המקבילית שלו עם מעבדים.
הנקודה התחלתית של כל סדרה היא כאשר ו- הם שלמים אקראיים הנמוכים מ-.
הנקודות הבאות בכל סדרה מחושבות על ידי .
אם רוב מחלקות השקילות של הן באורך אז טווח החיפוש מצטמצם ל- ולכן זמן הרצוי המשוער של האלגוריתם בגרסה משופרת זו הוא
זהו שיפור בפקטור של במהירות הביצוע.
אם משתמשים בהעתקת השלילה כאוטומורפיזם, מושג שיפור בפקטור של .
במקרה של עקום קובליץ מעל שהוא עקום פופולרי בתקנים של NIST וסרטיקום, העתקת פרובניוס המוגדרת על ידי וכן גם היא אוטומורפיזם של חבורה מסדר והיא קלה לחישוב היות שהעלאה בריבוע היא פעולה קלה בשדה הבינארי (בהצגה פולינומית העלאה בריבוע מודולו 2 שקולה למעשה להכנסת אפסים בין כל הספרות לסירוגין).
אם הוא מסדר ראשוני כך ש- אינו מחלק של סדר העקום המסומן ב- אז ולכן היא אוטומורפית.
יהי אפשר להוכיח שאחד מהפתרונות של המשוואה המודולרית מקיים .
לכן באופן דומה, הגרסה המקבילית של אלגוריתם רו עם מעבדים המשתמשת במחלקות השקילות תחת העתקת פרובניוסמגיעה לזמן ריצה של
ואם מנצלים גם את העתקת השלילה מושג שיפור כולל בזמן הריצה בפקטור של .
למשל ההערכה המקורית שניתנה ב-1996 הייתה שכדי לפתור את בעיית הלוגריתם הבדיד בעקום אליפטי מסדר 113 בהנחה שזמינים 10,000 מעבדים לצורך המשימה כשכל אחד מהם מסוגל לבצע איטרציה אחת בעשר מילישניות, אם אז מספר החזרות הצפוי בכל מעבד לפני שמוצאים לוגריתם הוא
שזה שקול בערך ל-1045 ימים או שלוש שנות עיבוד עם כמות של כארבע גיגה-בית זיכרון.
הערכות יותר מעודכנות קצת יותר אופטימיות.
לדוגמה ב-2002 הצליח צוות חוקרים בראשות קריס מוניקו לפצח את העקום האליפטי ECCp-109 עם 10,000 מחשבים שעבדו במקביל בסך הכול 549 ימים.
הם השתמשו בגרסה משופרת של אלגוריתם רו של פולרד והצליחו לפתור את בעיית דיפי-הלמן בעקום זה.
אלגוריתם רשויות ורכזים (Hubs and Authorities; בשמו הרשמי Hyperlink-Induced Topic Search, בראשי תיבות: HITS) הוא אלגוריתם לניתוח קישורים אשר נועד לדרג דפי אינטרנט, ופותח על ידי ג'ון קליינברג .
הרעיון מאחורי HITS נבע מתוך הצורך בהבנה מעמיקה של יצירת דפי האינטרנט וחיפושם בזמן המצאת האינטרנט.
דף אינטרנט נקרא "רכז" אם הוא מצביע על הרבה דפי אינטרנט אחרים.
דף "רשות" טוב הוא דף אשר הרבה רכזים מצביעים עליו.
האלגוריתם, אם כן, פולט שני פרמטרים לכל דף, "רשות" אשר מעריך את הקישורים אל העמוד, ו"רכז" אשר מעריך את הקישורים מהעמוד לעמודים אחרים.
האלגוריתם נוצר על ידי ג'ון קלינברג בשנת 1997 בעת שעבד ב-IBM ונועד לדרג אתרים, מבחינת דיוק נחשב למדויק ביותר מבין האלגוריתם אבל מבחינת יעילות נחשב למוצלח פחות.
בשל היותו פחות יעיל מאלגוריתם אחרים אין כמעט מנועי חיפוש שמשתמשים בו.
חברות החיפוש מעדיפות להשתמש ב-PageRank של גוגל אשר מבחינת יעילות נחשב לטוב ביותר, אחד ממנועי החיפוש הגדולים אשר עדיין משתמשים באלגוריתם HITS הוא ask.com אשר מטרתו לתת למשתמש את התשובה הטובה ביותר לכל שאלה.
בעוד ש-PageRank שולף ממאגר נתונים את תוצאות החיפוש בתוך זמן אפסי (ננושניות בודדות), כל חיפוש בעזרת אלגוריתם HITS מצריך להפעיל את האלגוריתם מחדש מה שגורם לתוצאות החיפוש להיות אטיות באופן משמעותי.
ישנם כתבי עת אשר נחשבים למשפיעים יותר מאשר כתבי עת אחרים, למשל Science ו-Nature.
כאשר משווים שני כתבים עת מודדים אותם על פי מספר הציטוטים בהם, בעזרת האלגוריתם ניתן לתת ערך רב יותר לציטוטים מאתרים כמו Science ו-Nature מאשר מציטוטים מאתרים פחות נחשבים.
במילים אחרות עדיף לקבל אזכורים בכתבי עת נחשבים מאשר מכתבי עת פחות נחשבים ואת זה האלגוריתם עושה בהצלחה.
תופעה זו קיימת גם באינטרנט, ספירת הקישורים שמובילים לדף מסוים יכולה לתת הערכה על האיכות שלו, או לפחות על ההתבלטות שלו ברשת, אך לעיתים דף עם פחות קישורים יכול להיות משמעותי יותר אם הקישורים מופנים ממנועים חיפוש גדולים כגון יאהו, גוגל, MSN.
באלגוריתם HITS השלב הראשון הוא למצוא מספר עמודים מצומצם הכי רלוונטיים בעזרת אלגוריתם חיפוש מבוסס טקסט, לקבוצת דפים זו נקרא "קבוצת השורש".
לאחר מכן ניצור "קבוצת בסיס" אשר תכלול בתוכה את "קבוצת השורש" והקשרים אשר יוצאים ממנה, בנוסף לכך נכלול מספר עמודים אשר מקושרים לדפים בקבוצת השורש.
בזכות יצירת כל הקשרים למעלה נוצר תת-גרף, בשביל לחסוך בזמן ריצה, אלגוריתם HITS רץ רק על תת-הגרף שנוצר ולא על האינטרנט כולו.
לדברי קלינברג, רוב הרשויות הרלוונטיות יהוו חלק נכבד "מקבוצת הבסיס" ובכך האלגוריתם יחזיר תשובה נכונה ככל הניתן.
ערכי הרשות והרכז נקבעים זה מתוך זה.
ערך הרשות של דף יעלה אם רכז טוב מצביע עליו, ובאופן דומה ערכו של רכז יעלה אם הוא מצביע על רשות טובה.
האלגוריתם רץ מספר מחזורים, אשר מבצעים בכל מחזור שני שלבים בסיסים:
עדכון ערך רשות: מבצעים סכימה של כל ערכי הרכזים אשר מצביעים על דף זה, מחלקים במספר הרכזים ומעדכנים את ערכה של הרשות.
נובע מכאן שככל שהרכזים יהיו בעלי ערך רב יותר כך ערך הרשות יהיה גבוה יותר.
עדכון ערך רכז: מבצעים סכימה של כל ערכי הרשויות אשר רכז זה מצביע עליהם, מחלקים במספר הרשויות ומעדכנים את ערכו בהתאם.
ככל שערך הרשות גבוהה יותר כך ערך הרכז יעלה.
האלגוריתם לחישוב הרכז והרשות מחושב כך:
בתחילה כל צומת (דף) מקבל ציון 1 לרשות ולרכז.
מעדכנים את ערכה של כל רשות.
מעדכנים את ערכו של כל רכז.
מנרמלים את הערכים על ידי חילוק כל ציון רכז בסכום כל ציוני הרכזים בריבוע, וכן חילוק כל ציון רשות בסכום כל ציוני הרשויות בריבוע.
חזרה על שלב העדכון, אם נדרש.
HITS, כמו אלגוריתמי חיפוש אחרים, הוא אלגוריתם לולאתי שמבוסס על קישורים באינטרנט.
למרות זאת ישנם כמה הבדלים מהותיים:
הוא מבוסס שאילתה, זאת אומרת, ציוני הרשות והרכז הנובעים מניתוח הקישור מושפעים ממונחי החיפוש.
מבוסס שאילתה ולא אינדקס, בשל כך זמן החיפוש הוא ארוך יותר.
לא נפוץ בקרב מנועי חיפוש (אחד ממנועי החיפוש היחידים אשר משתמשים באלגוריתם דומה לו הוא Ask.com).
לעומת אלגוריתמים אחרים שמחשבים תוצאה אחת, HITS מחשב שתי תוצאות (רכז ורשות).
הוא מנתח מספר קטן של דפים רלוונטיים ("קבוצת הבסיס"), לא כמו PageRank שמנתח את הדפים.
על מנת להתחיל את הדירוג, דרגת כל רשות ורכז ייקבעו ל-1.
אנו מתכוונים לבצע שני עדכונים: עדכון ערכי רשויות, ועדכון ערכי רכזים.
כלל עדכון הרשויות – לכל רשות p נבצע עדכון של ערכה –
כאשר n מייצגת את מספר הרכזים אשר מפנים אל רשות זו.
כלל עדכון הרכזים – לכל רכז p נבצע עדכון של ערכו –
כאשר m מייצגת את מספר הרשויות אשר רכז זה מצביע עליהן.
על מנת להגיע לתוצאה אופטימלית מבצעים על תהליך החישוב מספר חזרות, ואחרי כל חזרה מעדכנים את ערך הרשות/רכז.
בתורת החבורות ובקריפטוגרפיה אלגוריתם פוליג-הלמן הוא אלגוריתם לפתרון בעיית הלוגריתם הבדיד במקרה הפרטי כאשר סדר החבורה הוא מספר חלק (שגורמיו הראשוניים קטנים).
האלגוריתם הומצא ב-1978 על ידי סטיבן פוליג ומרטין הלמן.
בעיית הלוגריתם הבדיד הכללית היא: בהינתן חבורה ציקלית מסדר ויוצר ויהי איבר כלשהו.
הוא נקרא הלוגריתם הבדיד של בבסיס בקיצור .
אם ראשוני, אלגוריתם צעד-קטן צעד-גדול פותר את הבעיה בסיבוכיות זמן של צעדים ובסיבוכיות מקום זהה.
אלגוריתם רו של פולרד פותר את הבעיה בזמן דומה אך ללא צריכת זיכרון משמעותית.
בעיית הלוגריתם הבדיד נחשבת במקרה הכללי לבעיה קשה.
האלגוריתם הטוב ביותר הידוע לפתרון הבעיה כאשר סדר החבורה הוא מספר ראשוני הוא אלגוריתם רו של פולרד המבוסס על אלגוריתם צעד-קטן צעד-גדול.
אלגוריתם פוליג הלמן מנסה להאיץ את חישוב הלוגריתם הבדיד במקרה שסדר החבורה אינו ראשוני וידועים גורמים לא טריוויאליים שלו.
ידוע שהסדר של האיבר הוא השלם הקטן ביותר המקיים .
יהי הסדר של ונניח שקיים שלם שהוא מחלק שלו () אז הסדר של הוא .
הכללה של משפט השאריות הסיני אומרת שאם ידוע הפירוק: כאשר כל זר יחסית לגורמים האחרים (כלומר עבור כל ) כאשר gcd היא מחלק משותף מקסימלי, אז קיימת התאמה או איזומורפיזם בין החבורות למכפלה הקרטזית שלהם וקיימת דרך יעילה לעבור בין הייצוגים השונים.
בהינתן היוצר ואיבר כלשהו נניח ואנחנו מעוניינים למצוא את כך שמתקיים , נניח שהסדר של הוא וידועים לנו הגורמים שלו: (הגורמים לא חייבים להיות ראשונים כל עוד הם זרים זה לזה), אז ידוע שמתקיים:
אם עבור כל אז מתקבלות בעיות של לוגריתם בדידי ב- חבורות, כל אחת מסדר שהסדר שלהן קטן משמעותית מ-.
אם נפתור את המופעים הללו בעזרת כל אלגוריתם כוח גס לפתרון בעיית לוגריתם בדיד, נוכל לפתור את הבעיה בחבורה הגדולה (נובע ממשפט השאריות הסיני).
כלומר הלוגריתמים הבדידיים מ-1 עד מקיימים: .
היות ש- שקול ל- מודולו עבור כל לפי משפט השאריות הסיני למערכת המשוואות הבאה:
יש פתרון יחיד מודולו .
כך שאפשר לחשב אותו מתוך עם אלגוריתם כמו אלגוריתם גאוס או אלגוריתם של גרנר (מתואר בהמשך).
תיאור אלגוריתם פוליג-הלמן מתוך הספר "מבוא למתמטיקה של ההצפנה".
תהי חבורה ונניח שיש לנו אלגוריתם לפתרון בעיית הלוגריתם הבדיד ב- עבור כל איבר מסדר שהוא חזקה ראשונית (מתואר בהמשך).
למשל אם הוא מסדר ונניח שיש לנו אלגוריתם שפותר את הבעיה בסיבוכיות של .
אם הסדר של הוא שניתן לפירוק מהצורה אז אפשר לפתור את בעיית הלוגריתם הבדיד בסיבוכיות של
היות שכל הוא מסדר חזקה ראשונית, אפשר להשתמש באלגוריתם לפתרון בעיית הלוגריתם הבדיד עם סדר מחזקה ראשונית שמתואר להלן, כתת-שגרה שלו, כדי לפתור את הבעיה .
פותרים את מערכת המשוואות המודולרית בעזרת משפט השאריות הסיני:
אלגוריתם פוליג-הלמן בעצם מצמצם את בעיית הלוגריתם הבדיד של איבר מסדר כלשהו לבעיית הלוגריתם הבדיד של איבר מסדר שהוא חזקה של ראשוני.
לכן בעיית הלוגריתם הבדיד בחבורה קלה לפתרון אם הסדר של החבורה הוא כפולה של ראשוניים קטנים.
למשל במקרה של השדה אם מתפרק לגורמים קטנים אז לא מומלץ להשתמש בשדה הזה אם רוצים חבורה שבה הבעיה נחשבת קשה.
מה שאפשר לעשות זה למצוא שדה כזה כך שהראשוני שווה כאשר ראשוני וכן לבחור יוצר מסדר ואז עובדים בתת-חבורה מסדר של וסיבוכיות פתרון בעיית הלוגריתם הבדיד בתת-חבורה זו יהיה מסדר .
בגלל שאלגוריתם תחשיב אינדקסים הוא תת-מעריכי צריך להיות גדול.
יתרה מזו אפשר לצמצם את בעיית הלוגריתם הבדיד של איבר מסדר חזקה ראשונית לסדר ראשוני בסיבוכיות (להיפטר מהחזקה).
בגלל הטריק הבא: אם הוא מסדר אז הוא מסדר .
אם חוזרים על פעולה זו מספר פעמים אפשר להגיע לפתרון הלוגריתם הבדיד.
הרעיון הוא לכתוב את המעריך בצורה:
ואז לחשב רקורסיבית את .
היות ש- הוא מסדר מזה נובע ש:
הראשון נובע מהעלאת שני האגפים של בחזקת .
השני נובע מההצגה המורחבת של השלישי נובע מהעובדה ש-.
הוא לוגריתם בדיד שהבסיס שלו הוא איבר מסדר .
ההנחה היא שאפשר לפתור בעיה זו ב- צעדים.
אם פתרנו את המשווה הזו נוכל למצוא את עם המאפיין:
בשלב הבא מבצעים חישוב דומה והפעם מעלים את שני האגפים של בחזקת ומקבלים את:
היות שאנחנו כבר יודעים את ערכו של , כדי למצוא את אנחנו צריכים לחשב את הלוגריתם הבדיד
שוב אפשר עם האלגוריתם לפתרון לוגריתם בדיד מסדר ראשוני ב- צעדים למצוא את ואז קיבלנו את ו- המקיימים:
באותה דרך אפשר למצוא את , באופן כללי אחרי שאנחנו יודעים מהם הערכים של אז אפשר לחשב את על ידי פתרון:
כל לוגריתם כזה ניתן לפתרון בזמן שורש צעדים.
לכן אחרי צעדים אפשר לקבל את המעריך המקיים .
והבעיה היא לפתור את המשוואה בשדה שהוא מסדר 11250. במקרה זה פותרים את הלוגריתם הבדיד של תת-בעיות מסדר נמוך לפי הגורמים הראשוניים של .
שני הגורמים הראשונים קטנים לכן הפתרון שלהם טריוויאלי.
להלן דוגמה לפתרון בעיית הלוגריתם הבדיד בסדר של הגורם השלישי.
אנחנו מנסים לפתור את המשוואה בשדה .
היות שהראשוני נבחר בצורה כזו ש- מתחלק ב- ולכן הוא מסדר בשדה .
פותרים אותו בהדרגה כדי לקבל את כדלהלן:
1. הצעד הראשון הוא לפתור את המשוואה , שמצטמצמת למשוואה זה קל כי הוא הפתרון היחיד ובשלב זה ערכו של הוא .
2. בצעד השני מנסים לפתור את:
כל מה שצריך לבדוק עבור זה ערכים בטווח 1 עד 4. כך שאפשר לפתור את זה בכוח גס די בקלות.
במקרה זה הפתרון הוא , לכן בשלב זה ערכו של הוא .
3. ממשיכים לצעד הבא ומנסים לפתור את:
שמצטמצמת למשוואה לכן והמשמעות במקרה זה היא שערכו של נשאר 11 בשלב זה.
4. הצעד הבא והאחרון הוא לפתור את:
5. התוצאה האחרונה היא , שהפתרון שלה הוא לכן התשובה הסופית היא:
אפשר לראות שמתקיים בשדה .
להלן דוגמה לאלגוריתם פוליג הלמן המשתמש במשפט השאריות הסיני כדי לחבר ביחד את כל הפתרונות לפתרון השלם.
בטבלה הבאה מוצגים פתרונות שלוש תת-הבעיות:
הבעיה המופיעה בשורה השלישית היא הבעיה מהדוגמה הקודמת.
בשלב זה מנצלים את משפט השאריות הסיני כדי לפתור את מערכת המשוואות המודולרית:
אלגוריתם גרנר לפתרון מערכת משוואות מודלרית לפי משפט השאריות הסיני.
קלט: שלם חיובי שהוא כפולה של שלמים חיוביים זרים זה לזה וייצוג מודולרי (השאריות) של מודולו בהתאמה.
פלט: שלם המקיים את משוואת CRT.
עבור עד מחשבים את: .
במדעי המחשב, אלגוריתם רבין–קארפ (או קארפ–רבין) הוא אלגוריתם לחיפוש מחרוזת, שנוצר על ידי תבנית:Harvs, ומשתמש בגיבוב (hashing) כדי למצוא התאמה מדויקת של מחרוזת דוגמה בתוך טקסט.
האלגוריתם עושה שימוש ב־rolling hash (גיבוב מתגלגל) כדי לסנן במהירות מיקומים בטקסט שלא יכולים להכיל את הדוגמה, ורק לאחר מכן בודק התאמה במיקומים שנשארו.
הכללות של אותו רעיון מאפשרות למצוא יותר מהתאמה אחת של דוגמה בודדת, או למצוא התאמות עבור מספר דוגמאות שונות.
כאשר מחפשים התאמה אחת לדוגמה אחת, זמן הריצה המצופה של האלגוריתם הוא ליניארי באורך הכולל של הדוגמה והטקסט, אם כי במקרה הגרוע זמן הריצה עלול להיות מכפלת שני האורכים.
כאשר מחפשים התאמות רבות, זמן הריצה המצופה הוא ליניארי באורכי הקלט, בתוספת האורך הכולל של כל ההתאמות – דבר שיכול לחרוג מזמן ליניארי.
לעומת זאת, אלגוריתם אהו–קורסיק (Aho–Corasick) יכול למצוא את כל ההתאמות של מספר דוגמאות בזמן ובזיכרון ליניאריים באורך הקלט ובמספר ההתאמות (ולא באורך הכולל שלהן).
יישום מעשי של האלגוריתם הוא בזיהוי העתקות (פלגיאט).
בהינתן חומר מקור, האלגוריתם יכול לסרוק במהירות מסמך כדי למצוא משפטים מתוך החומר המקורי, תוך התעלמות מפרטים כמו אותיות רישיות או סימני פיסוק.
בשל הכמות הרבה של המחרוזות המבוקשות, אלגוריתמים לחיפוש של מחרוזת אחת אינם מעשיים.
אלגוריתם חיפוש מחרוזת נאיבי משווה את מחרוזת הדוגמה לכל מיקום אפשרי בטקסט הנתון.
כל השוואה כזו לוקחת זמן פרופורציונלי לאורך הדוגמה, ומספר המיקומים בטקסט פרופורציונלי לאורך הטקסט.
לכן, זמן הריצה במקרה הגרוע הוא מכפלת שני האורכים – של הדוגמה ושל הטקסט.
במקרים מעשיים רבים ניתן לקצר את זמן הריצה על ידי הפסקת ההשוואה ברגע שמתגלה חוסר התאמה, אך גישה זו אינה מבטיחה שיפור מהותי בביצועים.
מספר אלגוריתמים מתקדמים לחיפוש מחרוזת, כמו אלגוריתם Knuth–Morris–Pratt ואלגוריתם Boyer–Moore, משפרים את זמן הריצה במקרה הגרוע על ידי שימוש במידע נוסף שמתקבל מכל חוסר התאמה, כדי לדלג על מיקומים בטקסט שבוודאות לא יתאימו לדוגמה.
לעומתם, האלגוריתם של רבין–קארפ משיג את שיפור הביצועים שלו באמצעות פונקציית גיבוב, אשר מבצעת בדיקה מקורבת (approximate check) בכל מיקום.
השוואה מדויקת מתבצעת רק אם תוצאת הגיבוב של תת-המחרוזת שווה לזו של הדוגמה.
פונקציית גיבוב היא פונקציה שממירה מחרוזת לערך מספרי הנקרא ערך הגיבוב שלה.
לדוגמה: hash("hello") = 5. אם שתי מחרוזות שוות, ערכי הגיבוב שלהן בהכרח שווים.
בפונקציית גיבוב טובה, גם הכיוון ההפוך מתקיים באופן הסתברותי – מחרוזות שונות כמעט תמיד יניבו ערכי גיבוב שונים.
האלגוריתם של רבין–קארפ מחשב, בכל מיקום בטקסט, את ערך הגיבוב של תת-מחרוזת באורך זהה לדוגמה.
אם ערך הגיבוב תואם לזה של הדוגמה – מתבצעת בדיקה מלאה של התאמה באותו מיקום.
כדי שהאלגוריתם יעבוד ביעילות, יש לבחור פונקציית גיבוב מתוך משפחה של פונקציות גיבוב, כך שסביר שלא יהיו הרבה התאמות שווא – מיקומים בטקסט עם ערך גיבוב זהה לדוגמה אך ללא התאמה אמיתית.
מיקומים כאלה מוסיפים זמן ריצה מיותר לאלגוריתם.
בנוסף, חשוב שפונקציית הגיבוב תהיה גיבוב מתגלגל (rolling hash) – פונקציית גיבוב שאפשר לעדכן את ערכה במהירות ממיקום אחד בטקסט למיקום הבא, בלי לחשב מחדש את כל הגיבוב מהתחלה, דבר שהיה גוזל זמן רב.
return not foundהשורות 2, 4 ו־6 דורשות כל אחת זמן ריצה של O(m).
עם זאת, שורה 2 מבוצעת רק פעם אחת, ושורה 6 מתבצעת רק אם ערכי הגיבוב תואמים – דבר שלא סביר שיקרה יותר מפעמים ספורות.
שורה 5 מתבצעת O(n) פעמים, אך כל השוואה בה לוקחת זמן קבוע, ולכן ההשפעה שלה היא בסך הכול O(n).
חישוב נאיבי של ערך הגיבוב של תת-המחרוזת s[i+1..i+m] דורש O(m) זמן, כיוון שיש לבדוק כל תו בנפרד.
מאחר שחישוב הגיבוב מתבצע בכל איטרציה של הלולאה, האלגוריתם עם חישוב גיבוב נאיבי דורש זמן כולל של O(mn) — אותה סיבוכיות כמו אלגוריתם חיפוש מחרוזת פשוט.
כדי להשיג מהירות, יש לחשב את הגיבוב בזמן קבוע.
ה"טריק" הוא שהמשתנה hs כבר מכיל את ערך הגיבוב של s[i..i+m-1].
אם ניתן להשתמש בערך הזה כדי לחשב את ערך הגיבוב הבא בזמן קבוע, אז חישוב ערכי הגיבוב העוקבים יהיה מהיר.
ניתן לנצל את הטריק הזה באמצעות גיבוב מתגלגל (rolling hash) — פונקציית גיבוב שמעוצבת במיוחד כדי לאפשר את הפעולה הזו.
פונקציית גיבוב מתגלגל פשוטה (אך לא מאוד טובה) פשוט מחברת את הערכים של כל התווים בתת-המחרוזת.
הפונקציה הזו מאפשרת לחשב את ערך הגיבוב הבא מתוך הערך הקודם בזמן קבוע, באמצעות הנוסחה:
כלומר, מסירים את ערך התו הראשון בתת-המחרוזת הקודמת, ומוסיפים את ערך התו החדש שנכנס.s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
אלגירדס מיקולאש ברזאוסקאס (; 22 בספטמבר 1932 – 26 ביוני 2010) היה נשיאה וראש ממשלתה של ליטא.
ברזאוסקאס נולד בעיר רוקישקי בשנת 1932. בשנת 1951 סיים את בית הספר התיכון Kaišiadorys ובאותה שנה נכנס למכון הפוליטכני של קובנה.
הוא סיים את לימודיו במכון הפוליטכני של קובנה ב-1956 כמהנדס אזרחי במגמת ההתמחות בהנדסה הידראולית.
ב-1974, השלים תואר דוקטור בכלכלה.
בשנים 1956 - 1960 שירת שירות חובה בצי הסובייטי.
לאחר שחרור מן השירות, עבד במשרות בכירות בחברות הבנייה ובממשל הליטאי במפלגה הקומוניסטית הליטאית.