tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
לאחר סיום ריצת האיטרציות, האלגוריתם עובר פעם נוספת על כל הקשתות ובודק האם עדיין מתקיים , כלומר "עדיין יש מה לתקן".
זה יכול לקרות אם ורק אם הגרף מכיל מעגלים שליליים, ולכן אפשר לתקן אותו "עד אינסוף", כי כל מסלול יכול להיכנס אל תוך המעגל השלילי וללכת עליו כמה פעמים שירצה כדי להקטין את משקלו.
ניתן לשפר את זמן הריצה של האלג' על ידי ביצוע מיון טופולוגי לגרף, מדובר בבדיקה פשוטה על ידי הרצת אלג' DFS על הגרף וסידור הקודקודים לפי זמני היציאה שלהם.
אם הגרף טופולוגי, כל המסלולים המזעריים של הגרף מתגלים באיטרציה הראשונה על ידי מעבר על הצלעות לפי המיון הטופולוגי של הקודקודים.
אלגוריתם חיפוש לרוחב הוא אלגוריתם המשמש למעבר על צומתי גרף, למשל לצורך חיפוש צומת המקיים תכונה מסוימת.
הגרף יכול להיות מכוון או לא מכוון.
צומת כלשהו בגרף נקבע להיות הצומת ההתחלתי , והאלגוריתם עובר על כל הצמתים במרחק צלע אחת מ-, ואז על כל הצמתים במרחק 2 צלעות מ- וכן הלאה.
צורת חיפוש זו היא חיפוש לרוחב הגרף, בניגוד לחיפוש לעומק הגרף.
חיפוש לרוחב בגרף לא מכוון סורק את הגרף בצורה שמבטיחה שכל צומת שנמצא באותו רכיב קשירות של הצומת ההתחלתי ייבדק, וסריקה זו נעשית בזמן ליניארי במספר הקשתות והצמתים בגרף (שהוא אופטימאלי עד כדי מכפלה בקבוע).
בשל כך, חיפוש לרוחב מהווה בסיס לאלגוריתמים רבים שפועלים על גרפים, בהם אלגוריתם דייקסטרה, האלגוריתם של פרים והאלגוריתם של אדמונדס-קארפ.
פלט האלגוריתם, המכונה עץ החיפוש לרוחב (BFS), מקיים את התכונה שהמסלול משורש העץ לכל אחד מהצמתים הוא המסלול בעל מספר הצלעות הנמוך ביותר בגרף המקורי, ובגרף שאינו גרף ממושקל הוא גם המסלול הקצר ביותר.
סיבוכיות הזמן והמקום של האלגוריתם בגרף קשיר היא , כאשר מייצג את קבוצת הצמתים בגרף ו- מייצג את קבוצת הקשתות בגרף.
האלגוריתם משתמש במבנה נתונים מסוג תור על מנת לקבוע מהו הצומת הבא בו הוא עומד לבקר.
בכל פעם שהוא מבקר בצומת הוא מסמן אותו ככזה שנבדק, ואז בודק את כל הקשתות שיוצאות ממנו.
אם קשת מובילה לצומת שטרם נבדק, צומת זה מתווסף לתור.
בדרך זו מובטח כי האלגוריתם יסרוק את הצמתים בסדר שנקבע על פי מרחקם מהצומת ההתחלתי.ראוי לציון שכאשר מחליפים את מבנה הנתונים תור במבנה נתונים מחסנית, האלגוריתם המתקבל הוא חיפוש לעומק.
הקוד להלן מתאר אלגוריתם חיפוש לרוחב המתחיל בצומת start ומחפש צומת goal,
במדעי המחשב, אלגוריתם חיפוש לעומק הוא אלגוריתם המשמש למעבר על גרף או לחיפוש בו.
האלגוריתם מוגדר עבור גרפים בלתי מכוונים ועבור גרפים מכוונים.
אינטואיטיבית, האלגוריתם מתחיל את החיפוש מצומת שרירותי בגרף, ובכל צעד מתקדם מהצומת בו הוא נמצא לצומת שכן שעוד לא ביקר בו, אם יש כזה.
אם ביקר בכל הצמתים השכנים, הוא חוזר על עקבותיו עד שהוא מגיע לצומת שיש לו שכן שטרם ביקר בו.
דרך פעולת האלגוריתם דומה במידת מה לסריקה שיטתית של מבוך.
האלגוריתם מחזיר עץ מכוון שבו לכל צומת שאינו שורש נכנסת קשת מהצומת שגילה אותו.
במיוחד כל קשת בעץ החיפוש לעומק היא גם קשת בגרף עליו נעשה החיפוש.
התכונה המאפיינת עץ חיפוש לעומק בגרף לא מכוון, שהיא הסיבה לשימושיות שלו, היא שכל קשת בגרף עליו נעשה החיפוש מחברת צומת עם צאצא שלו בעץ החיפוש.
להמחשה: בגרף שעץ החיפוש לעומק שלו מופיע בציור, לא תיתכן קשת בין צומת 2 לצומת 7, מפני ש אף אחד מצמתים אלו אינו צאצא של השני.
אך תיתכן קשת בין צומת 2 לצומת 5, מפני ש-5 צאצא (נכד) של 2.
אלגוריתם חיפוש לעומק מתחיל בצומת כלשהו, שייקרא שורש (צומת 1 בציור המצורף).
בכל שלב האלגוריתם בודק אם לצומת בו הוא נמצא כרגע, נסמנו u, יש צומת שכן, נסמנו v, שהאלגוריתם עדיין לא ביקר בו.
אם יש שכן v כזה האלגוריתם עובר מ־u ל־v ואומרים ש־u גילה את v (בציור צומת 2 גילה את הצמתים 3 ו-6).
אם כל השכנים של הצומת u כבר בוקרו, האלגוריתם נסוג לצומת ממנו התגלה u.
אם אין צומת שגילה את u חייב להתקיים ש u הוא שורש.
במקרה זה האלגוריתם בודק אם קיים צומת שעדיין לא ביקר, ואם יש כזה הוא מגדיר אותו כשורש וחוזר על התהליך עד שכל הצמתים בוקרו.
מימוש פשוט ויעיל של החיפוש הוא על ידי מחסנית.
גילוי צומת מתבטא בהכנסתו לראש המחסנית ונסיגה מצומת מתבטאת בהוצאתו מראש המחסנית.
סיבוכיות המקום של האלגוריתם היא, במקרה הגרוע, כאשר d הוא אורך המסלול הפשוט המקסימלי בגרף, וסיבוכיות הזמן היא O(m), כאשר m מספר הקשתות בגרף.
אלגוריתם חיפוש לעומק הוא בסיס לאלגוריתמים רבים שפועלים על גרפים.
למשל, מציאת צמתי הפרדה ורכיבים אי-פריקים בגרף לא מכוון, מציאת רכיבים קשירים היטב בגרף מכוון, מציאת מסלול אוילרי ומעגלים בגרף או מיון טופולוגי שלו.
אלגוריתם זה נמצא בשימוש באופטימיזציה הרמונית.
פסאודו קוד - מימוש על ידי מחסנית
DFS – מימוש על ידי מחסנית
המימוש ממספר את הצמתים על פי הסדר בו התגלו,
קלט: גרף G=(V,E), מכוון או לא מכוון
פלט: יער DFS של G וגם לכל צומת v זמן הגילוי של v.
סימון: k[v] זמן הגילוי של v, ו-p[v] – האב של v ביער ה-DFS.
הגרף המכוון שנוצר על ידי הרצת האלגוריתם הוא הגרף המורכב מהקשתות (p(u),u).
כעת נוכיח מספר תכונות של האלגוריתם, ובמיוחד שגרף זה הוא יער מכוון המכיל את כל צמתי הגרף.
אלגוריתם דו-כיווניות של יוניקוד מאפשר קביעת כיוון זרימת מלל במערכות מחשב, מימין לשמאל או משמאל לימין.
כדי לעמד מלל דו-כיווני כהלכה משתמש האלגוריתם בנתון סוג הכיווניות של תווים כדי לנתח את הטקסט ולפרק אותו לקטעים או רצפים של תווים, בעלי כיווניות מסוימת.
לכל תו ניתן לקבוע כיווניות חזקה ימין-לשמאל, חזקה שמאל-לימין, חלשה ימין לשמאל, חלשה שמאל-לימין, ונייטרלי.
באלגוריתם, תווים מטווח יוניקוד לעברית, ערבית, אשורית ודומותיהן נחשבים בעלי כיווניות ימין-לשמאל חזקה.
תווי האלף-בית הלטיני נחשבים בעלי כיווניות שמאל-לימין חזקה.
תווי מספרים נחשבים בעלי כיווניות שמאל-לימין חלשה.
תווי פיסוק וניקוד נחשבים נייטרליים מבחינת כיוונם.
בהכללה, קובע האלגוריתם את כיווניותם של תווים נייטרליים בהתאם להקשר שבו הם נמצאים: אם הם נמצאים בין שני תווים בעלי כיווניות חזקה אחת, הם יירשו אותה.
לדוגמה, כאשר תווי פיסוק נייטרליים כמו פסיק ונקודה נמצאים בין תווים בעלי כיווניות ימין-לשמאל חזקה הם מקבלים אותה גם הם וממוקמים משמאל לתו האחרון במילה.
מקרה מורכב מעט יותר הוא כזה שבו התו הקודם הוא בעל כיווניות מסוימת, אך עוקבו הוא בעל כיווניות אחרת.
במקרה זה, יורש התו הנייטרלי את הכיווניות של התו הבא לפניו ברצף:
מקרה מורכב עוד יותר מתרחש כאשר ישנו רצף של תווים נייטרליים מסוגים שונים הדורש הכרעה כיצד יש לסדרם.
כאן, אלגוריתם דו-הכיווניות כשל לעיתים ורק בגרסתו האחרונה תוקנו בעיות כמו רצפים של תו>מקף>מספר/תו לטיני.
קודם לכן, האלגוריתם שיבש את הסדר ודרש מיישומים שביקשו לתמוך בכיווניות נכונה במקרה נפוץ זה (בעברית) ליישם פתרונות "עוקפי-יוניקוד".
בגרסת "אופיס 2000" של ערכת התכנות המשרדיות של מיקרוסופט הוגדרה כיווניות כללית לפסקה, ובהתאם לה התנהגו התווים הנייטרליים כאילו הם בעלי כיווניות ימין-לשמאל או שמאל לימין.
בגרסה הנוכחית של האלגוריתם פתרונות כאלו אינם נחוצים.
לדוגמה, המשפט הבא יוצג נכון באלגוריתם יוניקוד בגרסתו העדכנית:
באלגוריתם ישנן עדיין מספר בעיות בשימוש בעברית (ובערבית).
יוצג בשימוש רגיל באופן שגוי:
מקרה אחר קיים עם הטקסט הבא:
בעיה נוספת נפוצה בכתיבת מספרי טלפון:
הטקסט יוצג כאשר הקידומת מימין למספר הטלפון:
כדי לפתור בעיות אלו ניתן לעשות שימוש בתווים סמויים מיוחדים המכניסים כיווניות ימין-לשמאל או שמאל-לימין.
תוצאה נוספת אפשר לקבל כאשר מכניסים רווחי אפס בעלי כיווניות או תווים השוברים או מאחדים "הקשריות" (בערבית).
זה אינו פתרון שמשתמשים רגילים יכולים לעשות בו שימוש בנקל, ועדיין נדרשת השלמה תוכנתית לחסר.
תקן יוניקוד מגדיר שני תווי כיווניות סמויים.
תווים אלו אינם נראים במסמך ותפקידם לקבוע את כיווניות הטקסט שנמצא לפניהם ואחריהם.
תו LRM (Left-to-Right Mark) – בעל כיווניות חזקה שמאל-לימין.
תו RLM (Right-to-Left Mark) – בעל כיווניות חזקה ימין-לשמאל.
תו נייטרלי שיוצב בסמוך לתו LRM, יירש את כיווניותו שהיא שמאל-לימין, ואילו תו נייטרלי שיוצב בסמוך לתו RLM, יירש את כיווניותו שהיא ימין-לשמאל.
אופני השימוש בתווי כיווניות סמויים בפסקה עברית:
כשרושמים בתוך פסקה עברית את השם הלועזי של חברת Yahoo!, סימן הקריאה יופיע משמאל לשם ("Yahoo!"), מכיוון שאחריו יש אות עברית, אבל הוא אמור להופיע מימין.
כדי לגרום לו להופיע מימין, אפשר להוסיף אחריו את התו LRM.
התו מורה, למעשה, שהכיווניות של ימין לשמאל תימשך גם אחרי סימן הקריאה.
בדומה לכך, כשרושמים בתוך פסקה עברית את הפונקציה המתמטית f(x), ייראה הסוגר הסופי כמו סוגר פותח כך: f(x), מכיוון שאחריו יש אות עברית, אבל הוא אמור להופיע בקצה הימני של הביטוי.
כדי לגרום לו להופיע נכון בקצה הביטוי, אפשר להוסיף אחריו את התו LRM.
כאשר בתוך פסקה עברית יש רשימה של מילים לועזיות שמופרדת בפסיקים, למשל Alice, Bob, Carlos, הפסיקים יופיעו מימין לכל מילה, כי לפניהם ואחריהם יש אותיות לועזיות, וגם סדר המילים יהיה הפוך, אבל הפסיקים אמורים להופיע משמאל לכל מילה: Alice, Bob, Carlos.
כדי לגרום למילים ולפסיקים להופיע בסדר הרצוי יש להוסיף לפני הפסיק את התו RLM.
התו מורה שהכיווניות של שמאל-לימין תיפסק לפני הפסיק ובמקומה תהיה הכיווניות ימין-לשמאל, כך שהפסיק יופיע משמאל למילים כרגיל בכיווניות של ימין-לשמאל.
בעת כתיבת מספר טלפון עם קידומת בפסקה עברית כמו בדוגמה "(02) 9876543", שהקידומת מופיעה מימין למספר, וכן בכתיבת מספר שלילי עם סימן מינוס לפניו, שסימן המינוס מופיע מימין למספר, יש להוסיף לפני הקידומת או המינוס את התו LRM.
התו גורם לכיווניות להיות משמאל-לימין באופן מוחלט (כיווניות שמאל-לימין 'חזקה'), החל ממקום הקלדת התו.
תווים אלה עדיין אינם כלולים במקלדת עברית תקנית.
בטיוטת התקן הישראלי לפריסת מקלדת עברית ניתן להוסיף תו LRM באמצעות הצירוף , ותו RLM באמצעות הצירוף .
תקן זה מיושם בחלקו במערכת ההפעלה Windows, החל מ־Windows 8.
בנוסף, מערכות הפעלה ויישומים שונים מאפשרים הזנת תווי LRM ו-RLM במגוון דרכים:
במערכת הפעלה Windows מגרסה 8 ובפריסות מקלדת בלינוקס משנת 2013, בפריסת מקלדת עברית תקנית: LRM מוזן באמצעות (סוגר שמאלי) במקלדת הנומרית ו־RLM מוזן באמצעות (סוגר ימני).
ב־HTML תווים אלה מוכנסים כך: , ו-.
השם אלגוריתמים גנטיים מתאר משפחה של אלגוריתמים לחיפוש, מידול ומיטוב (אופטימיזציה), שבהם משלבים זה בזה אלמנטים של פתרונות אפשריים לבעיה, ומפעילים הליכים של ברירה מלאכותית כדי לבחור את המועמדים שיעברו לשלבים הבאים.
רעיון תכנותי בסיסי זה מושפע מההצלחה של האבולוציה בפתרון בעיות אמיתיות.
בשנות ה-50 וה-60 של המאה ה-20 ניסו מספר מדענים בתחומי המחשב לבחון מערכות אבולוציוניות (התפתחותיות), כאשר הם האמינו שאבולוציה תשמש ככלי לאופטימיזציה של בעיות הנדסיות ומדעיות.
הרעיון הכללי אליו כיוונו המדענים הוא לנסות לפתח אוכלוסייה של פתרונות אקראיים לבעיה נתונה, על ידי שימוש באופרטורים שמושפעים משינויים גנטיים טבעיים ובחירה טבעית.
התורה עליה התבססו מדענים אלה היא בעצם תורת האבולוציה של דרווין, כלומר פתרון לכל בעיה יעשה בתהליך גנטי על בסיס תורת האבולוציה.
בין המדענים החלוצים בתחום האלגוריתמים הגנטיים ניתן למנות את אלכס פרייזר והנס-יואכים ברמרמן.
האלגוריתם הגנטי הומצא על ידי ג'ון הנרי הולנד החל משנות ה-60 המוקדמות ואליך במהלך עבודתו באוניברסיטת מישיגן.
מטרתו העיקרית של הולנד, בניגוד למדענים אחרים אשר ניסו לכתוב תוכניות אבולוציוניות ונקטו בגישה אבולוציונית למציאת פתרון ספציפי, הייתה להבין בעצם את עקרון האדפטיביות כפי שהוא בא לידי ביטוי בטבע, כלומר יכולת ההסתגלות לתנאים משתנים.
הולנד ניסה לייבא תכונות אלה של אדפטיביות לתוך מערכות ממוחשבות.
אלגוריתמים גנטיים משמשים בעיקר כדי לפתור בעיות אופטימיזציה שלא ידוע עבורן פתרון דטרמיניסטי או הסתברותי העובד בזמן סביר.
העיקרון של אלגוריתם גנטי הוא שכמו כל יצור בטבע רק המתאימים שורדים.
הבעיה שעימה כל זן צריך להתמודד היא התאמה לסביבה והשינויים שחלים בה.
שילוב אלמנטים של פתרונות אפשריים לבעיה, הפעלת הליכים של ברירה מלאכותית כדי לבחור את המועמדים שיעברו לשלבים הבאים.
לכן אם ניקח אוכלוסייה של פתרונות ונבחר מתוכם רק את המתאימים ביותר לפתרון בעיה, נערבב אותם אחד עם השני ונוסיף קצת רעש, נקבל דור חדש של פתרונות הקרוב צעד נוסף לפתרון הבעיה הנתונה.
נחזור על התהליך מספר רב של פעמים (דורות) ולבסוף נגיע לפתרון הקרוב ביותר.
ייצוג בינארי של שני כרומוזומים
כל ביט במחרוזת מייצג אופין מסוים של הפתרון.
אפשרות נוספת היא שכל מחרוזת תיוצג על ידי מספר.
קיימים דרכים רבות לייצוג, הייצוג תלוי בעיקר בפתרון הבעיה.
במודל תכנותי זה יוצרים קהילה של פרטים אשר מאופיינים בכרומוזומים, ומעבירים אותם "תהליך אבולוציוני".
האלגוריתם עוסק במעבר בין אוכלוסייה של כרומוזומים (רצף של סיביות 0 ו-1 ) לרצף חדש של סיביות ("אוכלוסייה חדשה") על ידי שימוש בבחירה הטבעית ואופרטורים כמו crossover.
לאחר יצירת קהילת הפרטים הראשונה, מדרגים כל פרט על מנת למצוא את הפרטים הטובים ביותר.
לאחר מכן, עורכים מיזוג (זיווג) בין פרטים אלה על מנת ליצור קהילה חדשה, טובה במקצת מקודמתה, ומעבירים אותה את אותו התהליך.
ההנחה כאן היא שמיזוג בין שני פתרונות טובים לבעיה עשוי להניב פתרון טוב יותר.
כמו בגנטיקה ביולוגית, שני הורים בעלי סט גנים טובים יוצרים צאצא שגם הוא עליון מבחינה גנטית.
לאחר מספר חזרות על הפעולה, הפרטים ישתפרו דרמטית ויציגו את הפתרון הטוב ביותר, או פתרון טוב באופן יחסי לבעיה הנתונה.
בכתיבת אלגוריתם גנטי יש לממש:
זיווג (Crossover) של שני פרטים שמחזיר שני צאצאים או יותר.
הצאצאים נושאים מטען גנטי שהוא שילוב של הפרטים שזווגו.
פועל על גנים נבחרים מהכרומוזומים של ההורים ויוצר צאצא חדש.
הדרך הפשוטה ביותר לביצוע היא לבחור באופן אקראי נקודה לזיווג, להעתיק את כל הביטים שלפני הנקודה מהורה אחד ולהעתיק את כל הביטים שאחרי הנקודה מההורה השני.
אם crossover לא מבוצע, הצאצא יהיה העתק מושלם של ההורים.
הפעולה מבוצעת במטרה להכיל את החלקים הטובים של הכרומוזומים הישנים ולכן הכרומוזומים החדשים יהיו טובים יותר.
למרות זאת, חשוב להשאיר חלק של האוכלוסייה הישנה לדור הבא.
מוטציה (Mutation) על פרט בודד שמשנה את התכונות שלו.
המטרה היא לבצע שינוי בהעתקות שנוצרו על ידי הזיווג, זאת כדי למנוע חזרה של חלקים שלמים במחרוזת הביטים.
אם לא נבצע את פעולת המוטציה הצאצא ייווצר מידית לאחר פעולת הזיווג או שיועתק ישר מההורים ללא כל שינוי.
כאשר מבצעים מוטציה חלק אחד או יותר מהכרומוזומים משתנים.
מוטציות מתרחשות לרוב בהסתברות נמוכה כלשהי (בין 0.1% ל-0.01%) וזאת מכיוון שאם ההסתברות תהיה גבוהה האלגוריתם הגנטי יהפוך לאלגוריתם של חיפוש אקראי (האלגוריתם יצא משליטה).
שיערוך (Evaluation) בו בוחרים את הפרטים שישתתפו בתהליך הזיווג לפי רמת התאמה, בעזרת "פונקציית כשירות" (fitness function).
לפונקציית השערוך יש מרכיבים רבים שיכולים להחליש או לחזק את ביצועי האלגוריתם הגנטי.
ביצועי האלגוריתם הגנטי רגיש מאוד לטכניקה של תהליך הנרמול, כך למשל אם נדרוש שיפור יתר - הדבר יכול להוביל לקבלת חומר גנטי אלטרנטיבי באוכלוסייה ויקדם שליטה של צאצא יחיד.
במקרה כזה, לפעולת ה-crossover אין השפעה והאלגוריתם מרכז את מרב החיפושים אחר הפתרון הנדרש סביב הכרומוזום הטוב האחרון שמצא.
לעומת זאת, אם תהליך הנרמול לא יפעל כראוי האלגוריתם ייכשל במציאת פתרון בזמן סביר וקרוב לוודאי שפתרונות טובים מקרב האוכלוסייה יאבדו.
מאפיין חשוב נוסף של פונקציית השערוך הוא החוזק והחולשה של האלגוריתם הגנטי.
ביישום האלגוריתם בדרך כלל לוקחים ערך יחיד שחוזר על ידי פונקציית השערוך ומשתמש בערך כדי לקבוע התאמה יעילה.
בקביעת פונקציית השערוך יש להתייחס לאילוצים של היישומים כדי לפסול צאצאים שייתכן ואינם חוקיים.
הערך את ההתאמה של כל פרט באוכלוסייה
בחר את הפרטים המתאימים ביותר לזיווג
צור דור חדש של פרטים על ידי זיווג ומוטציה של הדור הקודם
חזור על שלבים 2–3 עד סיום הסימולציה
כשם שבתורת האבולוציה של דרווין ישנו שימוש ניכר במוטציות ובשינויים גנטיים, גם במודל תכנותי זה יש חשיבות רבה למוטציות הגנטיות.
בכל זיווג של 2 פרטים ניתן לשלב "שגיאות" אקראיות שיאפשרו יצירה של מידע חדש, שאותו אין לאף פריט אחר באוכלוסייה (קהילה) הנוכחית.
אם שגיאה זו תוכר כהצלחה, הפריט ימוזג שוב, ולכן ה"שגיאה" תמשיך להתקיים; אם לא, היא תיעלם כלא הייתה.
הסיבה לשימוש במוטציות כחלק מהאלגוריתם הגנטי הוא שישנה סכנה שאוכלוסיית הפתרונות תקלע למינימום מקומי במרחב הפתרון.
השימוש במוטציות נותן אפשרות לצאת ממינימום מקומי ובכך להגיע לפתרון טוב יותר לבעיה.
מטרת פונקציית ההערכה היא להגדיר סדר על הפרטים.
ההערכה מאפשרת לבחור את הפרטים המוצלחים ביותר מתוך הקהילה.
לעיתים ההערכה תתבסס על פונקציה פשוטה המקבלת מספר פרמטרים ומחזירה דירוג (כאשר הבעיה היא דטרמיניסטית), ולעיתים תמומש סימולציה מלאה של חיי הפרט בתוך הקהילה (כאשר הבעיה היא סטוכסטית).
אלגוריתמים גנטיים שייכים לקבוצה גדולה של אלגוריתמי חיפוש ואופטימיזציה.
כיום הם נחשבים על פי רוב למוצלחים פחות מאלגוריתמים המבוססים על טיפוס בהר.
עם זאת אלגוריתמים גנטיים מתאימים לבעיות של בחירת תתי-קבוצות אופטימליות (subset-selection), וכן לבעיות של מציאת מערכת שעות ולוחות זמנים.
כלכלה- באלגוריתם הגנטי עושים שימוש עבור יצירות מודלים של תהליכי חדשנות, אסטרטגיה של מיקוח, חדשנות והתמתחות שווקים כלכליים.
אקולוגיה- נעשה שימוש באלגוריתמיקה גנטית לשם הגעה למודלים של תופעות אקולוגיות.
בראייה מתמטית, אלגוריתם גנטי מאפשר למצוא נקודות קיצון של פונקציה ב-n משתנים.
תהי פונקציית הכשירות, בה רוצים למצוא נקודות קיצון גלובליות, אזי:
הוא פרט במודל ואיבר בתחום של הפונקציה
הוא השיערוך של פרט .
זיווג הוא לקיחת פרטים בתחום והחזרת שמורכב מהכרומוזומים של x ו-y.
דוגמה ב-: זיווג של יכול להיות .
מוטציה משנה חלק מהכרומוזומים של פרט .
אלגוריתמים קו-אבולוציוניים (Co-evolutionary Algorithms) הם תת-משפחה של אלגוריתמים גנטיים שבם פונקציית הכשירות נקבעת על פי יחס בין אוכלוסיות ולא אבסולוטית, קרי, טיב פתרון מאוכלוסיית פתרונות אחת נקבע ביחס כלשהו לאינטראקציה שלו עם קבוצת פתרונות של אוכלוסייה אחרת שמשתתפת באלגוריתם.
היחס המדובר יכול להיות שיתופי (כל אוכלוסייה מייצגת חלק מן הפתרון הכולל לבעיה) או תחרותי (כל אוכלוסייה מיצגת חלק אחר של הבעיה, או מתחרה על פתרונות לבעיה).
במדעי המחשב, אלגוריתם חיפוש הוא אלגוריתם המשמש לחיפוש נתון נדרש במבנה נתונים.
חיפוש הוא פעולה בסיסית בפיתוח תוכנה, למשל לשם אחזור מידע מבסיס נתונים, ולכן הושקע מאמץ בפיתוח אלגוריתמים יעילים לביצוע משימה זו.
את האלגוריתמים ניתן לחלק לשני סוגים.
חיפוש ממצה הוא חיפוש המאפשר לקבוע שהנתון נמצא במערכת כמפתח לחיפוש.
ובמקרה שהוא נמצא, ניתן לקבל את הנתונים שהוא מאנדקס.
החיפוש הבסיסי ביותר הוא חיפוש בכוח גס - מעבר על כל הנתונים לפי סדרם, עד למציאת הנתון המבוקש, אם הוא אכן נמצא.
מקובל לכנותו חיפוש ממצה בסיסי, או אלגוריתם חיפוש נאיבי.
זהו חיפוש בלתי יעיל, וכאשר מספר הנתונים שבהם יש לחפש הוא גדול, החיפוש נמשך זמן רב, במידה בלתי סבירה.
כאשר הנתונים ממוינים, ניתן לשפר משמעותית את החיפוש על ידי שימוש בחיפוש בינארי.
הבעיתיות בשיטה זו היא הדרישה שהנתונים יהיו ממוינים מראש, והצורך לשוב ולמיינם בכל פעם שנתון חדש מוכנס למאגר או כשנתון קיים מוצא ממנו.
כדי לאפשר חיפוש מהיר מחד, ולהימנע מן הצורך למיין את הנתונים בכל פעם שחל בהם שינוי מאידך, פותחו מבני נתונים השומרים על הנתונים במצב ממוין.
מבנה נתונים בסיסי המאפשר זאת הוא עץ חיפוש, שהוא מבנה נתונים ממוין המאפשר הכנסה, הוצאה וחיפוש.
עצי חיפוש משוכללים יותר כמו עץ אדום שחור ועץ AVL מאפשרים לבצע את הפעולות הללו במהירות (דהיינו בסיבוכיות נמוכה).
לחיפוש בגרפים (כמו עצי החיפוש שהוזכרו לעיל) משמשים אלגוריתם חיפוש לעומק ואלגוריתם חיפוש לרוחב.
בחיפוש כזה מוסכם לפני תחילתו שבהסתברות ידועה, החיפוש לא יחשוף נתון שכן מצוי במערכת, ואף מפתח לנתון שכן מצוי.
אלגוריתם גאוס-לז'נדר הוא אלגוריתם מהיר לחישוב קירובים של הקבוע המתמטי , המבוסס על הממוצע האריתמטי-גאומטרי של שני מספרים.
מספר הספרות המדויקות בהערכת הקבוע מוכפל בכל צעד, ובעזרת מחשב מודרני האלגוריתם מאפשר לחשב מיליארדי ספרות, ואף יותר.
אלגוריתם זה, ודומים לו, נחקרו על ידי קרל פרידריך גאוס ואדריאן-מארי לז'נדר בראשית המאה ה-19. האלגוריתם איטרטיבי מטבעו, ומבוסס על החלפה חוזרת של שני מספרים בממוצעים האריתמטי והגאומטרי שלהם.
הגרסה השנייה המוצגת כאן ידועה כ"אלגוריתם בראנט-סלאמין", בשל העובדה שהאלגוריתם נתגלה מחדש, באופן בלתי תלוי, על ידי מדען המחשבים ריצ'רד בראנט והמתמטיקאי יוג'ין סלאמין ב-1975.
ב-1800, חקירותיו של גאוס על הממוצע האריתמטי גאומטרי הובילו אותו לגלות את הנוסחה הנפלאה:
כאשר ו- הוא הממוצע האריתמטי-גאומטרי של .
אתחול האלגוריתם מתבצע על ידי מתן הערכים ההתחלתיים
השלב האיטרטיבי, בו חוזרים ומעדכנים את ערכי הפרמטרים בנוסחאות הבאות עד השגת מספר הספרות הרצוי:
(עד שההפרש בין קטן מערך רצוי)
בתום השלב האיטרטיבי מחושב הקירוב ל- בעזרת הפרמטרים לעיל, על ידי הנוסחה:
ארבע ההצבות הראשונות בנוסחה נותנות:
אלגוריתם גאוס-ניוטון הוא אלגוריתם לפתרון בעיות ריבועים פחותים לא ליניאריות.
האלגוריתם, המיוחס לקרל פרידריך גאוס, הוא למעשה תיקון של שיטת ניוטון למציאת שורשים של פונקציה ממשית, ללא שימוש בנגזרות ממעלה שנייה.
בהינתן m פונקציות כאשר , וכן ,
בעיית האופטימיזציה היא למצוא וקטור כך שהסכום הוא מינימלי, כלומר לכל וקטור מתקיים .
אלגוריתם גאוס-ניוטון הוא תהליך איטרטיבי.
כלומר, יש לספק ערך התחלתי ל-, שנקרא לו .
ערכים עוקבים של ניתנים אחר כך על ידי חזרה על היחס:
ו- מסמן את היעקוביאן של ב-.
את המטריצה ההופכית אין צורך לחשב במפורש.
במקומה נוכל לסמן את מתקיים
על ידי הכפלה של שני הצדדים ב
וקיבלנו אם כך מערכת משוואות ליניאריות למציאת .
אלגוריתם גרצל הוא אלגוריתם עיבוד אותות ספרתי (DSP) המזהה מרכיבי תדר באות.
האלגוריתם פורסם על ידי ד"ר ג'רלד גרצל ב-1958.
בניגוד לאלגוריתם FFT שמחשב רכיבי תדר בנקודות שמחולקות באופן שווה לאורך רוחב הסרט של האות, אלגוריתם גורצל מאפשר התמקדות בתדר ייחודי, ודורש עבור כל תדר מבוקש כ-6N חישובים.
המדד להעדפת אלגוריתם הFFT יהיה כאשר M הוא מספר פסי התדר הנדרשים.
במקרה שלנו M שווה לכל היותר 8 ועבור 777 דגימות האלגוריתם של גרצל כבר יותר יעיל.
כמו כן FFT מחייב כמות דגימות שהיא בדיוק חזקה שלמה של 2 ואחסון של טבלאות ערכים של פונקציות הקוסינוס והסינוס הדרושות לחישוב, ובכך המימוש שלו מורכב יותר ודורש יותר שורות קוד.
אחד השימושים החשובים של אלגוריתם גרצל הוא זיהוי טונים בטלפוניה (DTMF), על ידי איתור מרכיבי התדר שמכיל האות.
צורת העבודה של האלגוריתם היא חישוב נוסחת נסיגה התלויה בערכי דגימות קודמות.
כאשר, ערכי הדגימות (s(-2) ,s(-1 שווים לאפס.
עבור ערך ידוע של ω מדובר בחיבור אחד חיסור אחד והכפלה אחת.
האלגוריתם מממש מסנן IIR מסדר שני כאשר במוצא אמורים להתקבל ערכי ה DFT של האות.
התמרת Z של המשוואה תהיה:
אם נעביר את התוצאה במסנן הבא:
התוצאה לאחר שני המסננים תהיה:
או בעצם DFT מוכפל בגודל קבוע.
כדי לקבל רק את ה DFT במוצא נגדיר:
כאשר (y(N-1 הוא מוצא המסנן עבור N דגימות בשימוש עם הגדרת המסנן השני.
מכיוון ש ω הוא התדר הדיגיטלי ביחידות של מחזורים הנדרשים למטרת דגימה אחת,
אזי ωN הוא גודל שלם, k.
נובע מכך שניתן לפשט את המשוואה ל:
אם נחשב את הערך המוחלט של המוצא נקבל:
אלגוריתם חסר נעילות הוא אלגוריתם המיועד לביצוע בידי מספר תהליכונים (Threads) באופן מקבילי ואינו משתמש לשם כך בנעילות חוסמות.
פעולות אטומיות (על מידע קטן ממדים) דרושות עבור כל האלגוריתמים חסרי הנעילות ולהן תפקיד חשוב באיפשור פעולות שינוי מידע אמינות בין תהליכונים.
לא פעם לאלגוריתם חסר נעילות יש מגבלות על כמות התהליכונים ותפקידם (החלק באלגוריתם אותו יכול לבצע כל תהליכון ותהליכון).
אלגוריתם לטיפול בתור יכול לדוגמה להתאים רק לשני תהליכונים, האחד מכניס מידע אל התור והשני שולף.
דוגמה נוספת היא שתהליכונים רבים יכולים לקרוא מידע ממבנה נתונים ואילו רק תהליכון אחד יכול לשנותו.
קשה להפריד את האלגוריתמים חסרי הנעילות מהיכולות החומרתיות הזמינות.
הפעולות האטומיות הזמינות במחשבים מודרניים הן שמכתיבות את הפעולות הזמינות לכותבי האלגוריתמים חסרי הנעילות.
הפעולה הבסיסית ביותר שדרושה תמיד היא כתיבה אטומית.
כלומר לאפשר לכתוב ליחידת זיכרון (קטנה - בדרך כלל מילת מעבד) כך שכל מי שקורא באותו זמן את יחידת הזיכרון הזו יראה את הזיכרון כפי שהוא היה לפני הכתיבה או כפי שהוא אחרי הכתיבה ולא בכל מצב ביניים.
בדרך כלל פעולת הכתיבה ליחידת זיכרון בגודל מילת מעבד היא כזאת מבלי צורך בפעולה מיוחדת.
פעולה אטומית חשובה באלגוריתמים חסרי נעילה היא פעולת "השווה והחלף" (בלעז Compare and Swap).
בפעולה זו ערך ביחידת זיכרון מסוימת נבדק ובמידה והוא שווה לערך מסוים, הוא מוחלף בערך נתון.
הפעולה מחזירה אינדיקציה אם הצליחה או נכשלה.
משמעות האטומיות היא בכך שלא יכולים יותר מתהליכון (מעבד) אחד לקרוא את אותו הערך ולהצליח בפעולה, אם יותר מתהליכון אחד קראו את אותו הערך, רק אחד מהם יצליח בפעולת ההחלפה, השאר יכשלו.
כך ניתן למעשה להיות בטוחים, במידה והפעולה הצליחה, שאף תהליכון אחר לא שינה את יחידת הזיכרון בין הקריאה (ההשוואה) להחלפה.
השווה והחלף היא פעולה שמספק כמעט כל מחשב מודרני (לעיתים בעזרת שתי תתי פעולות: "טען"-LD ו"אחסן"-ST אשר ניתן להשיג בעזרתן את אותה התוצאה).
כדאי להזכיר בהקשר של אלגוריתמים אלו את מחסומי הזיכרון (בלעז Memory Barriers) שמבלי להבינם לא ניתן ליישם אלגוריתם חסר נעילות.
במערכות מחשב מודרניות יש מספר מעבדים ומעבר לזיכרון הרגיל (RAM) זיכרון מטמון לכל מעבד ומערכת ניהול זיכרון מורכבת אשר מעבירה מידע מהזיכרון הראשי אל זיכרון המטמון וחזרה .
יש גם מעבדים בעלי מספר מרכיבים שכל אחד עושה פעולות מסוג שונה וייתכן שפעולה שכתובה בקוד התוכנית (קוד המכונה שנמצא בזיכרון) לפני פעולה אחרת תתבצע בפועל אחרי או במקביל לפעולה אחרת.
במקרים אלו המעבד ידאג שמבחינת התהליכון הרץ התוצאה תהיה אותה התוצאה אך לא ידאג לתיאום עם תהליכונים אחרים.
במידה ובתיאום בין תהליכונים, סומכים על הסדר הזה יכולה להיווצר בעיה.
כדי למנוע בעיות שכאלו מספקים מערכות מחשב מודרניות פקודות מעבד ייעודיות אשר מאפשרות שליטה פרטנית יותר על מערכת ניהול הזיכרון.
לכל ארכיטקטורת חומרה יש פקודות שונות המתאימות לפעולות שמערכת ניהול הזיכרון בחומרה זו מסוגלת לבצע.
בעזרת פקודות אלו ניתן להשיג את שלושת התחבירים המפורטים להלן.
בעזרת שימוש במחסום זיכרון עם תחביר זה, תוכנית יכולה להצהיר בפני המערכת מחשוב שפעולת שינוי מסוימת על זיכרון נעשית בעבור שמעבדים אחרים יראו אותה ויסיקו ממנה שעבודה מסוימת של המעבד הנוכחי על הזיכרון הסתיימה.
על מערכת המחשוב להראות למעבדים האחרים את כל השינויים האחרים שנעשו על הזיכרון על ידי מעבד זה לפני שהם רואים את השינוי האחרון הזה.
בעזרת שימוש במחסום זיכרון עם תחביר זה, תוכנית יכולה להצהיר בפני המערכת מחשוב שפעולת שינוי מסוימת על זיכרון נעשית בעבור שמעבדים אחרים יראו אותה ויסיקו ממנה שעבודה מסוימת של המעבד הנוכחי על הזיכרון מתחילה.
על מערכת המחשוב להראות למעבדים האחרים את השינוי הזה לפני שהיא מראה להם שינויים מאוחרים יותר שמבצע מעבד זה.
מחסום זיכרון מלא (בלעז Full Memory Barrier)
מחסום זיכרון עם תחביר זה מספק את שתי המשמעויות של תחביר שחרור ותחביר ניכוס ביחד.
כל אלגוריתם חסר נעילות הוא רעיון חדש בפני עצמו כיצד לבצע פעולה מסוימת ממספר תהליכונים, בצורה אמינה וללא נעילות, עם זאת יש מספר שיטות פעולה שניתן לראותן ביותר מאלגוריתם אחד.
חזרה על פעולה עד שהיא מצליחה (כאשר מרב הסיכויים הם שלא יידרשו חזרות רבות).
סימון צורך בפעולה ולאפשר לתהליכון אחד בלבד לעשות את הפעולה הנרחבת יותר.
התחלת פעולה בתהליכון אחד וזיהוי המצב בתהליכון אחר והמשך הפעולה שם.
יש מספר אלגוריתמים חסרי נעילות שיכולים לשאת את השם הזה, האלגוריתם המתואר פה הוא הפשוט ביותר מביניהם.
כפי ששמו רומז הוא מוגבל לתהליכון אחד שקורא ותהליכון אחד שכותב.
מצביע לאובייקט הבא (כתיבה למצביע זה צריכה להיות אטומית)
קביעת 'מצביע לחדש' שיצביע לאובייקט הזה.
קביעת 'מצביע לישן' שיצביע גם הוא לאובייקט הזה.
יוצר אובייקט חדש עם כל המידע הדרוש (קורא מ'מצביע לחדש' את האובייקט הנוכחי ועושה את השינויים הדרושים באובייקט חדש).
גורם לאובייקט המוצבע כעת על ידי 'מצביע לחדש' שה-'מצביע לאובייקט הבא' שלו יצביע לאובייקט החדש.
מחליף את ה'מצביע לחדש' להצביע גם הוא על האובייקט החדש.
במידה ובאובייקט המוצבע על ידי 'מצביע לישן', ה-'מצביע לאובייקט הבא' אכן מצביע לאובייקט נוסף:
קרא את ה-'מצביע לאובייקט הבא' ל-A (משתנה פרטי לתהליכון)
הרוס את האובייקט המוצבע על ידי 'מצביע לישן'.
קבע את 'מצביע לישן' ל-A.
במידה ובאובייקט המוצבע על ידי 'מצביע לישן', ה-'מצביע לאובייקט הבא' אינו מצביע לאובייקט נוסף, צא מן הלולאה.
קרא מהאובייקט המוצבע על ידי 'מצביע לישן' והשתמש במידע.
באלגוריתם זה אפשר לראות דוגמה לכך שתהליכון אחד מתחיל פעולה ואילו האחר משלים אותה.
התהליכון הכותב מתחיל פעולה של החלפת האובייקט אך משאיר את המחיקה של האובייקט הישן לתהליכון הקורא.
אלגוריתם דויטש-ג'וזה הוא אלגוריתם קוונטי להבדלה בין פונקציה קבועה לבין פונקציה מאוזנת.
האלגוריתם מהווה דוגמה ליתרון המתקבל משימוש של מחשב קוונטי על פני מחשב קלאסי.
האלגוריתם פורסם על ידי ריצ'רד ג'וזה ודייוויד דויטש בשנת 1992, והניח את היסודות לפיתוח אלגוריתם גרובר ואלגוריתם הפיקטור של פיטר שור.
תהי פונקציה המקבלת קלט באורך ביטים, ופולטת פלט באורך ביט יחיד, כך שמתקיים אחד מהשניים:
היא פונקציה קבועה, כלומר, לכל מתקיים , או שלכל מתקיים ; או
היא פונקציה מאוזנת, כלומר למחצית מה--ים מתקיים ולשאר
אלגוריתם דויטש-ג'וזה מקבל כקלט את הפונקציה , ומחזיר כפלט האם היא קבועה או מאוזנת.
האלגוריתם עושה זאת על ידי הפעלה של הפונקציה פעם יחידה בלבד.
באופן קלאסי, זיהוי האם פונקציה קבועה או מאוזנת מצריך לכל הפחות הפעלות של פונקציית הקלט עם ערכי שונים.
אם בכלל הפעלות הפונקציה מתקבל אותו ערך אזי היא קבועה, ואם בשתיים מההפעלות מתקבלים ערכים שונים, אזי הפונקציה היא מאוזנת.
לא קיים פתרון דטרמיניסטי המפעיל את הפונקציה פחות מ פעמים, שכן תמיד ייתכן מצב בו הערכים שעליהם נשאלה הפונקציה מקיימים ועדיין שאר הערכים מקיימים , כלומר הפונקציה מאוזנת.
מצד שני, קיימים פתרונות הסתברותיים לבעיה זו.
לדוגמה, ניתן להגריל כמות של קלטים שונים ולבדוק את ערך הפונקציה עבור קלטים אלו בלבד.
במידה ומתקיים קיימת הסתברות שהאלגוריתם יטעה, אך הסתברות זו נחשבת זניחה מכיוון שהיא קטנה מ-.
האלגוריתם הקוונטי מתואר בתרשים משמאל.
המעגל מקבל כקלט אוגר קוונטי המכיל קיוביטים.
ניתן להסתכל על הקלט כשני אוגרים המאותחלים ל .
על כל אחת מהכניסות מופעל שער אדמר, ומצבם המשותף ניתן כעת לביטוי בתור .
כעת מופעלת הפונקציה הקוונטית על האוגר, כאשר הכניסות הראשונות הן הקלט, ואילו הכניסה האחרונה משמשת עבור הפלט.
לאחר הפעלת הפונקציה מצב האוגר הוא .
העיקרון עליו מבוסס האלגוריתם הוא הבא:
אם קיוביט הפלט ניתן לרישום בתור
ואילו עבור אותם -ים עבורם נקבל
כלומר הסימן של האוגר משתנה בהתאם לערך הפונקציה , והאוגר ניתן לרישום בתור .
נשים לב שהקיוביט האחרון אינו תלוי בערך של הפונקציה, ערכו תמיד וניתן להתעלם ממנו בהמשך.
כעת נפעיל בשנית שער אדמר על האוגר ונבדוק את שני המצבים האפשריים:
אם הפונקציה הייתה קבועה לערך 0, אזי האוגר היה מהצורה .
לאחר הפעלת השער יהיה ערכו ועל כן מדידתו בבסיס החישוב תתן את התוצאה בהסתברות 1.
אם הפונקציה הייתה מאוזנת, אז חצי מהערכים הם בעלי פאזה חיובית ומחציתם בעלי פאזה שלילית.
נשים לב שלאחר הפעלת שער אדמר על אוגר בעל ערך כלשהו, התוצאה היא סכום משוקלל של כלל הערכים האפשריים כאשר הפאזה של כל אבר נקבעת בהתאם לערך .
כמו כן, נשים לב שהפאזה של האבר בסכום זה היא תמיד חיובית, ללא תלות בערכו של .
לפיכך, כאשר נפעיל את השער אדמר על סופרפוזיציה של אברי הבסיס האפשריים כאשר הפאזה של חציים חיובית ושל חציים שלילית - במוצא השער האבר יתאפס, ומדידה בבסיס החישוב לעולם לא תפיק את התוצאה .
אלגוריתם גרובר הוא אלגוריתם קוונטי לחיפוש במבנה נתונים שאינו ממויין.
האלגוריתם הומצא בשנת 1996 על ידי לוב גרובר.
בעוד אלגוריתם קלאסי הפותר בעיה דומה מצריך גישות אל מערך הנתונים על מנת למצוא ערך מבוקש, האלגוריתם של גרובר עושה זאת ב-, ובכך מהווה דוגמה ליתרון החישובי של מחשב קוונטי על פני מקבילו הקלאסי.
אלגוריתם גרובר הוא אלגוריתם הסתברותי, ולאחר הפעלתו קיימת הסתברות גבוהה מאוד לקבלת התשובה הנכונה (אך הסתברות זו קטנה מ-1).
ניתן להגדיל את הסיכוי לקבלת התשובה הנכונה על ידי הפעלה חוזרת של האלגוריתם מספר פעמים.
עקרון הפעולה של האלגוריתם מבוסס על ביצוע מחזורי של מספר פעולות בסיס כגון הפעלת הפונקציה הקוונטית המתארת את הגישה אל מבנה הנתונים, הפעלת שער אדמר ושער הפיכת פאזה.
סט הפעולות ידוע בשם איטרטור גרובר, ויש להפעילו פעמים על מנת לקבל הסתברות גבוהה ביותר לסיום האלגוריתם עם התשובה הנכונה.
כאמור, אלגוריתם גרובר נועד לחיפוש במבנה נתונים לא-ממוין.
לייתר דיוק, הקלט של האלגוריתם היא פונקציית אוב כך שהפעלת הפונקציה על הערך המבוקש מחזירה 1, ועל כל שאר הערכים מחזירה 0. נניח, למשל, כי אנו מחפשים אינדקס מסוים מתוך המערך .
נסמן את האינדקס המבוקש (שערכו אינו ידוע לנו) ב .
באופן קלאסי, הסתברותי, על מנת למצוא את האינדקס המבוקש, "ננחש" אינדקס כלשהו ונפעיל את עד לניחוש מוצלח עבורו הפונקציה החזירה את הערך 1. בממוצע, נצטרך להפעיל את הפונקציה פעמים.
בעזרת הפונקציה ובעזרת שער אדמר נבנה מעגל המממש את האופרטור עבורו כלומר ערך הפונקציה משוקף בפאזה של האוגר.
אתחל אוגר קוונטי באורך ואתחל אותו לסופרפוזיציה שווה של כל אברי בסיס החישוב (במילים אחרות, אתחל את האוגר למצב והפעל עליו את שער אדמר).
בצע את סט הפעולות הבאות פעמים
הפעל שער המבצע הפיכת פאזה לאיבר בלבד
[צעד זה חסר משמעות מבחינה פיזיקלית, אך הוא נוח לשם האנליזה של האלגוריתם.]
לאחר הפעלת האיטרטור במספר הפעמים הנדרש, יש לבצע מדידה בבסיס החישוב.
תוצאת המדידה יהיו האינדקס המבוקש בהסתברות .
נגדיר את הבסיס עבור המרחב אשר בו אבר בסיס אחד הוא , האינדקס אותו אנחנו מחפשים, ואבר שני הוא סופרפוזיציה שווה של כל שאר האינדקסים, .
שני איברים אלו אורתוגונליים ולכן ניתן להרחיב אותם לבסיס של המרחב, למשל על ידי שימוש בתהליך גרם-שמידט.
פעולת איטרטור גרובר, Q, היא למעשה סיבוב ההטלה של המצב הקוונטי על המישור הנפרש על ידי בזווית המקיימת .
באתחול האלגוריתם יוצרים אוגר שהוא סופרפוזיצה שווה של כלל האיברים, וניתן להציג אותו בבסיס החדש כ
בכל פעם שמפעילים את Q, מתבצע סיבוב בזווית , כך שלאחר ביצוע t הפעלות מתקבל המצב
אם נבצע מדידה לאחר t הפעלות של האלגוריתם, ההסתברות למדוד את האיבר המבוקש נתונה על ידי
הסתברות ההצלחה תלויה במספר ההפעלות של האיטרטור, ותהיה קרובה ל-1 ככל ש יתקרב ל-.
מספר ההפעלות המינימלי, , עבורו הסתברות ההצלחה היא גבוהה מקיים , כלומר .
עבור N גדול ושימוש בזהויות טריגונומטריות ובקרובים טריגונומטריים ניתן לבצע את הקרובים , ומתקבל
יש לשים לב כי הפעלת האיטרטור במספר פעמים גבוה יותר עלול לפגום בהסתברות ההצלחה.
אלגוריתם כהן-סאת'רלנד (Cohen–Sutherland) הוא אלגוריתם בגרפיקה ממוחשבת המשמש ל-Clipping של קווים בשניים או שלושה ממדים.
האלגוריתם מחלק את המרחב הדו־ממדי ל-9 חלקים, וב-3 ממדים מחלק ל-27 חלקים ואז קובע באופן יעיל את הקווים והחלקים של הקווים שנמצאים בחלק המרכזי (ה-viewport).
האלגוריתם פותח ב-1967 על ידי דני כהן ואיוואן סאת'רלנד.
אתחול ושימוש ב־outcodes (בדו מימד) :
ראשית מבצעים חלוקה של 9 אזורים ומקצים זיכרון של 4 ביטים לכל אזור:
האלגוריתם קובע אילו קווים נמצאים ב-viewport על פי ההבחנה הבאה:
עבור שני קצוות הקו מתקבל הערך 0000 אזי שניהם מצויים ב-viewport לכן: כל הקו עובר ב-viewport, הקו שייך.
עבור שני קצוות הקו יש ביט משותף דולק (לדוגמה: 1000 ו-1010) אזי שני קצוות הקו נמצאים על אותו אזור שאינו ב-viewport לכן: אף חלק מהקו לא עובר ב-viewport, הקו לא שייך.
שני הקצוות באזורים שונים (לדוגמה: 0101 ו-1010) אזי אולי חלק מהקו עובר ב-viewport : להבדיל מהמקרים הקודמים שהם טריוואליים.
כאן בוחר האלגוריתם את קצה הקו שנמצא באזור שמחוץ ל-viewport (יש לפחות אחד כזה), ומחשב את נקודת החיתוך של הקו מהנקודה החיצונית עם גבולות ה־viewport (באמצעות משוואה פרמטרית של קו) והנקודה החדשה (החיתוך) מחליפה את הנקודה החיצונית ל-viewport.
האלגוריתם ממשיך עד להגעה לאחד המקרים הטריוויאלים לעיל.
אלגוריתם זה מוגבל לביצוע clipping במלבנים בלבד.
אלגוריתם כללי יותר הפועל על פוליגונים קמורים הוא אלגוריתם Cyrus–Beck.
אלגוריתם חיפוש *A הוא אלגוריתם חיפוש מונחה היוריסטיקה על צומתי גרף ממושקל, תוך חיפוש צומת המקיים תכונה מסוימת (צומת היעד) במרחק הקצר ביותר מן המקור.
האלגוריתם תואר לראשונה ב-1968 על ידי פיטר הרט, נילס נילסון וברטהם רפאל ממרכז המחקר של אוניברסיטת סטנפורד.
אלגוריתם *A נפוץ ביותר ונעשה בו שימוש נרחב לבעיות הדורשות מציאת מסלולים בגרפים.
A הוא שלם, כלומר הרצת אלגוריתם החיפוש מבטיחה מציאת מסלול בין צומת המקור לצומת היעד אם קיים מסלול כזה, בתנאי שמרחב החיפוש סופי.
במקרה של מרחב חיפוש אין־סופי, *A שלם בתנאי שמחיר הקשתות חסום מלמטה על ידי קבוע חיובי ושההיוריסטיקה אי־שלילית.
האלגוריתם הוא מסוג אלגוריתם חיפוש לרוחב ומוצא את המסלול הזול ביותר מצומת המקור לאחד מצומתי היעד.
כאשר *A עובר על הגרף הוא מנסה לפתח בכל פעם את המסלול שנראה הזול ביותר תוך כדי שימוש בתור עדיפויות ממוין.
האלגוריתם משתמש בפונקציית עלות המשלבת היוריסטיקה () בצירוף מידע ידוע () כדי לבחור איזה צומת לפתח.
פונקציית העלות היא הסכום של שתי הפונקציות:
שהיא המרחק הידוע בין צומת ההתחלה לצומת הנוכחי x.
שהיא הערכה למרחק בין x לבין צומת היעד.
כדי שהאלגוריתם יחזיר פתרון אופטימלי, פונקציית ההיוריסטיקה, , צריכה להיות אדמיסיבלית (קבילה), כלומר לא יותר יקרה מהמרחק האמיתי לצומת היעד.
בניתוב היא יכולה להיות מרחק אווירי, מכיוון שהוא מהווה את המרחק המינימלי בין כל שני צמתים.
בנוסף אם ההיוריסטיקה מונוטונית (קונסיסטנטית), כלומר מקיימת את התנאי לכל קשת (x,y) בגרף (d מסמן את אורך הקשת), האלגוריתם ירוץ מהר יותר מכיוון שאין צורך לבדוק בשנית צמתים בהם האלגוריתם כבר עבר.
אפשר להסתכל על האלגוריתם כהרחבה של אלגוריתם דייקסטרה עם היוריסטיקה (בדייקסטרה הפונקציה ההיוריסטית תהיה תמיד שווה ל-0).
הערה: מימוש האלגוריתם מניח שפונקציית ההיוריסטיקה היא מונוטונית, ולכן מדלג על צמתים שנמצאים ב-.
אם ההיוריסטיקה אינה מונוטונית, יש למחוק את בדיקה זו, מאחר שערך ה-g שניתן לצומת שפותח בשלב קודם יכול להיות גדול יותר מערך ה-g האמיתי של הצומת, ולכן יש לפתח אותו מחדש (להחזיר את הצומת ל-).
סיבוכיות הזמן של *A תלויה בהיורסטיקה, במקרה הגרוע ביותר, מספר הצמתים שיפותחו יהיה מעריכי ביחס לאורך הפתרון (המסלול הקצר ביותר).
הסיבוכיות תהיה פולינומית אם מתקיימים התנאים הבאים: מרחב המצבים הוא עץ, קיים מצב מטרה יחיד והפונקציה ההיוריסטית h מקיימת:
כאשר היא ההירוסטיקה האופטימלית, כלומר העלות המדויקת בין x למטרה.
אלגוריתם אוקלידס הוא אלגוריתם אריתמטי המאפשר למצוא, בהינתן שני מספרים טבעיים, את המחלק המשותף המקסימלי שלהם.
התיעוד הקדום ביותר של האלגוריתם הוא בספר יסודות של אוקלידס, בסביבות שנת 300 לפני הספירה.
זהו אחד האלגוריתמים העתיקים ביותר הנמצאים בשימוש היום.
האלגוריתם הוא אחד מהכלים המרכזיים בתורת המספרים ויש לו שימושים רבים, לדוגמה בצופן RSA.
המחלק המשותף המקסימלי של מספרים, המסומן , היא פעולה המקבלת שני מספרים טבעיים, ומחזירה את המספר הגדול ביותר שמחלק את שניהם.
לדוגמה, המחלק המשותף המקסימלי של 36 ו-24 הוא 12, מאחר שהמספר מחלק את שניהם ואין מספר גדול יותר בעל תכונה זאת.
תמיד יש מספר כזה כיוון שהמספר אחד מחלק כל מספר.
ואכן המחלק המשותף המקסימלי של שני מספרים ראשוניים (כלומר זרים) הוא אחד.
דרך אפשרית למציאת המחלק המשותף המקסימלי היא פירוק שני המספרים לגורמים ראשוניים, והכפלת הגורמים המשותפים.
בדוגמה הנ"ל, הפירוק לראשוניים של 36 הוא 2×2×3×3 ושל 24 הוא 2×2×2×3, הגורמים המשותפים הם 2, 2 ו-3, ומכפלתם היא 12. דרך זו היא אינטואיטיבית, אך אינה שימושית עבור מספרים גדולים, כי פירוק לגורמים הוא פעולה מורכבת ואין שיטה פשוטה לחישובו.
אלגוריתם אוקלידס מאפשר את מציאת המחלק המשותף המקסימלי ללא פירוק לגורמים, בדרך פשוטה יחסית.
למעשה, שיטות מתקדמות לפירוק לגורמים (לדוגמה אלגוריתם נפת שדה מספרים) משתמשות באלגוריתם אוקלידס.
האלגוריתם מבוסס על העיקרון הבא: הוספת כפולה של אחד המספרים למספר השני, אינה משנה את המחלק המשותף הגדול ביותר.
בניסוח מתמטי, אם מספרים טבעיים אז מתקיים: .
בתכונה זו ניתן להשתמש בכיוון ההפוך – במקום להגדיל את אחד המספרים, מקטינים אותו: לכל זוג מספרים , ניתן לחשב את השארית מחלוקת ב-, כאשר .
מכאן מתקבל השוויון , שבו הוחלף המספר הגדול במספר קטן יותר משני המספרים המקוריים, בלי לשנות את המחלק המשותף.
אפשר להמשיך בתהליך שוב ושוב עם מספרים קטנים יותר ויותר, עד שמגיעים לזוג שאחד המספרים בו הוא 0; , ולפיכך נמצא המחלק המשותף הגדול ביותר.
באופן רקורסיבי ניתן להגדיר את האלגוריתם בצורה הבאה: לחישוב כאשר , אם b הוא 0, התוצאה היא a.
אחרת, חלק את ב- ומצא את השארית ; התוצאה היא (שאותה יש לחשב בעזרת אותו אלגוריתם עצמו).
באופן כללי, ניתן להשתמש באלגוריתם בכל חוג אוקלידי.
כך לדוגמה ניתן להשתמש באלגוריתם כדי למצוא את המחלק המשותף המקסימלי של שני פולינומים מעל שדה.
ראשית יש להוכיח את השוויון .
נניח כי מחלק את .
אז קיימים טבעיים עבורם .
כלומר מחלק את , ומכאן שהוא מחלק משותף של .
קיבלנו שמספר הוא מחלק משותף של אם ורק אם הוא מחלק משותף של .
לכן קבוצת המחלקים המשותפים של הזוגות זהה, ובפרט האיבר המקסימלי שלהם זהה.
נחשב את המחלק המשותף המקסימלי של 1071 ו-462, או :
462 נכנס ב-1071 פעמיים, והשארית היא 147. לפיכך עלינו למצוא את .
147 נכנס ב-462 שלוש פעמים, והשארית היא 21. לפיכך עלינו למצוא את .
21 נכנס ב-147 7 פעמים בדיוק, כלומר בשארית 0. לפיכך עלינו למצוא את .
מאחר שהמספר הקטן הוא 0, התשובה היא 21, וזו גם התשובה לשאלה המקורית.
לפתרון ניתן לתת משמעות גאומטרית כמודגם באיור: 21 הוא אורך הצלע של האריח הריבועי הגדול ביותר שמאפשר לרצף במדויק את המלבן שצלעותיו הן 1071 ו-462.
דוגמה למימוש האלגוריתם בצורה רקורסיבית בקוד (פייתון)
מבחינת סיבוכיות חישובית, האלגוריתם יעיל.
מספר הפעולות הנדרשות לביצוע אינו עולה על ( הוא יחס הזהב).
על כן הסיבוכיות שלו היא לוגריתמית.
ניתן להגיד שמספר הפעולות אינו עולה על פי-5 ממספר הספרות.
המקרה הגרוע ביותר (worst case) הוא כאשר מדובר בשני מספרי פיבונאצ'י עוקבים; זאת, כיוון שככל שהמנה המתקבלת בפעולות החילוק קטנה יותר, המספר קָטֵן פחות, ויש צורך ביותר פעולות.
במספרי פיבונאצ'י כל המנות הן 1, ועל כן התהליך הוא הארוך ביותר.
תכונה זו נתגלתה על ידי גבריאל לאמה.
אחת התכונות החשובות של המחלק המשותף המקסימלי היא שניתן להציג אותו בצורה הבאה: , כאשר שלמים.
ניתן לחשב את באמצעות אלגוריתם אוקלידס בעזרת התכונה שאם כל פעם השתמשנו ב-, אז .
לפיכך, אם אנחנו יודעים בשלב מסוים איך להציג את שני המספרים בצורה (ההתחלה פשוטה: או להפך) ניתן להציב בביטוי ולהתקדם בשלבי האלגוריתם עד להצגה הרצויה.
לדוגמה, נמצא בדוגמה להלן את ההצגה של 10 כ-:
האלגוריתם המורחב שימושי בחשבון מודולרי, למשל לצורך מציאת הופכי כפלי מודולרי, עבור שני מספרים זרים.
מידת סיבוכיות האלגוריתם המורחב היא מאותו סדר גודל של הרגיל, מאחר שאין צורך לבצע איטרציות נוספות אלא רק חישובים בסיסיים.
אלגוריתם הבנקאי (Banker algorithm) הוא מנגנון להקצאת משאבים והימנעות ממצב קיפאון שפותח על ידי אדסחר דייקסטרה.
האלגוריתם מבצע זאת על ידי דימוי ההקצאה של הכמות המקסימלית של כל משאבי המערכת שסוכמו מראש ואז ביצוע בדיקת "מצב-בטוח", לשלילת אפשרות של מצב קיפאון עבור כל שאר התהליכונים בסיכון, לפני שמבוצעת החלטה אם להקצות את המשאבים.
האלגוריתם פותח בתהליך התכנון של מערכת ההפעלה THE ושמו נקבע בגלל הדמיון לאילוצים הקיימים על הבנקאי בחישוב נזילות כספים.
1. המערכת לא נמצאת במצב קיפאון (deadlock).
2. המתזמן ידאג שתהליך ירוץ עד שיושלם.
בהתאם לכך, האלגוריתם יכול להיות באחד מתוך 3 מצבים:
1. safe - שני התנאים מתקיימים.
2. unsafe – רק התנאי הראשון מתקיים ומצב קיפאון הוא אופציונלי.
אלגוריתם הבנקאי מופעל על ידי מערכת ההפעלה בזמן שתהליך מבקש הקצאה.
האלגוריתם נמנע מקיפאון על ידי שלילה או דחייה של הבקשה, אם הוא מזהה שהבקשה יכולה להעביר את המערכת למצב לא בטוח (שייתכן ויתרחש קיפאון).
כאשר תהליך חדש נכנס למערכת, הוא חייב להצהיר מראש מהו המספר המקסימלי שהוא יצטרך להשתמש מכל משאב בו זמנית.
כמובן שלא ניתן לחרוג מהמספר הכולל של המשאבים שקיים במערכת.
ברגע שתהליך מקבל את כל המשאבים שהוא ביקש, הוא מחויב להחזיר אותם תוך זמן מוגבל.
כדי שאלגוריתם הבנקאי יעבוד, הוא צריך להתייחס לשלושה דברים:
עבור כל תהליך: כמה התהליך יוכל לדרוש מכל משאב באופן מקסימלי [CLAIM].
עבור כל תהליך: כמה התהליך מחזיק מכל משאב ברגע זה [ALLOCATED].
כמה מכל משאב זמין כרגע במערכת [AVAILABLE].
משאבים יוקצו עבור תהליך רק אם הוא יעמוד בתנאים הבאים:
דרישה ≤ מקס', אחרת סמן שגיאת - תהליך שעבר את המקסימום שהוא הצהיר.
דרישה ≤ זמין, אחרת התהליך יחכה עד שהמשאבים יהיו זמינים.
חלק מהמשאבים המבוקשים במערכות אמתיות הם זיכרון, סמפורים וממשק גישה.
אלגוריתם הבנקאי קיבל את שמו מכך שהאלגוריתם יכול לשמש במערכת בנקאית, כדי לוודא שלבנק אין חוסר במשאבים, כיוון שהבנק אף פעם לא יכול להקצות את הכסף שלו בדרך כזו שהוא לא יוכל לספק את הצרכים של כל הלקוחות.
על ידי שימוש באלגוריתם הבנקאי, הבנק מוודא שכאשר לקוח מבקש כסף, הוא עדיין יישאר במצב-בטוח.
אם הבקשה של הלקוח לא גורמת לבנק לצאת ממצב-בטוח, הכסף יוקצה ללקוח, אחרת הלקוח חייב לחכות עד שלקוח אחר יפקיד כסף.
ניתן ליישם את אלגוריתם הבנקאי על ידי שימוש בכמה מבני נתונים בסיסיים:
בהינתן n תהליכים במערכת ו-m סוגי משאבים, נשתמש במבני הנתונים הבאים:
Available: וקטור באורך m שמייצג את מספר המשאבים הזמינים מכל סוג.
אם Available[j] = k, אז קיימים k מופעים של המשאב Rj במצב זמין.
Max: מטריצה בגודל n×m שמגדירה את דרישת המשאבים המקסימלית של כל תהליך.
אם Max[i,j] = k, אז Pi לא יוכל לדרוש יותר מאשר k מהמשאב מסוג Rj.
Allocation: מטריצה בגודל n×m שמייצגת את מספר המשאבים מכל סוג שכרגע מוקצים לכל תהליך.
אם Allocation[i,j] = k, אז עבור התהליך Pi מוקצים כרגע k משאבים מסוג Rj.
Need: מטריצה בגודל n×m שמייצגת את מספר המשאבים מכל סוג שנזקקים לכל תהליך.
אם Need[i,j] = k, אז Pi יזדקק לעוד k משאבים מסוג Rj כדי להשלים את המשימה שלו.
בהנחה שהמערכת מבחינה בין ארבעה סוגים של משאבים (C, B, A וD), ניתן דוגמה להקצאה של המשאבים.
יש לשים לב שהדוגמה מראה את המצב של המערכת לפני שהגיעה דרישה חדשה למשאבים.
בנוסף, סוגי המשאבים ומספרם ניתנו רק לצורך הדוגמה.
במערכת אמיתית למשל, יהיו יותר סוגי משאבים ויותר מכל אחד מהם.
משאבים שמוקצים כרגע עבור כל תהליך(Allocation):
מקסימום מכל משאב עבור כל תהליך(Max):
נצרכים = מוקצים כרגע - מקסימום עבור תהליך
משאבים שעדיין נצרכים עבור כל תהליך(Need):
"מצב בטוח" ו"מצב לא בטוח"
מצב (כמו בדוגמה שלמעלה) נחשב ל"מצב בטוח", אם זה אפשרי עבור כל התהליכים לסיים את ההרצה שלהם.
מאחר שהמערכת לא יודעת מתי תהליך יסתיים או לכמה משאבים הוא יזדקק, המערכת מניחה שכל התהליכים מתכוונים לממש את ההצהרה שלהם לשימוש מקסימלי ושהם יפסיקו לרוץ בצמוד.
זאת הנחה די סבירה מאחר שלא באמת מעניין את המערכת כמה זמן כל תהליך רץ בנפרד (לפחות לא מנקודת המבט של הימנעות מקיפאון).
בנוסף, אם תהליך מסתיים מבלי לממש את ההצהרה למימוש מקסימלי, זה רק יקל על המערכת.
ההחלטה אם תהליך יכנס לתור התהליכים המוכנים (Ready queue), נעשית על ידי הגעה למצב בטוח.
מצב בטוח יוצר בטיחות במערכת מפני קיפאון.
אם נקבל את ההנחות הללו, האלגוריתם קובע אם מצב הוא בטוח בעזרת ניסיון למצוא קבוצה של הקצאות עבור תהליכים שתאפשר עבור כל אחד מהתהליכים להגיע לדרישת המקסימום שלו ואז להסתיים (ולהחזיר את המשאבים למערכת).
כל מצב שלא מצליח למצוא קבוצה כזאת, יחשב למצב לא בטוח.
ניתן לראות שהמצב שנתון בדוגמה הקודמת הוא מצב בטוח על ידי כך שנבחין שכל תהליך יוכל לקבל את דרישת המקסימום שלו ואז להסתיים.
המשאבים הנדרשים כדי למלא את הדרישה המקסימלית של P1 הם: 2 A, 1 B, ו-1 D.
המשאבים שזמינים במערכת לפני שP1 מחזיר משאבים הם: 1 A, 0 B, 1 C, ו-1 D.
המשאבים ש-P2 צריך הם עוד 2 B, ו-1 D ואז הוא יוכל לסיים ולהחזיר את כל המשאבים שלו.
המשאבים ש-P3 צריך הם 1 B ו-4 C ואז הוא יוכל להסתיים.
כיוון שכל התהליכים מסוגלים לסיים לרוץ, המצב הזה הוא "מצב בטוח".
יש לשים לב שבקשות התהליכים וההקצאות נעשו בהדמיה.
האלגוריתם למעשה מדמה אותם כדי לוודא שזהו מצב בטוח, אבל בפועל, שום משאב לא הוקצה ושום תהליך לא הסתיים.
בנוסף יש לשים לב שלא משנה הסדר שבו התהליכים מבקשים את המשאבים - אם קיימת דרך כלשהי לסדר את הבקשות, המצב עדיין יחשב "מצב בטוח".
דוגמה למצב לא בטוח, היא הדוגמה הראשונה בשינוי תהליך P2 כך שיחזיק בהתחלה עוד יחידה מהמשאב B.
כאשר המערכת מקבלת מאחד התהליכים בקשה למשאבים, היא מריצה את אלגוריתם הבנקאי כדי לקבוע האם זהו מצב שבטוח להיענות בו לבקשה.
ברגע שקיימת יכולת הבחנה בין מצב בטוח ומצב לא בטוח, האלגוריתם מסוגל להמשיך בצורה די פשוטה:
אם לא, לא ניתן לבצע את ההקצאה וצריך לדחות אותה או להעביר את התהליך לרשימת המתנה.
האם המצב החדש הוא בטוח?
אם כן, הקצה את המשאבים.
אם לא, דחה את הבקשה או שים אותה בתור ברשימת המתנה.
ההחלטה אם לדחות או להשהות בקשה לא תקינה או שמביאה למצב לא בטוח, היא החלטה נקודתית בכל מערכת הפעלה.
נתחיל באותו מצב שבו הדוגמה הקודמת מתחילה בשינוי תהליך P3 שדורש 2 מהמשאב C.
אין מספיק משאבים זמינים מהמשאב C כדי להיענות לבקשה.
כדוגמה נוספת נוכל להניח שתהליך P3 דורש רק יחידה אחת מהמשאב C.
ישנם מספיק משאבים כדי להיענות לבקשה.
המצב החדש של המערכת יהיה:
משאבים שמוקצים כרגע עבור כל תהליך:
מקסימום מכל משאב עבור כל תהליך:
נבדוק האם המצב החדש שנוצר הוא בטוח.
P1 יכול לקבל את המשאבים: 2 A, 1 B, ו1 D ולהסתיים.
אחר כך P2 יוכל לקבל את המשאבים: 2 B ו1 D ולהסתיים.
לבסוף, P3 יוכל לקבל את המשאבים: 1 B ו3 C ולהסתיים.
לכן המצב החדש הוא מצב בטוח.
מאחר שהמצב החדש הוא מצב בטוח, נקצה את המשאבים.
ולדוגמה אחרונה שתתחיל גם היא באותו מצב למעט העובדה שתהליך P2 דורש רק יחידה אחת של המשאב B.
נניח שP1 P2 וP3, ידרשו מהמשאב B
אין מספיק מהמשאב B כדי לספק את בקשת P1.
אין מספיק מהמשאב B כדי לספק את בקשת P2.
אין מספיק מהמשאב B כדי לספק את בקשת P3.
שום תהליך לא יוכל לקבל מספיק משאבים כדי להסתיים ולכן זהו מצב לא בטוח
כיוון שהמצב לא בטוח, דחה את הבקשה.
כמו אלגוריתמים נוספים, קיימות כמה הגבלות כאשר אלגוריתם הבנקאי ממומש.
בעיקר הצורך שלו לדעת כמה מכל משאב התהליך יוכל לבקש.
ברוב המערכות מידע זה לא זמין, מה שהופך את מימוש אלגוריתם הבנקאי לבלתי אפשרי.
בנוסף, זה לא ממשי להניח שמספר התהליכים הוא יציב כיוון שברוב מערכות ההפעלה מספר התהליכים משתנה.
ויותר מכך, הדרישה שתהליך ישחרר את כל המשאבים שלו בסופו של דבר (מתי שהתהליך יסתיים), מספיקה עבור התקינות של האלגוריתם אבל היא לא מספיקה עבור מערכת ממשית.
המתנה של שעות (או אפילו ימים) כדי שמשאבים ישתחררו ותהליך אחר יוכל להשתמש בהם, הוא בדרך כלל לא אפשרי.
אלגוריתם לויד-מקס הוא אלגוריתם הקרוי על שמו של סטוארט לויד למציאת חלוקה לקבוצות של נקודות במרחב אוקלידי לתאים קמורים.
בדומה לאלגוריתם k-מרכזים, האלגוריתם מוצא נקודות מרכז לכל קבוצה בחלוקה, ואחר כך מחלק את הנקודות בהתאם לקרבתן למרכזים.
בהקשר זה פעולת המיצוע על הנקודות מוחלפת באינטגרל על שטח המרחב, ופעולת מציאת המרכזים הקרובים יוצרת דיאגרמת וורונוי.
את האלגוריתם ניתן להפעיל במרחב אוקלידי, אך אלגוריתמים דומים יכולים להיות מופעלים על מרחבים מממד גבוה יותר או למרחבים לא אוקלידים.
בקוונטיזציה, האלגוריתם מאפשר למזער את השגיאה הריבועית הממוצעת.
בקוונטיזציה אחידה, בהינתן N, מספר הרמות שאליהן אנו מחלקים את הטווח, מספיק לקבוע את רמת הקוונטיזציה הראשונה ואת ההפרש בין הרמות, וכך הקוונטיזציה נקבעת חד-חד-ערכית.
אולם, הדבר מגביל אותנו מבחינת שגיאת הקוונטיזציה שאותה ניתן להשיג.
נרצה להשיג חופש גדול יותר בבחירת מדרגות הקוונטיזציה וערכיהן בשביל לקבל שגיאה נמוכה יותר.
עבור , נגזור ונשווה ל-0:
- קבע בצורה שרירותית ואחידה את עבור .
- בצע בצורה איטרטיבית עד התכנסות:
לא בהכרח מתכנס למינימום מוחלט (יכולים להיתקע במינימום מקומי)
כאמור, אלגוריתם זה נותן קוונטיזציה
ישנן טבלאות עבור התפלגות גאוסית עבור ערכי N שונים.
במקרים שהתוחלת היא , אזי:
ובמקרים שהשונות היא , אזי:
דוגמה להתכנסות אלגוריתם לויד- מקס למינימום מקומי:
נניח N=2. בתמונה משמאל ניתן לראות את .
, וכן מתקיימים התנאים לLloyd Max.
למרות שקיימנו את תנאי Lloyd Max, קיבלנו מינימום מקומי.
פתרון טוב יותר היה הפונקציה התחתונה:
לפי תנאי 1 באלגוריתם, מקבלים את הערך של והוא יהיה יותר קרוב למלבן הרחב בציור הראשון.
באנליזה נומרית, אלגוריתם דה-קַסְטַלְז'וּ מתאר שיטה רקורסיבית כדי להעריך פולינום ברנשטיין או עקומות בזייר, הקרויה על שם ממציאהּ, פול-דה-קסטלז'ו.
אלגוריתם דה-קסטלז'ו יכול לשמש גם כדי לפצל עקומת בזייר יחידה לשתי עקומות בזייר בעזרת פרמטר בעל ערך שרירותי.
למרות שהוא איטי יותר במרבית הארכיטקטורות בהשוואה לגישה הישירה, הוא יציב יותר מבחינה נומרית.
עקומת בזייר B (בדרגה n, עם נקודות הבקרה ) יכולה להיות כתובים בעזרת פולינומי ברנשטיין כדלקמן
כאשר b הוא פולינום בסיס מתצורת ברנשטיין
העקומה בנקודה t0 ניתנת להערכה בעזרת נוסחת נסיגה
אז, בנקודה יכול להיות מוערך ב השלבים של האלגוריתם.
יתר על כן, עקומת בזייר יכולה להתפצל בנקודה לשתי עקומות עם נקודות בקרה, בהתאמה:
כאשר עושים את החישוב באופן ידני, שימושי לכתוב את המקדמים במשולש כ:
בעת בחירת נקודה t0 כדי להעריך את פולינום ברנשטיין אנחנו יכולים להשתמש בשני האלכסונים של המשולש כדי לבנות חלוקה של פולינום
אנחנו רוצים להעריך את פולינום ברנשטיין מדרגה 2 עם מקדמי ברנשטיין
אנחנו מתחילים את הרקורסיה עם
עם איטרציה שנייה הרקורסיה מפסיקה עם
אשר הוא הפולינום ברנשטיין הצפוי מדרגה 2.
בעת הערכת עקומת בזייר מדרגה n במרחב 3-ממדי עם n+1 נקודות בקרה, Pi
אנחנו מחלקים את עקומת בזייר לשלוש משוואות נפרדות.
אשר אנו מעריכים בנפרד באמצעות האלגוריתם של דה-קסטלז'ו.
האינטרפולציה הגאומטרית של דה-קסטלז'ו הוא ברור וישיר.
נניח עקומת בזייר עם נקודות בקרה .
אם נחבר נקודות ברצף אנחנו יוצרים את פוליגון הבקרה של העקומה.
מחלקים עכשיו כל מקטע של הפוליגון עם יחס ומחברים את הנקודות המתקבלות.
בדרך זו, מגיעים לפוליגון חדש עם מקטע אחד פחות.
חוזרים על התהליך עד שמגיעים לנקודה אחת - זו הנקודה של העקומה המתאימה לפרמטר .
התמונה הבאה מראה את התהליך הזה עבור עקומת בזייר מעוקבת:
יש לשים לב כי נקודות הביניים שנבנו הן למעשה נקודות בקרה עבור שתי עקומות בזייר החדשות שנוצרו, שתיהן בדיוק מתואמות עם הקודמת.
אלגוריתם זה לא רק מעריך את העקומה ב- , אלא גם מפצל את העקומה לשתי חתיכות ב-, ומספק את המשוואות של שתי תת-עקומות בזייר שנוצרו.
הפרשנות שניתנה לעיל תקפה לעקומת בזייר אי-אציונאליות.
כדי להעריך עקומת בזייר רציונלית ב , אנו יכולים להטיל את הנקודה לתוך ; למשל, עקומה בשלושה ממדים עשויה לקבל את נקודות הבקרה ומשקולות מוטלת לנקודות הבקרה המשוקללות .
האלגוריתם ממשיך כרגיל, מבצע אינטרפולציה ב .
התוצאה של נקודות ארבעה-ממדיות עשויות להיות מוטלות בחזרה לתוך מרחב תלת־ממדי עם מטריצת מעבר כלשהי.
באופן כללי, פעולות על עקומה רציונלית (או משטח) שוות ערך ל פעולות על עקומה לא-רציונלית במרחב פרויקטיבי.
ייצוג זה כ"נקודות בקרה משוקללות" ומשקולות הוא לעיתים קרובות נוח בעת הערכת עקומות רציונליות.
במדעי המחשב, אלגוריתם בויאר-מור הוא אלגוריתם חיפוש מחרוזות יעיל המשמש מדד השוואה סטנדרטי עבור אלגוריתמי חיפוש.
האלגוריתם פותח על ידי החוקרים האמריקאים רוברט בויאר וג' סטרותר מור ב-1977. האלגוריתם מבצע עיבוד מקדים למחרוזת החיפוש (התבנית), אך לא לטקסט שבו יבוצע החיפוש.
האלגוריתם מתאים היטב אפוא ליישומים שבהם תבנית החיפוש קצרה בהרבה מהטקסט או למקרים שבהם נעשה שימוש חוזר בתבנית החיפוש.
אלגוריתם בויאר-מור משתמש במידע הנאסף בשלב העיבוד המקדים על מנת לדלג על חלקים בטקסט, והודות לכך הוא משיג ביצועים טובים ביחס לאלגוריתמי חיפוש אחרים.
באופן כללי, האלגוריתם רץ מהר יותר ככל שמחרוזת החיפוש ארוכה יותר.
התכונות החשובות של האלגוריתם הן שהוא מחפש מסוף מחרוזת החיפוש ולא תחילתה, והוא מדלג בטקסט על מספר תווים במקום לחפש תו-תו.
עימודים של התבנית PAN על הטקסט ANPANMAN, מ k=3 ועד k=8. התאמה נמצאת ב k=5.