tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
[S[i יסמן את התו באינדקס ה-i של המחרוזת S, החל מ-1.
[S[i..j יסמן את תת-המחרוזת ב S אשר מתחילה בתו i ומסתיימת בתו j, כולל.
תחילית של S היא תת-מחרוזת S[1..i] עבור i כלשהו בטווח , כאשר n היא אורך המחרוזת S.
סיפא של S היא תת-מחרוזת S[i..n] עבור i כלשהו בטווח [1, n], כאשר n היא אורך המחרוזת S.
מחרוזת החיפוש תסומן באמצעות P ותקרא לעיתים תבנית החיפוש.
האורך שלה יסומן באמצעות n.
הטקסט שבו מחפשים את מחרוזת החיפוש מסומן באמצעות T.
האורך שלו יסומן באמצעות m.
עימוד של P ל T הוא אינדקס k ב T שבו התו האחרון של P מועמד מול האינדקס k של T.
התאמה של P קוראת בעימוד אם P שווה ל T[(k-n+1)..k].
אלגוריתם בויאר-מור מחפש מופעים של מחרוזת חיפוש P בטקסט שבו מחפשים T באמצעות השוואת תווים בעימודים שונים.
במקום שימוש בחיפוש כוח גס של כל העימודים (ישנם כאלו), בויאר-מור משתמש במידע מעיבוד מקדים של תבנית החיפוש P על מנת לדלג על מספר עימודים גדול ככל האפשר.
לפני שהוצג אלגוריתם זה, השיטה הנהוגה לחיפוש טקסט הייתה לבדוק כל תו בטקסט ביחס לתו הראשון במחרוזת החיפוש, ואם נמצאה התאמה נעשה חיפוש בהתאם לתו הבא במחרוזת החיפוש וכן הלאה.
בצורה זו נדרשים להשוות כל תו בטקסט.
ההבחנה החשובה באלגוריתם זה היא שאם סוף מחרוזת החיפוש מושוות לטקסט, ניתן לדלג על תווים בחיפוש ולא לבדוק כל תו בטקסט.
הסיבה לכך היא שאם משווים את התו האחרון של תבנית החיפוש לתו בטקסט ואין התאמה, אין צורך לחפש אחורנית בתבנית החיפוש.
אם התו בטקסט לא מתאים לאף אחד מהתווים בתבנית החיפוש, אז התו הבא להשוואה בטקסט נמצא n תווים בהמשך, כאשר n הוא אורך תבנית החיפוש.
אם התו נמצא בתבנית החיפוש, נדרשת הזזה חלקית של תבנית החיפוש אל התו המתאים והתהליך חוזר על עצמו.
החיפוש בטקסט באמצעות דילוגים לעריכת השוואות במקום לבדוק כל תו ותו מצמצם את מספר ההשוואות הנדרשות ובכך תורם ליעילות האלגוריתם.
באופן פורמלי יותר, האלגוריתם מתחיל בעימוד , כך שהתחלת תבנית החיפוש P מועמדת מול ההתחלה של הטקסט T.
נערכת השוואה בין התווים ב-P וב-T אשר מתחילה מהאינדקס n בתבנית P ו-k ב-T, והולכת אחורה: המחרוזות מושוות ביחס לסופה של P ועד לתחילתה.
ההשוואות ממשיכות עד הגעה לתחילתה של תבנית החיפוש P (במקרה של התאמה) או עד לאי התאמה שבעקבותיה העימוד מוזז קדימה בהתאם לערך המותר המרבי בהתאם למספר כללים.
ההשוואות נערכות פעם נוספת בעימוד החדש, והתהליך חוזר על עצמו.
חוקי ההזזה ממומשים באמצעות טבלת חיפוש המוגדרת באמצעות עיבוד מקדים של תבנית החיפוש P.
ההזזה מחושבת באמצעות שני כללים: כלל התו הלא מתאים, וכלל הסיפא הטובה.
הזזה בפועל היא הערך המרבי המוגדר על ידי שני כללים אלו.
הדגמה של הכלל עבור תבנית החיפוש NNAAMAN.
כלל התו הלא מתאים מתייחס לתו ב-T שבו ההשוואה נכשלת.
המופע הקודם של תו זה ב-P נמצא, ומוצעת הזזה המעבירה את המופע אל מול האי התאמה ב-P.
אם התו הלא מתאים לא נמצא מלפני P, מוצעת הזזה המזיזה את P מעבר לתו הלא מתאים.
ישנן שיטות שונות בנוגע לטבלאות חיפוש עבור כלל התו הלא מתאים, להלן גרסה פשוטה הפועלת בזמן קבוע: יוצרים מערך דו־ממדי שבו האינדקס הראשון הוא התו c באלפבית והאינדקס השני הוא האינדקס i בתבנית החיפוש.
טבלת החיפוש תחזיר את המופע של c ב P עם האינדקס השני בגודלו או אם לא נמצא מופע.
ההסטה המוצעת תהיה , כשסיבוכיות הזמן הנדרשת היא וסיבוכיות המקום היא , בהנחה של אלפבית סופי באורך k.
הדגמה של הכלל עבור תבנית החיפוש ANAMPNAM.
כלל הסיפא הטובה הוא כלל מורכב יותר ביחס לכלל הקודם.
הוא הסיבה לכך שההשוואות נעשות מסוף תבנית החיפוש ולא מתחילה.
נניח כי עבור עימוד מסוים של תבנית החיפוש P ו T, תת-מחרוזת t של T מתאימה לסיפא של P, אך יש אי התאמה בהשוואה הבאה (בתו הקודם).
במקרה זה מחפשים, במידה וקיים, את העותק האחרון של t ב P כך ש אינה סיפא של P והתו הקודם ל ב P שונה מהתו הקודם ל t ב P.
נעשית הסטה של P קדימה כך שתת-המחרוזת ב P מועמדת מול תת-המחרוזת t ב T.
אם לא קיימת, מזיזים את ההתחלה של P כך שתעבור את סוף ' ב T כך שהתחילית של התבנית המוסטת מתאימה לסיפא של t ב T.
אם לא קיימת הסטה כזו, מסיטים את P ב n מקומות קדימה.
אם נמצא מופע של P, אז מסיטים את P כך שהתחילית של P המוסטת תתאים לסיפא של המופע של P ב T.
אם לא קיימת הסטה כזו, מסיטים את P ב n מקומות, כלומר, מסיטים את P שתעבור את t.
כלל הסיפא הטובה דורש שתי טבלאות: אחת לשימוש במקרה הכללי, ואחת לשימוש כאשר המקרה הכללי לא מחזיר תוצאה משמעותית או שמתקיימת התאמה.
טבלאות אלה יסומנו L ו - H בהתאמה.
עבור כל תו i, הוא העמדה הגדולה ביותר שקטנה מ-n כך שהמחרוזת מתאימה לסיומת של כך שהתו הקודם לסיומת לא שווה .
מוגדר להיות אפס אם אין עמדה המקיימת את התנאי.
נגדיר את [H[i כסיומת הארוכה ביותר של שהיא גם קידומת של P, אם קיימת כזו.
אם לא קיימת כזו, הערך של יהיה אפס.
את שתי הטבלאות האלה ניתן לבנות בזמן ובמקום .
עימוד ההזזה עבור האינדקס i ב P מוגדר להיות או .ב-H נעשה שימוש רק אם הוא אפס או שנמצאה התאמה.
אופטימיזציה פשוטה אבל חשובה של בויאר-מור הוצעה על ידי צבי גליל ב-1979. כלל גליל עוסק בהאצת ההשוואות שנעשות בכל עימוד, באמצעות דילוג על קטעים שידוע על התאמתם.
נניח כי בעימוד k1, נעשית השוואה בין P ל T עד לתו c של T.
זמן הריצה במקרה הגרוע ביותר של אלגוריתם בויאר-מור כפי שהוצג במאמר המקורי הוא , רק אם תבנית החיפוש אינה מופיעה בטקסט.
תוצאה זו הוכחה לראשונה על ידי קנות', מוריס ופראט בשנת 1977,
ואחרי כן על ידי גוביאס ואודליזקו ב-1980 עם חסם עליון של 5n השוואות במקרה הגרוע ביותר.
ריצ'רד קול סיפק הוכחה עם חסם עליון של 3n'' השוואות במקרה הגרוע ביותר ב-1991.
כאשר תבנית החיפוש נמצאת בטקסט, זמן ריצה של האלגוריתם המקורי הוא במקרה הגרוע ביותר.
ניתן לראות זאת כאשר תבנית החיפוש והטקסט מורכבים מתו שחוזר על מנת.
עם זאת, הכללתו של כלל גליל תורמת לזמן ריצה ליניארי בכל המקרים.
קיימים מימושים שונים במגוון שפות תכנות.
ב - C++, ספריית Boost מספקת מימוש כללי של חיפוש בויאר-מור תחת ספריית Algorithm.
אלגוריתם בויאר-מור משמש גם את תוכנית החיפוש grep.
במדעי המחשב, אלגוריתם לאס וגאס הוא אלגוריתם אקראי שמחזיר תוצאות נכונות בלבד.
אם הוא לא השיג כזו, הוא מודיע על כישלון.
במילים אחרות, אלגוריתם לאס וגאס אינו מהמר על נכונות התוצאה, אלא רק על המשאבים המשמשים לצורך החישוב.
דוגמה פשוטה היא מיון מהיר אקראי, כאשר איבר הציר נבחר באופן אקראי, אבל התוצאה תמיד ממוינת.
ההגדרה הרגילה של אלגוריתם לאס וגאס כוללת את ההגבלה שתוחלת זמן הריצה תמיד תהיה סופית, כאשר התוחלת מתבצעת מעל מרחב המידע האקראי, או האנטרופיה, בהם האלגוריתם משתמש.
הגדרה חלופית דורשת שאלגוריתם לאס וגאס תמיד יסתיים (יהיה יעיל), אך הוא עשוי לתת כפלט סמל שאינו חלק ממרחב הפתרונות כדי לדווח על כשל במציאת פתרון.
אלגוריתמים מסוג לאס וגאס הוצגו על ידי לסלו בבאי ב-1979, בהקשר של בעיית איזומורפיות גרפים, כזוג לאלגוריתם מונטה קרלו.
ניתן להשתמש באלגוריתמים מסוג לאס וגאס במצבים בהם מספר הפתרונות האפשריים מוגבל, וכאשר אימות נכונותו של הפתרון המועמד הוא קל יחסית, בעוד חישוב הפתרון הוא מורכב.
מקור השם מהעיר לאס וגאס, אשר ידועה כסמל להימורים.
מחלקת הסיבוכיות של בעיות הכרעה להן קיים אלגוריתם לאס וגאס עם תוחלת זמן ריצה פולינומית, היא ZPP.
מתקיים כי , דבר הקשור באופן הדוק עם הדרך שאלגוריתמים מסוג לאס וגאס נבנים לעיתים.
כלומר המחלקה RP מורכבת מכל בעיות ההכרעה להן קיים אלגוריתם זמן-פולינומי אקראי המחזיר תשובה נכונה, כאשר התשובה הנכונה היא "לא", אבל רשאי לטעות בהסתברות מסוימת הרחוקה מ-1, כאשר התשובה היא "כן".
כאשר קיים אלגוריתם כזה עבור בעיה והמשלימה שלה (התשובות "כן" ו "לא" מוחלפות), ניתן להריץ בו זמנית את שני האלגוריתמים ובאופן חוזר ונשנה: להריץ כל אחד מספר קבוע של צעדים, בתורנות, עד שאחד מהם מחזיר תשובה ודאית.
זו הדרך הרגילה לבנות אלגוריתם לאס וגאס הפועל בתוחלת זמן פולינומית.
שימו לב כי באופן כללי אין חסם עליון על זמן הריצה של המקרה הגרוע של אלגוריתם לאס-וגאס.
באלגוריתם מונטה קרלו, בדומה ללאס וגאס, המשאבים בשימוש חסומים אבל לא מובטח שהתשובה נכונה.
על ידי יישום של אי-שוויון מרקוב, ניתן להמיר אלגוריתם לאס וגאס לאלגוריתם מונטה קרלו באמצעות סיום מוקדם.
אלגוריתם אטלנטיק סיטי הוא אלגוריתם אקראי הפועל בזמן-פולינומי ועונה בצורה נכונה לפחות 75% מהזמן (או, בכמה גרסאות, ערך אחר גדול מ-50%).
המונח "אטלנטיק סיטי" הוצג לראשונה ב-1982 על ידי ג'יי פין בכתב יד שלא פורסם שכותרתו השוואה של בדיקות הסתברותית לבדיקת ראשוניות.
המחלקות הנפוצות האחרות של אלגוריתמים אקראיים הן אלגוריתם מונטה קרלו ואלגוריתם לאס וגאס.
אלגוריתם מונטה קרלו הוא תמיד מהיר, אבל צודק רק בהסתברות גבוהה.
מצד שני, אלגוריתם לאס וגאס תמיד צודק, אבל מהיר רק בהסתברות גבוהה.
אלגוריתם אטלנטיק סיטי הוא אלגוריתם זמן-פולינומי אקראי, שצודק בהסתברות גבוהה ומהיר בהסתברות גבוהה.
אלגוריתם ויטרבי , אלגוריתם תכנון דינמי למציאת רצף המצבים החבויים הסביר ביותר, שתוצאתו היא רצף תצפיות נתון.
בין שימושיו הנפוצים - מציאת רצף המצבים בהנחת מודל מרקוב חבוי, פיענוח קודי קונבולוציה ועוד רבים.
תחת זאת, משמש באופן תדיר במערכות תקשורת, כגון IEEE 802.11.
יתרונו הבולט של האלגוריתם הוא הורדת סיבוכיות המציאה של הרצף הסביר ביותר - מהמימוש הנאיבי (בעל סיבוכיות מעריכית בגודל הרצף) למימוש היעיל של האלגוריתם (בעל סיבוכיות ליניארית בגודל הרצף).
האלגוריתם פותח לראשונה על ידי אנדרו ויטרבי בשנת 1967 לטובת פיענוח קוד קונבולוציה מעל ערוץ תקשורת רועש.
הוא פותח באופן בלתי-תלוי על ידי מספר גורמים אחרים.
אלגוריתם ויטרבי מקבל כקלט רצף תצפיות , ומטרתו להוציא את רצף המצבים הסביר ביותר בהינתן התצפיות .
בהקשר זה, הוא אורך הרצף (תצפיות ומצבים), הוא גודל מרחב התצפיות ו- הוא גודל מרחב המצבים.
במהלך פעולתו, האלגוריתם משתמש בשתי טבלאות בגודל :
טבלה , שבה האיבר מכיל את ההסתברות של הנתיב (רצף) הכי סביר עד כה: .
טבלה שבה האיבר מכיל את של המסלול הסביר ביותר עד כה.
האלגוריתם ממלא את הטבלאות לפי סדר עולה של , ולפי הנוסחאות הרקורסיביות:
ההסתברויות ההתחלתיות , כך ש- היא ההסתברות ש-
רצף תצפיות כך ש- אם התצפית בזמן היא
מטריצת המעברים ממימד כך ש- היא הסתברות המעבר ממצב למצב
מטריצת הפלטים ממימד כך ש- הוא ההסתברות לתצפית בהינתן שהמצב הוא
אלגוריתם קולי-טוקי, על שמם של ג'יימס קולי וג'ון טוקי, הוא אלגוריתם התמרת פורייה מהירה (FFT) הנפוץ ביותר.
הוא מבטא מחדש, באופן רקורסיבי, את התמרת פורייה הבדידה (DFT) בגודל פריק שרירותי במונחים של N1 התמרות DFT קטנות יותר, כל אחת בגודל N2, וזאת על מנת להפחית את זמן החישוב ל-O(N log N) עבור N פריק מאוד.
מכיוון שאלגוריתם קולי-טוקי מפרק את ה-DFT להתמרות DFT קטנות יותר, ניתן לשלבו עם כל אלגוריתם DFT אחר.
לדוגמה, ניתן להשתמש באלגוריתמים של Rader או Bluestein לטיפול בגורמים ראשוניים גדולים שלא ניתן לפרק על ידי קולי-טוקי, או שאפשר להשתמש באלגוריתם FFT של גורם ראשוני ליעילות רבה יותר בהפרדת גורמי מספרים זרים .
האלגוריתם, כולל יישומו הרקורסיבי, הומצא בידי קרל פרידריך גאוס.
160 שנה מאוחר יותר, קולי וטוקי פיתחו אותו מחדש והפכו אותו לפופולרי .
אלגוריתם זה ויישומו הרקורסיבי, הומצאו כאמור בסביבות 1805 בידי קרל פרידריך גאוס, שהשתמש בו לחישובי אינטרפולציה של מסלולי האסטרואידים פאלאס ויונו, אך עבודתו לא זכתה להכרה רחבה (היא התפרסמה רק לאחר מותו, ובנאו-לטינית).
גאוס, בכל אופן, לא ניתח את זמן החישוב האסימפטוטי.
כמה צורות מוגבלות הומצאו מחדש מספר פעמים במהלך המאה ה-19 ותחילת המאה ה-20. FFT הפך לפופולרי לאחר שג'יימס קולי מ־IBM וג'ון טוקי מפרינסטון פרסמו ב-1965 מאמר הממציא מחדש את האלגוריתם ומתאר כיצד לבצע אותו בנוחות על מחשב.
על פי המדווח, טוקי הגה את הרעיון במהלך פגישה של הוועדה המייעצת למדע של הנשיא קנדי, שדנה בדרכים לאיתור ניסויים בנשק גרעיני בברית המועצות על ידי שימוש בסייסמומטרים הממוקמים מחוץ למדינה.
חיישנים אלה ייצרו סדרות זמן סייסמולוגיות.
הבעיה הייתה שניתוח נתונים אלה ידרוש אלגוריתמים מהירים לחישוב DFT בשל מספר החיישנים ואורך סדרות הזמן.
משימה זו הייתה קריטית לצורך אשרור האיסור המוצע על ניסויים גרעיניים, כך שניתן יהיה לזהות כל הפרה ללא צורך בביקור במתקנים סובייטיים.
משתתף אחר באותה פגישה היה ריצ'רד גארווין מ-IBM, שהכיר בפוטנציאל של השיטה ודאג ליצור קשר בין טוקי וקולי.
גארווין וידא שקולי לא ידע את המטרה המקורית.
במקום זאת, נאמר לו שזה נחוץ כדי לקבוע מחזוריות של כיווני הספין בגביש תלת-ממדי של הליום-3 .
קולי וטוקי פרסמו לאחר מכן את המאמר המשותף שלהם, שאומץ במהירות ובאופן נרחב, וזאת בשל הפיתוח הבו-זמני של ממירי אנלוגי לדיגיטלי המסוגלים לדגום בקצבים של עד 300KHz.
FFT מסוג Radix-2 הוא הגרסה הפשוטה והנפוצה ביותר של אלגוריתם קולי-טוקי.
יישומי קולי-טוקי בעלי אופטימיזציה גבוהה משתמשים לרוב בגרסאות אחרות של האלגוריתם, כפי שיתואר בהמשך.
בשיטה זו גודל הקלט N הוא חזקה של שתיים.
בכל שלב רקורסיבי, Radix-2 מחלק DFT בגודל N לשני DFT שזורים (interleaved) בגודל N/2.
התמרת פורייה הבדידה (DFT) מוגדרת בידי הנוסחה:
כאשר הוא מספר שלם הנע בין 0 ל .
אנו מניחים כאן ש-N הוא חזקה של שתיים.
Radix-2 מחשב תחילה את ה-DFT של ערכי הקלט בעלי האינדקס הזוגי ושל ערכי הקלט בעלי האינדקס האי-זוגי , ולאחר מכן משלב את התוצאות הללו כדי לחשב את ה-DFT של הרצף כולו.
את התהליך הזה ניתן לבצע באופן רקורסיבי ובכך להוריד את זמן הריצה הכולל ל-O(NlogN).
היישום יכול לרוב, הגם שלא תמיד, לבחור את מספר נקודות הדגימה N באופן חופשי (למשל בעזרת שיטות כגון שינוי קצב הדגימה, גודל החלון, או zero-padding).
לכן, לעיתים קרובות, הגודל של חזקה של שתיים אינו מגבלה חשובה.
אלגוריתם radix-2 מארגן מחדש את ה-DFT של הפונקציה בשני חלקים: סכום של האינדקסים הזוגיים וסכום של האי-זוגיים :
בסכום השני אפשר למצוא מכפיל משותף, , כמוצג במשוואה למטה.
שני הסכומים במשוואה זו הם ה-DFT של המרכיבים הזוגיים וה-DFT של המרכיבים האי-זוגיים של הפונקציה .
נסמן את ה-DFT של המרכיבים הזוגיים כ-.
נסמן את ה-DFT של המרכיבים האי-זוגיים כ-.
השוויון אמנם מתקיים עבור , אך הנקודה המכרעת היא שאת הערכים ו יש לחשב רק עבור .
הודות למחזוריות של המעריך המרוכב, מחושב גם הוא מ ו , כלהלן :
אנחנו יכולים לכתוב מחדש את ו כלהלן:
תוצאה זו, ביטויו הרקורסיבי של DFT באורך N במונחי שני DFT באורך N/2, היא הליבה של התמרת פורייה המהירה radix-2. מקור המהירות של האלגוריתם הוא השימוש החוזר בתוצאות חישובי ביניים כדי לחשב כמה תוצאות DFT.
התוצאות הסופיות מתקבלות על ידי שילוב +/− של ו , שהוא פשוט DFT בגודל 2 (הנקרא לעיתים פרפר בהקשר הזה); כאשר מכלילים לבסיסים גדולים יותר כמתואר להלן, ה-DFT בגודל 2 מוחלף בידי DFT גדול יותר (שבעצמו ניתן לחישוב בעזרת FFT).
תהליך זה מדגים את הטכניקה הכללית של אלגוריתמי הפרד ומשול ; עם זאת, ביישומים רבים, נמנעת הרקורסיה המפורשת, ובמקום זאת עוברים על העץ החישובי באלגוריתם חיפוש לרוחב .
הביטוי-מחדש של DFT בגודל N כשני DFT בגודל N/2, כמפורט לעיל, נקרא לעיתים הלמה של Danielson–Lanczos, מאחר ששני המחברים כתבו על זהות זו ב-1942 (בהשפעת עבודתו של Runge משנת 1903).
הם יישמו את הלמה שלהם כרקורסיה "לאחור", כך שגודל ה-DFT הוכפל שוב ושוב עד שספקטרום ההתמרה התכנס (הגם שנראה שהם לא הבינו שהם השיגו את הסיבוכיות האסימפטוטית O(NlogN)).
עבודתם קדמה לזמינות נרחבת של מחשבים מכניים או אלקטרוניים והצריכה חישוב ידני (אפשר שעם עזרים מכניים כגון מכונת חיבור); הם דיווחו על זמן חישוב של 140 דקות עבור DFT בגודל 64 הפועל על קלט ממשי בדיוק של 3–5 ספרות.
המאמר של קולי-טוקי משנת 1965 דיווח על זמן ריצה של 0.02 דקות עבור DFT מרוכב בגודל 2048 בריצה על IBM 7094 (כנראה תוך שימוש בנקודה צפה של 36 סיביות, כ-8 ספרות).
בשינוי קנה המידה של הזמן לפי מספר הפעולות, דיווח זה מתאים להכפלת מהירות בערך פי 800,000. (כדי לתת פרספקטיבה לזמן החישוב הידני, 140 דקות עבור גודל 64 תואמות לממוצע של לא יותר מ-16 שניות לכל פעולת נקודה צפה, כש-20% מהן הן פעולות כפל.)
יישומי FFT בעלי ביצועים גבוהים עורכים שינויים רבים במימוש האלגוריתם בהשוואה למימוש הבסיסי הפשוט.
לדוגמה, אפשר להשתמש במקרה בסיס גדול מ-N =1 להפחתת התקורה של הרקורסיה, גורם הסיבוב (twiddle factor) ניתן לחישוב מראש, ולעיתים קרובות נעשה שימוש בבסיסים גדולים יותר משיקולי זיכרון מטמון ; אופטימיזציות אלו ואחרות יכולות ביחד לשפר את הביצועים בסדר גודל או יותר.
(במימושים של האלגוריתם בספרי לימוד רבים, הרקורסיה של האלגוריתם חיפוש לעומק נשמטת לטובת הגישה הלא-רקורסיבית של אלגוריתם חיפוש לרוחב, אם כי נטען כי לרקורסיה של חיפוש לעומק ישנה מקומיות זיכרון טובה יותר.
כללית, אלגוריתמים של קולי-טוקי מבטאים-מחדש באופן רקורסיבי DFT בגודל מורכב N=N1N2 כ:
חשב N1 התמרות DFT בגודל N2.
חשב N2 התמרות DFT בגודל N1.
לרוב, N1 או N2 הוא גורם קטן (לא בהכרח ראשוני), הנקרא בסיס והוא יכול להיות שונה בין שלבי הרקורסיה.
גורמי הסיבוב הם שורשי יחידה מרוכבים, שהם נקודות על מעגל היחידה.
דהיינו, הכפלתם במספר מרוכב אחר, משנה רק את הזווית שלו.
גורמי הסיבוב במקרה של DFT בגודל 2 הם 1-/+.
ה-DFT הקטן של הבסיס נקרא לעיתים פרפר, בשל צורת תרשים זרימת הנתונים במקרה של radix-2.
ישנן וריאציות רבות של אלגוריתם קולי-טוקי.
יישומי האלגוריתם עם בסיסים מעורבים מטפלים בגדלים מורכבים שאפשר לפרק לכמה גורמים (לרוב קטנים) בנוסף ל-2, בדרך כלל (אך לא תמיד) תוך שימוש באלגוריתם הישיר, בסיבוכיות O(N 2), עבור מקרי הבסיס העיקריים של הרקורסיה אפשר גם להשתמש באלגוריתם O(NlogN) עבור מקרי הבסיס העיקריים, כגון האלגוריתמים של Rader או Bluestein .
בסיס מפוצל ממזג בסיסים 2 ו-4, תוך ניצול העובדה שההתמרה הראשונה של בסיס 2 אינה דורשת גורם סיבוב, על מנת להשיג את מה שהיה זמן רב מספר הפעולות האריתמטיות הנמוך ביותר הידוע עבור גדלים שהם חזקה של 2, למרות שווריאציות שפותחו לאחרונה השיגו מספר פעולות נמוך עוד יותר.
(במחשבים של ימינו, הביצועים נקבעים יותר על ידי שיקולי זיכרון מטמון וצינורות עיבוד נתונים מאשר על ידי ספירת פעולות קפדנית; יישומי FFT אופטימליים משתמשים לעיתים קרובות בבסיסים גדולים יותר ו/או התמרות בסיסיות מקודדות בגודל משמעותי.).
אפשר גם לראות את האלגוריתם של קולי-טוקי כביטוי מחדש של DFT חד-ממדי בגודל N כ-DFT דו־ממדי בגודל N1 על N2 (בתוספת סיבובים), כאשר מטריצת הפלט עוברת שחלוף.
עבור אלגוריתם radix-2, התוצאה נטו של השחלופים תואמת להיפוך סיביות של האינדקס של הקלט או הפלט.
אם, במקום להשתמש בבסיס קטן, נשתמש בבסיס של בערך השורש הריבועי של N, ובשחלופים מפורשים של מטריצת קלט/פלט, נקבל אלגוריתם שנקרא אלגוריתם בן ארבעה צעדים (או שישה צעדים, תלוי במספר השחלופים).
האלגוריתם הוצע בתחילה כדי לשפר את מקומיוּת הזיכרון, למשל עבור אופטימיזציה של זיכרון מטמון או פעולות מחוץ לזיכרון, ומאוחר יותר הוכח כי הוא אופטימלי כ-cache-oblivious algorithm .
הפירוק הכללי של קולי-טוקי משכתב את האינדקסים k ו-n כ ו , בהתאמה, כאשר האינדקסים ka ו-na הם בתחום שבין 0 ו-Na-1 (כאשר a הוא 1 או 2).
כלומר, הפירוק מארגן מחדש את הקלט (n) ואת הפלט (k) כמערכים דו-ממדיים של N1 על N2 בסדר עמודה ושורה, בהתאמה; ההבדל בין האינדקסים הללו הוא שחלוף, כמוזכר לעיל.
כאשר האינדקסים החדשים האלה מוחלפים בנוסחת DFT עבור nk, הביטוי הצולב נעלם (המעריך שלו הוא 1), ושאר הביטויים נותנים
כאשר כל סכום פנימי הוא DFT בגודל N2, כל סכום חיצוני הוא DFT בגודל N1, והביטוי בסוגריים הוא גורם הסיבוב.
אפשר להשתמש בבסיס r שרירותי (כמו גם בסיסים מעורבים), כפי שהראו הן קולי וטוקי והן גאוס (שנתן דוגמאות של שלבים של בסיס-3 ושל בסיס-6).
אולם ניתוח זה היה שגוי: פרפר הבסיס הוא גם DFT וניתן לחישוב באמצעות אלגוריתם FFT בסיבוכיות O(rlogr), ומכאן שבסיס מבטל למעשה את הסיבוכיות O(r log(r) N/r logrN), וה- r האופטימלי נקבע על סמך שיקולים מורכבים יותר.
בפועל, r גדול למדי (32 או 64) חשוב על מנת לנצל למשל בצורה יעילה את המספר הגדול של האוגרים במעבדים מודרניים, ואפילו בסיס לא מוגבל r = √ N משיג גם הוא סיבוכיות של O(N log N) ויש לו יתרונות תאורטיים ומעשיים עבור N גדול.
אמצע הריבוע הוא אלגוריתם פרימיטיבי שמשמש ליצירת מספרים פסאודו אקראיים על בסיס מספר "זרע" ממנו מתחילה יצירת המספרים.
האלגוריתם נחשב לשיטה גרועה למדי, שכן בשלב כלשהו יתקבל שוב מספר שכבר נכלל ברשימה והיא תתחיל לחזור על עצמה.
מכאן שהתפלגות המספרים ברשימה המתקבלת אינה אקראית ולכן לא מדובר בשיטה שמייצרת רשימה פסאודו אקראית של ממש.
עם זאת השיטה פשוטה, ומשמשת דוגמה טובה לשימוש במספר "זרע" ליצירת רשימה פסאודו אקראית.
בנוסף, שימוש בזרעים ספציפיים מניב רשימה ארוכה לפני שמתקבל מספר שכבר היה, ואם אין צורך במספרים פסאודו אקראיים רבים השיטה טובה די הצורך.
האלגוריתם הוא להעלות את המספר הקודם בריבוע, ולבחור את הספרות האמצעיות של התוצאה בתור המספר הבא.
דוגמה לבחירת מספר פסאודו אקראי בעל 4 ספרות
לכן השלב הבא הוא 8579
כך הזרע קובע באופן דטרמיניסטי לחלוטין רשימה אינסופית של מספרים, מבלי שיהיה צורך לייצר את הרשימה מראש.
על מנת למנוע דעיכה של הריבועים למספר קטן מ-10,000,000, אם המספר הבא קטן מ-1,000 מוסיפים ספרה קבועה בסיום המספר הבא, למשל את הספרה האחרונה של המספר הקודם, על מנת למנוע דעיכה של הריבועים למספר קטן מ-10,000,000. דעיכה כזו פירושה שיתקבלו מספרים שאינם בני 4 ספרות, בניגוד לדרישה מהאלגוריתם.
מסיטים את המספר ספרה לשמאל, ומוסיפים 9, שהוא הספרה הראשונה של המספר הקודם
כך שהמספר הבא הוא 9594
קיימות שיטות נוספות לפתרון סוגיה זו.
במדעי המחשב ובאופטימיזציה מתמטית, אלגוריתם היוריסטי הוא שיטה לפתרון בעיות בצורה מהירה יותר כאשר שיטות חישוב מדויקות הן איטיות מדי, או כאשר לא ניתן למצוא פתרון מלא בשל סיבוכיות מקום.
אלגוריתמים אלו פועלים על ידי החלפת אופטימליות, דיוק או שלמות במהירות חישובית, ובכך מספקים פתרונות מקורבים אשר לעיתים קרובות מספיק טובים לצרכים מעשיים.
ניתן לראות בהם קיצורי דרך חישוביים.
אלגוריתם היוריסטי כולל לעיתים פונקציה יוריסטית, אשר משמשת לדרג חלופות ולהנחות את תהליך החיפוש לפתרונות טובים יותר.
לדוגמה, ניתן להשתמש בפונקציה זו כדי לכוון אלגוריתם חיפוש לכיוון פתרון סביר מבלי לבדוק את כל האפשרויות האפשריות.
מטרתו של אלגוריתם היוריסטי היא למצוא פתרון מספק בזמן סביר.
עשוי שלא להיות אופטימלי, אך הוא טוב מספיק עבור הבעיה הנתונה.
נדרש להיות מהיר ויעיל, כך שיהיה ישים גם עבור בעיות מורכבות במיוחד.
יכול לפעול באופן עצמאי או להשתלב עם אלגוריתמי אופטימיזציה אחרים כדי לשפר את ביצועיהם.
שימוש באלגוריתמים היוריסטיים נפוץ במיוחד במקרים בהם הבעיה היא NP-קשה, כלומר לא ניתן למצוא לה פתרון מלא בזמן חישוב סביר.
בנוסף, אלגוריתמים היוריסטיים הם מרכיב מרכזי בבינה מלאכותית (AI), ומשמשים במקרים שבהם אין אלגוריתם מדויק ידוע לפתרון הבעיה.
1. פתרון בעיה פשוטה יותר
במקרים מסוימים, ניתן לפשט את הבעיה כך שהפתרון שלה יהיה גם פתרון של הבעיה המקורית, ובכך להפחית את המאמץ החישובי.
2. בעיית הסוכן הנוסע (TSP)
היא מספקת פתרון מקורב במהירות.
ניתן להעריך עד כמה הוא רחוק מהפתרון האופטימלי.
בבעיות חיפוש, ניתן להאיץ את תהליך מציאת הפתרון באמצעות שימוש ביוריסטיקה המכוונת את החיפוש לכיוונים מבטיחים יותר.
באלגוריתם חיפוש A*, הפונקציה היוריסטית מסייעת לכוון את החיפוש כך שיתכנס לפתרון אופטימלי מהר יותר, תוך שמירה על נכונות האלגוריתם.
4. ניואל וסיימון – השערת החיפוש היוריסטי
אלן ניואל והרברט סיימון, בנאום הזכייה שלהם בפרס טיורינג, הציעו את השערת החיפוש היוריסטי, הקובעת כי:"מערכת סמלית תייצר ותשנה מבני סמלים עד שהם יתאימו למבנה הפתרון."משמעות הדבר היא שהחיפוש מתבצע באופן חכם וממוקד, כך שמסלולים פחות מבטיחים נזנחים במהירות.
תוכנות אנטי-וירוס משתמשות באלגוריתמים היוריסטיים כדי לזהות וירוסים חדשים:
סריקה יוריסטית מזהה דפוסים והתנהגויות האופייניים לקוד זדוני, גם אם הווירוס עצמו לא נתגלה בעבר.
שיטה זו מאפשרת איתור וירוסים חדשים (זיהוי פרואקטיבי), גם ללא עדכון בסיס הנתונים של האנטי-וירוס.
בגאומטריה חישובית, אלגוריתם טאטוא (בתרגום חופשי אלגוריתם קו-סורק) (sweep line algorithm) או אלגוריתם טאטוא מישור (או סחיפה) (plane sweep algorithm) הוא פרדיגמה אלגוריתמית המשתמשת בקו סורק רעיוני או במשטח סורק כדי לפתור בעיות שונות במרחב האוקלידי.
זהו אחד הכלים המרכזיים בתחום הגאומטריה החישובית.
הרעיון העומד מאחורי אלגוריתמים מסוג זה הוא לדמיין קו (לעיתים קרובות קו אנכי) הנע על פני המישור, ועוצר בנקודות מסוימות.
הפעולות הגאומטריות מוגבלות לאובייקטים גאומטריים שנמצאים על הקו, חוצים אותו, או סמוכים לו ברגע שהקו עוצר.
הפתרון המלא מתקבל לאחר שהקו עבר על פני כל האובייקטים.
יישום של גישה זו הביא לפריצת דרך במורכבות החישובית של אלגוריתמים גאומטריים, כאשר בשנת 1976 הציגו שאמוס (Shamos) והוי (Hoey) אלגוריתמים למציאת חיתוכים של מקטעים במישור.
בפרט, הם הראו כי שילוב של שיטת קו הסריקה עם מבני נתונים יעילים (כגון עצי חיפוש מאוזנים) מאפשר לזהות האם קיימים חיתוכים בין מקטעים במישור בזמן חישוב של .
אלגוריתם קשור, אלגוריתם בנטלי–אוטמן (Bentley–Ottmann), עושה שימוש בטכניקת קו סורק כדי לדווח על כל החיתוכים בין מקטעים במישור בזמן חישוב של ובמורכבות זיכרון של .
מאז, גישה זו שימשה לעיצוב אלגוריתמים יעילים לבעיות רבות בגאומטריה חישובית, כגון בניית דיאגרמת וורונוי (באמצעות אלגוריתם פורצ'ן), טריאנגולציית דלוני, וכן ביצוע פעולות בוליאניות על פוליגונים.
סחיפה טופולוגית (topological sweeping) היא גרסה של קו סורק שבה סדר העיבוד של הנקודות פשוט יותר, ואינה דורשת מיון מלא של כל הנקודות; הדבר מאפשר ביצוע יעיל יותר של חלק מהאלגוריתמים.
טכניקת הקליפרים המסתובבים (rotating calipers) לעיצוב אלגוריתמים גאומטריים ניתנת גם היא לפירוש כצורה של קו סורק – אך במישור הדואלי הפרויקטיבי.
במסגרת דואליות פרויקטיבית, השיפוע של קו במישור אחד מומר לקואורדינטת x של נקודה במישור הדואלי.
כך, המעבר על קווים בסדר שיפועיהם (כפי שמבצע אלגוריתם הקליפרים המסתובבים) הוא דואלי למעבר על נקודות בסדר ערכי ה־x שלהן (כפי שקורה באלגוריתם קו סורק).
גישת הסחיפה ניתנת להכללה גם לממדים גבוהים יותר.
מיון הוא אלגוריתם לסידור נתונים על פי ערכי מפתח, למשל סידור רשימה של אנשים לפי שם המשפחה שלהם.
ישנן דרכים רבות למיין ערכים.
דרכים אשר שונות זו מזו ברמת הפשטות, היעילות והמהירות שלהן.
מבחינים בשני סוגי מיון: מיון עולה (הערך הקטן ביותר ראשון) ומיון יורד (הערך הגדול ביותר ראשון).
(ניתן לבצע מיון בטבלה הבאה לפי כל אחד מהשדות על ידי לחיצה על כותרת השדה)
מיון נחוץ מאוד כאשר עוסקים בעיבוד מידע במסדי נתונים, דבר שמפשט ומייעל עבודה עם נתונים ובכללה איתור תוכן, פעילות בין טבלאות ופעילויות אריתמטיות.
כך בדרך כלל במסדי נתונים שדה חשוב לפעילות מכל סוג, יכלל באינדקס שהוא שדה ממוין, וכל תוכן שיוכנס לתוכו ימוין אוטומטית מאחרי הקלעים.
באלגוריתמים הדבר נחוץ כי לעיתים קרובות פעולות על קלט ממוין הן מסיבוכיות נמוכה יותר.
למשל, ניתן למצוא את הערך המקסימלי והמינימלי (או בכלל, ה- בגודלו) במערך ממוין בסיבוכיות זמן של ולמצוא איבר כללי במערך בסיבוכיות לוגריתמית.
ישנם אלגוריתמי מיון רבים, הנבדלים זה מזה בסיבוכיות הזמן והזיכרון שלהם, בפשטות מימושם ובהנחה על הפעולות הבסיסיות.
חלוקה מקובלת היא בין אלגוריתמי המיון המבוססים על פעולת השוואה בין האיברים הנתונים לבין אלה המאפשרים פעולות כלליות על האיברים.
כל אלגוריתמי המיון המבוססים על פעולת השוואה דורשים לפחות פעולות השוואה במקרה הגרוע על-מנת לבצעם.
ניתן להגיע למסקנה זו על ידי התבוננות ב"עץ השוואות" המתאר מיון כללי, בו כל קודקוד מסמן השוואה בין שני איברים, כל קשת מסמלת תוצאה אחרת של אותה השוואה וכל עלה מייצג את סיום פעילות האלגוריתם ואת הסדר בו יש לסדר את הנתונים.
מאחר שקיימות לכל איברים דרכים לסדרם, הרי שמספר העלים בעץ יהיה , ומכיוון שדרגת העץ חסומה, לפי משפט מתורת הגרפים גובה העץ (מספר ההשוואות שהאלגוריתם יאלץ לעשות לפני שיגיע לעלה) יהיה .
ניתן לראות ש- (באמצעות נוסחת סטרלינג) ומכאן נובע החסם.
מיון בועות (bubble sort), הידוע גם בכינוי מיון החלפה הוא מיון פשוט, שבו מושווים שני איברים סמוכים במערך המתמיין.
מיון זה הפועל בסיבוכיות של .
המיון קיבל את שמו מהדרך בה מבעבעים אלמנטים במערך.
מבחינת צריכת זיכרון האלגוריתם חסכוני, והוא דורש .
מיון הכנסה (insertion sort) הוא אלגוריתם מיון השוואתי פשוט.
הוא יעיל עבור מערכים קטנים ועבור מערכים ממוינים או כמעט ממוינים.
סיבוכיות הזמן של האלגוריתם היא .
מיון בחירה (selection sort) הוא אלגוריתם השוואתי פשוט אך לא יעיל, שבו נמצא בכל צעד האיבר בעל הערך הקטן ביותר, והוא מועבר למקומו.
מיון ערימה (heap sort) הוא אלגוריתם מיון אשר נעזר במבנה נתונים הקרוי ערימה כדי לממש את מיון הבחירה בצורה יעילה יותר.
האלגוריתם בונה ערימה מהקלט ואז שולף בכל פעם את האיבר שבראש הערימה, שהוא האיבר הגדול ביותר בערימה, אל הפלט.
יתרונו לעומת מיון מיזוג הוא שאינו דורש זיכרון נוסף פרט לזיכרון שבו מאוחסן הקלט.
מיון מהיר (quicksort) הוא אלגוריתם מיון השוואתי אקראי מהיר במיוחד.
זהו אלגוריתם רקורסיבי הפועל בשיטת הפרד ומשול.
סיבוכיות הזמן הממוצע של האלגוריתם הוא פעולות, אך במקרה הגרוע עלול לדרוש פעולות.
מיון מיזוג (mergesort) הוא אלגוריתם מיון רקורסיבי קל למימוש המתבסס על קלות מיזוגם של מערכים ממוינים.
סיבוכיות הזמן במקרה הגרוע היא פעולות, אך זוהי גם הסיבוכיות במקרה הטוב ביותר.
Shell sort מיון "של" על שמו של הממציא.
אלגוריתם ה-Shell Sort פועל בשלבים, בהם הוא ממיין תאי מערך הרחוקים זה מזה מרחק שהולך וקטן בכל שלב, כשהמיון עצמו מתבצע בצורת מיון הכנסה.
מיון מסרק (comb sort) הוא אלגוריתם מיון שמשפר את מיון בועות.
הרעיון הבסיסי הוא להעלים צבים- ערכים קטנים המופיעים לקראת סוף הרשימה, היות שבמיון בועות הללו מאטים מאוד את המיון.
(ארנבים- ערכים גדולים סביב תחילת הרשימה- לא מהווים בעיה במיון בועות).
רשת מיון (sorting network) מאפשרת למיין מספר קבוע מראש של קלטים.
היתרון הגדול של רשת מיון הוא שהיא נוחה למיקבול (כלומר לחלוקה למשימות היכולות להתבצע במקביל).
כך, כשהמיון נעשה על מחשב המאפשר בצוע מקבילי ניתן להגיע באופן מעשי לביצועים של .
מיון ספגטי (spaghetti sort) דורש עיבוד מקבילי ורץ בזמן ליניארי.
מיונים עם הנחות נוספות על הקלט:
מיון מנייה (counting sort) הוא אלגוריתם למיון מספרים שלמים המתבסס על העובדה שהמספרים נמצאים בטווח חסום כדי לבצע את המיון בזמן מהיר יותר מזה שמסוגלים לו אלגוריתמי המיון מבוססי ההשוואות.
בצורה אינטואיטיבית, די למיון לעבור על קבוצת האיברים שרוצים למיין ולמנות את מספר המופעים של כל אחד מהאיברים, ומכאן שמו של האלגוריתם.
מיון סלים (bucket sort) הוא מיון של קבוצת מספרים ממשיים כאשר ידוע שפיזור האיברים אחיד (קרי, מקיימים התפלגות אחידה בדידה).
מיון בסיס (radix sort) הוא אלגוריתם למיון מספרים, המסתמך על מידע נוסף שאומר שכמות הספרות שבאמצעותן מיוצג כל מספר חסומה על ידי קבוע.
במיונים הללו (מנייה, סלים, בסיס) בעזרת מידע נוסף על הקלט סיבוכיות האלגוריתם יורדת אל מתחת לסיבוכיות המינימלית של אלגוריתם מיון מבוסס השוואות עד ל במקום .
מיון חיצוני הוא שם כולל לקבוצה של אלגוריתמי מיון המסוגלים להתמודד עם כמויות גדולות של מידע.
מיון חיצוני נדרש כאשר המידע שצריך למיין לא נכנס לזיכרון הראשי של המחשב (לרוב ה-RAM) ומשתמשים בהתקן זיכרון איטי יותר (לרוב דיסק קשיח).
אלגוריתם קירוב הוא אלגוריתם שמוצא פתרון שאינו בהכרח פתרון אופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון אופטימלי.
אלגוריתמים אלו שימושיים במיוחד בבעיות שהאלגוריתמים הידועים לפתרונן הם בסיבוכיות גבוהה, ובפרט בבעיות NP קשות, קבוצת הבעיות NP קשות שקיים להם אלגוריתם קירוב נקראת APX, ניתן להוכיח שיש בעיות שאין להם אלגוריתם קירוב אלא אם כן P=NP.
על פי רוב מודדים קירוב של אלגוריתם בהתאם ליחס בין הפתרון שנמצא על ידי האלגוריתם לבין הפתרון האופטימלי.
נאמר כי אלגוריתם קירוב לבעיה משיג יחס קירוב של (לפעמים נאמר גם אלגוריתם -מקרב) אם הפתרון המושג על ידי האלגוריתם קטן מ- פעמים הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מינימיזציה) או גדול מהחלק ה- של הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מקסימיזציה).
ישנם כמה סוגים של אלגוריתמי קירוב, שנבדלים ביניהם בסוג הקירוב שהם מציעים ובסיבוכיות שלהם:
אלגוריתמי קירוב אלו מציעים קירוב בפער של מכפלה במספר קבוע מהערך האופטימלי, למשל השמה של לפחות חצי מהערך המקסימלי בבעיית התרמיל, בזמן פולינומי לגודל הקלט.
אלגוריתמים חמדניים שנותנים קירוב הם מסוג זה.
אלגוריתמי קירוב מסוג סכמת קירוב פולינומית מקבלים כלשהו כקלט ומתייחסים אליו כקבוע, ומציעים קירוב של מכפלה של מהערך האופטימלי (או בבעיות מינימום).
כל זה בזמן פולינומי לגודל הקלט, זה עלול להיות אקספוננציאלי ביחס ל- (הוא יכול להיות החזקה).
תת קבוצה של אלגוריתמים אלו היא סכמת קירוב פולינומית מלאה (FPTAS).
באלגוריתמים אלו הסיבוכיות פולינומית גם בגודל הקלט וגם ב-.
קירוב כזה קיים לבעיית תרמיל הגב למשל.
בעיית הסוכן הנוסע בגרף מטרי מוגדרת כבעיית מציאת מסלול המילטוני בגרף ממושקל: דהיינו מסלול שעובר בכל צומת בדיוק פעם אחת וחוזר לצומת הראשון, ומשקלו מינימלי.
בעיה זו היא NP-קשה, אולם ניתן לקרב אותה באופן הבא (האלגוריתם של קריסטופידס):
מוצאים עץ פורש מינימלי בגרף.
בוחרים צומת כלשהו כשורש, ומטיילים לעומקו של העץ, במסלול ששקול לחיפוש לעומק.
כאשר אנו מגלים שאנו חוזרים לצומת בו כבר היינו, נבצע "קיצור דרך", דהיינו, נמשיך ישירות לצומת הבא ברשימה - וזאת עד שביקרנו בכל הצמתים ונחזור לצומת שממנו התחלנו.
על מנת להיווכח שהאלגוריתם המתואר לעיל הוא אלגוריתם קירוב, יש לבחון את הפתרון שנמצא ביחס לפתרון האופטימלי.
ראשית, קל להיווכח כי משקלו של העץ הפורש המינימלי קטן ממשקלו של המסלול ההמילטוני המינימלי, משום שהמסלול ההמילטוני מכיל עץ פורש, ולכן משקלו גדול יותר.
כמו כן ניתן להשתכנע כי המסלול שביצע האלגוריתם ללא קיצורי דרך עבר על כל קשת בדיוק פעמיים - פעם בדרך "הלוך" ופעם בדרך "חזור".
לכן, משקל המסלול שמצאנו ללא קיצורי דרך יהיה בדיוק פעמיים משקל העץ הפורש המינימלי ממנו התחלנו את האלגוריתם.
בנוסף, משום שהגרף הוא גרף מטרי, קיצור הדרך שביצענו רק הקטינו את משקלו של המסלול שמצאנו.
לכן משקלו של המסלול המקוצר (אותו מצא האלגוריתם) הוא לכל היותר פעמיים משקל העץ הפורש המינימלי, שהוא לכל היותר פעמיים משקל המסלול ההמילטוני, שהוא הפתרון האופטימלי לבעיה.
לפיכך, האלגוריתם שתואר הוא אלגוריתם קירוב עם יחס קירוב של 2.
אלגוריתם פלויד-וורשאל הוא אלגוריתם במדעי המחשב המשמש למציאת המסלולים הקצרים (או הקלים) ביותר בין כל שני צמתים, בגרף ממושקל ומכוון.
האלגוריתם מבוסס על פרדיגמת התכנון הדינמי.
האלגוריתם פועל גם על גרפים שמכילים קשתות עם משקלים שליליים, אבל שלא מכילים מעגל בעל משקל שלילי (בניגוד לאלגוריתם דייקסטרה שמניח קשתות אי שליליות).
אם בגרף יש מעגל עם משקל שלילי האלגוריתם יגלה זאת.
סיבוכיות זמן הריצה של האלגוריתם היא .
האלגוריתם פורסם על ידי רוברט פלויד בשנת 1962 בגרסתו המוכרת לנו כיום, אך גרסאות דומות של האלגוריתם פורסמו ב-1959 על ידי ברנארד רוי, ועל ידי סטיבן וורשאל ב-1962 במטרה לחשב את הסגור הטרנזיטיבי של קבוצת קודקודים בגרף.
האלגוריתם מתבסס על האבחנה הבאה: אם ממספרים את קבוצת הצמתים של הגרף כך שהיא מסומנת ומסמנים בתור את משקל המסלול הקצר ביותר מהצומת אל הצומת שעובר בצומתי ביניים השייכים אך ורק לקבוצה , אז מתקיים: .
הסבר: אם קיים מסלול קצר ביותר מ- אל שעובר בצמתים שמספרם לכל היותר לא עובר בצומת שמספרו , אז .
לעומת זאת, אם כל מסלול קצר ביותר כזה חייב לעבור בצומת שמספרו אז ניתן להניח שהוא עובר בו רק פעם אחת (כי אין מעגלים שליליים בגרף, ולכן אם חוזרים לאותו צומת פעמיים ניתן להשמיט מהמסלול את המעגל מהצומת לעצמו).
לכן אפשר לפרק כל מסלול כזה לשני מסלולים: אחד שהולך מ- אל , ושני שהולך מ- אל .
שני המסלולים הללו לא עוברים בצמתי ביניים שמספרם גדול מ-, ולכן סכום משקלם נתון על ידי .
לכן כל מה שנותר הוא לבדוק איזו משתי השיטות עדיפה לכל צומת.
כעת, פעולת האלגוריתם היא זו: הוא מבצע איטרציות, כאשר באיטרציה ה- הוא מחשב את לכל זוג צמתים ושומר את המידע בטבלה.
חישוב מתבצע בזמן בהינתן המידע מהאיטרציה הקודמת, ולכן כל איטרציה של האלגוריתם מתבצעת בזמן (מספרם של זוגות הצמתים האפשריים).
לכן זמן הריצה הכולל של האלגוריתם יהיה .
תהי W מטריצת משקלי הקשתות: כלומר w(i,j) הוא משקל הקשת המחברת את i עם j.
(משקל זה הוא אין-סוף אם אין קשת ביניהם).
בסוף, היא מטריצת אורך המסלולים הקצרים ביותר שעוברים דרך הצמתים .
מעניין לציין שגם בהרצה בסדר "הלא נכון" האלגוריתם עובד כשורה לאחר מספר חזרות, כלומר אם נחליף את השורות:
מעגל שלילי הוא מעגל שסכום קשתותיו קטן מאפס.
בין שני קודקודים שמשתתפים במעגל שלילי לא קיים מסלול קצר ביותר, כי בכל מעבר על המעגל נקבל מסלול שמשקלו קטן יותר, וניתן להמשיך כך עד אין-קץ.
על כן, במקרה של מעגל שלילי האלגוריתם לא יפיק פלט משמעותי.
עם זאת, במידה וקיים מעגל שלילי, ניתן להיעזר באלגוריתם על מנת לגלות זאת:
בתחילה, המרחק בין כל קודקוד לעצמו הוא 0.
מסלול יכול לשפר, אם ורק אם סכום קשתותיו שלילי, ז"א מדובר במעגל שלילי.
על כן, אם קיים קודקוד שמרחקו מעצמו שלילי, משמעות הדבר שקיים לפחות מעגל שלילי אחד בגרף.
מכאן, באמצעות התבוננות במטריצת המסלולים הקצרים ביותר שהפיק האלגוריתם, ניתן להסיק שקיים מעגל שלילי, אם באחד מהתאים על האלכסון הראשי קיים מרחק קטן מאפס.
אלגוריתם מילר-רבין (או 'רבין-מילר') Miller-Rabin, הוא אלגוריתם לבדיקת ראשוניות של מספר טבעי.
הוא דומה למבחן פרמה לבדיקת ראשוניות אשר מבוסס על ההיפוך הלוגי של המשפט הקטן של פרמה, אך מרחיב אותו בצורה שמתגברת על מספרי קרמייקל - מקרי הקצה עבורם מבחן פרמה אינו עובד.
הוכחת הנכונות של האלגוריתם דורשת את השערת רימן המוכללת.
יש לאלגוריתם גרסה הסתברותית מהירה יחסית, שמזהה כל מספר ראשוני ככזה, אבל עשויה, בהסתברות נמוכה ככל שנרצה, להכריז כך גם על מספר פריק.
גרסה זו, שפותחה על ידי פרופ' מיכאל רבין מן האוניברסיטה העברית, היא המבחן המקובל לבדיקת ראשוניות (תפקיד אותו מילא קודם מבחן סולוביי-שטרסן.)
בהינתן מספר אי-זוגי שלם , ניתן לכתוב , כאשר s מספר טבעי ו-r מספר טבעי אי-זוגי.
יהי a מספר שלם, כך ש a ו-n מספרים זרים.
אם n ראשוני, אז המשפט הקטן של פרמה מבטיח ש- .
מכיוון שבחשבון מודולו מספר ראשוני יש ל-1 בדיוק שני שורשים ריבועיים, , בהכרח מתקיים
תנאי זה חייב להתקיים אם n ראשוני.
לצורך המבחן, בוחרים באקראי את הבסיס a, ובודקים את השוויוניים לעיל.
אם הם אינם מתקיימים, n הוא מספר פריק.
אם אחד מהם מתקיים, אז a הוא עד חזק לכך ש- n ראשוני (המונח עד משמש, בהקשר דומה, במבחן פרמה), אבל זו אינה הוכחה לראשוניות: קיימים מספרים פריקים שיש עדים חזקים לראשוניות שלהם.
אפשר להוכיח שאם n פריק, אז לכל היותר רבע מבין המספרים הטבעיים עד n-1 עלולים להיות עדים חזקים לראשוניות של n.
משום כך, אם בדיקה באמצעות t עדים אקראיים מודיעה שהמספר הנבדק ראשוני, הסיכוי לטעות באימוץ ההצהרה הוא לכל היותר .
לצרכים מעשיים (למשל, הגרלת מספרים ראשוניים גדולים עבור אלגוריתמי הצפנה כגון RSA או שיטת רבין), מקובל להסתפק בבדיקה כזו ולא להפעיל אלגוריתמים דטרמיניסטיים לבדיקת ראשוניות, שהם איטיים בהרבה.
קוד של אלגוריתם מילר רבין
להלן מימוש של האלגוריתם בשפת פייתון:
נבדוק את המספר , שעבורו .
בבדיקת הבסיס 5 מתברר ש- (שהרי ).
לכן 5 הוא עד חזק לראשוניות של 781. עבור הבסיס 17, מקבלים , ולכן גם 17 הוא עד חזק.
לעומת זאת, בדיקת הבסיס 2 נותנת , ומכאן ש- 781 אינו יכול להיות ראשוני.
במדעי המחשב, אלגוריתם תוך-מקומי הוא אלגוריתם המתמיר מבנה נתונים תוך שימוש בכמות קטנה וקבועה של שטח אחסון נוסף.
בדרך כלל, פלט האלגוריתם נכתב על-גבי שטח הקלט, ללא שימוש במבנים זמניים משמעותיים.
אלגוריתם שאינו תוך-מקומי נקרא לעיתים לא-תוך-מקומי או חוץ-מקומי.
דוגמאות: מיון ערימה, מיון בועות.
נגדיר מערך 'a' באורך 'n' .
עכשיו, נגדיר פונקציה בשם reverse שתחזיר את המערך בצורה ההפוכה.
עכשיו נציג שתי דרכים לעשות זאת:
שיטה זו פחות יעילה, מכיוון שהיא צורכת כמות זיכרון גבוהה יותר בשביל המערך 'b'.
עכשיו נראה איך נוכל להפוך את הקוד ליותר יעיל, וגם לכתוב את הקוד במקום (אלגוריתם תוך-מקומי).
כפי שניתן לראות האלגוריתם השני (אלגוריתם תוך-מקומי) יעיל בהרבה, מבחינת ניצול הזיכרון.
מבחינת סיבוכיות ריצה ללא הפיכה ל ניתן לראות שהפונקציה הראשונה תהיה והשנייה .
כך שיוצא שהפונקציה השנייה יעילה במקצת בסיבוכיות.
אלגוריתם פונטי הוא אלגוריתם לניתוח מילים ומיפוי צורת ההגייה שלהן.
מיפוי כזה מאפשר השוואה בין צורות שונות לכתיב של אותה מילה ומאפשר להתגבר על שגיאות כתיב או הקלדה של מילים ושמות זהים באיות שונה.
אלגוריתם פונטי תלוי באופן טבעי בשפה שבה הוא מופעל, ועקב שליטתה של האנגלית בתחומי מדעי המחשב מרבית האלגוריתמים הפונטיים מותאמים לאנגלית (אך ניתן להתאימם לשפות אחרות, תוך שמירה על עקרונותיהם).
אלגוריתמים פונטיים נפוצים לשפה האנגלית הם -
סאונדקס (soundex) - פותח בארצות הברית בתחילת המאה ה-20 ושימש לניתוח שמות מתוך מרשם האוכלוסין.
משמש פעמים רבות כשם גנרי לכלל האלגוריתמים הפונטיים.
Daitch-Mokotoff Soundex - אלגוריתם שפותח על מנת להתאים להגייה של שמות יהודיים וסלאביים באנגלית
וDouble Metaphone - שני דורות של אלגוריתם שנועד לתת מענה טוב לכל המילים בשפה האנגלית, ולא מוכוון לשמות.
בישראל פותחו מספר אלגוריתמים פונטיים לשפה העברית.
בהם אלגוריתם דמוי סאונדקס שפותח במסגרת מרשם האוכלוסין בשנות ה-60 ואלגוריתם בשם GRAPHEX שפותח בצה"ל על ידי אסא כשר.
אלגוריתם פונטי משמש בעת הזנת נתונים למחשב, כחלק מבדיקות הקליטה, ובעת אחזור מידע.
בעת עדכון מאגר נתונים משמשת בדיקה באמצעות אלגוריתם פונטי כאישור נוסף לכך שרשומה שמצאנו במאגר הנתונים (על-פי מפתחה) אכן מתאימה לרשומת התנועה שבאה לעדכן אותה.
דוגמה: בקובץ חיילי צה"ל רשומה לכל חייל.
מפתח הרשומה הוא המספר האישי של החייל, שאינו כולל ספרת ביקורת.
עקב היעדר ספרת ביקורת, טעות בהקלדת ספרה במספר האישי תוביל בסבירות גבוהה לרשומה של חייל אחר, שאין כוונה לעדכנה.
השוואה בין שם החייל הרשום במאגר הנתונים לשמו המוקלד תאפשר לוודא שאכן מדובר ברשומה הנכונה.
השוואה רגילה בין השמות אינה יעילה, כיוון ששמות נכתבים בצורות שונות עקב סיבות רבות, כגון:
כתיב מלא וכתיב חסר (דוד - דויד, למשל)
החלפת אותיות בעלות צליל דומה (מכבי - מקבי, למשל)
החלפת אותיות בעלות גופן דומה (ף - ץ, למשל)
שינוי סדר אותיות סמוכות (ידין - דיין, למשל).
שיבוש אקראי (כוכבא - כוזיבא, למשל).
על-מנת להיות יעילה, על השוואת השמות להיות כזו שתתעלם מהבדלים לא משמעותיים ביניהם, ולכך משמש אלגוריתם פונטי.
בעת אחזור מידע ממאגר נתונים, מסייע אלגוריתם פונטי לאיתור הרשומות המבוקשות.
דוגמה: אדם מנסה לאתר בספר טלפונים ממוחשב את ידידו מנוער, יהושע דוידוביץ.
יש דרכים שונות לאיית שם זה, וחיפוש המסתייע באלגוריתם פונטי יאתר את כל השמות השקולים לשם המבוקש
אלגוריתמים פונטיים משפיעים באופן משמעותי על מגוון תחומים, כאשר התרומה שלהם ניכרת ביותר בעיבוד שפה טבעית.
דרך סיוע בהבנת הקשר והמשמעות של מילים, בהתאם להגייתן, הם מאפשרים למערכות לעבד טקסטים ודיבור בצורה טבעית יותר.
הבנה זו של וריאציות באיות הנובעות מהגייה דומה חשובה לא רק בהקשר של עיבוד טקסט, אלא גם בתחומים כמו ביומטריה, שם מיפוי תבניות הגייה ייחודיות מאפשר זיהוי מדויק של אנשים דרך הקול.
בנוסף, בתחום מערכות החיפוש וההמלצה, השימוש באלגוריתמים אלו משפר את הדיוק במציאת תוצאות רלוונטיות, תוך מתן מענה לאיות שגוי או וריאציות פונטיות, מה שמעלה את חוויית המשתמש.
מעבר לשפה האנגלית, הפיתוח וההתאמה של אלגוריתמים פונטיים לשפות אחרות מעידים על המאמץ להתמודד עם האתגרים הייחודיים לכל שפה.
למשל, בעברית, שפה בעלת מאפיינים פונטיים מיוחדים, התאמה זו מתבצעת דרך פיתוח אלגוריתמים ייחודיים המתאימים למבנה ולהגיית השפה.
במדעי המחשב, אלגוריתם תזמון הוא אלגוריתם המממש מדיניות תזמון מסוימת עבור סדרן התוכניות.
מדיניות זו קובעת את דרך חלוקת המשאבים, למשל המעבד, בין תהליכים ותהליכונים.
הצורך באלגוריתם תזמון נובע מהדרישה לריבוי משימות שקיימת ברוב המערכות המודרניות.
מטרותיו העיקריות של אלגוריתם תזמון הן ניצול מקסימלי של המעבדים ושמירה על זמן תגובה נמוך של המערכת לאירועים שונים.
דרישות נוספות מהאלגוריתם יכולות להתבסס על אופי המערכת בה הוא מתקיים.
במערכות זמן אמת, הדרישה לזמן תגובה נמוך הוא הכרחי ביותר עבור חלק מהתהליכים.
כך למשל, במערכת הטייס האוטומטי, במידה והמערכת מגלה ירידה במהירות הטיסה, נרצה שהמערכת תגביר מהירות באופן מיידי.
במערכות שנמצאות במחשב רשת מרכזי, בו התהליכים יכולים להיות משתמשי קצה שונים, ההוגנות (חלוקת זמן שווה וזמן המתנה שווה בין התהליכים) תהיה דרישה משמעותית.
כמו כן, ניתן לבצע אופטימיזציות ספציפיות לחומרה ובכך לשפר את ניצול המעבדים.
אלגוריתמי תזמון שמקיימים אופטימיזציות שכאלה הן למשל:
תזמון כנופיות (Gang Scheduling) - במחשבים מרובי מעבדים, עבור תהליכים מרובי תהליכונים - נרצה להפעיל במקביל על מספר מעבדים את כל התהליכונים (או כמה שניתן).
הסיבה נעוצה בעובדה שעל פי רוב, בין התהליכונים השונים יש סנכרון כלשהו שימנע מתהליכון אחד להמשיך לרוץ עד שאחר לא ימשיך.
לכן כדי למנוע ריבוי החלפות הקשר, נפעיל את התהליכונים במקביל.
תזמון דביק (Sticky Scheduling) - במחשבים מרובי מעבדים, נרצה בכל פעם להריץ תהליך על אותו המעבד עליו רץ בפעם האחרונה, כדי לחסוך חריגי מטמון.
על אלגוריתם תזמון להימנע ממצב בו עלולה להתקיים הרעבה של תהליכים/תהליכונים.
אלגוריתם שוֹר (Shor - על שם פיטר שור, ממציאו), הוא אלגוריתם קוונטי המשמש לפירוק לגורמים של מספר גדול, כלומר מציאת הגורמים הראשוניים של המספר.
האלגוריתם פורסם לראשונה על ידי פיטר שור בשנת 1994, ויחד עם אלגוריתם גרובר נחשב לאחד משני האלגוריתמים החשובים ביותר בתחום החישוב הקוונטי.
פיתוח האלגוריתם זיכה את ממציאו בפרס גדל (1999).
אלגוריתם שור מבוסס על הרעיונות הקוונטיים שהודגמו באלגוריתם סימון למציאת מחזור של פונקציה.
האלגוריתם משתמש בהתמרת פורייה קוונטית (QFT), על מנת לקבל מחזור שהוא כפולה של אחד מהגורמים הראשוניים של המספר אותו רוצים לפרק.
האלגוריתמים הטובים ביותר למחשבים בינאריים קלאסיים, מפרקים מספר גדול ,לגורמיו בסיבוכיות זמן של , שאינה פולינומית ב-.
לעומת זאת, אלגוריתם שור פועל בסיבוכיות זמן של שהיא קטנה אקספוננציאלית מפירוק במחשב קלאסי.
שימוש באלגוריתם זה על מנת לפרק מספרים גדולים מהווה איום על אלגוריתמים מתחום ההצפנה האסימטרית, אשר מושתתים על פעולות מתמטיות עם מספרים גדולים, כגון RSA ו-DSA.
שיטות אלו מסתמכות על מספר גדול בן 512–8192 סיביות (מספר בעל מאות ספרות), אשר ידוע לכלל.
הגורמים הראשוניים של מספר זה מהווים את המפתח הסודי.
שימוש באלגוריתם שור מאפשר מציאת המפתח באופן יעיל, כלומר, במספר "קטן" יחסית של פעולות.
מסיבה זו נעשים מאמצים למצוא חלופות פוסט קוונטיות לאלגוריתמים הקיימים, כדי לתת מענה הולם כאשר המחשבים הקוונטיים יהיו מעשיים בקנה מידה המהווה איום מוחשי.
עם זאת, היישום הפיזיקלי של האלגוריתם קשה, בגלל הקשיים הטכניים בבניית מחשב קוונטי.
ככל הידוע, הניסיון המוצלח ביותר באלגוריתם שור בוצע על המספר 56153. בניית מחשב קוונטי בעל מספר גדול יותר של קיוביטים, נחשבת אתגר קשה מאוד בטכנולוגיה בת ימינו.
ניתן לחלק את פעולת האלגוריתם לשני שלבים, הראשון הוא השלב קלאסי, הניתן לביצוע על כל מחשב שהוא, והשני שלב קוונטי, אשר מבוצע על מחשב קוונטי.
אם לא, בצע את השלב הקוונטי על מנת למצוא את המספר , שהוא המחזור של הפונקציה
אם המספר r המתקבל אי-זוגי, חזור לסעיף 1.
אחרת, ל גורם ראשוני משותף עם N.
חשב וקבל גורם ראשוני של N.
(הסבר: אם מחזור של אזי , כלומר, .
כאשר , הגורמים של N).
בחר מספר Q כך ש וכן Q הוא חזקה שלמה של 2, כלומר ניתן לכתיבה עבור q מספר טבעי.
1. אתחל שני אוגרים קוונטים, בגודל q קיוביטים כל אחד, למצב
שהוא סופרפוזיציה של Q מצבים.
2. הפעל את הפונקציה הקוונטית על האוגרים, לקבלת
3. בצע התמרת פורייה קוונטית על האוגר הראשון.
מהתמרת מקבלים , כאשר , ועל כן מצב האוגרים לאחר הפעלת השער הוא סופרפוזיציה של הרבה יותר מ מצבים, אך הרבה פחות מ :
מתקבל ערך כלשהו וערך כלשהו.
ההסתברות למדוד את הזוג נתונה על ידי
הסתברות זו נובעת מקיומם של ערכים רבים של עבורם , כאשר כל האיברים הללו תורמים להסתברות למדוד את אותו המצב .
החלק הימני של השוויון נובע מהעובדה שהפונקציה מחזורית, בעלת מחזור r (בהנחה שהאבר הקטן ביותר באותו מחזור, וb מקבל ערכים מ-0 עד , אז הביטוי כלל ה-ים הקטנים מ- המקיימים ).
5. מצא מספר ומספר , כך ש ו קרוב מאוד ל, ובאופן מפורש, .
6. קיים סיכוי גבוה מאוד כי הוא המחזור המבוקש.
אם לא - חזור על ביצוע האלגוריתם.
אלגוריתם קוונטי הוא אלגוריתם המיועד לפעול על מחשב קוונטי – מכשיר חישובי המנצל את עקרונות מכניקת הקוונטים, כגון סופרפוזיציה ושזירה קוונטית.
אלגוריתמים אלה שונים באופן מהותי מאלגוריתמים קלאסיים, בכך שהם פועלים על קיוביטים במקום על ביטים רגילים, ועושים שימוש בתכונות קוונטיות לביצוע חישובים באופן יעיל יותר עבור בעיות מסוימות.
בעוד מחשבים קלאסיים מבצעים חישובים על סדרות של ביטים הנמצאים באחד משני מצבים (0 או 1), מחשב קוונטי פועל על קיוביטים, שיכולים להימצא בכל סופרפוזיציה של המצבים |0⟩ ו-|1⟩.
כאשר מספר קיוביטים מקושרים באמצעות שזירה קוונטית, המערכת כולה יכולה להימצא במצב קוונטי מורכב המייצג בו-זמנית מספר אקספוננציאלי של מצבים.
אלגוריתם קוונטי הוא למעשה סדרת פעולות (שערים קוונטיים) שמבוצעות על קבוצת קיוביטים, ובסיומן מתבצעת מדידה.
מטרת האלגוריתם היא לפעול על ההתפלגות ההסתברותית של תוצאות המדידה כך שהתוצאה הרצויה תופיע בהסתברות גבוהה.
אלגוריתמים קוונטיים מסוגלים, לעיתים, לספק יתרון חישובי מהותי על פני אלגוריתמים קלאסיים.
ישנם שני סוגים עיקריים של יתרונות:
האצה אקספוננציאלית – לדוגמה, אלגוריתם שור לפירוק לגורמים ראשוניים פועל בזמן פולינומי, לעומת האלגוריתמים הקלאסיים הידועים כיום שפועלים בזמן אקספוננציאלי.
האצה ריבועית – לדוגמה, אלגוריתם גרובר מקצר את זמן החיפוש כאשר מחפשים פריט מסוים בתוך רשימה של פריטים לא ממויינת מ־ עבור חיפוש קלאסי ל־ באמצעות מחשב קוונטי.
אלגוריתם דויטש-ג'וזה הוא מהאלגוריתמים הקוונטיים הראשונים שהוצגו, ונחשב לדוגמה מובהקת ליתרון קוונטי תאורטי על פני חישוב קלאסי.
האלגוריתם עוסק בבעיה הבאה: נתונה פונקציה בוליאנית אשר מובטח מראש שהיא או קבועה (כלומר, מחזירה את אותה התוצאה לכל קלט) או מאוזנת (מחזירה 0 בדיוק למחצית מהקלטים ו-1 למחצית השנייה).
המטרה היא לקבוע בוודאות לאיזה סוג משתייכת הפונקציה.
באופן קלאסי, כדי להכריע בוודאות בין שני המקרים יש לבדוק עד מחצית מהקלטים האפשריים בתרחיש הגרוע ביותר – כלומר, קריאות לפונקציה.
לעומת זאת, אלגוריתם דויטש–ג'וזה מנצל תכונות קוונטיות כמו סופרפוזיציה והתאבכות קוונטית, ומצליח לקבוע בוודאות את סוג הפונקציה באמצעות קריאה אחת בלבד לאורקל קוונטי.
אף על פי שמדובר בבעיה מלאכותית שלא נחשבת שימושית באופן ישיר, האלגוריתם היווה נקודת מפנה חשובה בתולדות המחשוב הקוונטי, משום שהוא הדגים לראשונה כיצד מחשב קוונטי יכול לפתור בעיה מסוימת במהירות גבוהה לאין שיעור מזו של מחשב קלאסי.
כמו כן, רעיונות מתוך האלגוריתם שימשו כבסיס לפיתוח אלגוריתמים קוונטיים חשובים נוספים, כמו אלגוריתם סיימון ואלגוריתם שור.
אלגוריתם ברנשטיין–וזיראני (Bernstein–Vazirani algorithm) הוא האלגוריתם הקוונטי הראשון שפותר בעיה בצורה יעילה יותר מהאלגוריתם הקלאסי הידוע הטוב ביותר.
האלגוריתם הוא גרסה מוגבלת של אלגוריתם דויטש-ג'וזה, והוא נועד לפתור בעיה מקבילה.
במקום להפריד בין שתי מחלקות של פונקציות (הפרדה בין פונקציה קבועה לפונקציה שמחזירה בהסתברות שווה 0 או 1), אלגוריתם זה נועד למצוא את מילת הקוד שמגדירה את פונקציית האורקל.
האלגוריתם תוכנן על מנת להוכיח כי ניתן להפריד באמצעות אורקל (Separation oracle) בין שתי מחלקות הסיבוכיות BQP ו־BPP.
האלגוריתם של סיימון פותר בעיית סיימון (Simon's problem) בזמן מהיר יותר באופן מעריכי לעומת כל אלגוריתם קלאסי אחר, כולל אלגוריתמים הסתברותיים עם שגיאה מוגבלת.
בעיית סיימון היא בעיית קופסה שחורה שבה הקלט הוא באורך n והפלט באורך m כאשר מתקיים .
אלגוריתם סיימון היווה השראה לאלגוריתם שור לפירוק לגורמים.
אלגוריתם שור פותר את בעיית הלוגריתם הבדיד ואת בעיית הפירוק לגורמים בזמן פולינומי, בעוד שהאלגוריתמים הקלאסיים הידועים הטובים ביותר דורשים זמן על-פולינומי.
אלגוריתם שור הוא גם אחד מהאלגוריתמים הקוונטים היחידים שפותר בעיה שאיננה בעיית קופסה שחורה בזמן פולינומי, בעת שהאלגוריתמים הקלאסיים הידועים דורשים זמן על-פולינומי.
אלגוריתם הערכת פאזה קוונטית (Quantum phase estimation algorithm) משמש לקביעת הפאזה העצמית של וקטור עצמי המתאים לשער אוניטרי מסוים.
מציאת הפאזה נעשית באמצעות שימוש במצב קוונטי אשר פרופורציונלי לווקטור העצמי המבוקש וגישה לשער האוניטרי.
האלגוריתם משמש לעיתים קרובות כתת-שגרה באלגוריתמים אחרים.
סכום גאוסי (Gauss sum) הוא סוג של סכום מעריכי (Exponential sum).
האלגוריתם הקלאסי הידוע הטוב ביותר להערכת סכומים אלו דורש זמן מעריכי.
מאחר שבעיית הלוגריתם הבדיד ניתנת לצמצום להערכת סכומים גאוסיים, קיום אלגוריתם קלאסי יעיל להערכת סכומים גאוסיים היה מרמז על קיום אלגוריתם קלאסי יעיל לפתרון בעיית הלוגריתם הבדיד – דבר שנחשב בלתי סביר.
עם זאת, מחשבים קוונטים יכולים להעריך סכומים גאוסיים בדיוק פולינומי ובזמן פולינומי באמצעות מגוון שיטות קוונטיות.
דייג פורייה (fourier fishing) ובדיקת פורייה (fourier checking) הן שתי בעיות במחשוב קוונטי הקשורות לתכונות של פונקציה במרחב פורייה.
דייג פורייה היא בעיית דגימה, ואילו בדיקת פורייה היא בעיית החלטה.
ניתן לתאר בעיות אלו באמצעו אורקל המורכב מ-n פונקציות בוליאניות רנדומליות אשר ממפות כל אחת מחרוזת באורך n לערך בוליאני יחיד.
המטרה היא למצוא סט של n מחרוזות באורך n מהצורה אשר עבור התמרת אדמר-פורייה (שער אדמר) מתקיים:
באמצעות אלגוריתמים קוונטיים הדבר יכול להתבצע בסיבוכיות BQP.
בתחום הקריפטוגרפיה, מאיימים אלגוריתמים קוונטיים על מערכות הצפנה מודרניות, במיוחד אלו הנשענות על קושי פירוק לגורמים, כמו RSA ו־ECC.
אלגוריתם שור מסוגל לפרוץ מערכות אלה בזמן פולינומי.
בנוסף, אלגוריתם גרובר מקצר את זמן החיפוש במפתחות של הצפנה סימטרית, כמו AES, מ־ ל־, מה שמחייב הארכת מפתחות כדי לשמור על אותה רמת אבטחה.
בעקבות איומים אלה, מתפתח תחום קריפטוגרפיה עמידה לקוונטים.
בתחום הכימיה החישובית, מחשבים קוונטיים מתאימים במיוחד לסימולציה של מערכות מולקולריות מורכבות.
אלגוריתמים כמו VQE ו־QPE מאפשרים לחשב את אנרגיית היסוד של מולקולות בצורה יעילה.
תחום זה עשוי לשנות את הדרך שבה מתכננים תרופות, חומרים מתקדמים וזרזים כימיים.
סימולציות אלו כמעט בלתי אפשריות עבור מחשבים קלאסיים משום שמספר המצבים הקוונטיים האפשריים במערכת גדל בקצב אקספוננציאלי ככל שמוסיפים חלקיקים – דבר שדורש כמות עצומה של זיכרון וחישוב.
כאלגוריתם חיפוש, אלגוריתם גרובר מאפשר ביצוע חיפוש מהיר יותר במידע בלתי ממויין, והוא שימושי בבעיות כמו מציאת פריטים במאגר, פתרון בעיות SAT או בדיקת התנגשויות בפונקציות גיבוב.
יתרון זה חשוב בתחומים כמו אבטחת מידע, בקרה, בלוקצ'יין ומחקר סטטיסטי.
במדעי המחשב, אלגוריתם מקוון (online algorithm) הוא אלגוריתם אשר מאולץ לפלוט החלטות לפני השלמת קבלת כל הקלט.
מאידך גיסא, אלגוריתם שאינו מקוון (offline algorithm) מורשה לעבור על כל הקלט בטרם ייאלץ לפלוט את החלטתו הראשונה.
מסיבה זו, אלגוריתם מקוון עשוי להגיע להחלטות שאינן אופטימליות יחסית לאלגוריתם שאינו מקוון.
ניתוח התחרותיות (competitive analysis) של האלגוריתם הוא חקר איכות החלטות של אלגוריתמים מקוונים.
זהו ניתוח של החרטה של אלגוריתם מקוון.
בין שאר תפקידיה, מערכת הפעלה של מחשב מתפעלת מידע המחולק פנימית לדפים.
המשתמש מבצע פעולות המתרגמות לבקשות גישה לדפים.
רק לחלק מדפים אלה יש מקום בזיכרון המטמון של המחשב, ורובם נשמרים בדיסק הקשיח שלו.
זמן הטעינה של דפים מהדיסק הקשיח לזיכרון הוא ארוך מאוד בהשוואה לרוב פעולותיו האחרות של המחשב.
מסיבה זו, כשהמשתמש מבצע פעולה המתרגמת לצורך לטעון דף לזיכרון, ויש צורך לפנות דף אחר מהזיכרון לצורך כך, אידיאלית היה כדאי לפנות את הדף שיבוקש האחרון בעתיד.
דא עקא, שהמחשב אינו יודע בשלב זה את כל סדרת הבקשות בעתיד, ולכן זו בעיה מקוונת.
משחק בעל יותר משחקן יחיד
רוב המשחקים בעלי יותר משחקן יחיד (לדוגמה שחמט או דמקה) הם, לפי ההגדרה, מקוונים.
אי אפשר לקבל מראש את סדרת ההחלטות של היריב, מפני שפעולותיו של כל צד נקבעות בין היתר על פי פעולת הצד השני.