רמז – עזרה ופתרונות

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

כל מה שרצית לדעת על פונקציית אקרמן:פונקציית אקרמן היא דוגמה פשוטה לפונקציה רקורסיבית שאיננה רקורסיבית פרימיטיבית. פונקציה זו גדלה מהר יותר מכל פונקציה רקורסיבית פרימיטיבית. לשם המחשה, (4,2)A, בבסיס 10, הוא מספר בן 19,729 ספרות. הפונקציה קרויה על-שם מי שהגדיר אותה, בשנת 1928, המתמטיקאי הגרמני וילהלם אקרמן. נלקח מויקיפדיה הגדרות נוספות הקשורות לפונקציית אקרמן:•קצרמר מתמטיקה•רקורסיה•פונקציות…

כל מה שרצית לדעת על חידת שמונה המלכות:חידת שמונה המלכות היא חידת שחמט שבה יש למקם שמונה מלכות שחמט על לוח שחמט כך שאף אחת מהן לא מאיימת על אף אחת מחברותיה. החידה היא מקרה פרטי של בעיית n המלכות, בעיה דומה בה יש להציב n מלכות על לוח בגודל n x n‏. לחידה 92…

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

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

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

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

כל מה שרצית לדעת על רֵקוּרְסִיָּה:רֵקוּרְסִיָּה (בעברית: נסיגה) היא תופעה שכל מופע שלה מכיל מופע נוסף שלה, כך שהיא מתרחשת ומשתקפת בשלמותה בתוך עצמה שוב ושוב. רקורסיה יכולה להיות רקורסיית עצירה (או רקורסיית קצה), כאשר יש בה "סף עצירה" – רמה שמתחתיה לא מתקיימת עוד הרקורסיה, או רקורסיה אינסופית כאשר בכל רמה תכיל התופעה תופעות…

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