בתשובה לeasy, 26/06/06 15:06
בתור כדורגלן עבר 392872
קוריוז שלא מעניין אף אחד: בקורס שאני לומד עכשיו בתורת הסיבוכיות דווקא יש חשיבות גדולה לשאלה האם הקלט נתון בבסיס 2 או בבסיס 1. המספר n בבסיס 2 דורש רק מספר לוגריתמי ב-n של ביטים לייצוג, בעוד שבבסיס 1 הוא דורש בדיוק n. לכן, אם מודדים את הביצועים של התוכנה בהתאם לאורך הקלט שקיבלה, תוכנה שהביצועים שלה עלובים למדי על מספר שנתון בבסיס 2 דווקא תפגין ביצועים מרשימים אם המספר נתון בבסיס 1 (לא בגלל שהתוכנה מתנהגת בצורה שונה, אלא בגלל שמה שאנחנו קוראים לו "ביצועים עלובים" משתנה).
בתור כדורגלן עבר 392873
דווקא מעניין בהחלט. לא שממש הבנתי, אבל...
בתור כדורגלן עבר 392885
דוגמה פשוטה: נניח שנתון מספר ואתה רוצה לבדוק אם הוא ראשוני, ועושה את זה עם אלגוריתם סופר נאיבי - עובר על כל המספרים שקטנים ממש מהמספר וגדולים מ-‏1 ובודק אם המספר מתחלק בהם בלי שארית. בוא נניח גם שבדיקת חלוקה כזו מתבצעת בזמן קבוע (לא הנחה נכונה, אבל לא משנה).

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

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

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

מה עשיתם לדיון הכדורגל התמים..עד שהיה דיון שלם שהבנתי..התחלתם עם שעשועים מתמטיים.

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

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

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

(דווקא אצלנו השוער היה סטטוס חברתי בפני עצמו. הבלמים, שעמם נמניתי, הם הבררה האמיתית - גם לא יודעים לשלוט בכדור בכלל ולכן אין להם סיכוי לתקוף, וגם יש את מי להאשים כשתוקעים להם גול).
בתור כדורגלן עבר 392898
גם חברת הביטוח מרוויחה, וזה אומר שהם צריכים שרוב המבוטחים יפסידו.
בתור כדורגלן עבר 392901
רק שבמקרה הזה, גם אם הפסדת - הרווחת.
בתור כדורגלן עבר 392903
מה הרווחתי?
בתור כדורגלן עבר 392906
לא נשרף לך הבית ואיבדת את כל רכושך.
בתור כדורגלן עבר 392914
ואם לא היית עושה ביטוח הוא כן היה נשרף?
בתור כדורגלן עבר 392916
כמובן. זכור את המטרייה והגשם.
בתור כדורגלן עבר 392917
מנקר בי חשד שהדיון הזה לא יוביל למקום טוב.
בתור כדורגלן עבר 392920
אז אגש לעניין. עד כמה שאני מבין, הימורים, כמו ביטוח, לא עושים בשביל להרוויח כסף. ביטוח עושים, בדרך כלל, בשביל ''השקט הנפשי''. הימורים עושים, בדרך כלל, בשביל הריגוש.
בתור כדורגלן עבר 392922
אז נראה לי קצת חבל להקדיש לזה כוח חישובי. תהמר על מה שמרגש אותך כמה שיותר (למשל, אם תהמר על האנדרדוג קרוב לודאי שתפסיד, אבל כשתצפה במשחק תתרגש הרבה יותר כשהוא יבקיע ראשון את השער, גם אם אח''כ הקבוצה האחרת תבקיע רביעייה).
בתור כדורגלן עבר 392923
אני חושב שזה מה שרוב המהמרים עושים.

