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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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