גישה מהירה יותר מאשר בדפדפן!
25 יחסים: EXPSPACE, NL (סיבוכיות), NP (סיבוכיות), PP (מחלקת סיבוכיות), PSPACE, TQBF, משפט אימרמן, משפט סביץ', מחלקת סיבוכיות NPC, מדעי המחשב, מכונת טיורינג, מכונת טיורינג לא דטרמיניסטית, אלגוריתם, אוטומט סופי דטרמיניסטי, סימון אסימפטוטי, סיבוכיות מקום, סיבוכיות זמן, פלט, קלט, רדוקציה פולינומית, שפה רגולרית, תוכנה, זיכרון מחשב, חישוב (מדעי המחשב), בעיית הכרעה.
EXPSPACE
בתורת הסיבוכיות, המחלקה EXPSPACE היא קבוצת כל בעיות ההכרעה הפתירות על ידי מכונת טיורינג דטרמיניסטית ב O(2^) במַקום, כאשר P(n) מייצג פונקציה פולינומית של n. (מקצת החוקרים מגבילים את P(n) להיות פונקציה ליניארית) לחלופין, אם אנו משתמשים במכונת טיורינג לא דטרמיניסטית, אנחנו מקבלים את המחלקה NEXPSPACE, אשר שווה ל-EXPSPACE על ידי משפט סביץ'.
חָדָשׁ!!: סיבוכיות מקום וEXPSPACE · ראה עוד »
NL (סיבוכיות)
בתורת הסיבוכיות, NL (לא דטרמיניסטי עם מקום לוגריתמי) היא מחלקת סיבוכיות המכילה בעיות אשר ניתנות להכרעה על ידי מכונת טיורינג לא דטרמיניסטית אשר משתמשת בזיכרון לוגריתמי לכל היותר.
חָדָשׁ!!: סיבוכיות מקום וNL (סיבוכיות) · ראה עוד »
NP (סיבוכיות)
#הפניה NP (מחלקת סיבוכיות).
חָדָשׁ!!: סיבוכיות מקום וNP (סיבוכיות) · ראה עוד »
PP (מחלקת סיבוכיות)
במדעי המחשב ובתורת הסיבוכיות, PP, (ראשי תיבות של Probabilistic Polynomial Time), היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי כאשר האלגוריתם מחזיר תשובה נכונה בהסתברות שגדולה ממש מ-1/2.
חָדָשׁ!!: סיבוכיות מקום וPP (מחלקת סיבוכיות) · ראה עוד »
PSPACE
בתורת הסיבוכיות, PSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג דטרמיניסטית תוך שימוש בסיבוכיות מקום פולינומית.
חָדָשׁ!!: סיבוכיות מקום וPSPACE · ראה עוד »
TQBF
בתורת הסיבוכיות, השפה TQBF (קיצור ל-True quantified boolean formulas; או: QBF, QSAT) היא שפה פורמלית במחלקה PSPACE.
חָדָשׁ!!: סיבוכיות מקום וTQBF · ראה עוד »
משפט אימרמן
משפט אימרמן (Immerman–Szelepcsényi) הוא תוצאה בתורת הסיבוכיות (ענף במדעי המחשב) המראה כי מחלקות סיבוכיות מקום אי דטרמיניסטיות סגורות לפעולת המשלים (בעוד אותה שאלה עבור סיבוכיות זמן עודנה פתוחה וככל הנראה התשובה לה שלילית).
חָדָשׁ!!: סיבוכיות מקום ומשפט אימרמן · ראה עוד »
משפט סביץ'
משפט סביץ' (באנגלית: Savitch's theorem), שהוכח בידי וולטר סביץ' בשנת 1970, הוא משפט בתורת הסיבוכיות שקושר בין הזיכרון הנדרש לצורך פתרון בעיות בדרך דטרמיניסטית ובין הזיכרון הנדרש כאשר ניתן להשתמש באי-דטרמיניזם.
חָדָשׁ!!: סיבוכיות מקום ומשפט סביץ' · ראה עוד »
מחלקת סיבוכיות NPC
#הפניה NP (מחלקת סיבוכיות).
חָדָשׁ!!: סיבוכיות מקום ומחלקת סיבוכיות NPC · ראה עוד »
מדעי המחשב
מדְעי המחשב הם ענף מדעי העוסק בלימוד הבסיס התאורטי והמעשי של השימוש במערכות מחשב, ובמידה מסוימת, גם בשאלה של תכנון ובנייה של מערכות מחשב.
חָדָשׁ!!: סיבוכיות מקום ומדעי המחשב · ראה עוד »
מכונת טיורינג
הדמיה של מכונת טיורינג מכונת טיורינג (באנגלית: Turing machine) היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).
חָדָשׁ!!: סיבוכיות מקום ומכונת טיורינג · ראה עוד »
מכונת טיורינג לא דטרמיניסטית
#הפניה מכונת טיורינג לא-דטרמיניסטית.
חָדָשׁ!!: סיבוכיות מקום ומכונת טיורינג לא דטרמיניסטית · ראה עוד »
אלגוריתם
אלגוריתם הוא דרך שיטתית וחד-משמעית לביצוע של משימה מסוימת, במספר סופי של צעדים.
חָדָשׁ!!: סיבוכיות מקום ואלגוריתם · ראה עוד »
אוטומט סופי דטרמיניסטי
בתורת החישוביות, אוטומט סופי דטרמיניסטי (להלן: אס"ד) הוא מודל מתמטי, המגדיר שפה פורמלית.
חָדָשׁ!!: סיבוכיות מקום ואוטומט סופי דטרמיניסטי · ראה עוד »
סימון אסימפטוטי
סימון אסימפטוטי (ידוע גם כסימון לנדאו) משמש במתמטיקה כסימון מקוצר שמתאר את התנהגותן של פונקציות עבור ערכים הולכים וגדלים (או הולכים וקטנים), וזאת באמצעות השוואתן לפונקציות אחרות.
חָדָשׁ!!: סיבוכיות מקום וסימון אסימפטוטי · ראה עוד »
סיבוכיות מקום
במדעי המחשב, כאשר עוסקים בניתוח המשאבים שדורשים אלגוריתמים משתמשים במושג של סיבוכיות מקום (המכונה גם סיבוכיות זיכרון) על מנת להעריך את כמות זיכרון המחשב הדרוש להם.
חָדָשׁ!!: סיבוכיות מקום וסיבוכיות מקום · ראה עוד »
סיבוכיות זמן
פונקציות הנפוצות בניתוח אלגוריתמים המציגות את מספר הפעולות הנדרשות לפונקציה לעומת גודל הקלט בתורת החישוביות, סיבוכיות זמן של אלגוריתם היא הערכה, באמצעות חסמים, על מספר הפעולות שמבצע האלגוריתם כפונקציה של גודל הקלט.
חָדָשׁ!!: סיבוכיות מקום וסיבוכיות זמן · ראה עוד »
פלט
פֶּלֶט, בתחום המחשוב והאוטומציה, הוא תוצר של פעולת מחשב או מכשיר אוטומטי אחר.
חָדָשׁ!!: סיבוכיות מקום ופלט · ראה עוד »
קלט
בתחום המחשוב והאוטומציה, קלט הוא כלל הנתונים המגיעים אל המחשב או אל מכשיר אוטומטי אחר, מן העולם שמחוצה לו.
חָדָשׁ!!: סיבוכיות מקום וקלט · ראה עוד »
רדוקציה פולינומית
#הפניה רדוקציה חישובית.
חָדָשׁ!!: סיבוכיות מקום ורדוקציה פולינומית · ראה עוד »
שפה רגולרית
בתורת השפות הפורמליות, שפה רגולרית היא שפה פורמלית שאפשר לתאר על ידי אוטומט סופי, האמור לקבוע לגבי מילה נתונה אם היא שייכת לשפה אם לאו.
חָדָשׁ!!: סיבוכיות מקום ושפה רגולרית · ראה עוד »
תוכנה
תוכנה היא אוסף של הוראות ומידע הניתנות לביצוע על ידי מחשב.
חָדָשׁ!!: סיבוכיות מקום ותוכנה · ראה עוד »
זיכרון מחשב
#הפניה זיכרון גישה אקראית.
חָדָשׁ!!: סיבוכיות מקום וזיכרון מחשב · ראה עוד »
חישוב (מדעי המחשב)
חישוב במשמעותו הרחבה של מושג זה המקובלת במדעי המחשב, הוא כל תהליך של עיבוד מידע שניתן לייצוג באופן מתמטי.
חָדָשׁ!!: סיבוכיות מקום וחישוב (מדעי המחשב) · ראה עוד »
בעיית הכרעה
150 פיקסלים במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה אשר יש לה תשובה של "כן" או "לא".
חָדָשׁ!!: סיבוכיות מקום ובעיית הכרעה · ראה עוד »
מפנה מחדש כאן:
אזכור
[1] https://he.wikipedia.org/wiki/סיבוכיות_מקום
