בעיית התפוצצות מצבים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במתמטיקה, התפוצצות קומבינטורית מתארת גידול מהיר מאוד של פונקציות, כתוצאה משיקולים קומבינטוריים.

דוגמאות לפונקציות כאלה הן: פונקציית העצרת, פונקציית אקרמן וכדומה.

במדעי המחשב משתמשים במושג התפוצצות מצבים לתיאור בעיית מספר רב מאוד של מסלולי בקרה בתוכנה, כתלות בקלט שלה. תוכנה, המהווה למעשה פונקציה אשר מקבלת קלט, ומחזירה פלט כתוצאה מעיבוד הקלט, מחזירה מספר פלטים שונים הגדל בצורה מהירה מאוד, עבור מספר קלטים הגדל לאט. כשמדובר על אימות תוכנה אוטומטי עבור כל קלט, ישנה מגבלה של זמן ומקום המונעת, בגלל בעיית התפוצצות המצבים, אפשרות להבטיח כיסוי מלא בבדיקות תוכנה.

P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.