דוד צילג ז"ל

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

מהי נוסחת סטירלינג ואיך היא מוכיחה את קיום מפלצת הספגטי המעופפת

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

למה יש מיון מהיר יותר ממיון מהיר אבל בעצם אין

עד כה כל אלגוריתמי המיון שראינו פעלו בזמן של $latex \Omega\left(n\log n\right)$, כלומר דרשו לפחות זמן ריצה אסימפטוטי של לפחות $latex n\log n$ (כאשר $latex n$ הוא גודל רשימת האיברים שאותה ממיינים). השאלה הראשונה שמתעוררת היא – האם אפשר טוב יותר מזה, או שכל אלגוריתם מיון ידרוש זמן ריצה של לפחות $latex n\log n$ צעדים? …

עיון בהיר במיון מהיר

מבין כל אלגוריתמי המיון המפורסמים, מיון מהיר הוא החביב עלי, בגלל שהוא כל כך מוזר. ראשית, זה אלגוריתם מיון שזמן הריצה שלו במקרה הגרוע שלו הוא $latex \Theta\left(n^{2}\right)$, ובפועל הביצועים שלו גרועים במקרה הזה יותר מאשר אלו של מיון בחירה ומיון הכנסה, ולמרות זאת במקרה ה"ממוצע" (מה זה? נסביר בהמשך) הביצועים שלו דווקא מצויינים; שנית, …

איך להערים על מיון ערימה

בפוסט הקודם, שאני מניח שקראתם ואם לא מומלץ שתעשו זאת לפני הפוסט הנוכחי, דיברתי על אלגוריתמי מיון בסיסיים. שלושת הבסיסיים – מיון בחירה, מיון הכנסה ומיון בועות – היו איטיים למדי; זמן ריצתם היה $latex \Theta\left(n^{2}\right)$ כאשר $latex n$ הוא אורך הרשימה שאותה רוצים למיין. מבין השלושה זה שמשיג את הביצועים הטובים ביותר הוא מיון …

בקשת עזרה מקהילת הקוד הפתוח בכלל ומכל מי שמבין משהו ב-LaTeX בפרט

עדכון, 20/7/2012: כל הבעיות שהתלוננתי עליהן בפוסט הזה נפתרו לחלוטין על ידי רונן אברבנאל (ניתן לראות את הודעת ה"נצחון!" שלו למטה). כל הכבוד לרונן, שהוכיח (ולא בפעם הראשונה) שהוא המומחה הגדול בעולם ל-LyX בעברית. פרסומת זולה לבלוג הפיזיקה של רונן שמתארח אצלי על השרת: http://aprettiershell.gadial.net/ קצת רקע למי שלא מכיר אותי: אני גדי, סיימתי תואר שלישי …

מיון מהיר של מיונים איטיים

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

הסבר בזמן (O(n על סימונים אסימפטוטיים

כל מי שמתחיל ללמוד מדעי המחשב נתקל חיש קל בסימון האסימפטוטי $latex O\left(n\right)$. המשפט הזה נשמע לכם כמו ג'יבריש מוחלט? מצויין! הפוסט הזה מיועד בעיקר לכם, ובפרט לאלו מכם שהעניין הזה הבהיל אותם מלהתעסק במדעי המחשב. השורה התחתונה היא שזה סימון מתמטי פשוט יחסית, שמטרתו לעשות את החיים קלים לכל העוסקים במלאכה; בואו ננסה להבין …