התמרת פורייה המהירה

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

עד כה כל אלגוריתמי המיון שראינו פעלו בזמן של $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$ הוא אורך הרשימה שאותה רוצים למיין. מבין השלושה זה שמשיג את הביצועים הטובים ביותר הוא מיון …

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

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

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

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

הסריקה של גרהאם

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

קודים לתיקון שגיאות (שניתנים לבדיקה מקומית)

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

דיון מקרי על אלגוריתמים הסתברותיים

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

אז איך באמת בודקים ראשוניות (בעזרת אלגוריתם מילר-רבין)?

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

איך תופסים אריה במדבר?

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