משפט סביץ'

משפט סביץ' (באנגלית: Savitch's theorem), שהוכח בידי וולטר סביץ' בשנת 1970, הוא משפט בתורת הסיבוכיות שקושר בין הזיכרון הנדרש לצורך פתרון בעיות בדרך דטרמיניסטית ובין הזיכרון הנדרש כאשר ניתן להשתמש באי-דטרמיניזם. ^[1]

תוכן עניינים

15 יחסים: P=NP, מחשב, מדעי המחשב, מכונת טיורינג, מכונת טיורינג לא-דטרמיניסטית, אנגלית, אלגוריתם חיפוש, סיבוכיות מקום, פונקציה, פולינום, קלט, שפה פורמלית, תורת הסיבוכיות, חסם (מתמטיקה), גרף (תורת הגרפים).
משפטים במדעי המחשב

P=NP

#הפניה בעיית P.

לִרְאוֹת משפט סביץ' וP=NP

מחשב

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

לִרְאוֹת משפט סביץ' ומחשב

מדעי המחשב

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

לִרְאוֹת משפט סביץ' ומדעי המחשב

מכונת טיורינג

הדמיה של מכונת טיורינג מכונת טיורינג (באנגלית: Turing machine) היא מודל חישובי מתמטי אשר באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).

לִרְאוֹת משפט סביץ' ומכונת טיורינג

מכונת טיורינג לא-דטרמיניסטית

כל אלגוריתם ניתן לתיאור על ידי מודל מתמטי מופשט המכונה מכונת טיורינג.

לִרְאוֹת משפט סביץ' ומכונת טיורינג לא-דטרמיניסטית

אנגלית

אנגלית (באנגלית: English) היא שפה ממשפחת השפות הגרמאניות שמקורה באנגליה, והיא אחת השפות המדוברות ביותר בעולם.

לִרְאוֹת משפט סביץ' ואנגלית

אלגוריתם חיפוש

במדעי המחשב, אלגוריתם חיפוש הוא אלגוריתם המשמש לחיפוש נתון נדרש במבנה נתונים.

לִרְאוֹת משפט סביץ' ואלגוריתם חיפוש

סיבוכיות מקום

במדעי המחשב, כאשר עוסקים בניתוח המשאבים שדורשים אלגוריתמים משתמשים במושג של סיבוכיות מקום (המכונה גם סיבוכיות זיכרון) על מנת להעריך את כמות זיכרון המחשב הדרוש להם.

לִרְאוֹת משפט סביץ' וסיבוכיות מקום

פונקציה

פונקציה המתאימה לכל צורה את הצבע שלה פונקציה היא התאמה המשייכת לכל איבר בקבוצה אחת, איבר יחיד בקבוצה שנייה. במתמטיקה, פוּנְקְצִיָּה (נקראת גם העתקה) היא התאמה, המשייכת לכל איבר בקבוצה אחת, איבר יחיד בקבוצה שנייה.

לִרְאוֹת משפט סביץ' ופונקציה

פולינום

במתמטיקה, פולינום במשתנה \ x הוא ביטוי מהצורה \ a_0 + a_1 x + \cdots + a_n x^n כאשר \ a_0,a_1,\dots,a_n הם קבועים; למשל, 3x^2+7x-5.

לִרְאוֹת משפט סביץ' ופולינום

קלט

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

לִרְאוֹת משפט סביץ' וקלט

שפה פורמלית

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

לִרְאוֹת משפט סביץ' ושפה פורמלית

תורת הסיבוכיות

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

לִרְאוֹת משפט סביץ' ותורת הסיבוכיות

חסם (מתמטיקה)

במתמטיקה, חֶסֶם של תת-קבוצה של קבוצה סדורה חלקית הוא איבר של הקבוצה הסדורה שבינו לבין כל אחד מאברי התת-קבוצה מתקיים אי-שוויון חלש.

לִרְאוֹת משפט סביץ' וחסם (מתמטיקה)

גרף (תורת הגרפים)

גרף לא מכוון בעל 6 קודקודים ו-7 קשתות גרף מכוון בעל 4 קודקודים ו-5 קשתות בתורת הגרפים, גרף הוא ייצוג מופשט של קבוצה של אובייקטים, כאשר כל זוג אובייקטים בקבוצה עשויים להיות מקושרים זה לזה.

לִרְאוֹת משפט סביץ' וגרף (תורת הגרפים)

ראה גם

משפטים במדעי המחשב

אזכור

[1] https://he.wikipedia.org/wiki/משפט_סביץ'

ידוע גם בשם משפט Savitch.

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

זוהי מפה נפשית מקוונת ענקית המשמשת כבסיס לתרשימי מושג. זה בחינם לשימוש וכל מאמר או מסמך ניתן להוריד. זהו כלים, משאבים או התייחסות למחקר, מחקר, חינוך, למידה והוראה, שיכול להיות בשימוש על ידי מורים, מחנכים, תלמידים או סטודנטים; לעולם האקדמי: לבית ספר, יסודי, בית ספר תיכון המשני,, אמצע, מכללה, תואר טכני, מכללה, אוניברסיטה, סטודנט לתואר ראשון, תואר שני או תואר דוקטור; למסמכים, דוחות, פרויקטים, רעיונות, תיעוד, סקרים, סיכומים, או תזה. הנה ההגדרה, הסבר, התיאור, או את המשמעות של כל משמעותי שבו אתה זקוק למידע, ורשימה של המושגים הקשורים בם כמילון מונח. זמין ב עברית, אַנגְלִית, סְפָרַדִית, פורטוגזית, יַפָּנִית, סִינִית, צָרְפָתִית, גֶרמָנִיָת, אִיטַלְקִית, לק, הוֹלַנדִי, רוּסִי, עֲרָבִית, הינדי, שוודי, אוקראיני, הוּנגָרִי, קטלאנית, צ׳כית, דַנִי, פִינִית, אינדונזי, נורבגי, רומנית, טורקי, ויאטנמית, קוריאנית, תאילנדית, יווני, בולגרית, קרואטית, סלובקית, ליטאית, פיליפינית, לטבית, אסטונית ו סלובנית. שפות נוספות בקרוב.

המידע מבוסס על ערכים מויקיפדיה ומיזמים אחרים של ויקימדיה, וזמין תחת רישיון Creative Commons ייחוס-שיתוף זהה.

יוניונפדיה אינה נתמכת על ידי קרן ויקימדיה או קשורה אליה.

Google Play, Android ואת הלוגו של Google Play הם סימנים מסחריים של Google Inc.

מדיניות פרטיות