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

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

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

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

העתקות מביוס והספירה של רימן

אני ממשיך את סדרת הפוסטים שלי על אנליזה מרוכבת, והפעם אני רוצה להציג מחלקה חשובה של פונקציות מרוכבות – העתקות מביוס, שהן פונקציות מרוכבות מהצורה $latex f\left(z\right)=\frac{az+b}{cz+d}$ כאשר $latex a,b,c,d\in\mathbb{C}$ המקיימים את התנאי הנוסף $latex ad-bc\ne0$ שנבין בהמשך מה משמעותו. כדי להבין למה אלו העתקות מעניינות, בואו נראה שלושה סוגים של העתקות כאלו: $latex f\left(z\right)=az$ …

איך אקסיומת הבחירה הופכת אותנו ל(כמעט) יודעי כל

הנה חידה: אליס ובוב משחקים במשחק. אליס בוחרת פונקציה ממשית $latex f:\mathbb{R}\to\mathbb{R}$ כלשהי. בוב בתורו בוחר איזה שהוא מספר $latex x\in\mathbb{R}$, ואז אליס מגלה לו את ערכי $latex f$ על כל מספר ממשי פרט ל-$latex x$, דהיינו מגלה לו את הקבוצה $latex \left\{ \left(y,f\left(y\right)\right)\ |\ y\ne x\right\} $. כעת בוב מנחש מהו $latex f\left(x\right)$, ומצליח …

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

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