רקורסיה

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

ביטויים רגולריים

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

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

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

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

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

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

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

על גרפים, עצים פורשים ואיך זה נראה בקוד

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

קרוסקל את פרים – בוני מבוכים בע"מ

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

פרוייקט "התלמיד והמחשב", בעיות 16-20 – רובי

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

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

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

מספרי עבגד

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

פרוייקט "התלמיד והמחשב", בעיות 12-13-14

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

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

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

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

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

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

בעיה 9 בספר היא בעיית המיון. או ליתר דיוק, בספר מתעסקים במיון רשימות באורך המרשים של 2 ו-3 מספרים, באמצעות שרשרת של if-ים; אני כמובן לא מוכן לעשות את זה ותחת זאת אציג מיון של מערך כללי. מיון, כזכור, פירושו … להמשיך לקרוא

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

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

פרוייקט "התלמיד והמחשב", בעיות 5-6-7

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

פרוייקט "התלמיד והמחשב", בעיות 2-3-4

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

פרוייקט "התלמיד והמחשב" יוצא לדרך!

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

נוסחת טאפר – הנוסחה שמציירת את עצמה

בואו ניגש ללב העניין. התבוננו בנוסחה הבאה: $latex \frac{1}{2}<\left\lfloor \mbox{mod}\left(\left\lfloor \frac{y}{17}\right\rfloor 2^{-17\left\lfloor x\right\rfloor -\mbox{mod}\left(\left\lfloor y\right\rfloor ,17\right)},2\right)\right\rfloor $ בלי פאניקה! הכל יוסבר. ראשית, סימנים: $latex \left\lfloor a\right\rfloor $ מסמל את הערך השלם התחתון של המספר $latex a$, שמוגדר להיות המספר השלם … להמשיך לקרוא

ראשוני מחוץ לחוק

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