אנחנו עובדים על שחזור אפליקציית Unionpedia ב-Google Play Store
יוֹצֵאנִכנָס
🌟פישטנו את העיצוב שלנו לניווט טוב יותר!
Instagram Facebook X LinkedIn

בעיית הספיקות

מַדָד בעיית הספיקות

בעיית הספיקות בתחשיב הפסוקים (בקיצור: SAT - קיצור של המילה האנגלית Satisfiability, שמשמעותה ספיקות) הוא שמה של בעיית הכרעה הנחקרת במסגרת תורת הסיבוכיות במדעי המחשב. [1]

תוכן עניינים

  1. 19 יחסים: APX (מחלקת סיבוכיות), NP (מחלקת סיבוכיות), NP-שלמה, P (סיבוכיות), P=NP, PTAS, משפט קוק-לוין, מדעי המחשב, אלגוריתמיקה, אלגוריתם קירוב, ערך אמת, צורה נורמלית קוניונקטיבית, תחשיב פסוקים, תורת הסיבוכיות, למת המקומיות של לובאס, לוגיקה מתמטית, חיפוש מקומי, בעיית הכרעה, בינה מלאכותית.

  2. אלגברה בוליאנית
  3. בעיות NP-שלמות

APX (מחלקת סיבוכיות)

#הפניה APX.

לִרְאוֹת בעיית הספיקות וAPX (מחלקת סיבוכיות)

NP (מחלקת סיבוכיות)

במדעי המחשב, NP היא מחלקת סיבוכיות חשובה, שמכילה בעיות הנקראות "בעיות הכרעה", המוגדרות על ידי השאלה: בהינתן קלט, האם הוא מקיים תכונה נתונה? (דוגמה: הקלט יכול להיות מספר טבעי, והתכונה: המספר הוא זוגי, או ראשוני).

לִרְאוֹת בעיית הספיקות וNP (מחלקת סיבוכיות)

NP-שלמה

#הפניה NP (מחלקת סיבוכיות)#בעיות NP-קשות (NP-Hard) ובעיות NP-שלמות (NPC).

לִרְאוֹת בעיית הספיקות וNP-שלמה

P (סיבוכיות)

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

לִרְאוֹת בעיית הספיקות וP (סיבוכיות)

P=NP

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

לִרְאוֹת בעיית הספיקות וP=NP

PTAS

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

לִרְאוֹת בעיית הספיקות וPTAS

משפט קוק-לוין

משפט קוק-לוין הוא משפט יסודי בתורת הסיבוכיות, הקובע שהבעיה SAT היא NP-שלמה.

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

מדעי המחשב

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

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

אלגוריתמיקה

#הפניה אלגוריתם.

לִרְאוֹת בעיית הספיקות ואלגוריתמיקה

אלגוריתם קירוב

אלגוריתם קירוב (באנגלית: approximation algorithm) הוא אלגוריתם שמוצא פתרון שאינו בהכרח פתרון אופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון אופטימלי.

לִרְאוֹת בעיית הספיקות ואלגוריתם קירוב

ערך אמת

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

לִרְאוֹת בעיית הספיקות וערך אמת

צורה נורמלית קוניונקטיבית

#הפניה CNF.

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

תחשיב פסוקים

#הפניה תחשיב הפסוקים.

לִרְאוֹת בעיית הספיקות ותחשיב פסוקים

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

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

לִרְאוֹת בעיית הספיקות ותורת הסיבוכיות

למת המקומיות של לובאס

למת המקומיות של לובאס (באנגלית: Lovász Local Lemma) היא למה בתורת ההסתברות אשר פותחה בשנת 1975 על ידי לסלו לובאס ופול ארדש.

לִרְאוֹת בעיית הספיקות ולמת המקומיות של לובאס

לוגיקה מתמטית

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

לִרְאוֹת בעיית הספיקות ולוגיקה מתמטית

חיפוש מקומי

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

לִרְאוֹת בעיית הספיקות וחיפוש מקומי

בעיית הכרעה

150 פיקסלים במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה אשר יש לה תשובה של "כן" או "לא".

לִרְאוֹת בעיית הספיקות ובעיית הכרעה

בינה מלאכותית

250px בינה מלאכותית (באנגלית: אינטליגנציה מלאכותית - Artificial intelligence, ובראשי תיבות: AI) שם מטאפורי למצב בו מנסים לדמות את יכולות החשיבה האנושית באמצעים טכנולוגיים.

לִרְאוֹת בעיית הספיקות ובינה מלאכותית

ראה גם

אלגברה בוליאנית

בעיות NP-שלמות

אזכור

[1] https://he.wikipedia.org/wiki/בעיית_הספיקות