אלגוריתם מילר-רבין
מילר-רבין בודק אם מספר הוא ראשוני. מספר ראשוני מחלקים אותו רק בעצמם וב-1. האלגוריתם מהיר ולעיתים קטן יכול לטעות. קודם כותבים את n-1 בצורה n-1 = 2^s · r. זאת אומרת: מחלקים ב-2 עד שהשארית r אי-זוגית. (r הוא המספר שנותר.) בוחרים מספר a שלא מתחלק ב-n. מחשבים חזקות של a ומסתכלים על השארית בחלוקה ב-n. אם...
סולומון אש
סולומון אש (1907, 1996) היה פסיכולוג שחקר איך אנשים מתנהגים בקבוצה. גשטלט אומר לראות את התמונה כולה, לא רק חלקים. נולד בוורשה ב-1907. ב-1920 עלה לארצות הברית עם המשפחה. למד בקולג' והפך לפרופסור. לימד במכללות כמו סווארת'מור וראטגרס. נשא את פלורנס מילר. בנם, פיטר, נולד ב-1937 והיה גם הוא פרופסור. אש...
משולש פסקל
משולש פסקל הוא משולש של מספרים. בראש המשולש יש 1. כל מספר במשולש שווה לסכום שני המספרים שמעליו. בצדדים תמיד יש 1. אנשים בסין, בהודו ובמדינות מוסלמיות הכירו אותו בימי הביניים. מאוחר יותר בלז פסקל כתב עליו. המספר בעמדה מסוימת אומר כמה דרכים יש לבחור כמה פריטים מקבוצה. לדוגמה, בשורה שבה יש 5 איברים,...
Co-NP
co-NP הוא אוסף בעיות שהן ההפך של הבעיות ב־NP. NP הן בעיות שיש להן הוכחה קצרה שאפשר לבדוק מהר. זמן פולינומי הוא זמן חישוב סביר. דוגמה פשוטה: יש קבוצה של מספרים. שואלים אם יש תת־קבוצה שסכומה אפס. אם כן, נותנים את הרשימה ובודקים את הסכום. ההפך שואל האם אין בכלל תת־קבוצה שסכומה אפס. גם לזה יש הוכחה שני...
ניו המפשייר
ניו המפשייר היא מדינה בצפון ארצות הברית. היא ליד ורמונט, מסצ'וסטס, מיין וקוויבק שבקנדה. השם הגיע מהמחוז המפשייר באנגליה. ההתיישבות הוקמה ב-1623 על ידי ג'ון מייסון. ניו המפשייר הייתה אחת מ-13 המושבות שהקימו את ארצות הברית. ב-1776 קיבלה המדינה חוקה מקומית, לפני הכרזת העצמאות של ארצות הברית. הממשלה ...
תזמורת פילדלפיה
תזמורת פילדלפיה נמצאת בעיר פילדלפיה בארצות הברית. תזמורת היא קבוצה גדולה של נגנים. היא נוסדה ב-1900 על ידי פריץ של. התזמורת נחשבת לאחת הטובות בארצות הברית. מאז 2001 היא מופיעה במרכז קימל. לפני כן היא הופיעה מאה שנים באקדמיה למוזיקה. לאופולד סטוקובסקי היה מנצח חשוב מ-1912. הוא עשה את התזמורת מאוד מ...
מבחן לוקאס-להמר
מבחן לוקאס-להמר עוזר לבדוק אם מספר גדול הוא ראשוני. ראשוני פירושו שאין לו מחלקים חוץ מ-1 ומהמספר עצמו. הרעיון: בוחרים מספר קטן שנקרא עד (זה מבחן לבדיקה). מבצעים חישובים מיוחדים עם העד והמספר n. אם העד ממלא את הדרישות, אז n הוא בוודאות ראשוני. יש בעיה קטנה: צריך לדעת איך לפרק את n−1 לגורמים. פירוק ...
מבחן לוקאס-להמר למספרי מרסן
מבחן לוקאס‑להמר בודק מספרים מיוחדים שנקראים מספרי מרסן. מספר מרסן מקבלים כך: עושים 2 בחזקת p ואז מורידים 1. מתחילים סדרה שמתחילה ב‑4. כל איבר הבא הוא הריבוע של הקודם פחות 2. בודקים את האיבר במקום p-2. אם האיבר הזה מתחלק ב‑M (אין שארית), אז M הוא מספר ראשוני. זה אומר שאי אפשר לחלק אותו במספרים אחר...
לולאה (תכנות)
לולאה (Loop) היא דרך בתכנות לחזור על פעולה שוב ושוב. תוכנית עובדת על פריט אחד בכל פעם. כדי לעשות את זה שוב על הפריט הבא, התוכנית חוזרת להתחלה של הפעולה. לולאה חזקה כי היא יכולה לחזור עליה הרבה פעמים. דוגמה: כדי להכין לוח כפל משתמשים בשתי לולאות אחת בתוך השנייה. יש כמה סוגים של לולאות בשפות תכנות ...