מצד שני, אם יש דרך להשתמש ב"כח חישובי" בשביל להגדיל את הסיכוי לזכות, ולהפוך את כללי המשחק בינך לבין הקזינו, זה כבר סיפור אחר (ע"ע http://en.wikipedia.org/wiki/Edward_O._Thorp ו- http://en.wikipedia.org/wiki/Ken_Uston).
בתור כדורגלן עבר 392930
אני לפחות, עושה ביטוח קודם כל כדי להגן על עצמי מפני אסון שלא אוכל לעמוד בו. למשל, אם שריפה בדירה שלי תשרוף את הרמברנט של השכנים[*].

[*] אני אשמור על אלמוניותי הפעם כדי שאף אחד מכם לא ילך לבדוק.
בתור כדורגלן עבר 393000
אם לשכנים שלך יש רמברנדט בבית, אני מקווה שיש להם ביטוח משל עצמם.
בתור כדורגלן עבר 393019
ואת מי לדעתך חברת הביטוח שלהם תתבע?
אכן ביטוח הוא הגנה על סיכון 394730
הוא לא כדאי למי שיש לו מספר גדול מספיק של ''איברים'' כדי שחישובים סטיטיים יהיו אפקטיביים, לשם דוגמה אגד לא מבטחת את האוטבוסים שלה מעבר לביטוח ההכרחיים , חברת אוטובוסים פרטית כן, משום שאגד יכולה להסתמך על תוחלות והחברה הפרטית של שני אטוובוסים, תפסיד הרבה אם ינזק אטוובוס אחד.
כמובן גם שיש אלמנט של שינאת סיכון, כלומר שמעבר להסתברות רוב האנשים שונאים סיכון ומכונים לשלם על הגנה מסיכון
אכן ביטוח הוא הגנה על סיכון 394756
גם חברת אוטובוסים פרטית תיקח את הסיכון אם מחירי הביוח יהיו יקרים מאד, או אם הסיכון יהיה נמוך מאד.
בתור כדורגלן עבר 392897
אני דוקא מאד משועשע איך גם הדיון הזה נסחף אל המושכים המוזרים של האייל. גדי? הוא טיפס על עץ בעל התפצלות, או שמא היתה זאת התפלצות, הסתברותית, ולא יודע איך לרדת ממנו בלי השתברות של העצמות. הייתי נותן לו סולם, אבל יש לי רק סולם עם בסיס לא שלם ואני חושש מסיבוכיות חוקית.

אין לי מושג לגבי ווינר, אבל יש אתרים שפועלים ממש כמו הבורסה עם היצעים וביקושים וספר הוראות. העמלה היא אחוז מסויים מהצד המרויח.
בתור כדורגלן עבר 392890
מה זה "בסיס אחד"? אחד בכל חזקה הוא עדיין אחד, לא?
בתור כדורגלן עבר 392894
נכון. הרעיון הוא שכל מספר מיוצג על ידי מופעים של 1 כערכו. למשל 3 מיוצג על ידי 111 ואילו 8 על ידי 11111111. נשמע נורא, אבל זו שיטת ספירה לגיטימית (כבר הזכירו פה את האסירים, שתמיד מראים אותם מעבירים קו על עוד חמישייה).
בתור כדורגלן עבר 392900
גם הצגת מספר בגימטריה, או במספרים רומיים הם שיטות לגיטימיות לחלוטין. זה רק לא נראה לי כל כך ''על בסיס אחד'', במובן שזה לא באמת המשך אנליטי להצגות על בסיס שאר המספרים השלמים.
בתור כדורגלן עבר 392902
למה לא, בעצם? לי נראה שהוא מתאים לחוקיות שמאפיינת את שאר הבסיסים (כאשר זוכרים שיש רק סימן אחד שאפשר להשתמש בו).
בתור כדורגלן עבר 392908
אותה חוקיות גם קובעת שהסימן הזה יהיה אפס.
בתור כדורגלן עבר 392911
כן, נו, למה להתקטנן.
בתור כדורגלן עבר 392913
מספר הסימנים היא לא החוקיות היחידה (בספרות מאיה [http://he.wikipedia.org/wiki/%D7%A1%D7%A4%D7%A8%D7%9...] יש שלוש סימנים, אבל היא לא ספירה על בסיס שלוש, ובגימטריה יש 22 סימנים, אבל היא לא ספירה על בסיס 22).

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

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

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

לדעתי, מודולו העובדה שצריך להשתמש ב-‏0, אפשר לחשוב על הצגה בבסיס אונרי כמו כל הצגה בבסיס אחר: כדי לחשב את המספר המיוצג, כופלים כל אחת מהספרות בבסיס בחזקת המקום שלו במספר (מינוס 1) וסוכמים. במקרה של בסיס אחד, כל אחת מהספרות היא 1, וכל אחת מהחזקות גם היא 1.
בתור כדורגלן עבר 392924
כל הרעיון ב"המשך אנליטי" הוא שברור לך לגמרי איך אתה ממשיך. אם תיקח את ההצגה הדצימלית, ברור יהיה לך איך צריכה להראת ההצגה ההנדצימלית וכך הלאה.

מה זה "מודולו" עובדה?
בתור כדורגלן עבר 392926
אה, אם ככה, בסיס אונארי נראה לי בכלל בתור ''המשכה למטה'' של הבסיסים האחרים. אם זה מפריע לך - לא נורא. לא חייבים להסכים על הכל.

''מודולו עובדה'', בהקשר הזה, זו דרך אחרת לומר ''לא חייבים להסכים על הכל''.
בתור כדורגלן עבר 392899
אהמ... זה פחות או יותר מובן, אבל אני תהיתי יותר על השאלה מדוע זה חשוב בסיבוכיות כפי שתיארת אותה קודם.
בתור כדורגלן עבר 392905
חשבתי שאני מסביר את זה... תוכל לפרט?
בתור כדורגלן עבר 392909
אה, סליחה, בלבלתי את זה לרגע עם הוכחות אינטראקטיביות...
בתור כדורגלן עבר 392874
האם יש משמעות לבסיס לא שלם? נניח בסיס 1.001? אחד מרגעי ההארה שלי אירע כאשר הוסבר לי שאפשר להגדיר עץ עם יחס פיצול של 1+אפסילות ולפתח הפרעתית.
בתור כדורגלן עבר 392875
מהו "פיתוח הפרעתי"?
בתור כדורגלן עבר 392879
שיטה לקבלת קירובים משתפרים והולכים לבעיות שהם "קרובות" במובן מסוים לבעיות שפיתרונם המדויק ידוע.
למשל: רוצים לחשב את השורש החמישי של 40. אנחנו יודעים שהשורש החמישי של 32 הוא 2 ולכן
ננחש שהפיתרון הוא קרוב ל2 ( כלומר 2 + *הפרעה* קטנה שנסמנה ב e) כלומר:
40=(2+e)^5
קצת חשבון ( הבינום ) יראה לנו שעבור e קטן מספיק, אפשר לקרב את הביטוי כ
40=32+ 80*e

ומכאן אנו מקבלים פיתרון מקורב של e=0.1 ואכן, חזקה חמישית של 2.1 הוא 40.84101 , קירוב לא רע.

מי מבין את זה, עשוי גם להבין את זה
בתור כדורגלן עבר 392882
תודה.
בתור כדורגלן עבר 392877
אני לא מכיר, אבל אם יש מימד לא שלם אז למה לא.
בתור כדורגלן עבר 392881
כן. הפיתוח הופך להיות אז לא יחיד ומקבלים כל מיני תכונות מענינות בהתאם לתכונות האלגבריות של הבסיס.
בתור כדורגלן עבר 392884
זה קשור לcontinued fractions? ( לא יודע איך אומרים את זה בעברית. שברים מתמשכים?).
בתור כדורגלן עבר 392887
שברים משולבים. לא ידוע על קשר אבל מי יודע?
(כמו שאיזי ניחש) יש הרבה קשר לפרקטלים, כיון שהמידה המתקבלת אם מגרילים את הספרות לפי בסיס b באקראי היא המושך של מערכת ההעתקות (x/b, x/b+1).
סקירה מקיפה אפשר למצוא כאן:
בתור כדורגלן עבר 392886
דווקא את ''לפתח הפרעתית'' הבנתי, אבל נפלתי ב''עץ עם יחס פיצול''.
בתור כדורגלן עבר 392888
אני לא מצליח למצוא ברשת את המאמר שהדהים אותי‏1, אבל בגדול מדובר על מבנה של עץ, עם ענפים וכולי, שבמקום התפצלות של (נניח) 1->2 יש יחס של 1-->1.1 ענפים. איך? עד כמה שאני זוכר, מגדירים עץ עם התנהגות אקראית- בכל הזדמנות פיצול יש סיכוי מסוים לפצל את הענף, וסיכוי להמשיך ישר. בממוצע, מקבלים יחס "פיצול" של פחות מ2.

1 יכול להיות שבכלל מדובר על סריג היררכי ולא על עץ.
בתור כדורגלן עבר 392891
אם אין סיכוי ל-‏0 צאצאים, שאלת ההכחדה אינה רלוונטית.
בתור כדורגלן עבר 392892
מישהו דיבר על הכחדה?
בתור כדורגלן עבר 392896
אתה לא מוטרד מאפשרות ההכחדה?

(לא, אבל זה בד"כ הדבר הכי מעניין בתהליכי התפצלות)
בתור כדורגלן עבר 392915
כן, אם מסתכלים עליהם כ''תהליך''. מסתבר שמעניין לתת משקל לסוג מסוים של מהלך אקראי על עץ כזה ולשאול שאלות לגבי ההתפלגות של המשקלות.
בתור כדורגלן עבר 392927
נו, אתה לא יכול לתת תיאור כזה לקוני למישהו שזה התחום שלו. בקיצור: איזה מהלך אקראי? איזה משקולות?
בתור פיסיקאי עבר 392932
<אני כבר די חלוד בעניינים האלה.>
שים מספר אקראי (מהתפלגות חיובית‏1) על כל חיבור. הגדר על העץ מסלול שלא חוזר על עצמו (כלומר מסלול חד כיווני) בעל N צעדים. המכפלה של המספרים האקראיים לאורך המסלול היא המשקל של המסלול. מתעניינים ב(לוגריתם של) מומנטים של התפלגות המשקלות.
באופן מוזר, לא הצלחתי למצוא סקירה טובה ברשת. אתה יכול לנסות את פרק 5 בסקירה הבאה:
או לחפש על פי מילות המפתח שתמצא שם. אם חוסר הדיוק של הפיסיקאים מפריע לך, אתה יכול לנסות פה:
1 כן, גם עושים תרגיל דומה עם התפלגות מרוכבת ונדמה לי שאפילו עם מטריצות.
מה הבעיה? 393763
לך לפי ההוראות ב תגובה 392919
מה הבעיה? 394121
הבעיה היא שאני לא יודע כמה ספרות שונות יש בבסיס 1.1.
בתור כדורגלן עבר 392998
כבר דיברנו על כמעט זה, תגובה 222071
בתור כדורגלן עבר 393167
טוב, יש לי הצדקה, ניסיתי להראות "שימוש" לספירה בבסיס 1.

אגב, תוסיף עוד מישהו לרשימת הנאבקים במספרים גדולים שלך.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים