בתשובה לאופציונלי, 28/05/04 16:21
 |
|
 |
||
|
||||
 |
אתה מבלבל בין הסיבוכיות החישובית ובין החלק הקבוע (כמה זמן לוקח לגשת לדיסק/זיכרון). השימוש בנוטציה: O(n) על פי הגדרתו מתעלם מהקבוע.
|
 |
 |
 |
|
|
|
||
|
||||
|
השאלה כאן היא: מהם השימושים המעשיים למחשב קוונטי. שימושים כאילו יוכלו לגרום למוטיבציה מעשית למחקר. בוא נסתכל על חיפוש בתוך רשימה של 1000 רשומות: אם יש לך אלגוריתם שעובד ב־O(logn) אך עם קבוע של 10000 לעומת אלגוריתם שעובד ב־O(n) עם קבוע של 5, האלגוריתם השני יהיה יעיל יותר בפועל. זה מה שנקרא "O גדול מאוד של logn". |
|
|
|
|
|
|
||
|
||||
|
אפשר ואף רצוי להתעלם כאשר אתה מנתח אלגוריתם. אם אתה מתכנת אפליקציה בה אתה יודע מראש שהיא תתעסק בכמה מאות רשומות ולא יותר, אז בוודאי שיש חשיבות מסוימת (עד גדולה) לקבועים. אבל זה לא מה שה-O מנסה להגיד לנו. במקרה שהבאת מדובר בסה"כ במקרים לא מעניינים בהם ה-n מאוד קטן. אם ה-n גדול (ואלה המקרים המעניינים כשמדברים על חסם עליון) אז אפילו הקבוע 10000 הוא מאוד לא מרשים. עם n קטן אפשר לחפש באופן ידני בכרטיסיות ב-(אין)O (אפשר לאמר גם O של מיצמוץ). אתה בהחלט צודק אם אתה רק מתכוון לכך שה-O זה לא כל הסיפור וזה רק מדד שאומר *משהו* ולא נותן את כל התמונה (יש עוד מדדים). אך אם אתה חושב שאי אפשר להתעלם מקבוע גדול (כמו 10000 למשל) אז אתה טועה - אפשר גם אפשר. |
|
|
|
|
|
|
||
|
||||
|
איפה יש זכרון של יותר מ־10^12 רשומות? באופן כללי, כאשר אתה עובר את 10^6 אתה מתחיל להתקל במגבלות גודל הזכרון. ר' גם http://www.schneier.com/crypto-gram-0203.html#6 |
|
|
|
|
|
|
||
|
||||
|
הזיכרון מוגבל ל 57M ? ומה הקשר לזיכרון ? מה עם אלגוריתם של חיפוש רשומה בבסיס נתונים ? בסיס נתונים של עיריית ירושליים או תל-אביב יכול בקלות לעבור עשרות ג'יגה. ואז השאלה היא אם ייקח עשר דקות, חמש שעות, יומיים או חצי שנה להוציא דו"ח של כל התושבים בין גיל 30 ל 50 שיש להם פחות מארבעה ילדים, הכנסה ממוצעת של יותר מ8000 נטו וסך חובות לעירייה בארנונה ודו"חות חנייה שעולה על 10000 ש"ח. במצב הנ"ל מעבר לאיכות חומרה מסויימת הפרשים בזמן גישה לדיסק יהיו חסרי משמעות אם אלגוריתם החיפוש יהיה מספיק לא יעיל. |
|
|
|
|
|
|
||
|
||||
|
הכל טוב ויפה, אבל 12 בחזקת 10 זה 57G (ויכול להיות שהכוונה היתה בכלל 10 בחזקת 12 והעסק התהפך לו?). מה אנחנו מודדים בדיוק (בייטים? רשומות? ביסקוויטים?) גם לא ממש הבנתי. אגב, מה בא מהדיסק אל הזיכרון מתי וכמה, זה גם עניין לניתוח ולאלגוריתמים. גם פה הקבועים לא תמיד משחקים את התפקיד החשוב ביותר (מערכת הפעלה עם ניהול זיכרון וירטואלי או Process Scheduler לא יעיל, תהפוך את הכונן הקשיח, בעל זמן הגישה הקבוע המהיר ביותר, למטחנת בייטים רעשנית ואיטית למדי). עוד משהו שלא הבנתי זה *איפה* קיימת הגבלת הזיכרון לשיטתו. על מחשב ספציפי? על מערכת הפעלה ספציפית? זו לא דרך מחשבה שקצת מקובעת על מודל המחשב השולחני הבודד לשם פיתרון בעיות? _______ וכן! הצלחתי לשעמם את עצמי כבר באמצע התגובה. לחצתי על אשר רק כדי שלא אסבול לבד :) |
|
|
|
|
|
|
||
|
||||
|
כן, החזקות התהפעו להן. (לפי כיוון הטקסט דווקא כתוב שם 10 בחזקת 12, לא ברור לי למה הסימן "^" מתנהג שם כאילו הוא עברית. אתה צריך זכרון של המחשב הקוונטי. בשביל שאלגוריתם כזה יהיה מעשי אתה צריך קודם־כל לטחון את הדיסק כדי להביא את הנתונים הרלוונטיים לתוך הזכרון הקוונטי. (ואגב: הדיסק "טוחן" כאשר הקריאה אינה סדרתית בעיקרה. קריאת קובץ גדול תגרום בד"כ קריאה סדרתית שקטה יחסית) אם הרשומות הן בגודל בייטים, מה טוב. אם הרשומות גדולות הרבה יותר: הקבוע גדל בהתאם. כשהגדלים קטנים מספיק אז חישובים אסימפטוטיים אינם מועילים: הכל הוא O(1) |
|
|
|
|
|
|
||
|
||||
|
אני חושב שאתה מגזים (בכוונה?). מליוני רשומות (או יותר) זה בהחלט גדול מספיק בשביל שלחישובים אסימפטוטיים תהיה חשיבות מכרעת גם כאשר מעורבים קבועים ענקיים כמו C=10000(למשל, כבר בסביבות n=2^18 אלגוריתם ריבועי יתחיל לפגר אחרי ידידו שהוא NLOGN למרות היותו מוכפל בקבוע הענקי שדיברת עליו קודם C=10000). מבנה נתונים עם n=2^18 זה פיצ'פקס. להגיד שחישובים אסימפטוטיים אינם מועילים, זה כמו להגיד שחישוב ממוצע וסטיית תקן של ציוני הכיתה זה דבר שאיננו מועיל (מורים ומרצים, קחו לתשומת הלב!). מדובר במדדים שמספקים מידע לא שלם, בכך אין כל ספק, אבל הם בהחלט מדדים שאומרים *משהו* (חשוב). אתה מוזמן להתייחס אל הכל כאל קבוע, אבל אני לא חושב שתגיע עם זה רחוק במיוחד (מה עושים? כל פעם שיש רעיון לפתרון בעיה, מנחשים אלגוריתם באופן רנדומלי ורצים אל המחשב לתכנת ולמדוד אמפירית מה קורה בזמן ריצה?). לגבי החסם העליון של זיכרון, לא הבנתי בדיוק למה אתה מתכוון (אל חסם עליון במחשב ספציפי? אל חסם עליון במערכת מבוזרת? אל תיקרת הזכוכית?) ומה אתה בדיוק מכנה זיכרון (RAM? זיכרון וירטואלי? מדיה? זיכרונו של דובי קננגיסר בעל היכולות המפורסמות?). ברור שאם כל גישה להבאת נתונים תקח זמן קבוע של 20 שנה (או דקה וחצי) אז חישוב אסימפטוטי לא יעזור לנו יותר מדי באופן מעשי (אך מחקר תאורתי של אלגוריתמים המנותק ממגבלות טכניות הוא גם חשוב). אני לא טענתי משהו אחר. אני רק מתנגד פה לרעיון ה-"O no" ושקבועים זה הכל בחיים. איזו בעיה מיוחדת (לא טכנית רגעית, אלא תאורתית עקרונית) אתה רואה בהבאת נתונים אל זכרונו של המחשב הקוונטי? |
|
|
|
|
|
|
||
|
||||
|
נחשוב שוב בצורה מעשית: כמה קיוביטים צריך במחשב כדי שהאלגוריתם הזה יהיה יותר יעיל מחיפוש לינארי פשוט? באלגוריתמים כמו פיקטור, מכונה עם בערך אלף קיוביטים תהיה כבר מועילה למדי. הניחוש שלי שבמקרה של חיפוש ברשימה, הקבוע הוא מספיק גדול כך שאפילו חיפוש ברשימה של 10000 ערכים יהיה עדיין יותר מהיר באלגוריתם לינארי רגיל. כלומר: תצטרך מכונה קוונטית "גדולה" למדי כדי לנצל את האלגוריתם. צריך להתחשב גם בסיבוכיות המקום, לא רק בסיבוכיות הזמן... |
|
|
|
|
|
|
||
|
||||
|
הנה דיון שמישהו שאני עובד איתו מאוד אהב לנהל לא מזמן, עם כל מיני אנשים שלמדו מדעי המחשב ועובדים בתחום: "מה הסיבוכיות של חישוב N עצרת?" התשובה שכולם בלי יוצא מן הכלל (עד כדי חיפוש קאץ' ערמומי) עונים היא: פשיטא שליניארית (רצים על המספרים מ-1 עד N ומכפילים; N איטרציות, O של N). והתשובה הזו נכונה במושגים שבהם חושבים (ובצדק מסוים) מתכנתים. קצת מפתיע את כולם שהתשובה הזו, בלי שום קאץ' ערמומי, היא לא נכונה במושגים שלמדנו בקורס הבסיסי בחישוביות-סיבוכיות: הרי סיבוכיות נמדדת בגודל הקלט. גודל הקלט? *אורך* הקלט. זה כבר תלוי ייצוג: אבל בייצוג סביר, הקלט N מיוצג באורך של לוג N. ואם כך, מה סיבוכיות האלגוריתם באורך הקלט? נכון: אקספוננציאלית! למה כתבתי שיש "צדק מסוים" בלחשוב על התוכנית כלינארית? כי במושגים של מתכנת, הייצוג ואורך הקלט לא באמת מעניינים: המספר מיוצג באורך קבוע (נגיד, 2 בתים); מה שבאמת מעניין אותנו, לרוב, הוא מספר צעדי החישוב ביחס ל-N. על זה, כמובן, אי אפשר לבנות תורת סיבוכיות מעניינת, כי בהנחות האלו N ממילא חסום, ומכאן שגם משך ריצת התוכנית, והכל קורס ל-O של אחד. אבל זה מוסר ההשכל: יש הבדל בין הסיבוכיות של תאורטיקן תורת הסיבוכיות, לבין הסיבוכיות של מתכנת. לא? |
|
|
|
|
|
|
||
|
||||
|
לא בדיוק, לדעתי. המושגים של תורת הסיבוכיות הומצאו כדי להיות (גם) רלוונטיים, לא רק כדי לשעשע מתמטיקאים. בהקשר של חישובים אריתמטיים, אתה צודק שהכל קל (גם פירוק לגורמים...) אם המספרים חסומים, אבל זו לא כל כך השאלה: אלגוריתמים יעילים לפעולות אריתמטיות נעשים חשובים מאוד כשהמספרים גדולים, ובהרבה מצבים (מעשיים) אי אפשר להסתפק בגודל המילה של הקומפיילר. לא שאני רואה סיבה מיוחדת לחשב עצרת של מספר ענק... עם זאת, כמובן שיש הבדל בין סיבוכיות תיאורטית לסיבוכיות מעשית. בויכוח על חשיבות הקבועים שמתנהל כאן, אני מניח ששני הצדדים צודקים: יש חשיבות גם להתנהגות האסימפטוטית וגם לקבועים המעשיים. |
|
|
|
|
|
|
||
|
||||
|
"יש חשיבות גם להתנהגות האסימפטוטית וגם לקבועים המעשיים" זה מה שאני טוען (או לפחות מנסה). אני לא מבין את הערך שבבחירת O זה O זה. | |
|
|
|
|
|
||
|
||||
|
לא. היא אכן אקספוננציאלית, באופן מעשי ביותר. מתכנת חייב לקחת את זה בחשבון כשהוא מתכנת תוכנית שמבצעת עצרת, בלי שום קשר לעניין שיש או אין בתיאוריה, ואם גודל הקלט אינו חסום ויש אלטרנטיבה לחישוב העצרת - לבחור בה. לא? |
|
|
|
|
|
|
||
|
||||
|
לא נראה לי. אם אתה כבר נכנס לשיקולים כאלה, אז המשימה "כתוב תוכנית שמקבלת מספר ומחשבת עצרת שלו" לא מוגדרת היטב. לפעמים אינך יכול להניח שהקלט חסום בגודל הפרימיטיב שיש לך בשפה, אבל אז... מה תעשה? אם אתה כבר צריך להתחיל לחשוב על יצוג מתוחכם, עקב מגבלות הפרימיטיב, אז אתה עוד יותר צריך להתעסק בהנחות של פורמט הקלט ומגבלותיו. בקריירה הקצרה שלי כמתכנת, עוד לא יצא לי שהייתי צריך לחשוב על גדלים יותר גדולים ממה שנכנס לפרימיטיבים של השפה (חוץ מתרגיל אחד בלימודים, שזו היתה הפואנטה שלו). משאל בזק בקרב הלא-מעטים כאן שיצא להם לתכנת דבר או שניים: כמה פעמים זה קרה לכם? ובלי מתמטיקאים? |
|
|
|
|
|
|
||
|
||||
|
(כולל תרגיל אחד בלימודים, שזו היתה הפאנטה שלו). | |
|
|
|
|
|
||
|
||||
|
פעם, כשהייתי מתכנתת צעירה ונשואה באושר, היתה לי תכנית שרצה על מחשב, מודרני לזמנו, בו long, הפרימיטיב הגדול ביותר של שפת C, היה בן 32 ביט. השתמשתי במשתנה אחד לספור משהו-ים שהיו מהם כמה עשרות מיליונים ביום וכעבור מספר חודשים קרה הצפוי מראש. (אם הייתי משתמשת ב unsigned long הייתי קונה עוד כמה חודשים של שקט). בעיה שאני נתקלת בה לאחרונה, בנסיונות לחשב את קיצי לאחור, היא שבדקומפוזיציה של מטריצות גדולות, נופלים חלק מערכי הביניים בחישוב מתחת לגבול הדיוק של double. (למעשה זו אותה בעיה בשינוי אדרת). |
|
|
|
|
|
|
||
|
||||
|
אבל מה on earth גורם לאלמנה ויתום מן הישוב להגיע לעבודה בצהריים ולפצוח בדקומפוזיציה של מטריצות גדולות? 1 זה לא אני, זו הסקרנות. 2 "המשכורת" לא תתקבל כתשובה. |
|
|
|
|
|
|
||
|
||||
|
כשבעלי ימח שמו נפטר, הוא השאיר לי כירושה כמיליון וחצי שורות קוד (כתובות בצפיפות, בלי רווחים בין בלוקים, פונקציות וכו'). ''אלמנתי לעתיד,'' הוא אמר לי על ערש דווי, ''אם תפתרי את מעט הבאגים שנותרו, תהיה בידייך התשובה לאאאההה.....'' ולא יסף. מאז, אני והיתום (שהוא חירש וחיגר וגם לא חכם גדול) מנסים לתקן את התוכנה ולגלות את משמעותה של ''אאאההה'' |
|
|
|
|
|
|
||
|
||||
|
אני לא יודע מה זה דקומפוזיציה של מטריצות (זה LU וכאלה?), אבל מנסיוני בעסקים האלה, אם יש ערך ביניים שהוא מאוד קטן, בעוד שהתשובה הסופית סבירה, סימן שלא ביצעו את החישובים בסדר ה"נכון". נכון בהקשר הזה, הוא להשתדל לא להחסיר שני מספרים גדולים וקרובים אחד מהשני. אופציה אחרת, שמופיעה אף היא בתנ"ך ( כלומר ב NR), זה לשפצר את התוצאה המקורבת על ידי , נניח הצבה איטרטיבית. | |
|
|
|
|
|
||
|
||||
|
טוב, לי זה קרה. גיליתי להפתעתי (בעקבות דיווח על באג) שאלגוריתם שכתבתי עשוי באחד מהשלבים שלו, עבור קלט בתחום מסויים, לחרוג ממכסת ה32 ביט שהוקצבו למשתנים שהוא משתמש בהם. (התוצאה הסופית היתה תמיד במסגרת ה32 ביט) כמובן שזה גרר שגיאה גסה בכל פעם שהקלט היה בתחום הזה. הפתרון שלי היה מחפיר. חילקתי את הקלט ב2 לפני תחילת האלגוריתם ושיניתי את האלגוריתם בהתאם (אחרי שוידאתי שבאופן הזה לא תהיה חריגה) וכתבתי בתעוד של התוכנה שעבור הקלט תתכן סטייה של 1 מהערך המצופה. |
|
|
|
|
|
|
||
|
||||
|
אה, אם זה מה שאנחנו סופרים (Overflow), אז מן הסתם גם לי זה קרה מספר פעמים. אני פשוט לא הייתי סופר את זה כמקרה בו הפרימיטיבים של השפה לא מספיקים. בד"כ יש פתרון פשוט (או לפעמים מורכב) לרוב המגבלות שהשפה מציבה לנו (למשל, אפילו בפתרון המחפיר שלך שמחלק ב-2, היה מספיק לשמור במשתנה בוליאני,לפני החלוקה, את זוגיות המספר ואז גם אין סטייה של 1 מהערך המצופה). | |
|
|
|
|
|
||
|
||||
|
ומהו אותו משתנה בוליאני אם לא תוספת של ביט ל32 המקוריים? הפיתרון שלך שקול ללעבוד ב33 ביטים. | |
|
|
|
|
|
||
|
||||
|
זה בדיוק זה (הוספת ביט). מה רע? כל עוד אנו במסגרת של ה-O של 1 ביטים, השימוש בפרימטיבים הקיימים בשפה, בד"כ (כמעט תמיד?) מספיק. Long int לא מספיק בשבילך? השתמש בשניים (מצריך טיפול קל בהצגת תוצאות וחישובים, אבל הטיפול פשוט למדי). אבל אם השאלה הייתה "האם נתקלתם במצבים בהם הייתם צריכים להתמודד עם overflow" אז נראה לי שהתשובה הטריוויאלית היא: כן, מספר פעמים. |
|
|
|
|
|
|
||
|
||||
|
אין רע בפיתרון הזה, פרט לעניין אסתטי קטן: היה לו overflow אבל למעשה הוא פתר את זה על ידי הוספת ספרות בצד הקטן (LSB) של המספר. באופן טבעי מתבקש להוסיף ספרות דווקא לצד הגדול (MSB). בכל אופן, אם בבעיות עיגול מדובר, הנה טריק קטן שאני מאוד אוהב: נניח שצריך לחשב סכום של הרבה מספרים קטנים, אבל יש אוגר יחסית קטן. למשל: נניח שצריך לסכם אלף מספרים בין 0 ל 1023 אבל יש אוגר עם נניח 12 ביטים. ברור שכל יחידה של האוגר חייב לייצג 256 יחידות של הסכום ( הסכום המקסימלי הוא כמליון, אבל ב12 ביטים אפשר לייצג עד כ 4000 ). פרט לפיתרונות כמו הוספת עוד ספרות לאוגר או עוד אוגר ביניים ( שזה בעצם אותו דבר) מה אפשר לעשות? אפשר לעגל כל מספר בסכום לערכים 0, 256,512,768, ו1024, אבל אז מאבדים דיוק בצורה מחרידה. הטריק שלי הוא לעגל באופן *אקראי* כל מספר למעלה או למטה כך שב*ממוצע* יתקבל הערך המדוייק. כך למשל, את המספר 1 אפשר לעגל בהסתברות קטנה , של אחד מתוך 256 ל 256, ובהסתברות של 255 מתוך 256 לעגל כלפי מעלה ל 256. זה די פשוט לבצע את ההחלטה הזאת לגבי כל מספר לעצמו, על בסיס השארית בחלוקה ב 256, והשוואה למספר אקראי. |
|
|
|
|
|
|
||
|
||||
|
כמה מתכנתים בדיוק יש פה בקהל ?! | |
|
|
|
|
|
||
|
||||
|
אני קצת יודע לתכנת, אבל אני לא מתכנת, אם לזה התכוונת. | |
|
|
|
|
|
||
|
||||
|
אני מכיר אנשים שיודעים לתכנת ועובדים בזה שלא היו לגמרי מבינים מה כתבת שם. אני אפילו נמנה עליהם. |
|
|
|
|
|
|
||
|
||||
|
פרשתי זאת כבקשה להבהרה: קודם כל, הבעיה היא לא בעיה של *תיכנות* . אתה לא תהיה מתכנת טוב יותר אחרי שתבין את זה, רק בן-אדם טוב יותר :). תחשוב על הבעיה הזאת: אתה משלם למישהו משכורת לפי זמן, ויש ימים שמגיע לו 1.25 שח, ויש ימים שמגיעים לו 1.8 שח ואתה צריך להכניס לאקסל של החברה שלך כמה הוא הרוויח כל יום ובסוף החודש לשלם לו את הסכום. אבל, מעשה שטן, האקסל דפוק ומקבל ערכים רק בשקלים שלמים. מה תעשה? תכתוב על צטלה ותסכם בסוף החודש? זאת אפשרות טובה, אבל שלצרכינו לא רלבנטית. אולי תעגל ? ביום של 1.25 שח תרשום 1, ובים של 1.8 תרשום 2? זה לא רע, אבל כשהוא קולט את הפרינציפ , הוא מתחיל לזחול לכיוון ה 1.5001 שח ליום. רעיון אחר זה לשלם לו *בממוצע* את מה שמגיע לו: אם הוא הרויח 1.25 שח, תגריל מספר בין 1 ל100. אם יוצא קטן מ25, תרשום 2 שח, אחרת, תן לו 1 שח. אם כל יום בחודש הוא השתכר בדיוק 1.25 שח ליום, יש סיכוי טוב שהסכום שחישבת יהיה די קרוב ל30X1.25. אם הוא הרוויח ביום מסוים 1.8, תרשום 2 שח אם המספר קטן מ 80, ו 1 שח אחרת. ככל שיש יותר ערכים בסכום הזה, הדיוק היחסי שלך משתפר. |
|
|
|
|
|
|
||
|
||||
|
אם תבחר בשיטה הזו יש סיכוי טוב שתקבל תביעה על הלנת שכר מכל העובדים שיצא להם לקבל שכר נמוך מידי. העובדה שבסיכוי טוב את ההפרש קיבלו עובדים אחרים לא תעזור לך, ואם ימצא שאחד מהמצ'ופרים סטטיסטית הוא גם בן דוד שלך, העובדה הזו גם תפגע בך. בקיצור, תחליף אקסל. |
|
|
|
|
|
|
||
|
||||
|
מעבר לביקורת, שנתקבלה ברוח בה ניתנה, רציתי להבהיר שמדובר באותו עובד, שעבד הרבה ימים ולכן ההפרשים לא הלכו לעובדים אחרים. | |
|
|
|
|
|
||
|
||||
|
כלומר יש לך אוגר קטן מדי, אבל מצד שני יש בידך אפשרות לחשב הסתברויות בדיוק מלא. סיטואציה מוזרה, אבל פתרון נאה. | |
|
|
|
|
|
||
|
||||
|
מה מוזר? ראובן לא התכוון לכך שבאמת מדובר על מספרים קטנים כמו 1.25, זאת היתה דוגמא להמחשת הרעיון. | |
|
|
|
|
|
||
|
||||
|
לא, זה לא סיטואציה מוזרה בכלל: לחשב מספר אקראי זה חשב וזרוק. אין צורך לשמור את התוצאה, בחומרה זה אפילו די טריוואלי ( למשל- לחשב CRC של השעון). כמו כן אין צורך לחשב "הסתברות" - זה כבר נעשה מעצמו. הדיוק של החישוב האקראי תלוי בשיפור בדיוק שרוצים להשיג ביחס לעיגול דטרמניסטי רגיל. מצב קלאסי לשימוש באלגוריתם כזה הוא כאשר מגיעים מספרים אחד אחד, ויש לחשב את הסכום המצטבר. |
|
|
|
|
|
|
||
|
||||
|
הבנתי. בסיטואציה כזו זה אכן שימושי. | |
|
|
|
|
|
||
|
||||
|
לי היה פעם גרביל קטן. התוצאות לא היו יותר טובות משל ראובן. | |
|
|
|
|
|
||
|
||||
|
O(1)
|
|
|
|
|
|
|
||
|
||||
|
פתרון ממש יפה - ונראה שהוא גם אופטימלי בנתונים שהיו לך. אבל מצד שני הוא כנראה גם לא משפר יותר מדי (בהנחה שהמספרים שמהם התחלת התפלגו אקראית בתחום). לשם הנוחות, נניח שאתה מגריל אקראית מליון מספרים בין 0 ל- 101, ותסכם ערכים כאשר לכל מספר אתה בוחר אם לסכם 0 או 101. בשיטה ה"רגילה" של עיגול המספר, הטעות תתפלג באופן אחיד בין 50- ל- 50, מה שאומר שסטיית התקן של הטעות היא 29.155, ואחרי סיכום של מליון כאלו (חוק המספרים הגדולים - התפלגות נורמלית - ידה-ידה-ידה) תקבל טעות בעלת התפלגות נורמלית, עם סטיית תקן של 29,155. בשיטה שלך התפלגות הטעות הינה התפלגות "משולשת" בין 100- ל- 100, עם שפיץ בגובה כפול ממה שהוא "אמור" להיות ב- 0. כלומר, הסיכוי לטעות של 100 (או 100-) הוא 1 חלקי 101*102, טעות של 99 (או 99-) תתקבל בסיכוי של 2 חלקי 101*102 וכו'. טעות של 0 תקרה בסיכוי 2 חלקי 102, ולא 1 חלקי 102. סטיית התקן היא 29.011, ובסיכום של מליון מספרים - 29,011. לא הרווחת הרבה. הסיבה העצובה לחוסר הרווח שלך היא ש"מספרים גדולים פגיעתם גדולה", ובמקרה שלנו הטעויות הגדולות (של קרוב ל- 100) מזיקות מאד, אפילו שההסתברות להן קטנה - כי הם נכנסים בריבוע בחישוב התוחלת. אפשר לנקוט בפתרון ביניים שלא יאפשר טעויות גדולות בשום מקרה - למשל לעגל ל- 0 אם הערך קטן מ- 20 או ל- 100 אם גדול מ- 80, ובתחום הביניים לנקוט בשיטה שלך, אבל כנראה שזה לא יהיה יותר טוב. |
|
|
|
|
|
|
||
|
||||
|
הממ... נראה שהיתה לי טעות קטנה בחישוב (מרכין ראש בבושה) - לצערי היא דווקא לרעתך. בשיטה הרגילה גם כן יש סיכוי כפול ל- 0, ולכן סטיית התקן בסוף יוצאת 29,011 - *בדיוק* כמו בשיטה ה"משופרת" שלך (חבל, כי היא דווקא מאד יפה...). יוצא שאתה לא משפר כלום בהנחת התפלגות אחידה, וכנראה גם כל שיטות הביניים שתיארתי מניבות אותה תוצאה. עוד מקרה של רעיון יפה-אך-כושל נכנס לסטטיסטיקה... |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי את ההגיון שלך: אם ההתפלגות נורמלית, למה לסכם- תקע את הממוצע ושלום על ישראל. | |
|
|
|
|
|
||
|
||||
|
התכוונתי אחידה. בכל מקרה, אני משחק משחק שנקרא: נחש את הממוצע. השיטה הרגילה היא חסרת תוחלת ( pun intended) במקרה הזה. | |
|
|
|
|
|
||
|
||||
|
אני מעוניין לחשב את התפלגות הטעות (כלומר הסטייה של הסכום כמו שאתה מחשב אותו מהסכום האמיתי), כדי לראות אם הטעות באלגוריתם שלך קטנה יותר מהטעות באלגוריתם הפשוט יותר שהצגת. בשתי השיטות התוחלת זהה לתוחלת הסכום, ובשתיהן (בגלל שמדובר בסכום של הרבה משתנים ב"ת בעלי אותה התפלגות) מדובר בהתפלגות נורמלית, ולכן מה שמעניין זו סטיית התקן. As it happens, בשני המקרים סטיית התקן יוצאת זהה, ולכן בשיטה שלך לא מרוויחים כלום, אלא רק מפסידים (את הזמן שלוקח להגריל מספר, לחשב לאיזה כיוון צריך לעגל וכו'). | |
|
|
|
|
|
||
|
||||
|
במצב שההתפלגות היא אחידה,בין [0 ..101] לא מרוויחים כלום - מוסכם. אבל במצב כזה יש לי אלגוריתם עוד יותר פשוט: כתוב 50 כפול מספר האברים. הבעיה היא שאני לא יודע מראש את ההתפלגות או את הממוצע שלה ואני מנסה *לאמוד* את הממוצע. אתה עדיין מציע לי לעגל סתם? |
|
|
|
|
|
|
||
|
||||
|
1) במקרה של התפלגות אחידה (שהחישוב שלי התבסס עליו) שתי השיטות שקולות, ושיטת הכפלת הממוצע במס' האיברים טובה כמעט כמוהן. למעשה, במקרה כזה יש לי אלגוריתם טוב יותר: פשוט סכם את המספרים כמו שהם והתעלם מהגלישה. הסכום מתפלג נורמלית והתוחלת שלו ידועה לך - כך שאת ביטי ה- most של הסכום אתה ממילא יודע (בהסתברות מאד גבוהה). אם אתה מסכם מספיק מספרים ההסתברות לטעות היא ממש זניחה (אם כי במקרה של טעות - הטעות היא גדולה). 2) לא עשיתי את החישוב, אבל נראה לי שבכל מקרה של התפלגות ידועה השיטה שלך שקולה לשיטה של עיגול ל- 0 אם המספר קטן מהממוצע ול- 101 אם הוא גדול מהממוצע. 3) במקרה שההתפלגות אינה ידועה, או גרוע מכך - היא נבחרת על ידי מישהו בהנתן האלגוריתם במטרה למקסם את התוצאה (כמו במקרה העובד) - האלגוריתם שלך אכן יותר טוב. |
|
|
|
|
|
|
||
|
||||
|
אתה עדיין חושב שזה רעיון יפה אך כושל? | |
|
|
|
|
|
||
|
||||
|
לי היתה בראש בעיה שונה מהבעיה שאתה מנסה לפתור (כמו שאורי גוראל שם לב). עבור הבעיה שאתה מנסה לפתור הרעיון הוא טוב. | |
|
|
|
|
|
||
|
||||
|
אז נירגעתי :) מה הבעיה שאתה מנסה לפתור, אולי יש טריק גם כאן? | |
|
|
|
|
|
||
|
||||
|
כמו שכתבתי - אני חשבתי על המקרה שבו המספרים שאתה צריך לסכם מתפלגים אחיד בתחום מסוים ידוע. במקרה הזה נראה לי שהפתרון האופטימלי (זה שבו תוחלת הטעות היא מינימלית) הוא לסכם את כל המספרים ולהתעלם מהגלישה. ממילא אתה יודע את ביטי ה- most של הסכום, בהסתברות מאד גבוהה. לכן, בהסתברות מאד גבוהה תקבל את הסכום המדויק, ובהסתברות מאד נמוכה תקבל מספר שהוא רחוק מאד מהסכום (כי טעית בביטי ה- most של הסכום). | |
|
|
|
|
|
||
|
||||
|
אוקי, אתה מחפש מה שקוראים בעגה "variance reduction". למעשה, אתה יודע את הממוצע התיאורתי, ומעניין אותך לדעת כמה הראליזציה הזאת סוטה ממנה. שיטת העיגול הדטרמניסטית בעצם מודדת את האחוזון של הממוצע התיאורתי. במחשבה שניה, בכלל לא בטוח שהחשבון שעשית הוא נכון, כי לא לקחת בחשבון שהממוצע הנמדד סוטה מהממוצע התיאורתי. אני צריך לחשוב קצת על זה. |
|
|
|
|
|
|
||
|
||||
|
אם אתה מתכוון לחשבון שעשיתי לגבי הטעות במקרה שההתפלגות אחידה, אז הוא נכון: לכל מספר מגדירים מ"מ שהוא הטעות בעיגול של אותו המספר. בשיטה הדיפולטית (עיגול ל- 0 או ל- 101 ע"פ מי מהם שיותר קרוב למספר) מקבלים התפלגות כמעט אחידה בין 50- ל- 50: סיכוי של 1 ל- 102 לכל מספר, פרט ל- 0 שלו יש סיכוי של 2 ל- 102. תסכם הרבה כאלו ותקבל שהסכום שלך סוטה מהסכום האמיתי (הנמדד) בסכום הטעויות - שזה סכום של מ"מ ב"ת בעלי אותה התפלגות, כלומר מתפלג נורמלית עם סטיית תקן שקל לחשב. התוחלת של הטעות היא 0 (שים לב - זו תוחלת וסטיית התקן של ההפרש בין הסכום המחושב לסכום האמיתי, לא בין הסכום המחושב לתוחלת הסכום האמיתי). בשיטה שאתה הצגת לטעות יש התפלגות משולשית, עם סיכוי כפול ל- 0 (כפול מאשר גובה השפיץ, שהוא ב- 0). מקבלים אותה שונות בדיוק. אגב, גם את ההפרש מהממוצע התיאורטי קל לחשב: הטעות כאן תהיה 50.5- בסיכוי חצי, ו- 50.5 בסיכוי חצי, ואידך זיל גמור. |
|
|
|
|
|
|
||
|
||||
|
אני מודה שלא עקבתי אחרי החשבון. עניין של ריכוז, סליחה. לעומת זאת, יש לי טריק אחר שאולי יכול לשפר בשיטה "דיפולטית?" - בעצם אנחנו סופרים כמה נפלו מעל או מתחת לממוצע. בוא נגיד שנפלו N+A מעל לממוצע ו N-A מתחת לממוצע. אנו מנסים לאמוד את הסכום, על ידי עיגול ל 0 או 101,ולכן נאמוד את הסכום ב 101*(N+A). אבל בעצם יותר הגיוני לעגל ל 75 ו 25 ( אני מזניח מתוך עצלות את ההתעסקות עם 24.5 וכולי). זאת מכיוון שאנחנו יודעים שכל איבר שתורם ל 0 הוא בעל ממוצע 25. לכן, במקום לאמוד את הסכום ב 101*(N+A) ניתן לאמוד אותו כ 101 * N פלוס עוד 50*A . זה מקטין בצורה מהותית את השגיאה. |
|
|
|
|
|
|
||
|
||||
|
כן, אתה צודק. אם במקום לעגל ל- 0 או ל- 101 תעגל ל- 25 או ל- 75, התפלגות הטעות תהיה אחידה בין 25- ל- 25 במקום בין 50- ל- 50 (בערך, כמובן), ולכן סטיית התקן תקטן בשורש 2, וכך גם הטעות הממוצעת. אבל בכל מקרה, השיטה הכי טובה במקרה של התפלגות אחידה (אני חושב) היא לסכום ולשכוח מהגלישה. אגב - סתם מחשבה: אפשר לעשות משהו דומה גם בשיטת העיגול המוטה שלך? אפשר לחשוב על עיגול ל- 25 אם המספר קטן מ- 25, ל- 75 אם הוא גדול מ- 75 ולעיגול הסתברותי בתחום הביניים - אבל זה לא יעזור כנגד העובד הרשע שיעבוד 0שעות בכל שבוע וידרוש שכר של 25 שעות שבועיות... אולי אפשר להתאים את טכניקת העיגול באופן שאי אפשר יהיה להרוויח (בתוחלת), אבל הטעות תקטן (שוב בתוחלת)? לא חשבתי על זה יותר מדי. |
|
|
|
|
|
|
||
|
||||
|
פתרון ממש יפה - ונראה שהוא גם אופטימלי בנתונים שהיו לך. אבל מצד שני הוא כנראה גם לא משפר יותר מדי (בהנחה שהמספרים שמהם התחלת התפלגו אקראית בתחום). ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ נראה שזאת בדיוק ההנחה ממנה הוא רצה להמנע. כדי שלא לבזבז הודעה שלמה על אסף הנה חידה לכולם (חוץ מאסף, שמכיר): האם קיים גוף קמור שניתן לשים מסביבו טבעת עגולה קשיחה כך שאי אפשר לשחרר אותה (מבלי לשבור אחד מהם)? |
|
|
|
|
|
|
||
|
||||
|
אתה יכול להזכיר מה זה גוף קמור ( אין קו בין שתי נקודות על המעטפת שעובר בחוץ?). | |
|
|
|
|
|
||
|
||||
|
ההגדרה הרגילה היא: כל קטע המחבר כל שתי נקודות השייכות לגוף נמצא כולו בגוף. בגופים "סבירים" זה שקול להגדרה שנתת. אני מניח שאורי התכוון גם לומר שהגוף חסום (כלומר, מוכל כולו בכדור כלשהו), שכן אחרת ישר או גליל אינסופי הוא פתרון קל מדי. |
|
|
|
|
|
|
||
|
||||
|
תודה, איכשהו זה מזכיר לי את החידה של איך לגלגל בלי גלגל ששאלת לפני כמה זמן. | |
|
|
|
|
|
||
|
||||
|
נו... באחת וחצי בלילה אין צורך לאמר חסום, זה הולך ללא פתגם. בקיצור, שכחתי. |
|
|
|
|
|
|
||
|
||||
|
האם משטח כדורי עם חורים בשני הקטבים נחשב טבעת? (כנראה שלא, אחרת זה טריויאלי) |
|
|
|
|
|
|
||
|
||||
|
טבעת משמעותה טבעת. קבוצת הנקודות <x,y,z> המקיימתz=0 או משהו איזומורפי לזה.
x^2+y^2=1 |
|
|
|
|
|
|
||
|
||||
|
אה, טבעת זה בכלל משהו חד ממדי, שלא כמו טבעת מוביוס למשל. טוב, מישהו כאן צועק ''טטראדר'' ובדמיוני המרחבי המוגבל זה נראה כאילו הוא צודק. |
|
|
|
|
|
|
||
|
||||
|
בינתיים בניתי דגם מנייר, ובאמת הטבעת לא משתחררת. | |
|
|
|
|
|
||
|
||||
|
קח כוס חד פעמית, ולחץ על שפתה העליונה עד שהיא הופכת לקו ישר. החתך המקביל לבסיס של הגוף שנוצר הוא אליפטי, וטבעת אליפטית שמתלבשת על הכוס המעוותת שלנו לא יכולה להפרד ממנה כי הרדיוס הקטן של קטן מרדיוס הבסיס, והרדיוס הגדול קטן מה"רדיוס" של האליפסה השטוחה (במלים אחרות: חצי אורכו של הישר שיצרנו). בניגוד לטטראדר, את זה קל, יחסית, לצייר. הטבעת האליפטית האדומה לא ניתנת להפרדה מהכוס. הנה כך: |
|
|
|
|
|
|
||
|
||||
|
וראה איזה פלא, הרי זהו המשועיגול המפורסם (אני חושב שזה השם): מכיוון ראייה אחד עיגול, מכיוון שני ריבוע, ומשלישי משולש. | |
|
|
|
|
|
||
|
||||
|
וזה לא בדיוק יוצא. למה שיוצא יש לקרוא משוטרפמשהו, כיון שתקבל משולש, טרפז ומעין מעוין-מעוגל-שתי-פינות. ואפילו זה לא בדיוק. |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
החידה בכלל נראית כשייכת לתחום ההתמחות של גיל רונן. | |
|
|
|
|
|
||
|
||||
|
רק עתה נתקלתי בזה. רעיון יפה מאוד! | |
|
|
|
|
|
||
|
||||
|
"מחשבים טועים, הם לא מושלמים ולא כל יכולים, והטכנולוגיה לא תפתור לאנושות את כל הבעיות. כך מזהיר פרופ' דוד הראל, חתן פרס ישראל ודיקן הפקולטה למתמטיקה ומדעי המחשב במכון ויצמן. בספרו החדש הוא מזהיר: תוכנות לעולם יכללו באגים." "אבל אלגוריתם מבריק ככל שיהיה עלול להוביל לתוצאות הרסניות, למשל עקב כתיבת קוד עם שגיאות. פרופסור הראל מזכיר, למשל, את התפרקות הטיל הצרפתי אריאן 5 ביוני 1996, פחות מדקה אחרי שיגורו. הסיבה היתה שגיאה בשורת קוד, שניסתה לטעון מספר בן 64 סיביות במחשב שגודלו 16 סיביות בלבד, וגרמה לתוכנית לקרוס." הודעה חשובה לקוראינו בחו"ל: בעוד שלושה ימים יתפרסם הקישור של אפופידס. |
|
|
|
|
|
|
||
|
||||
|
אם מקבלים את "תוכנות לעולם יכללו באגים" כאמת, אז אולי יש אכן טעם להוציא את המשפט הנדוש "מחשבים לא טועים, אנשים טועים" לפנסיה. אבל זה בברור לא נכון, לא? נדמה שיש תוכנית או שתיים שעובדות כמו שצריך (=כמו שכותביהן התכוונו שתעבוד), ובכלל מה אפשר וצריך לעשות עם הצהרה כמו זו? אם הסיכון שבשליחת טיל לחלל אינו שווה את הרווח האפשרי, לא צריך לשגרו בלי שום קשר לשאלת ה-"באגים - הכרח או לא". |
|
|
|
|
|
|
||
|
||||
|
כלוא בתוך הפרימיטיב שלי. אבל מה אני אגיד לכם... לא כ''כ רע פה. יש מספיק מספרים בשביל כל מה שאני צריך. מדי פעם עוברים פה אנשים ומספרים לי סיפורים על העולם הגדול שמעבר לפרימיטיב. אבל מה אני אגיד לכם... זה לא בשבילי. אני - שים אותי בתוך הפרימיטיב שלי - ואני מאושר. |
|
|
|
|
|
|
||
|
||||
|
יונפק סטיקר "אני פרימיטיב גאה!"1 וישא"ק. ________ 1 כן כן, גם הפרימיטיבים האלה החליטו סוף סוף לצאת מהארון. |
|
|
|
|
|
|
||
|
||||
|
מקרה אחד של חישובים במספרים גדולים (חתימות דיגיטליות). מספר מקרים של התחשבות במספר ביטים שאי אפשר לחרוג ממנו (לשלוח ביטים דרך לווין עולה הרבה כסף) אבל לא מעבר לפרימיטבים של השפה. והמקרה המוכר מכולם - שעון המערכת של unix סופר 32 ביט שניות מאז 1.1.1970 כך שיגמרו לנו השניות בשבוע הראשון של פברואר 2038. הגדרת המשתנה כ-unsigned תשיג לנו הארכה של ביט נוסף, כלומר, עד השבוע השני של מרץ 2106. ואז... נעבור ל-64 ביט. |
|
|
|
|
|
|
||
|
||||
|
מתוך http://osl.iu.edu/~tveldhui/papers/Template-Metaprog... Here's a simple example which generates factorials at compile time: ושהקומפילציה תיעשה בלילה אוטומטית :-)
template<int N> class Factorial { public: enum { value = N * Factorial<N-1>::value }; }; class Factorial<1> { public: enum { value = 1 }; }; |
|
|
|
|
|
|
||
|
||||
|
כאמור, היה מי שהוכיח כי templates שקולים למכונת טיורניג: תגובה 199024. | |
|
|
|
|
|
||
|
||||
|
חשבתי שאמרת את זה על ה preprocessor לבד ! דמיט פיזרתי דיס-אינפורמציה בשבועות האחרונים... |
|
|
|
|
|
|
||
|
||||
|
שיקול מעניין. ומה הסיבוכיות של *סכום* כל המספרים עד N? | |
|
|
|
|
|
||
|
||||
|
כמו הסיבוכיות של חיבור 1, כפל שני מספרים, וחילוק ב-2. בקיצור, כמו כפל. | |
|
|
|
|
|
||
|
||||
|
ידעתי שמישהו יתחכם. תחליף ''חיבור'' ב''פעולה שאין נוסחה סגורה לחישוב'' למשל חיבור ההופכיים ( מחושבים לדיוק יחסי מסויים). | |
|
|
|
|
|
||
|
||||
|
אז לא הבנתי. תלוי בסיבוכיות של ה"חיבור". אם אין איזה טריק מיוחד, אתה עושה N פעמים את הפעולה, לא? | |
|
|
|
|
|
||
|
||||
|
לעשות פעולה N פעמים זה סיבוכיות אקספוננציאלית בN. אני רק רציתי להאיר את העניין בלי להשתמש בעצרת, שיש לזה קוננוטציות של משהו (סופר) אקסספוננציאלי בלאו הכי. מה שמחזיר אותי למחשב הקוונטי- האם ניתן להגיד שמחשב קוונטי מחליף את הסיבוכיות של החישוב בסיבוכיות של הכנת הקלט? הרי צריך לאתחל שתיים בחזקת N קטים כדי לבצע חישוב. |
|
|
|
|
|
|
||
|
||||
|
לעשות פעולה N פעמים זה סיבוכיות אקספוננציאלית ב*אורך של N*, כלומר אקספוננציאלית ב*לוג N*, כלומר *לינארית ב-N*. לא ללכת לאיבוד, ולא להתבלבל בסימנים! |
|
|
|
|
|
|
||
|
||||
|
גם אתה נודניק? שיהיה ב*אורך* של N אם זה מרגיע אותך. הכוונה הייתה שאורך הקלט הוא לוג N ומספר הפעולות הוא N, בדיוק כמו שירדן כתב. לא ללכת לאיבוד, ולא להוציא דברים מהקשרם. |
|
|
|
|
|
|
||
|
||||
|
אני חייב להיות נודניק. זה כתוב בכתובת המייל שלי :-) ------ אביב, שכתב כבר הרבה יותר מידי בשביל סו"ש אחד, והצליך לעבוד על עצמו עם מלכודת האיילים, למרות שהוא כותב רק ממחשב אחד. הוא מפסיק עכשיו. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שיש כאן בלבול קטן: הקונטציה ה(סופר)-אקספוננציאלית של עצרת היא בגלל אלגוריתמים שהם ב"סיבוכיות עצרת", לא בגלל חישוב עצרת כשלעצמה. אבל אתה צודק שיש נטיה לבלבל בשנייה הראשונה (גם אצלי), ולכן, מבחינה דרמטורגית, עדיף לשאול את השאלה על אלגוריתם יותר טריוויאלי. | |
|
|
|
|
|
||
|
||||
|
אני לא יודע אם יש צדק מסוים בתשובת המתכנתים, ואני גם לא חושב שמוסר ההשכל שלך הגיוני. התכנית שהמתכנתים חושבים עליה לא תעבוד לרוב המספרים מאחר ויהיה overflow אם יכניסו לה בתור קלט מספר גדול מ 30. רק בשביל לכתוב את העצרת של מספר בן 32 ביטים צריך משהו כמו 2 בחזקת 37 ספרות. (בערך 4 גיגה-בייט). |
|
|
|
|
|
|
||
|
||||
|
יש בזה משהו; זה בסך הכל מחזק את טענתו של ראובן מתגובה 222186, שמוטב לבחור דוגמה אחרת מחישוב עצרת. הנקודה שרציתי להעביר רלוונטית לכל חישוב שעושה איטרציות במספר הנתון בקלט. אני חושב שאבחר בתוכנית שמקבלת מספר N, ומדפיסה N עותקים של "בוקר טוב עולם". | |
|
|
|
|
|
||
|
||||
|
אני לא ממש זוכר את ההגדרות, אבל איפה אורך ה *פלט* בא לידי ביטוי? במקרה שהגדרת, אורך הפלט הוא O(NlogN וסיבוכיות החישוב היא פולינומיאלית (אני בכוונה נמנע מלהגיד ליניארית - לא התחשבת בזמן שלוקח לבצע פעולת כפל במספרים בעלי אורך לא חסום...) באורך הפלט. לשיטתך גם תוכנית הממירה מייצוג בינארי לייצוג אונארי של N עובדת בזמן אקספוננציאלי...
|
|
|
|
|
|
|
||
|
||||
|
נכון. הזמן הנדרש לכתיבת הפלט נחשב כחלק מזמן החישוב. זה אפילו באמת לוקח זמן. אני זוכר כל מיני שאלות בחישוביות שכדי להמנע מהבעיה הטכנית הזו דרשו שהקלט יהיה מספר אונארי |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |