רדוקציה חישובית
רדוקציה היא דרך להחליף בעיה בבעיה אחרת שעוזרת לפתור אותה. לדוגמה, כדי למצוא את המספר הקטן ביותר בסדרה, אפשר למיין את המספרים ואז לקחת את הראשון. רדוקציה עוזרת להראות אם בעיה ניתנת לפתרון או לא. משתמשים בה כדי לקשר בעיות שקשה לפתור. רדוקציה פולינומית היא רדוקציה שחישוב שלה יעיל. אם יש פתרון יעיל לב...
ניבים צפון-רוסיים
הניבים הרוסיים הצפוניים הם דרכי דיבור ברוסית. ניבים = דרכי דיבור מקומיות. יש בהם שתי תכונות חשובות: אוקנייה ויקנייה. אוקנייה ויקנייה אומרות שהתנועות שלא מדגישים נשמעות חזקות. רדוקציה = החלשה של צליל בתנועה שאינה מודגשת. כאן האות O תמיד נשמעת כמו o. האות E תמיד נשמעת כמו "יה" (je). ניבים כאלה מדוב...
אורקל (מדעי המחשב)
אורקל הוא קופסה שחורה שנותנת תשובות לשאלה בודדת בצעד אחד. קופסה שחורה הוא דבר שאפשר לשאול אבל לא לראות איך הוא עובד. אורקלים יכולים לפתור בעיות מאוד קשות, אפילו בעיות שלא תמיד אפשר לחשב, כמו בעיית העצירה (שאלה אם תוכנה תפסיק או תרוץ לנצח). מכונת טיורינג היא דרך לתאר מחשב פשוט בתור מודל. מכונת טיורי...
הוכחה בדרך השלילה
הוכחה בדרך השלילה היא דרך להראות שטענה נכונה על ידי הוכחת ההפך שגוי. כלומר, מניחים שהטענה לא נכונה. אם זה גורם לסתירה, הטענה המקורית נחשבת נכונה. שמה הלטיני הוא Reductio ad absurdum. זה אומר: להראות שהנחה מובילה למצב מצחיק או לא הגיוני. במתמטיקה משתמשים בשיטה הזאת הרבה. במקום לבנות הוכחה ישירה, מנ...
קבוצה בלתי תלויה (תורת הגרפים)
קבוצה בלתי תלויה היא קבוצה של נקודות (קודקודים) בגרף. נקודות בקבוצה כאלו לא מחוברות זו לזו. אם צובעים את הקודקודים כך ששכנים לא מקבלים את אותו צבע, כל צבע נותן קבוצה כזו. סימול נפוץ לגודל הגדול ביותר הוא α של הגרף. השאלה: האם יש קבוצה בלתי תלידה בגודל מסוים? זו שאלה קשה מאוד. ריצ'רד קארפ הראה שהי...
משפט קוק-לוין
משפט קוק-לוין אומר שבעיה בשם SAT היא אחת הקשות בקבוצה שנקראת NP. P הן בעיות שאפשר לפתור מהר. NP הן בעיות שאם נותנים פתרון, אפשר לבדוק מהר אם הוא נכון. שאלה גדולה היא האם כל בעיה שאפשר לבדוק מהר אפשר גם לפתור מהר. זוהי שאלה פתוחה. SAT היא בעיה של נוסחאות לוגיות. נוסחאות אלה כתובות עם משתנים שאפ...
פנומנולוגיה
פנומנולוגיה פירושה חקר איך דברים מופיעים לנו בתודעה. פנומנה = תופעה. זה עוסק במה שאנחנו מרגישים ומבינים ברגע עצמו. התודעה תמיד פונה למשהו. זה נקרא התכוונותיות, המחשבות שלנו תמיד מכוונות אל מושא. אדמונד הוסרל התחיל את הגישה. הוא ביקש לתאר חוויות כפי שהן נראות לתודעה בלי להיסחף לתיאוריות. כדי לעשות...
P (מחלקת סיבוכיות)
P היא קבוצה של בעיות שאפשר לפתור בצורה "מהירה" יחסית. "מהירה" כאן פירושו זמן פולינומי. זמן פולינומי אומר שהזמן גדל בצורה לא מוגזמת כשהקלט גדל. דוגמאות פשוטות ב-P הן חישוב המחלק המשותף הגדול של שני מספרים (GCD) ועץ פורש מינימלי. גם בדיקת האם מספר הוא ראשוני נכנסה ל-P בשנת 2002. בחירת זמן פולינומי ש...