משפט אימרמן

משפט אימרמן (Immerman–Szelepcsényi) הוא תוצאה בתורת הסיבוכיות (ענף במדעי המחשב) המראה כי מחלקות סיבוכיות מקום אי דטרמיניסטיות סגורות לפעולת המשלים (בעוד אותה שאלה עבור סיבוכיות זמן עודנה פתוחה וככל הנראה התשובה לה שלילית). ^[1]

השתמש ב-AI

תוכן עניינים

1. 20 יחסים: Co-NP, NP (סיבוכיות), מספר פריק, מספר ראשוני, מעגל המילטוני, משפט סביץ', מדעי המחשב, מכונת טיורינג לא-דטרמיניסטית, אסימפטוטה, אלגוריתם דטרמיניסטי, אינדוקציה מתמטית, סיבוכיות מקום, סיבוכיות זמן, סיבוכיות זיכרון, פרס גדל, תורת הסיבוכיות, תורת הגרפים, ללא הגבלת הכלליות, בעיית העצירה, יעילות אלגוריתמית.

Co-NP

בתורת הסיבוכיות, המחלקה co-NP היא המחלקה המשלימה למחלקה NP; כלומר, מחלקה שאיבריה הן בעיות המשלימות לבעיות הנמצאות במחלקה NP.

לִרְאוֹת משפט אימרמן וCo-NP

NP (סיבוכיות)

#הפניה NP (מחלקת סיבוכיות).

לִרְאוֹת משפט אימרמן וNP (סיבוכיות)

מספר פריק

מספר פָּרִיק הוא מספר שלם חיובי שאפשר לכתוב אותו כמכפלה של שני שלמים גדולים מ-1.

לִרְאוֹת משפט אימרמן ומספר פריק

מספר ראשוני

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

לִרְאוֹת משפט אימרמן ומספר ראשוני

מעגל המילטוני

#הפניה מסלול המילטוני.

לִרְאוֹת משפט אימרמן ומעגל המילטוני

משפט סביץ'

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

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

מדעי המחשב

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

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

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

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

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

אסימפטוטה

x, שבו נוצרות שתי אסימפטוטות: לקו y.

לִרְאוֹת משפט אימרמן ואסימפטוטה

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

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

לִרְאוֹת משפט אימרמן ואלגוריתם דטרמיניסטי

אינדוקציה מתמטית

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

לִרְאוֹת משפט אימרמן ואינדוקציה מתמטית

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

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

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

סיבוכיות זמן

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

לִרְאוֹת משפט אימרמן וסיבוכיות זמן

סיבוכיות זיכרון

#הפניה סיבוכיות מקום.

לִרְאוֹת משפט אימרמן וסיבוכיות זיכרון

פרס גדל

פרס גֶדֶל (באנגלית: The Gödel Prize) הוא פרס המוענק אחת לשנה, החל משנת 1993, עבור מאמר בולט באיכותו בתחום מדעי המחשב.

לִרְאוֹת משפט אימרמן ופרס גדל

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

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

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

תורת הגרפים

תורת הגרפים היא ענף של המתמטיקה העוסק בתכונותיהם של גרפים.

לִרְאוֹת משפט אימרמן ותורת הגרפים

ללא הגבלת הכלליות

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

לִרְאוֹת משפט אימרמן וללא הגבלת הכלליות

בעיית העצירה

בעיית העצירה היא בעיה מרכזית בתחום החישוביות, שהוא אחד מעמודי התווך של מדעי המחשב התאורטיים.

לִרְאוֹת משפט אימרמן ובעיית העצירה

יעילות אלגוריתמית

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

לִרְאוֹת משפט אימרמן ויעילות אלגוריתמית

אזכור

[1] https://he.wikipedia.org/wiki/משפט_אימרמן

ידוע גם בשם משפט Immerman-Szelepcsényi.

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

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

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

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

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

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