תוֹכֶן
- הגדרה - מה המשמעות של אלגוריתם לא-דטרמיניסטי?
- מבוא ל- Microsoft Azure ו- Microsoft Cloud | במהלך מדריך זה תוכלו ללמוד על אודות מיחשוב ענן וכיצד Microsoft Azure יכולה לעזור לכם להעביר ולנהל את העסק שלכם מהענן.
- Techopedia מסביר את האלגוריתם הלא-דטרמיניסטי
הגדרה - מה המשמעות של אלגוריתם לא-דטרמיניסטי?
אלגוריתם לא דטרמיניסטי יכול לספק תפוקות שונות לאותה קלט בהוצאות להורג שונות. בניגוד לאלגוריתם דטרמיניסטי שמייצר פלט יחיד לאותה קלט אפילו בריצות שונות, אלגוריתם לא דטרמיניסטי נוסע בנתיבים שונים כדי להגיע לתוצאות השונות.
אלגוריתמים לא-דטרמיניסטיים מועילים למציאת פתרונות משוערים, כאשר קשה או יקר להשיג פיתרון מדויק באמצעות אלגוריתם דטרמיניסטי.
מבוא ל- Microsoft Azure ו- Microsoft Cloud | במהלך מדריך זה תוכלו ללמוד על אודות מיחשוב ענן וכיצד Microsoft Azure יכולה לעזור לכם להעביר ולנהל את העסק שלכם מהענן.
Techopedia מסביר את האלגוריתם הלא-דטרמיניסטי
דוגמה אחת לאלגוריתם לא דטרמיניסטי היא ביצוע אלגוריתמים במקביל בתנאי מירוץ, שיכולים להציג תפוקות שונות בריצות שונות. בשונה מאלגוריתם דטרמיניסטי הנוסע נתיב יחיד מכניסה לפלט, אלגוריתם לא דטרמיניסטי יכול לעבור נתיבים רבים, כאשר חלקם מגיעים לאותן תפוקות, ואחרים מגיעים לפלטים שונים. תכונה זו משמשת באופן מתמטי במודלים של חישוב לא-דטרמיניסטי כמו אוטומט סופי שאינו דטרמיניסטי.
אלגוריתם לא דטרמיניסטי מסוגל לבצע במחשב דטרמיניסטי שיש לו מספר בלתי מוגבל של מעבדים מקבילים. לאלגוריתם לא דטרמיניסטי בדרך כלל שני שלבים ושלבי פלט. השלב הראשון הוא שלב הניחוש, העושה שימוש בתווים שרירותיים כדי להריץ את הבעיה.
השלב השני הוא שלב האימות, שמחזיר אמת או כוזב עבור המחרוזת שנבחרה. ישנן בעיות רבות שניתן להמשיג בעזרת אלגוריתמים לא-דטרמיניסטיים, כולל הבעיה הבלתי פתורה של P לעומת NP בתורת המחשוב.
משתמשים באלגוריתמים לא-דטרמיניסטיים בפתרון בעיות המאפשרות תוצאות מרובות. כל תוצאה שהאלגוריתם הלא-דטרמיניסטי מייצר תקפה, ללא קשר לבחירות שעשה האלגוריתם במהלך הביצוע.