פוסט של בעיית ההתאמה של פוסט

"בעיית ההתאמה של פוסט" – Post Correspondence Problem, ובקיצור PCP – היא בעיה נחמדה במדעי המחשב שנקראת על שם אמיל פוסט, אחד מחלוצי מדעי המחשב (ואינה קשורה לדואר, כמו שחשבתי הרבה זמן) שתיאר אותה ב-1946. מה שנחמד בבעיה הזו הוא … להמשיך לקרוא

על גבולות עליונים ותחתונים של קבוצות וממשיים

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

משפט ארבעת הריבועים של לגראנז'

אני רוצה לדבר על אחת מהתוצאות הנחמדות ביותר (לטעמי) בתורת המספרים האלמנטרית – משפט ארבעת הריבועים של לגראנז'. בפשטות, המשפט אומר שאפשר להציג כל מספר טבעי בתור סכום של ארבעה ריבועים של מספרים טבעיים (כש-0 נחשב למספר טבעי). הנה דוגמאות … להמשיך לקרוא

פרוייקט "התלמיד והמחשב", בעיה 25

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

פרוייקט "התלמיד והמחשב", בעיות 21-24

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

המחט של בופון

היום חל "יום פאי", כלומר תאריך היום הוא ה-14/3, שבארצות פחות מתוקנות נכתב כ-3.14, כלומר כמו התחלת הפיתוח העשרוני של הקבוע \(\pi\), פאי (היחס בין היקף מעגל לקוטרו בגאומטריה האוקלידית) – ומכאן, תירוץ לחגוג ולאכול פאי עם פאי. מבחינתי זה … להמשיך לקרוא

אמי נתר (או: על נשים ומתמטיקה וחוקי שימור טובים פחות וטובים יותר)

התירוץ שלי לכתוב את הפוסט הזה הוא הכתבה הזו ב"הארץ" על הכמות הדלה של רחובות בתל-אביב שנקראים על שם נשים, מכיוון שבכתבה הזו נזרק התירוץ של "אף אחד לא ממליץ". ובכן, אני חושב שאמי נתר היא המלצה מצויינת, ובהמשך הפוסט … להמשיך לקרוא

בסיסים אורתונורמליים במרחבי הילברט

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

אז מה זה מרחב הילברט?

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

פותרים את SAT – אלגוריתם CDCL

בפוסט הקודם על פתרונות לבעיית SAT ראינו את אלגוריתם DPLL – זה היה פחות או יותר האלגוריתם הבסיסי שרוב פותרי ה-SAT המדוייקים (להבדיל מהסתברותיים) מבוססים עליו, אבל מן הסתם פותרים מודרניים הולכים רחוק יותר ממנו, ובפוסט הזה אני רוצה להציג … להמשיך לקרוא

המניפולציה המתמטית של ההמבורגר

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

איך ייתכן ש …+1+2+3 שווה למינוס 1 חלקי 12?!

בימים האחרונים משוטט ברשת סרטון של Numberphile שמציג "הוכחה" לסכום הבלתי נתפס הבא: \(1+2+3+\dots=-\frac{1}{12}\). במילים: הסכום של כל המספרים הטבעיים הוא מינוס (מינוס!) אחד חלקי שתיים עשרה. זו כמובן תוצאה בלתי נתפסת. איך ייתכן שסכום של מספרים חיוביים יהיה משהו … להמשיך לקרוא

החבורה שלכם? לינוקס!

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

פרדוקס האוטובוס הצפוף

אהוד אהרוני (שבנוסף למעלליו בפוסט הזה גם יוצר סרטוני וידאו די פנטסטיים למראה) פנה אלי עם סיפור שאותו המציא: ישנה עיירה ובה מפעל, ובכל יום הפועלים נוסעים למפעל באוטובוס. יש 30 פועלים ועומדים לרשותם 3 אוטובוסים שממתינים בחניה, וכל פועל … להמשיך לקרוא

פותרים את SAT – אלגוריתם DPLL

הגענו סוף סוף לדבר על האופן שבו פותרים את בעיית SAT במקרה הכללי. יש לנו פסוק CNF \(\varphi\) ואין לו בהכרח צורה "נחמדה" כמו בבעיות 2SAT או HORNSAT שראינו בפוסט הקודם – מה עושים? ראשית כל ההסתייגות הבלתי נמנעת – … להמשיך לקרוא

פותרים את SAT: המקרים של HORNSAT ו-2SAT

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

רזולוציה – איך אפשר להוכיח שאי אפשר?

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

מה זו בעיית SAT ולמה חשוב לפתור אותה?

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

האלגוריתם של קרוסקל ומבנה הנתונים Union/Find

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

אלגוריתמים לעץ פורש מינימלי בגרף – מה הרעיון הכללי?

בפוסט הקודם תיארתי את הבעיה המתמטית שאנחנו רוצים לפתור: מציאת עץ פורש מינימלי של גרף ממושקל. בפוסט הזה ניגש ישר לעסק ונתאר איך עושים את זה. בפוסטים הבאים אני הולך לתאר שני אלגוריתמים שעושים את זה – של קרוסקל ושל … להמשיך לקרוא