 |
מותר הקיוביט מן הביט? | 1950 |  |
||||||||
 |
|
 |
|||||||||
 |
 |
פרסומים אחרונים במדור "מדע"
|
| הצג את כל התגובות | הסתר את כל התגובות |
|
|
 |
||
|
||||
|
"ראינו שהוא טוב כדי לפצח צפנים, אבל ניתן להניח שברגע שיהיה קיים מחשב כזה יעברו לשיטות הצפנה שחסינות בפניו". למעשה, אפשר להוכיח (ואף הוכיחו), שמרגע שיש מחשב קוונטי עם קו תקשורת שיכול להעביר קיוביט אחד בדיוק כל פעם, אפשר להצפין לחלוטין הודעות. באמצעות אלגוריתם קידוד (חפש בגוגל את BB84, הגרסה הראשונה שהוצגה) אפשר להעביר מפתח סודי שאורכו כאורך ההודעה שרוצים להעביר, ולהצפין את ההודעה לגמרי. מסתבר שהדרישה המהותית כאן היא הדרישה לקיוביט אחד בדיוק כל פעם - באמצעים של היום, כשמעיבירים פוטונים מקוטבים, לפעמים יוצאים שניים ביחד, ועל בסיס זה אפשר כן לפצח את האלגוריתם. |
|
|
 |
|
|
|
||
|
||||
|
לגבי הצפנה קוונטית, כאן בפרוש כבר מדובר בבעיה טכנית בלבד. אין צורך במחשב קוונטי בשביל ההצפנה והפענוח (מחשב רגיל יספיק) בתנאי שיש קו תקשורת (קלאסי ולא מוגן) בין המצפין והמפענח. | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שהבנתי. או שאתה טוען שמחשב רגיל יכול לעבוד עם קיובטים (אני לא חושב שהוא יכול), או שאתה טוען שמחשבים רגילים יכולים ליצור בצורה בטוחה מפתח באורך ההודעה תוך תקשורת ביניהם (בלי להסכים מראש על מפתח), דבר שאני לא מכיר ולא חושב שאפשרי כיום. גיגלתי קצרות, והנה לינק: |
|
|
|
|
|
|
||
|
||||
|
הצפנה קוונטית ניתנת לביצוע ע"י מכשור מתאים שלא כולל מחשב ומצפין 0 ו1 במצבים קוונטיים ומפענח אותם בחזרה. המחשב משמש רק ליצירת ההודעה לפני הצפנתה ולהצגתה לאחר פענוחה. (קשה לאנשים לקרוא ולכתוב בבינארית) | |
|
|
|
|
|
||
|
||||
|
עם שיטת ההצפנה הזו יש רק בעיה אחת: היא טובה רק לאורך קו מאובטח אחד. אי אפשר סתם להשתמש בה על מדיומים שונים. לדוגמה: תקשורת מחשבים אפשר לבצע אפילו באמצעות יוני דואר (RFC2549, לדוגמה). בשנות הארבעים הוצעה דרך דומה (ופשוטה) להסתרת התוכן של שיחת טלפון: מקבל ההודעה מוסיף רעש אקראי על הקו. מכיוון שמקבל ההודעה יודע מהו הרעששהוא הוסף, הוא יכול לסנן את הרעש הזה. כל מאזין אחר על הקו לא יכול לסנן את הרעש. והנה מה שיש לברוס שנייר להגיד בנידון: |
|
|
|
|
|
|
||
|
||||
|
השיטה של שנות ה40 יכולה לעבוד רק אם 1. הרעש הוא אקראי לחלוטין ו2. חזק הרבה יותר מהשיחה, (שאחרת אפשר להפריד ביניהם בגלל שלשיחה יש איפיונים סטטיסטיים שונים מרעש סתם). אז מעשית זה לא כל כך אפשרי כי "התחום הדינמי" של קו הטלפון לא מאפשר את התנאי השני. בכ"ז הצפנה דיגיטלית עדיפה על "טריקים" כאלה. | |
|
|
|
|
|
||
|
||||
|
אם אני לא טועה, בהתחברות ישירה לקו טלפון (לא בהקלטה) ניתן להפריד את כל האינפורמציה שמגיעה מקו א' לקו ב' מהאינפורמציה שזורמת בכיוון ההפוך. כך שהמסר ה"מוצפן" למעשה גלוי לחלוטין, כי הוא מופרד מהרעש. אני אסביר למה אני חושב ככה: אם לא, ניתן ליצור הצפנה כזו מאובטחת ב-100% (למרות שנאבד ביט יחיד מדי פעם). הרעיון הוא כזה: כל יח' זמן קבועה (לצורך המחשה, נגיד שנייה אחת) כל אחד משני הצדדים בשיחה בוחר באופן אקראי האם ליצור צליל, או לא. אם הוא בחר ליצור צליל, הוא יבחר באופן אקראי תדר מסוים לצליל, מבין כמה מאות אפשרויות. אם ב"שנייה" מסוימת שני הצדדים השמיעו צלילים, או ששניהם לא השמיעו צלילים, הם יתעלמו מאותה "שנייה". במידה ונשמע רק צליל אחד, הרי ששני הצדדים יודעים מי שלח אותו, אבל המצותת לא. לכן, הם יכולים לקבוע שאם צד א' שלח - אז כל אחד ירשום 0. אם צד ב' שלח - אז כל אחד ירשום 1. כך, הם ייצרו מפתח OneTimePad שיהיה מוסכם על שניהם, אבל המצותת לא יוכל למצוא אותו! כמובן שבשנייה שבה שניהם שלחו צליל, אך הוא היה מאותו תדר, הביט יתפספס. אך אם שולחים את אותו מידע פעמיים, הסיכוי שמידע יאבד - זניח. |
|
|
|
|
|
|
||
|
||||
|
לדעתי ,(תקן אותי אם לא הבנתי אותך) ,גם רעיון הצפנה אנלוגית כזו הוא מסוכן מבחינה פרקטית, כי ניתן להבחין בין שני הצדדים על סמך זה שהמצותת יושב בדרך כלל קרוב לאחד משני הצדדים ואז הוא מבחין 1) בהבדלי עוצמה. 2) בהדלי זמני התגובה לאיתותים. למעשה הטענה שלי היא שלא ניתן במכשור הקיים ליצוא הצפנה אנלוגית טובה בגלל אי הדיוק המובנה לתוך ציוד כזה. | |
|
|
|
|
|
||
|
||||
|
1) אני לא בטוח לגבי יכולת ההבחנה בין הצדדים. אני רק משער. 2) אינני יודע עד כמה הבדלי העוצמה ניכרים. חוץ מזה, אולי גם ניתן לקבוע את העוצמה המקורית של אותו צליל באופן אקראי? 3) אפשר לגרום למחשב שיושב בכל צד של הקו לא להגיב לאיתותים. את הזמן בו צריך לשלוח את הצליל המחשב ימדוד לבד. 4) ניתן להעביר ברשת הטלפון מידע בדיוק טוב מאוד (האיכות של קו מטלפון שאינו אלחוטי היא מצוינת!). כל המידע באינטרנט עובר דרך רשת הטלפון. 5) לגבי יכולת ההפרדה בין קול אנושי לבין רעש, יש לי רעיון: ניתן להסוות (באמצעים דיגיטליים) את הקול האנושי לרעש, וכך הוא יאבד את תכונותיו הסטטיסטיות. מחשב בצד השני של הקו יפענח את ההצפנה (שהוא עצמו הצפין) וימיר אותו חזרה לקול אנושי. |
|
|
|
|
|
|
||
|
||||
|
ברגע שאתה משתמש באיתות דיגיטלי ,ז"א 0'ים ו 1'ים שמומרים לסט סופי של אותות חשמליים , (שיכולים להיות למשל תדרים שונים כמו שאמרת) ניתן להגיע לדיוק מדהים כל זמן שאינך משדר יותר ביטים לשנייה ממה שקרוי "חסם שנון". אינני מתווכח איתך על שיטות כאלה. הטענה שלי היא שבשיטה שבה מועבר האינפורמציה באופן רציף (אנלוגי) קשה מאוד להצפין. טענות 2-5 אצלך מייצגות איתות דיגיטלי ולא רלוונטיות לשיטה שהוצגה בראש הפתיל שהיא אנלוגית. | |
|
|
|
|
|
||
|
||||
|
אתה לא מבין את המשמעות. בוא נגיד שאני אירגון צבאי שנמצא במתיחות גבוה עם צבא מעבר לגבול. אני כצבא אירגוני , בעל מטרה בלעדית לאיסוף מודיעין על האויב, אני מאזין לכל תדר או נתונים שעפים מהעבר השני, ושומר אותו באיזה ארכיון עד שאצליח לפצח. בוא נניח שהם היום בבעית חוסר הספק , אז ברגע שנכנס המחשב החדש, כל חוסר ההספק הקיים נעלם , ונוצרת תמונת מצב מאוווד מעמיקה על האויב--> מודיעין ! וצבא לא משתנה בשנה, עד היום סובלים "מדליפות" ממלחמת כיפור. |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח שפיענוח כל המידע ממלחמת מאה השנים יכול לעזור לצבא האנגלי כיום. | |
|
|
|
|
|
||
|
||||
|
thats a good point, however, it's true even today, without quantom computing.
that is, computers today could decrypt all the data from 1989, for instance, with little effort. why not do that? the reason it's not done, IMO, is that most of the encrypted data is not something readily available, just waiting to be decrypted. I think it's mostlly transmitted underground, with real cables (or fiber optics), and not running freely in the air. |
|
|
|
|
|
|
||
|
||||
|
על סמך מה הקביעה שחומר מ- 1989 אפשר לפענח? | |
|
|
|
|
|
||
|
||||
|
waht was computationally (Hisoviut-wise) impossible 15 years ago, is now possible. If in the 80's you'd use a 64 bit key (since on 80's computers it would take a million years decrypting it), decrypting a 64 bit encryption on a strong computer today should take less then a week (and I'm very cautious here. I think it should take less then an hour. maybe a computer science guy would like to comment on that.)
|
|
|
|
|
|
|
||
|
||||
|
אפשר להניח שאנשי 1989 הבינו את העניין הזה, וחישבנו את אורכי המפתחות שלהם כך שיחזיקו מעמד גם נגד המחשבים של היום. | |
|
|
|
|
|
||
|
||||
|
האם שמעת פעם על באג 2000? | |
|
|
|
|
|
||
|
||||
|
עד כמה שזכור לי, אנשי ההיי-טק גרפו רווחים נאים מהבאז סביב הבאג, ככה שזה כנראה היה באינטרס שלהם. | |
|
|
|
|
|
||
|
||||
|
ברור, ברור, מתכנתי הקובול של שנת 1970 בבנקים הגדולים היו בלבניסטים, רק שאני לא מצליח להבין אם הם היו מתבדלים או שתלבנים. | |
|
|
|
|
|
||
|
||||
|
תביא עוד שתי ספרות (בשביל התאריך) ואני מגלה לך. | |
|
|
|
|
|
||
|
||||
|
decrypting a 64 bit encryption on a strong computer today should take less then a week יש כשש-מאות אלף שניות בשבוע, בערך שתיים בחזקת 19. ויקיפדיה יודעת לספר ששיאן העולם במספר-פעולות-נקודה-צפה-לשנייה (flops) נכון לראשית נובמבר השנה הוא IBM Blue Gene, שמשיג בערך שתיים בחזקת 46 flops. בשביל לעמוד בזמנים, אתה צריך להיות מסוגל לבדוק כל מפתח ע"י 2 פעולות נקודה צפה (בהנחה שאין לך משהו יותר טוב לעשות מאשר לנסות את כל המפתחות). זה לא נראה לי מעשי.
|
|
|
|
|
|
|
||
|
||||
|
כבר שאלתי את זה כאן פעם, אבל אם אנחנו מדברים על נושאים טכניים, אני אנסה שוב: איך בדיוק בודקים מפתח? הרי לא מספיק לנסות ולהשתמש בו בתוך אלגוריתם הפיענוח - איך תדע שהפלט שקיבלת הוא הודעה מפוענת ולא ג'יבריש? הרי אין תקן לפיו בשורה הראשונה תמיד כתוב "ברכותי, פיצחת את ההצפנה שלי!" לי נראה שכדי לבדוק האם הטקסט המפוענח "עושה היגיון" צריך להשקיע הרבה יותר זמן ומשאבים מאשר בבדיקת המפתח נטו (ואת הזמן הזה אפשר להגביר עוד יותר באמצעות כל מני "טריקים" - למשל, הצפנה כפולה כך שיש בחירה אקראית של אלגוריתם ההצפנה שבו מצפינים את הטקסט, שבעצמה נעשית על פי Seed שמוצפן בעצמו). וכל זה רק כשהאובייקט המפוענח הוא טקסט. מה אם זה קובץ תמונה? |
|
|
|
|
|
|
||
|
||||
|
מה קרה בפעם הקודמת ששאלת? נראה לי שאתה עושה סלט בין מצבים שונים מאוד: פענוח כשידוע אלגוריתם ההצפנה (*כל* האלגוריתם) ולא המפתחות, ופענוח כשגם האלגוריתם לא ידוע. אם ה"הצפנה הכפולה" שתארת ידועה למפענח, אין הבדל בינה לבין הצפנה "אחת"; אם לא, המצב באמת קשה, ובמקרה הכללי (מפתח חד-פעמי) קל לראות שאין שום דרך לפתור את הבעייה. בסופו של דבר, מחרוזת הנושאת אינפורמציה - טקסט, תמונה, אודיו, לא חשוב - היא לא חלקה סטטיסטית. מבין כל המערכים של פיקסלים בגודל 640 על 480, חלק מזערי עד מאוד הם כאלה שמצוייר בהם משהו, איך שלא תגדיר "משהו". |
|
|
|
|
|
|
||
|
||||
|
אני יכול לחפש את הדיון הקודם שוב, אבל אמרו בו בערך אותם דברים. בוא נדבר קודם על מה שקורה כשאלגוריתם ההצפנה ידוע לחלוטין. במקרה זה, לבדוק מפתח ייקח הרבה יותר מאשר שתי פעולות, לא? אתה צריך להפעיל אלגוריתם כלשהו שיבדוק את החלקות הסטטיסטית של הפלט שקיבלת. זה אומר שצריך לעבור על חלק מהפלט (לא על כולו, אני מניח - אבל אז אפשר "להתחכם" ולהכניס קטעי רעש לתוך מה שמצפינים כדי לבלבל את הבודק). לכן, העסק נראה לי הרבה יותר מורכב מאשר סתם "לבדוק את כל המפתחות". כל בדיקה של מפתח עושה רושם של סיוט לא קטן בזכות עצמו, אלא אם תגלה לי שבדיקת חלקות סטטיסטית היא פשוטה מאוד. עכשיו בוא נדבר על ה"הצפנה הכפולה" שתיארתי. למה לדעתך אין הבדל בינה לבין הצפנה אחת? אנסה להציג יותר בבירור את מה שאני אומר כאן: ראשית, לוקחים מספר אקראי בתור Seed עבור הגרלה שבה מחליטים באיזה אלגוריתם הצפנה להשתמש. את המספר הזה בעצמו מצפינים עם אלגוריתם שידוע לכולם, וכך מי שמפענח צריך קודם כל לגלות מה המספר (כדי לדעת מה האלגוריתם) ורק אז להשתמש באלגוריתם הנכון עם המפתח כדי לפענח את הקלט. מכיוון שה-seed שלנו הוא מספר אקראי, אי אפשר פשוט "לבדוק חלקות סטטיסטית", כי זה מראש מספר אקראי. לכן, הדרך היחידה לעקוף את זה היא בכלל לא לחשב את ה-seed, אלא לבדוק כל מפתח עבור כל אלגוריתם הצפנה אפשרי. לכן השאלה היא כמה אלגוריתמי הצפנה יש. כאן זו כבר שאלה טכנית למביני דבר בהצפנה: יש משפחות של אלגוריתמי הצפנה שלכל אחת יש "מספר מאפיין" משלה, כמו שנניח יש עבור פונקציות ערבול? או שאולי כל משפחה כזו היא בעצם אלגוריתם הצפנה בווד עם "מפתח כפול" - גם ה-seed, וגם המפתח שבו משתמשים להצפנה עצמה. יצא מאוד מבולבל. אולי אחרי שאני אלמד קצת קריפטוגרפיה אני אוכל להתנסח יותר טוב (או שכבר יהיו לי תשובות לשאלות הללו). |
|
|
|
|
|
|
||
|
||||
|
לחלק הראשון: בעיקרון, זה נכון, וזו גם הסיבה שאני ספקן לגבי הערכת הזמנים של גלעד. כדאי לזכור, עם זאת, שיש לא מעט מצבים בהם קטעים מסויימים (נגיד, הפתיחה) של ההודעה הם קבועים וידועים (נגיד, חלק מהפורמט של הקובץ המוצפן). במקרה כזה יש מעט מאוד עבודה לעשות אחרי ניחוש המפתח וסימלוץ ההצפנה. הרבה מהדיון התאורטי בהצפנה נעשה תחת ההנחה הזו, במידה רבה של צדק (זיהוי הפענוח הוא בעייה נפרדת, המכפילה באיזשהו גורם, תלוי במקרה, את הזמן הדרוש). לחלק השני: אכן יצא מבולבל. אולי תסביר מה עושה אלגוריתם הצפנה, ומה זה מפתח? ייתכן שמה שיסדר לך את המחשבות הוא הנתון שבהרבה אלגוריתמים יש כמה רמות של מפתחות (אחד שמתחלף בכל הודעה ומצורף אליה, אחד שמתחלף פעם ביום, אחד יסודי ומסובך שמתחלף פעם בחודשיים, וכו'). אני לא מבין את ההבדל בין הצפנה אחת מורכבת להצפנה "כפולה". |
|
|
|
|
|
|
||
|
||||
|
בכל הנוגע לחלק הראשון: אני מסכים בהחלט שמבחינה תיאורטית יש חשיבות נמוכה לשאלה איך בודקים האם הצלחנו לפענח את הקלט, אבל הרי בבחינה המעשית עסקינן. ננסה לנסח שוב את החלק השני: אלגוריתם הצפנה לוקח קלט (ה-plaintext) ומייצר פלט (ה-ciphertext) תוך שימוש במספר כלשהו, שהוא המפתח. כדי להפוך את התהליך צריך מפתח (לא בהכרח אותו אחד, וזה מה שקורה בהצפנת מפתח ציבורי). עכשיו, נניח שיש לנו לא אלגוריתם אחד, אלא משפחה של אלגוריתמים. המשותף לכולם הוא שהם משתמשים באותו סוג של מפתח (כלומר, בהינתן מפתח מסויים להצפנה ומפתח מסויים עבור פיענוח, כל אחד מהאלגוריתמים יעבוד כראוי איתם). לכאורה, המלאכה של מפצח ההצפנה היא עכשיו כפולה. לא מספיק לו להשתמש באלגוריתם הפיענוח עבור כל המפתחות האפשריים, הוא צריך גם לעשות את זה עבור כל אלגוריתם הצפנה אפשרי. השאלה היא איך בוחרים את האלגוריתם מתוך המשפחה. כאן זה כבר סיפור טכני. אני מכיר רק RSA כדוגמא להצפנת מפתח ציבורי, ולא ברור לי האם ניתן להשתמש בשיטות מפתח ציבורי אחרות עם אותם מפתחות ש-RSA עובד איתם. ממה שידוע לי RSA עובד עם מפתח "נועל" שהוא מספר גדול שהוא מכפלה של שני ראשוניים, ועם מפתח "פותח" שהוא שני המספרים הראשוניים עצמם. השאלה היא האם אפשר להשתמש באותם סוגי מפתחות בדיוק באלגוריתמים אחרים. למשל, אם אלגוריתם GAG הדמיוני משתמש לצורך ההצפנה דווקא במספר שהוא מכפלה של שתי חזקות גבוהות של שמונים ושלוש, ומפענח עם שתי החזקות הללו, אי אפשר להשתמש באותם מפתחות הן עבור RSA והן עבור GAG. לכן, הכי הגיוני הוא שהמשפחה כולה תהיה של אלגוריתמים מאותו הסוג, שאופן התנהגותם תלוי בפרמטר מספרי כלשהו שמועבר אליהם (וזה המספר שמוגרל). ב-Hash functions עושים דבר דומה אם אני לא טועה, כשרוצים לעשות Re-hasing. השאלה היא האם יש הבדל מהותי בין ה"התחכמות" הזו ובין הרחבה פשוטה של המפתח. כדי להגדיר לך מה זה "הבדל מהותי" אני אצטרך ללמוד קודם קריפטוגרפיה. |
|
|
|
|
|
|
||
|
||||
|
אני לא חושב שיש הבדל מהותי. פשוט שינית את המפתח ממספר, למפתח שהוא שרשור של מספר ואלגוריתם. עדיין נשארת עם מחרוזת אחת בתור מפתח כשלקבוצת המפתחות האפשריים-תאורטית יש בדיוק אותה עוצמה. | |
|
|
|
|
|
||
|
||||
|
תקן אותי אם אני טועה, אבל מכיוון שכל מפתח הוא מספר שלם סופי, הרי שכל קבוצה אינסופית של מפתחות אפשריים תהיה בת מנייה. השאלה היא האם ניתן ''לסבך הרבה'' באמצעות ''מעט מפתחות''. גם את שני המושגים הללו אני לא יודע להגדיר לך כמו שצריך. תזכור בכל מקרה שאני מדבר כאן על מה שקורה באופן פרקטי, לא תיאורטי. מבחינה תיאורטית זה לא ממש משנה אם אתה מוחק את סימני הזיהוי הבסיסיים מהקובץ שאתה מצפין (מכניס ''רעש'' בהתחלה, למשל, ככה שלא יוכלו לבדוק אם ההקדמה היא מה שמצפים לו), אבל מבחינה מעשית זה יכול לסבך די הרבה את הליך הבדיקה העיוורת. |
|
|
|
|
|
|
||
|
||||
|
המשפט הראשון הוא מקרה פרטי של מה שהתכוונתי. מכיוון שכל מפתח (ולצורך העניין גם מספר + אלגוריתם נחשב מפתח) הוא מחרוזת סופית, הרי שכל קבוצה אינסופית של מפתחות אפשריים תהיה בת-מניה, וזה כלל לא משנה איך תסבך את המפתח. אם אני מבין נכון, הטענה שלך למעשה היא ש"סיבוך" המפתח ע"י הפיכת הסיפא שלו לבחירת אלגוריתם, יהיה יעיל יותר מאשר "סיבוך" ע"י בחירת מפתח דומה אך גדול יותר. אני כלל לא בטוח שאתה צודק. בכל מקרה, הטענה "לכאורה, המלאכה של מפצח ההצפנה היא עכשיו כפולה. לא מספיק לו להשתמש באלגוריתם הפיענוח עבור כל המפתחות האפשריים, הוא צריך גם לעשות את זה עבור כל אלגוריתם הצפנה אפשרי." אינה נכונה, מהטעמים שהראיתי. | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שהבנתי (או שאני מסוגל להבין) את הטעמים שהראית, אבל בכל מקרה שים לב: בדיקת מפתחות לא נעשית על קבוצה אינסופית, אלא רק על קבוצות סופיות (שהרי המפתחות מוגבלים בגודלם). נראה לי שהשאלה מצטמצמת לשאלה הטכנית "האם בדיקה של עשרה מפתחות על ידי אותו אלגוריתם זהה בזמן שהיא לוקחת לבדיקה של מפתח אחד על ידי עשרה אלגוריתמים" ואין לי מושג מה התשובה לשאלה הזו (אני מנחש שאין תשובה חד משמעית, אבל זה משחק דווקא לטובתי) |
|
|
|
|
|
|
||
|
||||
|
אתה מסוגל להבין (ולפי הפיסקה השניה כנראה שגם הבנת), הידע שלי בנושא לא גדול משלך. סופיות קבוצת המפתחות לא משנה לעניינו; אתה מציע לקחת מפתח ולהוסיף לו סיפא של בחירת אלגוריתם. אני טוען שהרווח מכך כנראה שלא יהיה גדול מהרווח שבהגדלה "רגילה" של המפתח. | |
|
|
|
|
|
||
|
||||
|
נתראה אחרי שאני אקח קריפטוגרפיה, או לפחות אלמד עצמאית את הנושא יותר ברצינות. | |
|
|
|
|
|
||
|
||||
|
משהו יכול להסביר לי דבר אחד קטן משץמשים ב SHA לMessage Digest אבל אם הMESSAGE מגיעה ל ?TRUDDY והוא רוצה לשנות מה בעיה שישנה ואז יעשה את כל התהליך וישלח את MESSAGE עם שה חדש |
|
|
|
|
|
|
||
|
||||
|
טרם לקחתי את הקורס בקריפטוגרפיה, אז אני לא מסוגל לפענח את ההודעה שלך. | |
|
|
|
|
|
||
|
||||
|
יש כל מיני שיטות. למשל, בין הפשוטות, יש מילונים מיוחדים, שבודקים ביעילות אם הטקסט המופענח מכיל מילים המופיעות במילון. הגיוני יותר, לבדוק דברים יותר מתוחכמים, כמו האם התוכן המפוענח מתאים בכלל לפורמט מוכר (של טקסט, של תמונה וכו') לפי זיהוי של תבניות ידועות פחות או יותר, ועל בסיס סטטיסטי. |
|
|
|
|
|
|
||
|
||||
|
טוב, אני צריך לרדת לעובי הקורה הטכני כדי להתייחס ברצינות למה שאתה אומר - כמו למשל מה זו בדיוק תבנית ידועה ואיך מזהים אותה בצורה שתמנע מהמצפין לעבוד על הבדיקה בקלות (תעלול פרימיטיבי במיוחד שאני יכול להמציא על המקום בתור דוגמה הוא להשתיל אות רנדומלית על כל שלוש אותיות, כשהאות הרנדומלית נבחרת מבין אלו שיש להן שכיחות נמוכה, מה שידפוק את שכיחויות האותיות בקובץ המפוענח ויבטיח שאף מילה בו לא תימצא במילון) | |
|
|
|
|
|
||
|
||||
|
השיטה הזו, ומן הסתם כל שיטה אחרת שתחשוב עליה, היא בסך הכל הצפנה כפולה. | |
|
|
|
|
|
||
|
||||
|
משום מה, מי שיודע לא מדבר. מה שפחות ברור זה למה מי שלא יודע כן מדבר. | |
|
|
|
|
|
||
|
||||
|
נכון, אבל כאן נכנסת עוד הנחה שאני לא מבין עד הסוף - שאנחנו כבר יודעים מה אלגוריתם ההצפנה ורק מחפשים את המפתח. בהצפנה כפולה, איך המפענח יודע מה בדיוק לעשות כדי להפוך את הטקסט לבעל משמעות? הוא צריך לדעת לשם כך מה הייתה ההצפנה שהשתמשו בה מעבר לשיטה המקורית (גם מה השיטה המקורית הוא לא צריך לדעת, אבל אפשר להניח שהוא יודע אותה שכן המפענח המיועד של ההודעה צריך לדעת אותה). כלומר, קל לומר "הצפנה כפולה", אבל לא ברור לי למה זה לא מגדיל בהרבה, יותר מפי שתיים, את קושי הפיענוח. |
|
|
|
|
|
|
||
|
||||
|
הו, לא. לא שוב... תגובה 211062 |
|
|
|
|
|
|
||
|
||||
|
הדיון ההוא לא ממש נגמר אף פעם, אלא רק חוסל טכנית. כאמור, כדי להשתתף בו אני צריך להבין מה מאפיין הודעה ''חלקה'', ועד כמה קל להנדס הודעה ''לא חלקה'' כדי שתיראה חלקה. | |
|
|
|
|
|
||
|
||||
|
אם לא הבנת מהי הודעה חלקה, למה לא שאלת אז? אתה רוצה כאן קורס מזורז בתורת האינפורמציה, או שאתה מעדיף מרצה בשר-ודם על-פני מכונת טיורינג מפוקפקת? (זה קל מאוד מאוד "להנדס" הודעה לא חלקה כך שתיראה חלקה. הטל-נא מטבע 50,000 פעמים וחבר את התוצאות (מודולו 2) לביטים של ההודעה שלך. אולי התכוונת לשאול, כמה קל להנדס הודעה לא חלקה כדי שתיראה חלקה, אבל כך שניתן יהיה גם להעביר מפתח באורך סביר לשותף שלך כדי ש*הוא* יוכל לקרוא אותה. לזה קוראים "הצפנה"). |
|
|
|
|
|
|
||
|
||||
|
לא כולנו סטודנטים בטכניון, ולא לכולנו תהיה אפשרות לעמוד מול מרצה בשר דם וקואלה ולשמוע אותו מעביר קורס על תורת האינפורמציה. אתה יכול לעזור לאלא שסיימו את לימודיהם לפני שהקואלות החליפו את בני האדם ולהסביר לנו מה זה הודעה חלקה (או, לפחות, איך כותבים את זה באנגלית שנוכל לשאול את דוד גוגל)ץ | |
|
|
|
|
|
||
|
||||
|
"הודעה חלקה" היא כזו שלא ניתן להבדיל מן התוצרת של קוף המקשקש על מכונת כתיבה (לפני שיצאו לו כל כתבי שייקספיר). אם נניח שההודעות שלנו מורכבות מסיביות (0 או 1), אז הרצף כולל 0-ים ו-1-ים בהסתברות שווה, אבל גם 00, 01, 10, ו- 11, וכן הלאה. | |
|
|
|
|
|
||
|
||||
|
תודה. כשאתה אומר "לא ניתן להבחין", אתה מתכוון מבחינה סטטיסטית בלבד? ברמה של הסתברות הופעת רצף בלבד? האם מדובר בהסתברות שווה באמת, או עד כדי שגיאה מסוימת (אם אני אראה הודעה שכל הרצפים האפשריים יופיעו בה בהסתברות שווה לשאר הרצפים באותו אורך, אני מאד אחשוד ולא אאמין שייצר אותה קוף)? |
|
|
|
|
|
|
||
|
||||
|
לא ניתן להבחין מבחינה סטטיסטית. יש הבדל תאורטי חשוב בין "אקראי" ל"פסאודו-אקראי" (הראשון הוא אקראי באמת, השני רק לא ניתן לאבחנה מרצף אקראי באמצעות מבחנים סטטיסטיים עם שגיאה בסיכוי אפסילון ועוד דברים טכניים מסוכנים כאלה). עלית על מבחן לא רע: אם בהודעה באורך (נאמר) מליון בתים (בית = 8 סיביות) מופיע כל בית בשכיחות של מליון חלקי 256 בדיוק, סימן שזו *לא* הודעה אקראית (קופים לא סופרים את האותיות ואומרים לעצמם שבינתיים צ' לא הופיע מספיק). |
|
|
|
|
|
|
||
|
||||
|
שמעתי כבר הרבה השערות על זהותו האמתית של שייקספיר, אבל רק עכשיו אני מבינה שזו בעצם אחת מהן. | |
|
|
|
|
|
||
|
||||
|
כל אחד עם האמת שלו. | |
|
|
|
|
|
||
|
||||
|
את מכירה את ההשערה לפיה לא שייקספיר כתב את המחזות המיוסחים לו, אלא אדם אחר שבמקרה נקרא באותו שם? | |
|
|
|
|
|
||
|
||||
|
זה אמור להצחיק, אבל בעצם זה לא ממש בדיחה. יכול להיות שהאדם שמזוהה עם שייקספיר באופן היסטורי הוא לא אותו אדם שכתב את המחזות. למשל יש קריין ברדיו בשם מנחם פרי, אבל הוא לא הפרופסור לסיפרות הידוע. | |
|
|
|
|
|
||
|
||||
|
לא, גם את זה לא שמעתי. ההשערות שאני מכירה הן שמדובר בבן דוד שלו, בכל מיני אנשים אחרים (כולל אישים אחרים) מאותה תקופה, שאינני זוכרת את שמותיהם כרגע - ואפילו את ההשערה שכתבה את כתביו המלכה אליזבט... | |
|
|
|
|
|
||
|
||||
|
ואני זוכר מהדורת חדשות ברדיו, שאני יכול לתארך אותה לאוגוסט אבל לא בטוח באיזו שנה - משהו בסדר גודל של 85, שבה דווח על מחקר שטוען ששייקספיר היה ערבי בשם השייח זוּבּיר. מחברו של המחקר הוא אחד, הקולונל מועמר קדאפי. | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
אה... את זה לא היכרתי. מרשים. אבל למען האמת, נראה לי שרק חוקרים מעטים מאמינים היום שאת כתבי שייקספיר אכן כתב שייקספיר. (אם כי אינני יודעת מניין בא הספק). |
|
|
|
|
|
|
||
|
||||
|
הליבה של תאוריית הקונספירציה השקספירית (חסידי סטרטפורד מול חסידי אוקספורד) נעוצה בחוסר ההתאמה שבין תוכן יצירתו לבין פרטי הביוגרפיה שלו (הדלילים למדי). אביא רק 2 דוגמאות: 1. יצירות שקספיר בנויות על ידע נרחב למדי של ארועים ודמויות היסטוריות ומיתולוגיות קלאסיות, בעוד ביוגרפית לא ידוע על שום השכלה פורמלית של שקספיר. 2. שקספיר כתב מחזה שמשבח או לכל הפחות עוסק גם בהשכלת נשים (אילוף הסוררת), ובכלל הנשים שלו לפעמים משכילות (פורשיה מן הסוחר מונציה) ותמיד רהוטות (ליידי מקבת למשל) בעוד בנותיו שלו לא ידעו אפילו קרוא וכתוב. המפורסם מבין השקספירים ה"תחליפיים" הוא כריסטופר מרלו, כותב ומחזאי אחר (וגם סוכן חשאי), בן תקופתו של שקספיר שהיה משכיל הרבה יותר ממנו. (למגינת ליבם של ה"בלשים": מחזות מרלו (הידוע שבהם הוא "טמבורליין") נחשבים נחותים מול היצירה השקספירית, שקספיר המשיך לכתוב לאחר הרצחו של מרלו, ואאל"ט השניים גם מזכירים זא"ז במכתביהם). תאוריה נפוצה אחרת, מדברת על קיום בו זמנית של שני אנשים בשם ויליאם שקספיר (אחד הסוחר הבור מסטרטפורד והשני המחזאי והמשורר המשכיל מאוקספורד). על תאוריית המלכה אליזבת לא שמעתי, אבל היא נשמעת מעניינת, שכן המלכה אליזבת ה-I (המלך החשוב ביותר של בריטניה) קיבלה השכלה מצויינת, היתה כותבת מוכשרת במיוחד וגם נעזרה במכתביה ובמסמכיה בשרשרת יועצים משכילים ומוכשרים במיוחד. באופן אישי, אני חושב שכתיבה קולקטיבית של מחזות היתה יותר נפוצה בזמן שקספיר מאשר חושבים. יתכן שאיש אחד כתב מחזה או חלקים ממנו וכותבים אחרים הוסיפו או שכתבו את המחזה או חלקים ממנו (בערך כפי שתסריטים נכתבים היום), כך שלא בהכרח כל מה שמופיע במחזות של שקספיר נכתב ע"י כותב אחד ויחיד. יתכן ששקספיר היה זה שעבר אחרון על הטקסט, דאג לאחידות הטקסט וחתם עליו. |
|
|
|
|
|
|
||
|
||||
|
מרלו ובייקון נשמעים לי מועמדים בלתי סבירים בעליל, בגלל ההבדל האדיר בסגנונם. ו"אילוף הסוררת" עוסק בהשכלת נשים? לא זכור לי דבר כזה. בכל מקרה, מה שאדם "מטיף" לו בכתיבתו ומה שהוא עושה בביתו... הקשר לא תמיד ישיר. איך זה לא שמעת על "מועמדותה" של המלכה אליזבת? היא מופיעה גם בלינק שנתת.:) האמת היא שלטעמי, במידה שכותב המחזות היה ידוע גם בשמו האמתי, היא באמת נשמעת לי המשכנעת ביותר. אבל תחושתי היא שמדובר באדם שלא היה מוכר בשמו האמתי. מ אידך גיסא, מה אני יודעת... אמור נא, סתם מתוך סקרנות - אתה למדת הסטוריה, פיסיקה או שניהם? |
|
|
|
|
|
|
||
|
||||
|
נראה שאני זוכר את ההיסטוריה שלא למדתי, הרבה יותר טוב מאשר את הפיסיקה שלמדתי. "אילוף הסוררת" - אני לא ממש זוכר את העלילה, אבל קתרינה היא בודאי מה שקוראים היום "דעתנית". אם זכרוני אינו מטעה אותי היא גם חובבת ספרים ומצטטת מתוכם בויכוחיה עם פטרוצ'יו המחזר. ושוב אאל"ט כל העלילה שם מלאה במורים אמיתיים ומתחזים של קתרינה ו/או ביאנקה אחותה. נראה לי ששקספיר התעניין יותר בהיבטים הדרמטיים של מחזותיו, מאשר בלקחים המוסריים שאפשר להפיק מהם (כך שקספיר האנטישמי כתב את המונולוג של שיילוק). באותה מידה אני בספק אם אפשר להגיד שאילוף הסוררת משבח את מעלותיה של הצייתנות הנשית. אני לא חושב שמישהו הבקיא אפילו מעט במחזות שקספיר יתקשה להביא דמויות של נשים אינטליגנטיות ואפילו משכילות ממחזותיו. בכל אופן, ברור שיהודית שקספיר, ביתו שחתימת ה-X שלה מופיעה על אישור הנישואין שלה, בודאי לא היתה האבטיפוס של ליידי מקבת, פורשיה ואפילו לא של יוליה, אופליה או דזדמונה. בכל זאת קשה להבין כיצד בנותיו של מחזאי, שחקן ומשורר הן כל כך חסרות השכלה, בפרט שמחזות שקספיר מצטיינים בין היתר גם בנפח ובעומק של תפקידי הנשים ולא תמיד בהקשרים רומנטיים. יכול להיות שההסבר הוא קצת אחר. כל הדמויות הללו על הבמה לא היו אלא נערים מחופשים, כך שיתכן שההשראה לדמויות אלו באה למעשה מגברים צעירים. בגלל השפה קשה לדעת, אך נדמה לי שחלק מן הסונטות של שקספיר נקראות כשירי אהבה הומוסקסואליים. למעשה אני לא ממש מאמין בכל התאוריות הללו, ההוכחות לקיומם של בייקון או מרלו אינן מרובות מן ההוכחות לקיומו של המחזאי שקספיר. המלכה הזקנה בס נראית לי, מועמד מעניין אבל לא סביר. לא ידוע לי על כל נטייה או עניין תרבותי מיוחד שהיה למלכה. דוקא יורשה ג'ימס ה-I (בנה של מרי סטיוארט) היה חובב תאטרון וחובב שקספיר בפרט. אני חושב שגם האמירה המקובלת כי אריסטוקרטים התביישו לפרסם בשמם יצירות שנועדו לתאטרון ההמוני, נראית לי מופרזת. לא זכור לי שהנסיך המלט התעניין במיוחד בשאלה למי יש ליחס את השורות שהוא כתב לשחקנים הנודדים. |
|
|
|
|
|
|
||
|
||||
|
טוב, נשים דעתניות, משכילות ואינטליגנטיות מאוד מופיעות ברבים ממחזותיו של שייקספיר - אפילו יוליה בת ה-14, למשל, או גיבורת "מהומה רבה" (ששכחתי את שמה). לגבי אליזבט ה-1, דוקא אם אינני טועה היא הייתה אישה משכילה מאוד, ובלי ספק אינטליגנטית ביותר. לגבי ההומוסקסואליות, יש הקוראים כך את כל הסונטות של שייקספיר, אבל זה נראה לי עניין של אופנה. בכל אופן, העובדה שכל שחקניו היו גברים, לא ממש שייכת לעניין. בסופו של דבר, זו הייתה המוסכמה התיאטרלית של התקופה. נשים לא שיחקו על במות ציבוריות. ואני לא בטוחה אם שייקספיר התעניין יותר בהיבטים הדרמטיים של מחזותיו. ודאי שהוא כתב דרמות סוחפות, אבל הכניס בהן הרבה מאוד הגיגים פילוסופיים (לא בהכרח שלו, יש להודות - גם חלק מאלה הוא לקח מהיוונים - רק הפליא לנסח אותם). |
|
|
|
|
|
|
||
|
||||
|
לגבי ההשכלה והאינטלגנציה של המלכה בס, לא תמצאי מי שיחלוק עלייך, אך הם התבטאו בתחומי השפות, הידע הגאוגרפי-היסטורי-תאולוגי, ההבנה הפוליטית-כלכלית, הבעה בכתב ובע"פ. בתחום התרבותי נראה שעניינה היחיד היה בתחום המחולות. נדמה לי שהטענות ששקספיר היה ביסקסואל הן יותר מאשר אופנה. צריך לזכור ששקספיר היה שחקן מקצועי, והומוסקסואליות סמוייה או פעילה באנגליה הפוריטנית לא היתה נדירה ובפרט בתחום התאטרון, גם מפני שכל השחקנים היו גברים. שקספיר הכניס את כל התובנות הפילוסופיות כדי לעגל ולהעשיר את הדמויות שלו. הוא התכוון לרתק ולשעשע את הצופים ולא להטיף להם. (התאטרון באותם ימים שאף לחנך ולהעשיר את צופיו, באותה מידה שמגרשי הכדורגל בימינו מנסים לחנך את קהל האוהדים לחיים ספורטיביים). האם המונולוג של שיילוק, נועד להזכיר לצופיו שגם היהודי הוא בשר ודם? לאור דמותו של שיילוק והשימוש הנדיב במילת הגנאי "יהודי" במחזות בכלל, ספק רב אם זהו המצב. שקספיר פשוט רצה להעשיר את דמותו של שיילוק ולהעניק לשחקן תפקיד "שמן" יותר. מן המחזה "אילוף הסוררת", קשה להסיק מה היא האסכולה החינוכית של המחזאי או מה יחסו לפמיניזם. מה שודאי הוא ש"כוונת המשורר" היתה ליצור עלילה מסובכת ורבת תהפוכות, מרתקת ובעיקר משעשעת. לדעתי, הציר המרכזי של כל התאוריות השקספיריות הוא הניגוד בין הפרובינציאליות והשממה התרבותית בביתו של בעל הקרקעות והסוחר המבוסס מסטרטפורד לבין המחזאי והשחקן הפעיל בתיאטרון הגלוב. אם בנותיו של כוכב כדורגל בישראל היו מתגלות כאינטלקטואליות פמיניסטיות, הדבר בודאי היה מעורר תמיהה. |
|
|
|
|
|
|
||
|
||||
|
אתה אומר שסביר להניח ששייקספיר היה ביסקסואל, אבל אתה אומר זאת בהנחה שכותב המחזות היה אכן שייקספיר, לא? ואינני סבורה ששייקספיר (המחזאי) ניסה "להטיף" לקהלו, אבל כדי לעבות את דמויותיו הוא לא היה זקוק דווקא לפילוסופיה - וזו בהחלט בולטת אצלו. נראה שזה פשוט עניין אותו. (ואני חייבת להודות שלו הייתי נתקלת בבת של שחקן כדורגל שהיא אינטלקטואלית ופמיניסטית לא הייתי נדהמת במיוחד. אם מדובר בכוכב, הרי ודאי יש לו כסף להקנות לביתו חינוך טוב ביותר. וסביר שהוא גם מעוניין בזה). |
|
|
|
|
|
|
||
|
||||
|
יש לי הרגשה שלשאול ייקח את הדיון לכיוונים טכניים, שעדיף אם יילמדו עם מרצה בשר ודם במסגרת קורס 3 נקודות (ו/או הצקות לאותו מרצה במשרד שלו). אני אחכה לסמסטר חורף הקרוב כדי להמשיך את הויכוח. | |
|
|
|
|
|
||
|
||||
|
כן, צריך להזהר מאד פן הדיון באייל יסחף לכיוונים טכניים. | |
|
|
|
|
|
||
|
||||
|
ברגע שבו אפשר יהיה לכתוב עם tex באייל, אני מבטיח לשנות את הגישה. | |
|
|
|
|
|
||
|
||||
|
ברמה מעשית, כמפענח שמקבל טקסט מוצפן ורוצה לפענח אותו, להניח שאתה יודע מהי שיטת ההצפנה (או אפילו כמה שכבות הצפנה יש) מבלי שיש לך על זה מידע כלשהו היא הנחה שחצנית מכדי לקדם אותך. זה ממש חיפוש המטבע מתחת לפנס. להבדיל, כמחקר אקדמי, אין בעיות להניח מה שאתה רוצה, והתוצאות שתקבל יכולות להיות בעלות משמעות גם אם ההנחות ההתחלתיות היו לא מציאותיות. למשל, אם תגלה שפענוח שיטת הצפנה בלתי אפשרי, *גם בהנתן שיטת ההצפנה*, אז אפשר להשתמש בשיטת ההצפנה באופן מסחרי. |
|
|
|
|
|
|
||
|
||||
|
אה, אם הדיון תיאורטי, אני מוכן לקבל את ההנחה שאנחנו אוטומטית יודעים שפיענחנו ברגע שפיענחנו. אני מוכן להניח שיש הודעה תקנית שאומרת "ברכותי! פיענחת את הצופן" בתחילת כל הודעה. אבל דווקא הפעם השאלה שלי הייתה על המישור הפרקטי. |
|
|
|
|
|
|
||
|
||||
|
גם ברמה הפרקטית, כל עוד השיטה היא RSA (וזו השיטה הרלוונטית היום, וב-1989), ניתן להשתמש בכוח החישוב שלנו כדי לפרק לגורמים מספר של 64 ביט 1. נוכל לוודא בקלות את הצלחתנו (קוראים לפעולה הזאת "כפל") ומהמספרים הראשוניים למצוא בקלות את המפתח הפרטי. 1 השאלה היא, אם אכן ניתן כבר היום במאמץ סביר, לפרק לגורמים מספר כזה. |
|
|
|
|
|
|
||
|
||||
|
למה למחשב קוונטי יכול להיות כח חישוב "החורג" מזה של מכונת טיורינג? למיטב הבנתי, ניתן לסמלץ מחשב קוונטי ע"י מחשב רגיל די בקלות. | |
|
|
|
|
|
||
|
||||
|
אם הבנתי נכון, זה כמו בשיר של אריק איינשטיין- מחשב קלאסי עושה אותם הדברים אבל לאט. | |
|
|
|
|
|
||
|
||||
|
נכון להיום לא ידועה דרך לסמלץ מחשב קוונטי ע''י מחשב רגיל כך שכל פעולה של המחשב הקוונטי תבוצע במספר פעולות קטן (פולינומיאלי) במחשב רגיל. כאמור במאמר, אין שום הוכחה שלמחשב קוונטי יש כוח חישוב גדול משל מחשב רגיל, אבל ידועים כמה אלגוריתמים למחשב קוונטי שנכון להיום אין להם אלגוריתמים מקבילים במחשב רגיל. |
|
|
|
|
|
|
||
|
||||
|
האם ההסבר הבא נכון? הטריק של המחשב הקוונטי הוא שהוא יכול לבצע הרבה מאוד פעולות בו זמנית. כשם שמכניקת הקוונטים מייצגת את האלקטרון ע"י "ענן הסתברות" המתאר את האפשרות של האלקטרון להיות בכל מקום בענן בהסתברות המתאימה, כך המחשב הקוונטי יכול לתאר כל משתנה ע"י "ענן הסתברות" המתאר את האפשרות של המשתנה להיות בעל ערך מסויים בהסתברות המתאימה. ביצוע מכפלה של משתנים כאלו שקול לביצוע כל המכפלות של כל הערכים האפשריים. הבעיה היא רק כיצד מתוך כל המכפלות האפשריות הקיימות בפוטנציה לגרום לפונקציית הגל לקרוס דוקא על המכפלה המעניינת אותנו. |
|
|
|
|
|
|
||
|
||||
|
כבר שמעתי את ההסבר הנ''ל יותר מפעם אחת ואפשר להגיד שיש בזה משהו. הבעיה היא למצוא דרך לגרום לפונקציית הגל לקרוס לתוצאה הרצויה, וזה בד''כ בלתי אפשרי. מה שכן אפשרי זה לגרום לפונקציית הגל לקרוס קודם כל לתוך תת-מרחב של המצבים האפשריים, שכולל את התשובה הנכונה, ואז יש הסתברות לא רעה שבמדידה מלאה נקבל את התשובה הנכונה, ואם לא, נחזור על התהליך שוב. תהליך כזה דורש שבדיקת הנכונות של התשובה הוא קל - למשל פרוק נכון לגורמים קל לאימות. |
|
|
|
|
|
|
||
|
||||
|
כלומר, מחשב trial and error? משהו כמו מחשבי הירי בטנקים הצה"ליים? | |
|
|
|
|
|
||
|
||||
|
האלגוריתם כולל בדיקה של נכונות וחזרה על החישוב במקרה הצורך. האלגוריתמים הידועים כיום הם כאלו שבזמן סביר יתנו תשובה נכונה בהסתברות יותר טובה מהסיכוי שלך לשרוד עד מתן התשובה. (שמעתי כבר את ההשוואה - הסיכוי לתשובה שגויה הוא קטן מהסיכוי שיפול על המחשב אסטרואיד) |
|
|
|
|
|
|
||
|
||||
|
שוב אנחנו חוזרים לבעייה המקורית, תת-מרחב הפתרונות האפשריים הוא כל כך גדול שבדיקה שלהם תקח ימבה זמן ועד שנמצא את התשובה הנכונה כבר אפשר יהייה לצעוד לירח ובחזרה (עד אז יבנו שביל להולכי רגל). | |
|
|
|
|
|
||
|
||||
|
כיום אין שום אלגוריתם למחשב קוונטי שיכול לפתור בעיה שידוע שהיא קשה (NP-Complete לאלו שמכירים את המינוח) וגם אין נימוק ממש טוב למה שיהיה כזה. כל האלגוריתמים הקוונטיים שידועים כיום ושהם יותר טובים מכל אלגוריתם קלאסי שידוע, הם לבעיות שיתכן שיש להן פתרון קל במחשב רגיל, רק שלא ידוע כזה. | |
|
|
|
|
|
||
|
||||
|
עוד לא הוכח כי בעיות NP-complete הן באמת קשות על מחשב קלאסי. גם להן ייתכן פתרון קל במחשב רגיל. | |
|
|
|
|
|
||
|
||||
|
אתה צודק, אבל הסיכוי שיתגלה פתרון פולינומיאלי לבעיות NP-complete הוא נמוך, לדעת רבים, מהסיכוי שרוזנקרנץ וגילדנשטרן חיים. יש משהו מפתיע, שלא לומר מסתורי, בעובדה שגם בחישוב קוונטי וגם בהצפנה ציבורית עוד לא הצליחו1 להתלבש על בעיות NP-complete, והלא יש כל כך הרבה כאלה. 1 ככל הידוע לי. |
|
|
|
|
|
|
||
|
||||
|
יש פה אי-הבנה. כשאומרים שכח חישוב של מודל X (מחשב רגיל) גדול מזה של מודל Y (מחשב קוונטי), אז בדרך כלל מתכוונים לכך ש-X יכול לפתור יותר בעיות מ-Y - בלי שום קשר למהירות. זה היה המובן שבו אני השתמשתי. זה די טריביאלי לסמלץ פעולה של מחשב קוונטי ע"י מספר אקספוננציאלי של פעולות. יש אפילו סימולטורים כאלו. לכן ברור שלכל אלג' למחשב קוונטי יש אלג' למחשב רגיל (עם נזק אקספונציאלי על זמן הריצה). היינו, למחשב קוונטי אין כח חישוב גדול יותר משל מחשב רגיל. ברור שלא יודעים לסמלץ כל פעולה של מחשב קוונטי ע"י מספר פעולות פולינומיאלי - הרי זה היה כל הרעיון. מה שאתה (כנראה) מתכוון ב"כח חישוב גדול יותר" הוא ש-P (הבעיות שניתן לפתור בזמן סביר על מחשב רגיל) מוכל ב-QP (הבעיות שניתן לפתור בזמן סביר במחשב קוונטי) ואולי גם מוכל ממש. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק. | |
|
|
|
|
|
||
|
||||
|
בגודל של המחשבים הקוונטיים שוידעים לבנות היום, אין שום בעיה לסמלצם בזמן סביר :-( | |
|
|
|
|
|
||
|
||||
|
תלוי למה אתה מתכוון ב''כח חישוב''. הם שקולים מבחינה חישובית, כלומר יכולים לפתור את אותן הבעיות, רק לא באותה המהירות. | |
|
|
|
|
|
||
|
||||
|
אם אפשר איזה טיפ קטן בכתיבת מדע פופלרי: היה יכול להיות נחמד אם הייתה מציג בהתחלה איזו בעייה אקזוטית ומשם עובר לנושא של המאמר. פתיחה עם תאור טכני מתאימה יותר לפטנט. |
|
|
|
|
|
|
||
|
||||
|
לאנשי מדעי המחשב: הרעיון המקורי היה שמחשב קוונטי פועל כמו "מכונת טיורינג אי-דטרמניסטית". "מכונת טיורינג אידטרמניסטית" הוא שינוי של מודל מכונת טיורינג: בכל מקום שבו המכונה נדרשת "להחליט" החישוב מתפצל למספר מסלולי חישוב שרצים במקביל. כך נוצר עץ אורך ומסועף של חישובים אפשריים. המכונה עונה "כן" אם לפחות באחד ממסלולי החישוב יש תשובה "כן". אחת ההגדרות של המחלקה NP (וזהו למעשה מקור שמה) הוא "השפות שמכונת טיורינג אי-דטרמניסטית יודעת לזהות בזמן פולינומיאלי" . כולם יודעים שעד היום לא יודעים האם P=NP, אולם ההרגשה הכללית בקרב החוקרים שזהו אי־שיוויון: מכונת טיורינג אי־דטרמניסטית יודעת לעשות דברים בזמן "סביר" שמכונה לא רגילה לא יודעת לבצע בזמן "סביר". רוב הבעיות הקשורות להצפנה שוכנות באותו מרחב שמחוץ ל־P אך בתוך NP . הסיבה לכך היא שרוצים בעיה שניתן לבדוק בה נכונות פיתרון בזמן סביר אך אין אפשרות למצוא פתרון בזמן סביר. התקווה היתה, אם כן, שמכונות קוונטיות יוכלו לבצע כל פעולה שיכולה לבצע מכונת טיורינג אי־דטרמניסטית. אולם למיטב ידיעתי היום הדעה הרווחת היא שזה לא נכון. יכול להיות שאפילו הוכיחו שאם P!=NP אז מחלקת הבעיות שניתנות לפתרון ע"י מחשב קוונטי בזמן פולינומיאלי (QP) לא כוללת את קבוצת הבעיות "הקשות" של NP (הקבוצה הידועה בשם NPC). בעיית הפירוק לגורמים, אגב, אינה בתוך NPC (בהינתן ש־P!=NP, כמובן). ר' גם: http://encyclopedia.thefreedictionary.com/computatio... |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
ואם תצליחו להסביר לו, אשמח גם להסבר שאפילו אני אוכל להבין. | |
|
|
|
|
|
||
|
||||
|
יש תאור לא מתמטי ודי בהיר וקצר של המחשב הקוונטי בספר המצויין "סודות ההצפנה"/סיימון סינג http://www.bookme.co.il/bookdetail.asp?book_id=96038... | |
|
|
|
|
|
||
|
||||
|
לבעייה חישובית יש קלט המתאר את הבעייה, ופלט שהוא תשובה - לצורך העניין, "כן" או "לא". למשל: נתונה משוואה, האם יש לה פתרון? נתונה מפה מדינית, האם אפשר לצובעה בשלושה צבעים (כך שלמדינות שכנות צבעים שונים)? נתון מספר, האם הוא ראשוני? ככל שהבעייה "גדולה" יותר, כלומר דרושות יותר מילים כדי לתאר אותה, היא כמובן קשה יותר. יותר קשה לבדוק ראשוניות של מספר עם 1000 ספרות ממספר עם 3 ספרות. השאלה העיקרית היא, *כמה* יותר קשה הפתרון. בעייה נמצאת ב-P אם יש מספר, m, כך שהזמן הדרוש לפתרונה אינו עולה על (גודל הקלט) בחזקת m. זהו קצב גידול פולינומיאלי, הנחשב מתון: גם אם m הוא גדול, נניח 20, עדיין x^20 הוא בסופו של דבר הרבה פחות מאשר, נניח, x עצרת או שתיים-בחזקת-x. בעייה נמצאת ב-NP אם היא מקיימת תנאי (לכאורה) חלש בהרבה: אם מישהו מנחש או מציע פתרון לבעייה, דרוש זמן פולינומי כדי לבדוק אם הוא צודק. למשל, אם מישהו מציע צביעה של המפה, האם אפשר לבדוק במהירות שהצביעה היא בסדר? (כלומר, שאין זוג מדינות שכנות עם אותו הצבע). אם מישהו מציע שני גורמים של המספר, האם אפשר לכפול אותם במהירות ולבדוק שאכן יוצא המספר הנתון? בשני המקרים, התשובה היא כן. "במהירות" כאן, כמו קודם, זה "תוך זמן שאינו עולה על גודל הקלט בחזקת משהו". כמעט כל בעייה סבירה נמצאת ב-NP. לעומת זאת יש מעט מאוד בעיות שידוע שהן ב-P. כל בעייה ב-P היא גם ב-NP (אם אפשר לפתור מהר, ברור שאפשר גם לפתור מהר כשמותר לנחש). ההפתעה הגדולה היא שעד היום איש לא הצליח *להוכיח* שאיזושהי בעייה ב-NP *לא* נמצאת ב-P. (מקור השם NP, אגב, הוא Non-deterministic Polynomial. אפשר להסביר קצת יותר אם רוצים. ועוד לא דיברנו על NPC). |
|
|
|
|
|
|
||
|
||||
|
ליתר דיוק: יש הרבה בעיות ב־P . רוב האלגוריתמים שאנו משתמשים בהם בחיי היום־יום (לדוגמה: מיון, פעולות אריתמטיות) הם ב־P . אין לנו יכולת מעשית לפתור בעיות שאינן ב־BPP (אלא אם כן הקלט קטן מספיק: לדוגמה: כל מיני אתגרים לפיקטור מספרים בני בערך 500 סיביות) | |
|
|
|
|
|
||
|
||||
|
איני מסכים. מספר הבעיות שידוע שהן ב-P הוא זעום לעומת מספר הבעיות ב-NP. כמעט כל בעייה שצצה בחיי היום-יום בתורת-הגרפים, ביולוגיה חישובית, אנליזה נומרית או גרפיקה חישובית וכו' היא ב-NP, ולעיתים נדירות מאוד ב-P. האלגוריתמים בהם *משתמשים* בחיי היום יום הם, מטבע הדברים, ב-P, כי אלגוריתמים לא פולינומיאליים הם בד"כ איטיים להחריד. ה*בעיות* בהן נתקלים הן כמעט תמיד ב-NP ולא (ככל הידוע) ב-P. ה"פרדיגמה" הגדולה ב-P היא תכנון לינארי. חלק ניכר מהבעיות ב-P הן שם כי ניתן להציגן כבעיות תכנון לינארי. פרט לזאת יש די מעט אלגוריתמים פולינומיאליים מבריקים (בדיקת ראשוניות היא הילד החדש בבלוק, אבל גם קודם היה ידוע שהיא "כמעט" ב-P). |
|
|
|
|
|
|
||
|
||||
|
תוכל בבקשה להסביר בשורה או שתיים מה זה "תכנון לינארי" או להפנות למקום שמסביר? בפעם האחרונה שנתקלתי בזה, זה היה בהקשר של תורת המשחקים, וגם אז רק שמעתי שמוכיחים איתו משפט (המינימקס של פון-נוימן, אם אני זוכר נכון), לנו הוכיחו את המשפט הזה עם קבוצות קמורות. | |
|
|
|
|
|
||
|
||||
|
למיטב ידעתי: "בעיות תכנון לינארי" הן כל בעיות האופטימיזציה של פונקציה לינארית תחת אילוצים ליניאריים. זהו מקרה פרטי שימושי במיוחד של התחום הכללי שעוסק באופטימיזציה בתחומים קמורים (אילוצים ליניאריים יוצרים בהכרח תחום קמור). מה קורה עם שאר התחומים? לאלון ועוזי הפתרונים. הסיבה שבעיות כאלה חשובות, היא כי מסתבר שהמון בעיות אחרות ניתנות לניסוח כבעיות תכנון לינארי (ברשתות זרימה, בחקר ביצועים, בתורת המשחקים כמו שאמרת...). איפשהו בשנות החמישים בחור בשם ג'ורג' דנציג פיתוח אלגוריתם לפיתרון שלהן למען הצבא הבריטי (אלגוריתם הסימפלקס). אומנם אין לו חסם אסימפטוטי פולינומיאלי, אבל נדמה לי שברוב המיקרים "הישומיים" הוא יעיל מאד ולכן נמצא גם היום בשימוש נרחב (זאת, והעובדה שהוא מאפשר ניתוח רגישות פשוט, עובדה חשובה מאד בעולם האמיתי, כך סיפרו לי), למרות שפותחו אלגוריתמים נוספים ופולינומיאלים לפיתרונן (הסימפלקס הוא אלגוריתם on-boundry - כלומר הולך ומתקרב לאופטימום על פני שפת תחום האילוצים, בעוד שהאלגוריתמים הפולינומיאלים הם in-boundy, ומתקרבים לאופטימום מתוך תחום האילוצים). אני, בכל אופן, נתקלתי רק בסימפלקס (קיימים לו גם ויראציות שונות, אשר יעילות יותר בצורות מיוחדות של בעיות תכנון ליניארי). ודעה אישית לסיום: כל זה מאד מאד משעמם, אפילו שזה מתמטיקה. |
|
|
|
|
|
|
||
|
||||
|
זיכרון מעורפל מנצנץ במוחי מהקורס בחישוביות וטוען שדווקא נמצא חסם לסימפלקס. (O(n^3 אם אני זוכר נכון. | |
|
|
|
|
|
||
|
||||
|
הזכרון מוטעה. ההסבר של הילדה די מדויק (למעט זה שאני לא בטוח שאפשר לתאר את אלגוריתם האליפסואיד כ in-boundary). יש כל מיני תוצאות חיוביות על הסימפלקס כולל הוכחה שהוא רץ בזמן פולינומי על קלטים שעשו להם פרטרובציה קלה. ראה |
|
|
|
|
|
|
||
|
||||
|
הידע שלי בנושא זעום עד לא קיים, לכן אני מתנצל מראש על טיפשיות השאלה. (אני יתייחס בשאלה שלי לאופטימיזציה של פונקציה לינארית של 2 משתנים כי יותר קל לדמיין את זה, אבל זה נראה לי נכון לכל מספר משתנים שהוא) אם יש לי אוסף של הגבלות לינאריות, החיתוך שלהם אמור להיות מצולע כלשהו, או תחום לא חסום. משהו מעומעם שאני זוכר מאינפי, אומר לי שכל נקודות המקסימום והמינימום של פונקציה לינארית בתוך המצולע חייבות להתקבל על הקודקודים (משהו עם זה שהנגזרת תמיד שונה מ-0). במידה והתחום לא חסום - לא הוכחתי פורמלית, אבל נראה לי שאו שהפונקציה לא חסומה, או ששוב היא מקבלת מינימום/מקסימום על הקודקודים. מן הסתם אני מפספס משהו, ואני מניח שזה קשור לזכרונות הלא ממש מדוייקים שלי משיעורי אינפי. מישהו מוכן להעמיד דברים על דיוקם? |
|
|
|
|
|
|
||
|
||||
|
הכל נכון - רק שמספר הקודקודים של הקומפלקס הוא אקספוננציאלי במספר המשוואות... | |
|
|
|
|
|
||
|
||||
|
אם יש לי n משוואות, אני לא אמור לקבל מצולע עם (עד) n צלעות? האם למצולע עם n צלעות אין בדיוק n קודקודים? אפילו מספר נקודות החיתוך הכולל של n משוואות לינאריות הוא לפי דעתי סדר גודל של n^2. שוב, אני כנראה מחמיץ משהו בסיסי... |
|
|
|
|
|
|
||
|
||||
|
מימד. אתה מדבר על המישור (שני משתנים), שם הכל באמת קל. כשהמימד גדל, כלומר כשיש הרבה משתנים, מספר הקדקודים, ובאופן כללי הפאות, עשוי להיות גדול מאוד גם אם אין הרבה מדי משוואות. דוגמה: את הקוביה ה-n ממדית אפשר להגדיר ע"י 2n אי-שוויונים: 0 <= xi <= 1 אבל יש לה שתיים-בחזקת-n קדקודים.
|
|
|
|
|
|
|
||
|
||||
|
נפל האסימון. זה מה שקורה שמנסים להוכיח טענות באמצעות "נראה עבור n=2, ההוכחה הכללית דומה". תודה רבה על ההבהרה (לך ולעוזי). |
|
|
|
|
|
|
||
|
||||
|
יש לך קישור טוב למשהו שכתוב פשוט ובהיר על כהנמן ומחקר כלשהו שהוא עשה על הרגלי צריכה של סטודנטים? | |
|
|
|
|
|
||
|
||||
|
לא ברור לי למה אתה מניח שדווקא אני אדע דבר כזה. הידע שלי בתורת המשחקים (זו הסיבה?) הוא אפסי, וכולל קורס בסיסי אחד ועוד טיפה, אז אני חושש שאני לא יכול לעזור לך. אם הצדקת את הכינוי (הקבוע) שלך, וזו הייתה הערה ארסית, פספסתי לגמרי את העוקץ, סליחה. |
|
|
|
|
|
|
||
|
||||
|
שום ארסיות,פשוט חיפשתי עליו ופתאום הופעת עם תורת המשחקים... בינתיים מצאתי משהו קטן. |
|
|
|
|
|
|
||
|
||||
|
לא נראה לי שיש הרבה מה להוסיף מעבר להסבר של ילדה, אלא אם כן אתה רוצה יותר פרטים טכניים. כדאי להזכיר שבתכנון לינארי יש תופעה חשובה של "דואליות" - לכל בעייה יש בעייה צמודה, ולפעמים הרבה יותר קל לפתור אותה. יש דוגמאות נאות בכל מיני מצבים מעשיים. הפניות למקומות שמסבירים יש בלי סוף. הנה ספר על הרשת: הספר הלא אלקטרוני שאני מכיר הוא זה של סחרייבר (Schrijver) ועוד כמה אנשים. |
|
|
|
|
|
|
||
|
||||
|
שמתי לב שלא זכרתי לגמרי נכון: המחלקה המשמעותית לגבי חישובים קוונטיים היא BQP: השפות שניתן למצוא בוודאות גדולה. בינתיים אין שום שפה שלגביה יכולים להגיד בוודאות שהיא ב־BQP אך לא ב־BPP (כלומר: שאין דרך לזהות אותה בוודאות גדולה ע"י מחשב רגיל). מה שכן, יש כמה בעיות חשובות שלהן ידוע אלגוריתם יעיל לפתרון ע"י מחשב קוואנטי. לדוגמה: פירוק לגורמים (שעל הקושי שלה מבוססת, בין השאר, הצפנת RSA) ולוגריתם דיסקרטי (אלוגריתם דיפי-הלמן להחלפת מפתחות, חתימת אלגמאל ותקן DSA). האלגוריתמים הללו נמצאים בשימוש נרחב היום. |
|
|
|
|
|
|
||
|
||||
|
שער H נקרא גם Hadamard Gate ומקיים: H|0> = 1/sqrt(2)[|0> + |1>] שער T נקרא גם Phase Shift Gate ומקיים:H|1> = 1/sqrt(2)[|0> - |1>] T|0> = |0>
T|1> = exp(iPI/4)|1> |
|
|
|
|
|
|
||
|
||||
|
זה כבר ממש פשוט. כאמור, CNOT פועל על זוג קיוביטים: CNOT |00> = |00>
CNOT |01> = |01> CNOT |10> = |11> CNOT |11> = |10> |
|
|
|
|
|
|
||
|
||||
|
אז עכשיו אני לא מבין משהו. נראה שאפשר לייצג קיוביט כצ"ל של <0| ו <1| עם מקדמים שאינם רציונליים אבל הם צ"ל של 1 ושורש שתיים (ואולי i), כי כל השערים שתיארת נשארים בעולם הזה. זה לכאורה מאפשר לסמלץ מחשב קוונטי ע"י מחשב קלאסי בזמן פולינומי, ואני יודע שזה לא נכון, אז מה אני מחמיץ? | |
|
|
|
|
|
||
|
||||
|
אני לא איזי אבל העניין הוא שאתה יכול לדחוף שתיים בחזקת N ערכים לתוך הקופסא במקביל, ולצאת עם אותו מספר תוצאות ביציאה. איך אתה עושה את זה בזמן פולינומיאלי? למשל: |00> + |01> +|10>+|11> נכנסים, יוצא סכום דומה אבל עם מקדמים אחרים. כדי לחשב את זה קלסית, צריך לחשב בנפרד לכל קט |XY> ובסוף לסכם, אבל קוונטית זה מתחשב במכה אחת. |
|
|
|
|
|
|
||
|
||||
|
כמו שאמר פעם אביב: צ'יצ'ינג. תודה. | |
|
|
|
|
|
||
|
||||
|
הבנת? טוב מאד. עכשיו הסבר בבקשה גם לי. ובהמשך לתגובה 221035, גם לי זה נראה מוזר. אם אני מבין נכון, זה נראה שלכל קלט נתון הפלט נמנה על מרחב בר מניה של אפשרויות (או סופי, תלוי מה קורה שם בתוך הקופסא), אך עבור הקלט עצמו ניתן לבחור מקדמים ממשיים כרצוננו, ולכן מבחינה זו מרחב הפלט אינו מוגבל א-פריורי. |
|
|
|
|
|
|
||
|
||||
|
(אם הבנתי נכון:) אילו "מצב" היה קט עם מקדם רציונלי (או רציונלי + רציונלי כפול שורש שתיים, לא משנה), ומצבים כאלה היו נכפלים ומחוברים ועוברים שערי H ו-T וכו', היה קל לסמלץ קלאסית. זה היה נכון גם אם "מצב" היה צ"ל של מספר פולינומי של קטים כאלה. (כששאלתי את השאלה היתה לי בראש תמונה של מספר קטן של קטים). אבל נראה ש"מצב" הוא צ"ל של מספר אקספוננציאלי (בגודל ה"קלט") של קטים, ובצעד-חישוב אחד אתה משנה את המקדמים של כל המצב, כלומר מספר אקספוננציאלי של מספרים. זה באמת נותן יותר כח - כמה יותר, כבר תלוי במרחב התמרון המותר עם הפעולות הללו. איני חושב שעושים שימוש כלשהו במקדמים ממשיים שרירותיים בקלט, זה נשמע לי לא מעשי להחריד. אני חושב שהכל קורה בשדה מספרים (הרחבה סופית, בפרט בת-מנייה, של Q, אולי פשוט ((Q(sqrt(2 ). |
|
|
|
|
|
|
||
|
||||
|
עכשיו הבנתי. תודה לשניכם. | |
|
|
|
|
|
||
|
||||
|
מה זה בעצם "מצב קוונטי"? צירוף ליניארי של המצבים 0 ו- 1, שסכום ריבועי המקדמים שלו הוא 1? אם כן, מה פשר הפעולה T? | |
|
|
|
|
|
||
|
||||
|
נראה כאילו המקדמים יכולים להיות מרוכבים, וסכום ה*ערכים המוחלטים* בריבוע הוא 1. | |
|
|
|
|
|
||
|
||||
|
בנוסף, מבחינת מכניקת הקוונטים פאזה גלובאלית אינה ניתנת למדידה (אני מקווה שזכרוני אינו מבזני כאן), ולכן <T|1 נחשב כאותו מצב קוונטי כמו <1| . פאזה יחסית לעומת זאת, באה לידי ביטוי בתוצאות ניסויי התאבכות (למשל) ולכן T[|0>+|1>] הוא מצב קוונטי השונה מ-|0>+|1>
|
|
|
|
|
|
|
||
|
||||
|
בדיוק. אתה זוכר נכון. | |
|
|
|
|
|
||
|
||||
|
אבל נראה שכששער הדמאר פועל על קיוביט, הוא מאריך אותו (נכנס 1) ויוצא שורש של אחד וחצי. לא? | |
|
|
|
|
|
||
|
||||
|
לא, למה? | |
|
|
|
|
|
||
|
||||
|
אה, לא ראיתי את הסוגריים. carry on. | |
|
|
|
|
|
||
|
||||
|
ציור המעגל הלוגי בראש המאמר לא מאפשר לי להתאפק מלחוד חידה, לכל חובבי השערים הלוגיים: האם אפשר לבנות מעגל לוגי המבצע שלושה היפוכים (NOT), תוך שימוש בשני שערי NOT בלבד (וכמה שערי AND ו-OR שאתם רוצים)? הכוונה למעגל שלו שלוש כניסות a, b, c ושלוש יציאות x, y, z כך ש- x=NOT(a) ומדובר במעגל לוגי נקי וטהור, בלי מתחים אנלוגיים, פידבק, פליפ-פלופים וכאלה.
y=NOT(b) z=NOT(c) |
|
|
|
|
|
|
||
|
||||
|
יש לי זיכרון מעורפל ש AND (או OR) ו-0 ו-1 (או רק אחד מהם) הם מערכת שלמה (נדמה לי שמייצרים מהעסק XOR, ואז אפשר לעשות מה שרוצים). ואם אני צודק אז כן, זה ניתן. כדי לא לקלקל אני לא אגלה את האמצע. | |
|
|
|
|
|
||
|
||||
|
ברור שלא. AND ו-OR הם שערים מונוטוניים, ואינם יכולים לעולם להפוך 1 ל-0. אם אין לך NOT בכלל, אינך יכול לייצר NOT (ולא XOR). | |
|
|
|
|
|
||
|
||||
|
אין לי מושג איך פותרים את זה, רק אציין שלמעשה ייתכן רק שכל הכניסות זהות או שאחת שונה מהאחרות, אז אולי שימוש מושכל באינפורמציה הזאת יכולה להספיק ( אם כולם זהות, עושם "NOT" על אחד מהם ושולחים לכולם, ואם אחד שונה , עושים הצלבה). | |
|
|
|
|
|
||
|
||||
|
כולכם רשעים, מכריחים אותי לשחזר את הפתרון במקום למצוא אותו בעצמכם. אז לפני שארשום אותו, הנה עוד משהו, בתור עונש: נניח שמבקשים מכם לבנות מעגל שעושה *ארבעה* היפוכים עם כמה שפחות שערי NOT. אתם חושבים לעצמכם כך: אפשר בוודאי לבנות מעגל כזה עם שלושה שערי NOT, כי למדנו ב"אייל הקורא" איך עושים שלושה היפוכים עם שני NOTים, ואת הרביעי נהפוך פשוט עם עוד NOT. אבל רגע... עכשיו לפנינו מעגל לוגי כנדרש שבתוכו שערים משערים שונים ורק שלושה NOTים. מדוע שלא ניקח את הקופסה השחורה מה"אייל", שלה שלוש כניסות ושלוש יציאות ובתוכה רק שני NOTים, ונשתמש בה במקום שלושת ה-NOTים במעגל שלנו? ננתק את הכניסות והיציאות של שערי ה-NOT, נחבר אותן לקופסה השחורה, והנה - ארבעה היפוכים מ*שני* שערי NOT בלבד! יתרה מזו, אפשר כך להמשיך ולעשות N מהפכים משני שערי NOT! כל מה שהעולם צריך (חוץ מקצת סימפטיה) זה שני שערי NOT שישכבו להם באיזה מחסן ויספקו את צרכי ההיפוך של כל המעגלים הלוגיים בתבל...! האם השיקול הנ"ל נכון? האם אפשר לבנות מעגל של 4 מהפכים עם שני שערי NOT? הנה הפתרון לחידה המקורית. עצלנים. נתונים שלושה משתנים A, B, C (משתנים לוגיים, המקבלים את הערכים 0 או 1 בלבד). עלינו לחשב שלושה משתנים X, Y, Z שלהם הערכים ההפוכים (בהתאמה), תוך שימוש בשני שערי NOT בלבד. נשתמש ב-UV לסימון "U וגם V" וב-U v V לסימון "U או V". ראשית, נחשב את פונקציית ה"רוב", שהיא 0 אם רובם של A, B, C הם 0 ו-1 אחרת: Maj = AB v AC v BC קל לראות ש-Maj משיגה את הדרוש. עכשיו נבזבז את ה-NOT הראשון:M = NOT(Maj) M כבר משיג משימה חשובה, והיא לתת ערך 1 כמעט בכל המצבים בהם A הוא 0 ו-0 כמעט בכל המצבים בהם הוא 1 (וכנ"ל, מטעמי סימטריה, ל-B ו-C).כמו כן, עיון זריז בטבלת האמת של M מאפשר לראות שהוא לא מאוד רחוק מלהיות "XOR" של כל המשתנים. אם נסמן XOR ב-+, קל לראות ש- A+B+C = (M v ABC)(A v B v C) ועכשיו נבזבז את ה-NOT השני ונחשב:X = NOT(A+B+C) אגב, הפתרון המוצג הוא יחיד במובן הזה שכל פתרון לחידה ישתמש בשערי ה-NOT בדיוק לחישוב M ו-X. מכאן אפשר להמשיך בכל מיני דרכים ולא מצאתי איזה הסבר אינטואיטיבי, למרות שזכור לי במעורפל שאפשר לראות את זה ברור יותר (אולי בעזרת Mux?). בכל אופן, קל לבדוק ש:NOT(A) = (M v BC)(M(B v C) v X) והחישוב של (NOT(B ו-(NOT(C מתבצע באופן האנלוגי הברור.
|
|
|
|
|
|
|
||
|
||||
|
(בפתיחה רשמתי "לחשב את X, Y, Z" ואח"כ השתמשתי ב-X למשהו אחר. להתעלם מהפתיחה). | |
|
|
|
|
|
||
|
||||
|
מסתבר שאלון לא כל כך איטי בכל זאת... הנה ההסבר הפסאודו-אינטואיטיבית שלי לפסקה האחרונה: נניח שהיו אומרים לנו מראש בדיוק כמה ביטים הם 1. קל לראות שבמקרה זה ניתן לבנות מעגל הנותן NOT ללא שימוש בשערי NOT בכלל. כעת, בעזרת X ו-M ניתן לעשות MUX בין המעגלים לפי מספר הביטים שהם 1. למשל אם M אבל לא X אז יש שני ביטים דלוקים. בצורה דומה ניתן לעשות 2^n -1 NOTים בעזרת N שערי NOT בלבד.
|
|
|
|
|
|
|
||
|
||||
|
אכן. אפשר להוכיח את זה, וגם שזה הדבר הכי טוב שאפשר להשיג. אני אנסה לכתוב בתמציתיות, אבל עם קצת יותר הרחבה זאת יוצאת הוכחה ריגורוזית לכל דבר: הדרך לייצר 2 בחזקת n פחות 1 NOT'ים בעזרת n שערים היא להשתמש בשערי ה- NOT ע"מ לגלות בדיוק כמה ביטים דלוקים יש: נגדיר את מספר הביטים הדלוקים ב- m - מספר n ספרתי בייצוג ביטי. פונק' שהיא 1 אמ"מ יותר מחצי מהביטים דלוקים קל להגדיר - זוהי פונק' MAJ. בעזרת ה- NOT הראשון יהיו לנו שתי פונק' - כל אחת היא 1 אמ"מ ביט ה- most של m הוא משהו מסוים. כעת נניח שיש לנו 2 בחזקת k פונק' מציינות (שכל אחת מהן היא 1 אמ"מ k ביטי ה- most הם משהו מסוים). כל אחת תוחמת את m במקטע מסוים, ומכל אחת נוכל לחשב את הפונק' המציינת ש- m נמצא במחצית העליונה של המקטע ע"י AND של הפונק' המציינת עם פונק' MAJ מתאימה. לאחר שחישבנו את המחציות העליונות נאחד את כולן (OR) ונהפוך את כולן ביחד בעזרת NOT אחד - ואז נחתוך (AND) את התוצאה עם כל מקטע לקבלת המחציות התחתונות של כל אחד מ- 2 בחזקת k המקטעים. קיבלנו 2 בחזקת k+1 פונק' מציינות חדשות - שאומרות מה ערך k+1 ביטי ה- most של m. בהנתן מס' הביטים הדלוקים m קל לחשב את ה- NOT של משתנה מסוים - הוא 0 אמ"מ לפחות (למעשה בדיוק) m מהמשתנים האחרים הם 1 (וזה MAJ כמובן). למה אי אפשר לחשב 2 בחזקת n שערי NOT בעזרת n שערים (אם אתה מתמטיקאי ולא מהנדס שמחכה שהמעגל יתייצב אחרי כמה איטרציות)? משיקולי מונוטוניות: אם אפשר אז אפשר לחשב כל פונק' על 2 בחזקת n משתנים, אבל אם נדגום את הפונק' ב- (2 בחזקת n) ועוד 1 המקומות מהצורה 000.0111.11, ונחשוב עליה כעל פונק' מ- {0,1,...,2^n} ל- {0,1}), אז AND,OR הן פונק' מונוטוניות במובן הרגיל (מכאן והלאה מונוטוניות=מונוטוניות לא יורדת), ולכן לפני שמפעילים את ה- NOT הראשון יש לנו מקטע מונוטוני אחד (כל הפונק' מונוטוניות על כל הקטע). בכל פעם שמפעילים NOT, הוא מסוגל לפצל כל מקטע מונוטוני ל-2 מקטעי מונוטוניות (שבמסגרתם נשארות כל הפונק' לאחר מכן, בשל המונוטוניות), ולכן בסוף יהיו לנו לכל היותר 2 בחזקת n מקטעי מונוטוניות => קיים מקטע מונוטוניות באורך 2 לפחות => לא ניתן לייצג את כל הפונק' (וזה כמובן לא משנה על איזה פונק' הפעלנו NOT בכל שלב ומה עשינו אח"כ). ניסיתי לכתוב בתמציתיות - אם יצא לי לא מובן אני אפרט עוד. |
|
|
|
|
|
|
||
|
||||
|
הי, אסף, אל תתבייש לספר שמצאת את שני המשפטים הללו בעצמך. זה מקרה נדיר ויפה של חסם הדוק לגמרי בבעייה קומבינטורית. (שאלתי את אסף את החידה הזו לפני כמה שנים, והוא הוכיח את הנ"ל למרות שבהתחלה, ברוב טפשותי, הטעיתי אותו וסיפרתי לו שאפשר לעשות כמה notים שרוצים ע"י שניים. אח"כ גילינו שהתוצאה הכללית כבר פורסמה, למרבה הצער, מזמן). |
|
|
|
|
|
|
||
|
||||
|
מאחר ו- X היא פונקציה של M, נראה לי שנסיון לבנות מעגל של 4 מהפכים באמצעות שני שערי NOT בשיטה המוצעת יפר את תנאי ה"בלי פידבק". ______ מה "עצלנים"? תביא חידות שאפשר לפתור! :-) |
|
|
|
|
|
|
||
|
||||
|
אכן. איכשהו הטעות הזו חוזרת על עצמה בכתובים מדי פעם, זה פח שקל ליפול לתוכו ("ההרכבה של שני מעגלים תקינים היא מעגל תקין" - לא תמיד נכון). מעניין שמישהו פעם חקר איך המעגל הפידבקי הזה עובד בפועל (ליתר דיוק, מסומלץ), והוא טוען שהעסק תמיד מתייצב על הפתרון הנכון אחרי מספר קטן של איטרציות, כלומר במציאות דווקא כן אפשר לבנות רב-מהפך עם שני שערי NOT בלבד. _________ חידה שאפשר לפתור, והיא אולי תשעשע את מי שלא מכיר אותה: בעטתי כדור ששוקל 1 ק"ג והוא התגלגל יפה ובלי חיכוך במעלה גבעה חלקה ונאה בגובה 30 מטר וברוחב ממוצע של 20 מטר, ובדיוק כשהגיע לראש הגבעה נגמר לו הכח והוא נעצר. כמה זמן זה לקח? |
|
|
|
|
|
|
||
|
||||
|
כבר מזמן שכחתי את הנוסחאות בפיסיקה אבל האינטואציה שלי אומרת מאופי הנתונים שהפתרון צריך להיות משהו יוצא דופן כמו 'איןסוף' | |
|
|
|
|
|
||
|
||||
|
קצת פחות מ 2.5 שניות? מה משעשע כאן? | |
|
|
|
|
|
||
|
||||
|
מדוע? | |
|
|
|
|
|
||
|
||||
|
אין תלות במשקל הכדור או ברוחב הגבעה אלא בהשפעה גרביטציונית בלבד. אתה יכול פשוט לזרוק אותו למעלה ותקבל אותה תוצאה. | |
|
|
|
|
|
||
|
||||
|
אני רואה שעשית את כל הקירובים והחישובים מהר מאד. כל הכבוד. | |
|
|
|
|
|
||
|
||||
|
זה טיעון משונה קצת, לא? אם הגבעה מרוחקת ממני 10 קילומטרים, זה גם ייקח 2.5 שניות? | |
|
|
|
|
|
||
|
||||
|
ההנחה, מאופן הניסוח של שאלתך הראשונה, היא שאתה עומד למרגלות הגבעה (כלומר אין זמן בו תנועת הכדור היא רק אופקית, שבמישור ללא חיכוך לא תאט את תנועת הכדור, ולכן תלויה במרחק עד לגבעה). | |
|
|
|
|
|
||
|
||||
|
אבל אתה ממילא התעלמת מהנתון על רוחב הגבעה. ואם היא היתה ברוחב קילומטר, עם שיפוע מתון מאוד בהתחלה? מדוע אתה מניח שהתנועה האנכית זהה לזו של כדור הנזרק כלפי מעלה, ומדוע התנועה האופקית לא לוקחת זמן? | |
|
|
|
|
|
||
|
||||
|
אם אין מצב בו רכיב התנועה הוא *רק* אופקי, אז עדיין התשובה תהיה נכונה, מאחר והתנועה תמיד תואט רק כפונקציה של כוח המשיכה, ותעצר תמיד בראש הגבעה, שתמיד יהיה רק 30 מ' מעליך. | |
|
|
|
|
|
||
|
||||
|
יש פה איזו אי-רציפות? אם התנועה היא *רק* אופקית, ההתנהגות היא אחרת דרסטית מאשר אם התנועה היא בשיפוע מיליונית המעלה? הטעות שלך היא התעלמות מהכוח הנורמלי המופעל ע"י הגבעה. כשגוף נע בשיפוע *באוויר*, התאוטה האנכית שלו היא g. כשגוף נע בשיפוע על *משטח*, התאוטה היא אחרת, כמובן (למשל, אם המשטח הוא אופקי...) |
|
|
|
|
|
|
||
|
||||
|
עד כמה שזכור לי, הכוח הנורמלי שמופעל ע"י הגבעה היה נלקח בחשבון במקרה של חיכוך בלבד. מאחר ועפ"י נתוני הבעיה הגבעה *חלקה*, אין משמעות לכוח הנורמלי או לכל רכיב אופקי אחר - רק לכוח המשיכה. | |
|
|
|
|
|
||
|
||||
|
עניין הרציפות עם שיפוע אפס צריך להבהיר לך שאתה טועה. דמה מדרון מאד לא תלול (אבל חלקלק, כמקובל במחוזותינו) שאורכו כמה קילומטרים, נניח מאה. האם בשתיים וחצי שניות הכדור יעבור את המרחק הזה? מהירותו ההתחלתית אינה יכולה להיות גבוהה מאד, שכן עליו להיעצר בגובה 30 מ'. אני מתאר לעצמי שיש כאן איזה טריק, אבל אין לי מושג מהו. הניסוח "20 מ' בממוצע" אומר חשדני, ואני אכן חושד בו אך הוא מסרב לדבר עד שלא ייפגש עם אביגדור פלדמן. אולי מרומז כאן איזה מקום ספציפי ומאורע ספציפי שאנחנו מכירים - משהו עם בסיס 40 מ' ושפיץ, איזו פירמידה מפורסמת? משהו? שאלה לאלון: אנחנו על כדור הארץ בכלל? |
|
|
|
|
|
|
||
|
||||
|
עוד שאלה לאלון: הוא *התגלגל* ללא חיכוך, ובסוף נעצר, או שהוא *החליק* במעלה אותה גבעה? | |
|
|
|
|
|
||
|
||||
|
אפשר להניח שהכדור נקודתי. בכל אופן, עניין הגלגול אינו רלוונטי. | |
|
|
|
|
|
||
|
||||
|
זו שאלה פיזיקלית ''אמיתית'', אין פה איזה מקום או אירוע. אם אתה לא בטוח לגבי כדור-הארץ, אתה יכול לנסות לפתור אותה על הירח. לגבי השאלה אם יש פה איזה טריק, אתה צודק ואני לא מדבר בלי עורך-דין (חילוני). | |
|
|
|
|
|
||
|
||||
|
איזו מקריות! בדיוק בשבוע הבא אני טס לירח, כך שאקבל את עצתך ואנסה לפתור את זה שם. | |
|
|
|
|
|
||
|
||||
|
אתה בן 21? | |
|
|
|
|
|
||
|
||||
|
גם אני לא הצלחתי לקלוט מה הקטע ומה ניתן להסיק מהנתונים (מה הרלבנטיות של מסת הכדור ? 1 מה משמעות הרוחב הממוצע?). את הטיעון של צב מעבדה (תגובה 221610) ניתן להציג גם בלי נוסחאות: בשל הפיכות חוקי המכניקה (כשאין חיכוך או כחות מכלים), הזמן יהיה זהה לזה שבבעיה ההפוכה, המתקבלת ע"י הרצת הסרט ברברס. מאחר שכדור במנוחה 2 על ראש גבעה אינו מתחיל להתגלגל במורד מעצמו 3, הרי שלא יגיע אל רגלו של אלון בזמן סופי. 1 יש לי חשד בלתי מבוסס שבעיטה בכדור שמסתו 1 ק"ג כך שהוא מטפס לגובה 30 מטר (עם או בלי שיפוע), מאד תכאיב לרגל הבועטת. 2 אני מסיק מהניסוח "נגמר לו הכח והוא נעצר" שמדובר בעצירה מוחלטת (תאוצה אפס) ולא מנוחה רגעית. במקרה שמסקנה זו שגויה, גם הטיעון לעיל אינו תקף. 3 אלון הוא אדם הגון ולכן אני מאמין שגם אם הוא מכיר מושגים מגונים כמו "שבירה ספונטנית של סימטריה", הוא לא היה מתקיל אותנו בהם ללא אזהרה. |
|
|
|
|
|
|
||
|
||||
|
אתה והצב שיחקתם אותה. התשובה היא אכן אינסוף, הנימוק הפשוט ביותר הוא להקרין את הסרט לאחור, והרמאות הזולה שלי (בעטייה אני עשוי להיזקק לעו"ד) היא כל הנתונים שזרקתי שם. כולם לא רלוונטיים, אבל אם לא אומרים אותם התשובה ברורה לגמרי - אם אתה סומך על חד החידה שיש תשובה, היא חייבת להיות 0 או אינסוף אם אין שום נתון מספרי. | |
|
|
|
|
|
||
|
||||
|
אם אני עדיין זוכר את הפיזיקה שלמדתי בתיכון (אם כי צריך לקחת בחשבון שלמדתי אותה מהספר של מחברי תגובה 221916) התשובה אינה אינסוף, אם כי הכדור כמובן יעצר לזמן קצר בלבד(1) ואח"כ יתגלגל חזרה במורד הגבעה. התאוצה הפועלת על הכדור היא התאוצה הגרוויטציוונית מוכפלת בסינוס השיפוע. מכיוון שלגבעה גובה כלשהו (30 מ'), הרי השיפוע אינו אפס, והסינוס שלו גדול מאפס, כך שיש לכדור תאוצה (בכוון מורד הגבעה). יש לנו מספר נתונים לא רלוונטיים לפתרון השאלה: מסת הכדור, ורוחב המסלול. לעומת זאת חסר לנו (לפחות) אחד משני הנתונים: המהירות ההתחלתית של הכדור או שיפוע הגבעה. ___ (1) מכיוון שתנועת הכדור היא רציפה, לא ניתן לעבור מגודל חיובי לשלילי (ולהיפך) אלא דרך האפס. h (30 m) = ½ g sin θ t^2
v (0 m/s) = v0 - g sin θ t |
|
|
|
|
|
|
||
|
||||
|
למה השיפוע בפיסגה לא יכול להיות 0? (אני הבנתי מהשאלה שההנחה היא שהוא דווקא כן אפס). | |
|
|
|
|
|
||
|
||||
|
אוקי :-) כמובן שהיו לי כאן כמה קרובים (קו"ף צרויה(1), לא הבאתי את המשפחה) לצורך הפשטות, אבל, אם אכן הוא מגיע לפסגה במהירות גדולה מאפס, ושם השיפוע הוא אפס, (לצורך העיניין לא גבעה, אלא "הר שולחן"), אזי הוא ימשיך במהירות זאת לנצח. __ (1) אחות של דויד. |
|
|
|
|
|
|
||
|
||||
|
לא צריך גבעה שולחנית. מספיק גבעה רגילה עם נקודת מקסימום יחידה (פיסגה) עליה החליט הכדור השובב של אלון בלון לאבד כח ולהעצר. __ (1) דוית' לא דויד. שכנם של יעקוףףףף ומאייייר. |
|
|
|
|
|
|
||
|
||||
|
תגובה 221982 עדיין בתוקף? אני לא בטוח שהבנתי את הטיעונים. | |
|
|
|
|
|
||
|
||||
|
את המהירות ההתחלתית ניתן לחשב משימור אנרגיה mv^2=mgh | |
|
|
|
|
|
||
|
||||
|
תגובה 222860 טיפה יותר מדוייקת. | |
|
|
|
|
|
||
|
||||
|
הפתיל מתחיל להזכיר קצת שיעור במכניקה בסיסית, ובכל זאת אני מרגיש צורך לשאול שאלה נוספת. אינטואיטיבית גם לי נראה שהתשובה אינסוף אבל אז חשבתי על אנלוגיה מסויימת... נניח שיש שיפוע חלק ויפה בגובה של יותר מ30מ'. זורקים את הכדור כך שיגיע לגובה של 30מ', יעצר רגעית ואז יתגלגל חזרה מטה. אבל אם הכדור נקודתי מה זה בעצם משנה אם השיפוע ממשיך למעלה או נגדע בפתאומיות ויורד מטה (כמו בשאלה המקורית)? מה ההבדלים באיבודי האנרגיה בשני המקרים? |
|
|
|
|
|
|
||
|
||||
|
זהו, שאם הוא כבר נעצר אז too late. אבל אם היא מגיע לפסגה במהירות אפסילון, ואז השיפוע נגדע באכזריות לאפס, אזי הוא ימשיך באותה מהירות אפסילון לעבר השקיעה. כלומר, עזבנו את המכניקה הבסיסית והגענו (בחדווא ובדיצה) אל השאיפה לאפס. |
|
|
|
|
|
|
||
|
||||
|
השיפוע לא נגדע בפתאומיות, אלא מתמתן בצורה חלקה ויורד. אם תזרוק את הכדור באותה מהירות התחלתית בשני המצבים שתיארת, הכדור יגיע למהירות 0 במקרה הראשון בגובה מסויים, אבל במקרה השני (בגלל ההתמתנות) הוא יגיע לשיא במהירות גדולה בהחלט מ-0. הטריק בשאלה הוא ההנחה (המוזרה) שהכדור מגיא למהירות 0 בדיוק בשיא. זה לא יכול לקרות תוך זמן סופי, ודרך יותר ברורה (אולי) לפרש את זה היא כך: * אם ניתן לכדור מהירות התחלתית מסויימת, הוא יגיע לפסגה במהירות מטר לשנייה (וימשיך ויתגלגל במורד), וזה יקח (נגיד) 10 שניות. * אם ניתן מהירות נמוכה קצת יותר, הוא יגיע לפסגה במהירות סנטימטר לשנייה (וימשיך ויתגלגל במורד), וזה יקח 1,000 שניות. * אם ניתן מהירות טיפה יותר נמוכה, הוא יגיע לפסגה במהירות מילימטר לשנייה (וימשיך ויתגלגל במורד), וזה כבר יקח 10,000 שניות. וכו' וכו'. יש מהירות התחלתית קריטית מסויימת שמתחתיה הכדור בכלל לא מגיע לפסגה, מעליה הוא מגיע וממשיך, אבל *בה* הוא זוחל מעלה מעלה לאט יותר ויותר באיזור הפסגה ולעולם לא יגיע אליה, אלא *שואף* למצב מנוחה בפסגה בדיוק. |
|
|
|
|
|
|
||
|
||||
|
כל עוד הוא שואף למצב מנוחה ולא לריאות, לדעתי האישית זה בסדר. רק שיהיה בריא ושלא ישתה לנו חשיש. יאללה - עוד שאלה בסגנון (אם יש לך). |
|
|
|
|
|
|
||
|
||||
|
אם ''בסגנון'' זה חידות חמודות בפיסיקה בסיסית, אז יש אולי עוד כמה, אבל נפסיק להפריע לאיזי. אשלח משהו ל''אייל ששאל'' הבא, אחרי שתיפתרנה החידות. | |
|
|
|
|
|
||
|
||||
|
הטריק הוא שמהנדסים לא מכירים את המונח "בדיוק". או שהמהירות היא לא בדיוק אפס (נניח, פחות מ5% מהמהירות ההתחלתית זה וירטואלי אפס), או שהפיסגה היא לא *בדיוק* בשיא (מטר לפני/אחרי, מילימטר, מיקרון - בחר את רמת הדיוק הרצויה), או שהאינסוף הוא לא בדיוק אינסוף. | |
|
|
|
|
|
||
|
||||
|
אה, סליחה. מהנדסים מתבקשים לפנות לחידה הקודמת :-) "בחר את רמת הדיוק הרצויה" - גם מהנדס יכול לצייר גרף של משך הזמן כפונקציה של המהירות (ההתחלתית, הסופית, לא חשוב), עבור 30 ערכים בתחום סביר, להמשיך את הקו ולהשתכנע שהוא שואף ל<צונזר> - אה, כלומר, עולה ללא גבול. |
|
|
|
|
|
|
||
|
||||
|
או שהם היו מתמטיקאים, או שגשרים ותקרות לא היו מתמוטטים :) | |
|
|
|
|
|
||
|
||||
|
כמובן שהתאוצה מתאפסת בראש הגבעה (החוק השני של ניוטון). שאני אהבל |
|
|
|
|
|
|
||
|
||||
|
ממש לא. ומדוע אתה אומר שהכוח הנורמלי הוא אופקי? הוא *נורמלי*, כלומר ניצב למישור המשיק לגבעה. יש לו, בדרך כלל, רכיב אנכי ורכיב אופקי כאחד. גוף יושב על שולחן אופקי, ללא חיכוך. מהי תאוצתו האנכית? אפס. מדוע? הלא פועל עליו כוח המשיכה כלפי מטה? אילולא פעל עליו כוח נוסף, היה מאיץ. הכוח הנוסף הוא הכוח שמפעיל השולחן על הגוף (כתגובה לכוח שמפעיל הגוף על השולחן). זהו הכוח הנורמלי. גוף מונח על שולחן שאינו אופקי, אלא מוטה מעט. אין חיכוך, והגוף מתחיל לגלוש. האם תאוצתו האנכית היא בדיוק g? עזוב חוקים ונוסחאות, חשוב בהיגיון. דמיין אותו גולש ובמקביל גוף דומה צונח מטה ליד השולחן. הם יהיו תמיד באותו גובה? לא. הגוף הצונח מטה ייפול הרבה יותר מהר. הכוח הנורמלי שמפעיל השולחן פועל כעת לא ישר למעלה אלא קצת בזווית, ועל כן מנטרל *כמעט* את כח הכבידה - לא לגמרי, ומה שנשאר מביא לתאוצה האנכית. |
|
|
|
|
|
|
||
|
||||
|
הגיון הוא תמיד נימוק חשוד בפיסיקה. ההגיון אומר לנו שאם נעלה על מגדל נטוי (בפיזה נניח) ונזרוק מהמרפסת כדור ששוקל 100 ק"ג וכדור ששוקל 1- ק"ג, הראשון יגיע לארץ קודם. בענין הכוח הנורמלי אתה כמובן צודק. |
|
|
|
|
|
|
||
|
||||
|
ניסוי דומה לזה אכן נערך (המסות היו קצת אחרות אולם היחס ביניהן, כמו יתר הפרטים, כפי שתארת). כמובן שהכדור הכבד הגיע לארץ קודם. הגיוני, לא? (למי שמתעצל לקרוא את כל הקטע מומלץ לחפש את המילה "ninety" ) |
|
|
|
|
|
|
||
|
||||
|
היגיון הוא באמת נימוק חשוד, אבל בגבולות ההיגיון. ס"ז ניסה לתאר סיטואציה בה בשיפוע 0, התאוצה 0, ובכל שיפוע אחר, מתון ככל שיהיה, התאוצה g. זה *באמת* לא הגיוני, ובמצבים כאלה אני מעדיף להתחיל מהסבר אינטואיטיבי מאשר לזרוק נוסחאות. סיפורים פיזיקליים לא הגיוניים יש גרועים בהרבה ממגדל פיזה - אפשר לשוב ולהיזכר במאמר בו אנו נמצאים :-) |
|
|
|
|
|
|
||
|
||||
|
אבל מה עם רציפות? נבחר שרירותית שתי מהירויות התחלתיות של הכדור: V1 – הכדור לא מגיע לראש הגבעה, ו- V2 שבה הוא עובר אותה. ניקח את המהירות הממוצעת. אם היא לא מעבירה את הכדור לצד השני, נציב אותה כ- V1. אם כן, נציב אותה כ- V2. נעשה את זה שוב ושוב. V1 ו- V2 יתקרבו ויפגשו בגבול ב- V. האם מהירות התחלתית של V תעביר את הכדור או לא? | |
|
|
|
|
|
||
|
||||
|
אין צורך במיצוע האיטרטיבי שאתה מציע: יש באמת מהירות קריטית אחת, המקיימת 1/2 m V^2 = m g h והיא *לא* מעבירה את הכדור, אך גם *לא* מאפשרת לא ליפול חזרה אחרי זמן סופי - היא בדיוק המהירות שתגרום לו לזחול לנצח אל עבר הפסגה הנכספת.יש כאן סוג של אי-רציפות שהוא דווקא לא "לא פיזיקלי": כתלות בפרמטר, הזמן שואף לאינסוף, לא מוגדר בנקודה קריטית אחת, וחוזר ויורד מהאינסוף לאחר מכן. יש עוד דוגמאות דומות, למשל: כמה זמן לוקח לעיפרון העומד על חודו ליפול על השולחן, כפונקציה של זווית הסטייה ממצב אנכי לגמרי. |
|
|
|
|
|
|
||
|
||||
|
(כמובן שהסיפורים הללו הם ''פיזיקליים'' רק במובן הנאיבי של מכניקה קלאסית נקייה. בחיים האמיתיים, זה לא באמת עובד, בגלל המבנה האטומי של החומר, רעש תרמי, ריטוטים קוונטיים... אני מקווה שברור שהשאלה מתייחסת למציאות המתמטית הקצת בדיונית). | |
|
|
|
|
|
||
|
||||
|
חשב את עיקום המרחב בגובה פני הים, הצב בטנזורים המתארים תנועה בקו ישר באזור הזה, השתמש בקירובים המקובלים, וקבל: s=(gt**2)/2 כאשר s הוא הוקטור המאונך לפני הים ו g היא התאוצה בכיוון זה. השתמש בעקרון הסופרפוזיציה שמאפשר הפרדת וקטורים אורתוגונליים כדי לא להתעניין בשיפועים ושאר מרעין בישין. הצב s=30, g=10, וחשב את t. |
|
|
|
|
|
|
||
|
||||
|
משעשע, אך לא רלוונטי (תגובה 221920). | |
|
|
|
|
|
||
|
||||
|
מה שיפה כאן, זה שהכדור נעצר, לא נופל חזרה לאחור ולא ממשיך להחליק קדימה. | |
|
|
|
|
|
||
|
||||
|
בהחלט - זה העוקץ של החידה. | |
|
|
|
|
|
||
|
||||
|
אתה באמת מבריק (אני מתכוון לזה), אבל לצערי אתה טועה פה ובגדול. מכיוון שאין פה איבוד אנרגיה, למעט בשל כח הכבידה, חישוב המהירות ההתחלתית שיש לתת לכדור הוא די פשוט. משתמשים בחוק שימור האנרגיה(מקינטית לפוטנציאלית), מציבים את h (למסה אין חשיבות וכן לא לאורך המדרון) ומקבלים את המהירות ההתחלתית שצריך להשקיע. אבל זה לא מה שמבקשים פה. מה שמבקשים זה הזמן. הזמן תלוי בדרך ובתאוצה (פה הטעות של סירס זימנסקי, דרך אגב - הדרך בהחלט חשובה). אם היה מדובר במדרון ישר, החישוב היה די פשוט. אם מדובר במדרון עם שיפוע משתנה, החישוב הופך למסובך הרבה יותר. בכל מקרה הזמן הוא סופי ! בנוגע לטיעון שאתה הצגת, הוא הוצג לפני הרבה זמן על ידי היוונים. יש הרבה פרדוקסים שעוסקים בשאלה הזאת. הקץ' בטיעון שלך הוא שאתה מתעסק בגדלים ששואפים לאפס. אני לא צריך לחדש לך שסדרות אינסופיות יכולות להתכנס למספר סופי בהחלט, והוא המקרה כאן. |
|
|
|
|
|
|
||
|
||||
|
אבל הטיעון המוחץ הוא הרברסיביליות של חוקי המכניקה. אם הכדור נמצא במנוחה בראש הגבעה (בתסריט בו חץ הזמן מתהפך) הוא לא יזוז לשום מקום, ולפיכך השתלשלות הדברים המתוארת החידה לא יכולה להתרחש בזמן סופי. כמוך, גם אני בטוח שאלון יודע על טורים מתכנסים. כידוע, לא כולם כאלה. |
|
|
|
|
|
|
||
|
||||
|
מה עניין שמיטה להר סיני ? כל האנרגיה של הכדור הפכה לפוטנציאלית. לצערו של הכדור, או לא לצערו, הוא נמצא במצב שיווי משקל. מהירותו האופקית היא אפס ומתחתיו יש אדמה ולכן הוא ימתין שם עד שאלון יניד אותו קלות. תחשוב שבמקום ההר יש במקום בו היה צריך שיא ההר, נקודה בודדת. האם אתה מסכים איתי שהייתי יכול לזרוק את הכדור בצורה כזאת כך שהוא היה נושק לנקודה הזאת מלמעלה במהירות 0 ? ההר עצמו הוא סתם תוספת ותו לא (האמת שהוא משמש ליצירת הכח המאיט לכיוון X - אבל זה לא שייך) |
|
|
|
|
|
|
||
|
||||
|
לא, אני לא מסכים איתך. זה כבר נדון כאן בהודעות קודמות: כדי שהכדור יגיע לראש ההר עליו להיות בעל מהירות אופקית כלשהיא (קטנה, אבל חיובית) בסביבה הקרובה של הפסגה, מקום שם נגזרת הגובה הולכת ומתאפסת, ואז מה יעצור אותו בדיוק בראש הגבעה? התשובה היחידה: הפרה שעומדת שם. אבל בחידה של אלון הפרה הלכה לגבעה אחרת. ושוב: חשוב על היפוך הסרט, זה מסביר את מה שחייב להתרחש טוב יותר מנגזרות ואפסילונים (אלא אם כן שמך הפרטי הוא עוזי. במקרה זה האפסילונים הם ההסבר והסרט ההפוך הוא מסקנה). אם אתה עדיין לא משוכנע, אלון עצמו בטח ייטיב ממני להאיר את עיניך. |
|
|
|
|
|
|
||
|
||||
|
בוא נחשב: h=הפרש הגובה של הכדור משיא ההר (בנקודה נתונה). x=המרחק האופקי בין הכדור לשיא ההר (בנקודה נתונה). כפי שציינת המהירות בכל נקודה זה קבוע כפול שורש h. מכיוון שההר חלק, שיפועו שואף לאפס. ולכן x/h שואף לאינסוף. בוודאי שהזמן שנותר עד השיא > מ-x מחולק במהירות הנוכחית (שרק תפחת) = קבוע כפול שורש h. בקיצור, בניסוח סיזיפי - אם ניקח דגימות, נגלה שקיבלנו סידרה של מספרים עולים השואפת לאינסוף (באותו קצב שהשיפוע של ההר שואף לאפס). הזמן עד שיא ההר הוא לפחות הגבול של הסידרה הזו. |
|
|
|
|
|
|
||
|
||||
|
חישוב המהירות ההתחלתית הוא אכן חשבון פשוט, אך כפי שציינת לא רלוונטי כלל. מדוע "בכל מקרה הזמן הוא סופי!"? חוששני שאין כל קשר בין הפרדוקסים של זנון לנימוק שהבאתי, או בכלל לחידה הזו. סדרות אינסופיות (ואולי רצית לומר: טורים אינסופיים) יכולות בוודאי להתכנס למספר סופי. אז? איך זה קשור לשאלה? האם הנימוק שהצגתי הוא מהסוג "הנה טור אינסופי, ולכן התשובה היא אינסוף"? אולי אשאל אותך כך: תהי v0 המהירות ההתחלתית הקריטית, זו שמאפשרת לכדור להפוך את כל האנרגיה הקינטית שלו לאנרגיה פוטנציאלית וכך להגיע לפסגה ללא שריד של אנרגיה קינטית - היינו, במנוחה. הסכמת שיש מהירות קריטית כזו. נניח שהמהירות ההתחלתית גבוהה מ-v0 רק במיליארדית מטר לשנייה. זה יגרום לכדור להגיע לפסגה במהירות זו. מילימטר אחד לפני הפסגה, מה היתה מהירותו? דומה מאוד לזה, שכן התאוטה באיזור הפסגה היא קטנה. נניח, בכל זאת, שמהירותו מילימטר קודם היתה גבוהה *פי אלף* - לא ממש סביר - כלומר, היא היתה מיליונית מטר לשנייה. כמה זמן לקח לו לעבור את המילימטר האחרון? בערך 20 דקות, ולמעשה יותר שכן הוא מאט. ואילו התחלנו במהירות גבוהה רק בעשר בחזקת מינוס 20 מ-v0? מה יקרה אז? מה ההתנהגות של הזמן, בקיצור, כפונקציה של e, אם המהירות ההתחלתית היא vo+e? התשובה היא: כש-e שואף לאפס, הזמן עד לפסגה שואף לאינסוף. אין כאן פרדוקס או קץ', ואיני רואה מה הבעייה עם העובדה שאני מתעסק בגדלים ששואפים לאפס. זו עובדה מתמטית פשוטה. |
|
|
|
|
|
|
||
|
||||
|
ואללה, איך ידעתי שהיצור המאוס ההוא מאינפי א', אפסילון, ירים את ראשו המכוער ויאמר את דברו. אם הדיון לא יגווע כאן, אני מחכה בחרדה גם להופעת בת זוגו המעצבנת לא פחות, ''ני''. אני עוד זוכר שעל הניסוח ''עבור כל אפסילון קטן כרצוננו'' ענה מישהו ''תוציא את הרצון שלך מהמתמטיקה''. |
|
|
|
|
|
|
||
|
||||
|
ני! ני! ננננני! (סתם, שהחרדה תבוא ותחלוף מהר) |
|
|
|
|
|
|
||
|
||||
|
היה צפוי שאם מתעסקים ביוונית יגיעו יחדיו פסי וידידו חי. | |
|
|
|
|
|
||
|
||||
|
אם יורשו לי כמה השגות, לא על הפתרון עצמו, אלא על דרך ההוכחה. נקווה כי לא יחשב לי, בן נעוות מרדות שכמותי, לחוצפה יתרה לחלוק על דברי זקנים ממני. למעשה, מאחר שלרוב אני טועה, הרי שבדברי כנגד אלון נמצאתי מחזק את דבריו. הטיעון האפסילוני המופיע בתגובה מעלי שגוי. איזו סיבה יש להניח שהמהירות מילימטר לפני הפסגה _לא_ תהיה פי אלף או קוואדזיליון יותר מאשר המהירות בפסגה? ליתר דיוק אם במרחק x מהפסגה המרחק האנכי מהפסגה הוא h אזי מהירותי תהיה v=c*sqrt(h) לכן החסם הטריויאלי לזמן יתןt=x/v=x/(C*sqrt(h) ההנחה שלפסגה שיפוע אפס נותנת לנו רק שx/h שואף לאין סוף, אבלx/sqrt(h) יכול להיות חסום ולמעשה אף לשאוף לאפס. למעשה אם נבחר את הפונקציהh=x*sqrt(x) הרי שחישוב יתן לנו שאכן כדור יכול לטפס על גבעה כזו בזמן סופי. אליה וcatch בה - הגבעה הזו אינה גזירה פעם שניה באפס. הנחה שלדעת הוגה החידה היא בלתי סבירה פיזיקלית.גם טיעון היפוך הזמן נשען על כרעי תרנגולת מתימטית דומים. כדי שהטיעון יחשב (מתימטית) צריך להשתכנע כי למערכת הדיפרנציאלית הנ"ל יש פתרון יחיד. בלי גזירות שנייה של הגבעה זה לא חייב להיות. אם אין פתרון יחיד, מה אכפת לי שיש פתרון בו הכדור נשאר במקום? אין לי כח להסברים נוספים, נתתי כאן מספיק חומר לאלון לעשות ממני חוכא ואיטלולא לשבועיים הקרובים. אורי. |
|
|
|
|
|
|
||
|
||||
|
על "זקנים ממני" מגיע לך באמת עינוי סיני חפוז כעונש, השאר דווקא לא כזה גרוע. ככה: ה"טיעון" עם האפסילון לא התיימר להיות טיעון, רק להסביר מה בעצם הטענה ולנסות להראות שהיא לא כזו בלתי-סבירה. אתה צודק שההנחה על התאוטה בסוף לא היתה מוצדקת, אם כי צריך קצת להתאמץ (כמו שעשית) כדי למצוא מצב בו העדינות הזו חשובה. לגבי טיעון היפוך הזמן, אתה במצב קצת פחות מוצלח לדעתי. בהחלט ישנן סיטואציות מתמטיות שבהן למשוואה דיפרנציאלית מסדר ראשון אין פתרון יחיד גם בהינתן תנאי ההתחלה, והדוגמאות מוכרות. אבל כאן דווקא סביר להתחשב קצת בסבירות הפיסיקלית, שבהקשר הקלאסי הנוכחי אומרת שתנאי ההתחלה אכן קובעים את ההתנהגות, וכדור היושב על מקומו לא ייזכר פתאום שלמשוואה המתארת את תנועתו יש עוד פתרון אז יאללה נוסעים. אתה צודק - זה נימוק *פיסיקלי*, במסגרת השגרתית בה פיסיקאים מניחים שכל הפונקציות הנדונות גזירות מספיק פעמים. שאלה לגיטימית: ממילא המצב המתואר אינו ממש פיסיקלי מסיבות שהזכרנו קודם (חום וכאלה), אז למה ההפשטה המתמטית שתארתי היא בסדר והצעד הנוסף שאתה מאפשר הוא לא? אין כאן תשובה חד-משמעית, לדעתי. מודל תמיד תופס חלק מהסיטואציה ומתעלם מחלקים אחרים, ובמקרה דנן נראה לי שפיסיקאי ממוצע יקבל את הקירוב של גבעה מתמטית חלקה, מהירויות קרובות מאוד לאפס, וכו', אך ידחה כלא רלוונטיות דוגמאות של גבעה גזירה פעם אך לא פעמיים. אם אתה באמת רוצה שאעשה ממך חוכא ואטלולא, תתאמץ יותר. |
|
|
|
|
|
|
||
|
||||
|
אבל אם היו, הם היו מקבלים כמובנת מאליה את ההנחה שהגבעה חלקה על כל נגזרותיה. בעלי, הפגר, טען שנים שאין בכוונתו לעלות על סולם ולהחליף נורה בסלון, משום שבמבחן במכניקה קלאסית א', הסולם החליק עד שהתנתק מהקיר. | |
|
|
|
|
|
||
|
||||
|
נו, ובסוף הוא השתכנע, הסולם החליק ואת זכית למעמד המשפחתי הנכסף? | |
|
|
|
|
|
||
|
||||
|
לא, הוא מת תוך כדי נסיון נואש במיוחד להוכיח ש 196 לא הופך לפלינדרום כשהופכים אותו ומוסיפים אותו לעצמו מספר סופי של פעמים. | |
|
|
|
|
|
||
|
||||
|
קבלי את תנחומי. אני מתאר לעצמי שאת ממשיכה את פועלו. | |
|
|
|
|
|
||
|
||||
|
להפך, פועלו החתיך ממשיך אותו, לאחר שהתחתן עם האלמנה המאושרת. | |
|
|
|
|
|
||
|
||||
|
לא ממשיכה. אני כאמור בעסקי המטריצות הגדולות להחריד בימים אלו (וגם לא מספיק דלילות, לצערי, קשים חיי אלמנה). כשתפסתי את היתום קורא את ''הדוד פטרוס והשערת גולדבך'', הענשתי אותו חמורות. אני מקווה שזה יעזור. | |
|
|
|
|
|
||
|
||||
|
למה לא קנית לו כזה ליום-ההולדת? |
|
|
|
|
|
|
||
|
||||
|
למען האמת רציתי לכתוב ''זקנים וחכמים ממני'' אבל פסלתי אפשרות זו על הסף מפאת חנופתיותה. | |
|
|
|
|
|
||
|
||||
|
סימטריית היפוך הזמן היא תכונה של המשוואות בבעיה הנתונה, ללא תלות בצורת הגבעה. לכן גם הפתרונות הנוספים, אם קיימים, מצופים לתאר תחת היפוך זמן תנועה לגיטימית של כדור המתדרדר במורד הגבעה (פתרונות קבילים מבחינה פיסיקלית של משוואות המתארות מערכת פיסיקלית מסוימת, כמעט תמיד 1 מהווים אינדיקציה לקיומם של אפקטים תואמים). בוא נניח שקיימת גבעה העונה על תנאי הבעיה, שיש לה פתרון בו הכדור מגיע לראש הגבעה ונעצר שם בזמן סופי. אם העצירה אינה רגעית, הרי שהפתרון ההפוך בזמן יתאר כדור המתחיל לנוע מעצמו. אם העצירה רגעית, עדיין הפתרון ההפוך בזמן צריך לתאר כדור שהתדרדרותו מתחילה ממצב בו המהירות והתאוצה מתאפסות. אם נסמן את רגע תחילת התדרדרות זו ב- t0 , הרי שבזמן הקטן מ- t0 הפתרון הטריוויאלי שבו הכדור נמצא במנוחה מתמשכת הוא פתרון לגיטימי של משוואת התנועה שמקיים את תנאי ההתחלה ב- t0 , וניתן לתפור אותו לפתרון ב- t0<t כדי לקבל פתרון לגיטימי נוסף שהנגזרת השניה שלו רציפה. פתרון חדש זה, מתאר אף הוא כדור היוצא משיווי משקל בצורה ספונטנית. 1 ואולי אף תמיד. |
|
|
|
|
|
|
||
|
||||
|
מסתבר שאלון קצת איטי היום... הנה רמז קטן למי שמכיר: פולינומים סימטריים. |
|
|
|
|
|
|
||
|
||||
|
חוצפן בן-נעוות המרדות, כבר 17 דקות שהפתרון המלא שוכב לו שם, אז מי איטי? הא? אבל הרמז שלך יותר נחמד. |
|
|
|
|
|
|
||
|
||||
|
יבחוש בן שלולית שכמותך, לקח לי 18 דקות לרשום את הרמז הזה. | |
|
|
|
|
|
||
|
||||
|
אתה יכול לנסות לתת דוגמא לאלגוריתם שהמחשב הקוונטי יכול לבצע והמחשב הקלאסי לא ? | |
|
|
|
|
|
||
|
||||
|
כפי שהוזכר במאמר, אין שום הוכחה שמחשב קוונטי יוכל לבצע משהו שמחשב רגיל לא יכול. קיים אלגוריתם למחשב קוונטי, שאם יהיה מחשב כזה, הוא יוכל לפרק מספר גדול לגורמיו בזמן קצר בעוד שלא ידוע כיום שום אלגוריתם למחשב רגיל שיכול לבצע את זה. |
|
|
|
|
|
|
||
|
||||
|
התכוונתי להסבר קצת יותר טכני. כלומר, איך המחשב הקוונטי מתמודד אחרת עם בעיית הפיקטור ? או בניסוח אחר: "מה יש בו שאין בקלאסי ?". אם זה קשור להסבר של מישהו שכאן שבגלל הסופרפוזיציה המחשב הקוונטי יכול לערוך את חישוביו במקביל, אז אשמח לקבל הסבר מעט יותר מפורט. |
|
|
|
|
|
|
||
|
||||
|
זה קצת חורג מרמת המאמר והסבר שלם של האלגוריתם מצריך זמן ומקום, ובפרט, משוואות שאין לי אפילו יכולת לכתוב כאן. כל חיפוש בגוגל על Shor Algorithm יתן לך הרבה יותר מידע ממה שאתה רוצה. הבעיה שצריך לדעת כמה מושגי יסוד בחישוביות, בפיזיקה קוונטית ובמתמטיקה. בגדול, מה שיש במחשב קוונטי ואין בקלאסי זה Entanglement. |
|
|
|
|
|
|
||
|
||||
|
אכן, אלגוריתם שור בהכרח יוצר שזירות (entanglement). אבל סביר מאוד שזה איננו לוז הכוח של החישוב הקוונטי. והסיבה הפשוטה והחותכת: יש אלגוריתמים קוונטיים, אשר פועלים ללא שזירות, ועדיין מנצחים בהליכה את האלגוריתם הקלסי הטוב ביותר. כמו כן, זה לא לגמרי מדויק שעקרון הסופרפוזיציה הוא לב העניין. גם חישוב הסתברותי קלסי אפשר לתאר כפעולה במקביל על התפלגות של כמות אקספוננציאלית של ערכים. ההבדל המהותי היחיד לטובת חישוב קוונטי הוא שמקדמי ה"התפלגות" יכולים להיות שליליים. עבור בעיות מסוימות, (ע"ע פיקטור) מצליחים למצוא אלגוריתם שבו התוצאות השגויות מבטלות את עצמן. |
|
|
|
|
|
|
||
|
||||
|
כמו בגבעת חלפון, נ נ י ח שיש מחשב כזה, ונניח שהוא לפי התיאוריה הרבה יותר חזק (חישובית) ועובד. חוץ מהתחכום הנהדר הזה , שיכול, לפי התיאוריה לפחות, להיות חלומו הרטוב של כל גנטיקאי מתחיל, לפחות, מה יהיה ההבדל הפיזי שלו ממחשב היום? האם מערכת ההפעלה עדיין תהיה windows? מה יהיו דרישות ה RAM שלו? הרי כל הרכיבים האחרים שלו יצטרכו להיות גם קוואנטים, הוא יגדל? יקטן? יוכל לפעול רק על הצד החשוך של הירח? (קר, וואקום, וחשוך) מה שמעניין אותי הם ההיבטים התפעוליים... | |
|
|
|
|
|
||
|
||||
|
המחשבים הראשונים היו ענקיים, תפסו בניינים שלמים ודרשו מערכות קרור ואספקת חשמל עצומה. עד סוף שנות ה70 של המאה שעברה מחשב היה משהו שרק גוף גדול יכול לקנות ולתחזק. רק בסוף המאה ה20 הופיעו מחשבים בעלות סבירה למשק בית ושלא דורשים תחזוקה יום-יומית של טכנאים. האם זה מה שיקרה גם למחשב הקוונטי? אולי. אם יהיו בו יתרונות למשתמש הביתי, יהיה מן הסתם מי שינסה לפתח גרסה ביתית שלו במחיר סביר ובלי דרישות לא סבירות מהמשתמש. אם לא, נמשיך להשתמש במחשבים רגילים. אולי גם יתכן פתרון נוסף - מחשבי שרת קוונטים שנמצאים בתנאים מיוחדים (למשל באוניברסיטאות) וניתן להשתמש בשירותיהם דרך הרשת באמצעות מחשב רגיל. |
|
|
|
|
|
|
||
|
||||
|
המחשבים הראשונים גם הצליחו לפתור בעיות מעשיות באופן יעיל יותר מן השיטות האחרות בהן התחרו. אין כיום, וגם לא ממש מתוכנן לעשור הקרוב, מחשב קוונטי עם יכולות כאלה.כדאי לציין כי אותן שיטות מפתח פומבי שהמחשב הקוונטי עשוי בעתיד לפרוץ הן הרבה יותר שימושיות מבחינה מעשית מאשר מערכות החלפת המפתחות שהמחשוב הקוונטי מאפשר כיום. | |
|
|
|
|
|
||
|
||||
|
אז המחשב הקוונטי יישאר בסביבה עד שיתעורר צורך במחשב קוונטי. קשה לי להאמין שהצורך הזה לא יתעורר בשלב כזה או אחר. | |
|
|
|
|
|
||
|
||||
|
רק צריך לציין שאחד הדברים שמחשב קוונטי גדול מספיק אמור לפרוץ הוא שיטת החלפת המפתחות הסטנדרטית היום (דיפי-הלמן) | |
|
|
|
|
|
||
|
||||
|
נראה לי די מבאס לקנות מחשב קוונטי משוכלל עם 1 173TQB רק כדי לגלות למחרת שהכל התנדף בשל אפקט המנהרה. 1 טטרה-קיוביט = TQB |
|
|
|
|
|
|
||
|
||||
|
טוב, אז נניח שבסוף תגיע האנושות אל היעד הנכסף של מחשב סופר-דופר-קוואנטי, שיחשב בדקה את מה שלקח ל"דיפ ת'וט" ארבעים שנה. אז מה?! האם זה ישפר את חיי האדם באיזשהו אופן שעליו ניתן לומר שהוא מ ש מ ע ו ת י ? הממ? כי לדעתי, המצאת המחשב יצרה בעיקר יותר זמן. שבו משתמשת האנושות באחד האופנים הבאים: חלק אחד של האנושות התחיל לייצר, ולדרוש, עוד משימות-פרוייקטים-חישובים-ודיאגרמות, שקודם הסתדרו יפה גם בלעדיהם. [למשל, אנשים באו לפגישה המכרעת והציעו שם הצעות בלי מצגת אורקולית מלאת גרפים בארבע צורות שונות, ואיכשהו העניין עבד גם בלי זה]. חלק אחר של האנושות התחיל לבזבז את הזמן שהשתחרר לו מעבודה-קשה-בחומר-ובלבנים, לכל מיני דברים על הסקלה שבין שטויות נוראיות להתבהמות רבתי. והחלק האחרון של האנושות ממשיך לחיות חיים קצרים וברוטליים כמו קודם. [מסקנות? אין. תמשיכו בעבודה הטובה, מדענים]. ------------- 1 זה רק בגלל ששוב הבאתם לאייל נושא שהוא לגמרי מעל הראש שלי, ועד מתי אפשר להחריש ביגון אל מול הנושאים הקשים? וחוץ מזה, אני לא פה. |
|
|
|
|
|
|
||
|
||||
|
איפו היינו זוכים להכיר אותך אם לא היה מחשב? | |
|
|
|
|
|
||
|
||||
|
היית מכיר אנשים אחרים, אמיתיים ולא וירטואליים. | |
|
|
|
|
|
||
|
||||
|
את לא אמיתית? | |
|
|
|
|
|
||
|
||||
|
שכחת את החלק שמאבד את מקום עבודתו משום שכבר אין בו צורך. | |
|
|
|
|
|
||
|
||||
|
אני חושש שחלק ניכר מהפיתוחים הטכנולוגיים לא שיפרו את חיי האדם באיזשהו אופן משמעותי, וחלקם גם דרדרו אותם לבלי הכר. חלק ממה שמניע חלק מהאנשים הוא הרצון להיטיב עם בני-מינם, ואפילו אז קורה שהם טועים. אין, כמובן וכמו שאמרת, הרבה מה לעשות בעניין הזה. ספציפית לגבי מחשבים קוונטיים, אם העסק יתממש נראה שהאנושות תקבל עוד כוח חישוב. זה טוב וזה רע, תלוי מה בוחרים לעשות עם זה. |
|
|
|
|
|
|
||
|
||||
|
בל נשכח את המטרות המרכזיות שלשמן הומצא המחשב: שליטה יעילה יותר בבני אדם והרג יעיל יותר שלהם. אלו מטרות שהוגשמו מעבר לכל ציפייה. כל השאר - תוצאות לוואי. | |
|
|
|
|
|
||
|
||||
|
כמה נחמד. גם שהמחשב הוא בסה''כ תוצאת לוואי שולית של המצאת הכתב, שכידוע נועדה לשלוט להרוג וכל השאר תוצאות לוואי וכו'. | |
|
|
|
|
|
||
|
||||
|
מה בנוגע למכוניות? הן הורגות יותר אנשים ממחשבים... | |
|
|
|
|
|
||
|
||||
|
כבר לא בונים יותר מכוניות ללא מחשבים. | |
|
|
|
|
|
||
|
||||
|
אם להתייחס ברצינות לרגע, אני דווקא אני יכול לחשוב על לא מעט דברים עתירי חישוב שירוויחו ממחשבים יעילים יותר. בעצם, כל מה שדורש היום שימוש במחשבי על, כמו מודלים טובים של מזג אוויר לדוגמא, ירוויח. לא חייבים מחשוב קוונטי בשביל לשפר דברים כאלה, אבל נראה שהמחשוב הקלאסי די הגיע לסוף יכולת השיפור שלו. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שחלק מהנקודה זה שלא כל מה שדורש היום שימוש במחשבי על, כדאי לעזור לו לקרות. לא שאני איזה אנטי-טכנולוג, אבל השאלה "האם יותר כוח (חישוב, למשל) זה טוב?" היא לגיטימית. יש אכן "לא מעט דברים עתירי חישוב שירוויחו ממחשבים יעילים יותר", השאלה היא מי מרוויח *מהם*. |
|
|
|
|
|
|
||
|
||||
|
אני מסכים. בגדול, השימושים העיקריים במחשבי על למיטב ידיעתי הם למטרות של אולטרה-אופטימיזציה. זאת אומרת שעושים סימולציות בתעשיית הרכב כדי להקטין את צריכת הדלק ולהגדיל את הבטיחות, כנ"ל בתעשיית המטוסים, ובמיוחד בתעשיית החלל, איפה שממש ממש יקר להשתמש במשהו שהוא לא סימולציה. שמעתי שאפילו מתכנני ערים בימינו עושים מודלים של ערים במחשבי על ומנסים לחזות פקקי תנועה. כך שיש הרבה מה לשפר ולהרוויח מהאפליקציות האזרחיות של מחשבי על. בכלי משחית, לעומת זאת, לא במיוחד מפריע לי שהם יהיו אולטרא-אופטימליים. וזאת משתי סיבות: א. כלי המשחית המתוכננים היטב נמצאים בצד של הטובים (המערב) ו ב. אם כלי המשחית הם אולטרא אופטימליים, אז גם טכנולוגיית האנטי כלי משחית משופרת באותה מידה. |
|
|
|
|
|
|
||
|
||||
|
המחשב הקלאסי הגיע לסוף יכולת החישוב שלו? הסבר בבקשה. |
|
|
|
|
|
|
||
|
||||
|
אם ההיסטוריה הגיעה אל סופה, למה אתה מצפה מהמחשב? | |
|
|
|
|
|
||
|
||||
|
כוונתי הייתה שאת טכנולוגיית המעבדים של היום קשה מאד לשפר. אם היום רוחב תעלה בטרנזיסטורים הטובים שמייצרים הוא 85 אנגסטרם, אז כבר אין עוד הרבה לאן ללכת - אם תרד כבר לרמות של 7.5-10 אנגסטרם, אז האלקטרונים יתחילו למנהר לך מצד לצד, ואפקטיבית הטרנזיסטור יהיה פרוץ. אבל זה רק הגבול התאורטי - כל 5 אנגסטרם של ירידה ברוחב תעלה נקנים עכשיו בדם, וחשוב מזה - ב-יִילדים נמוכים של אצוות הייצור. אז נראה שהטכנולוגיה הנוכחית של הפוטוליתוגרפיה כבר די מיצתה את עצמה, וכדי לשפר ביצועי מעבדים צריך פריצת דרך. (ואם לא ברור הקשר בין רוחב תעלה לביצועים, אז הוא הולך ככה: תעלה קצרה => טרנזיסטור מהיר => נתיב חישוב קריטי קצר => מחזור שעון מהיר יותר => יותר פעולות בשנייה => ביצועים משופרים) |
|
|
|
|
|
|
||
|
||||
|
המחשב הקלאסי לא הגיע לקצה היכולת שלו מאחר ובהחלט ייתכן (ואפילו סביר) שיש עוד הרבה שיפורים אלגוריתמים שאפשר יהיה לעשות. בניגוד למה שאלון אמר, יש הרבה אלגוריתמים בעולם חוץ מ linear programming. דרך אגב, גם מחשב קוואנטי לא יידע לעשות כל דבר, וחוץ מפירוק מספרים לגורמים (בעייה שבהחלט ייתכן שמישהו ימצא לה אלגוריתם קלאסי), אני לא מכיר בעיה חישובית מרכזית שמחשב קוואנטי פותר אקספוננציאלית יותר מהר ממחשב קלאסי. אני מסכים עם זאת, שלא ברור אוטומטית שיותר כח חישוב זה דבר טוב. אני מאמין שאם מסתכלים על העבר אז כוח החישוב עזר לנו להנות מהמון דברים - צריך לזכור שמחשבים מופיעים בכל מקום, ולכן גם תרופות, מכוניות, מטוסים ובעצם כמעט כל דבר משתמש היום בצורה קריטית במחשבים. לכן אסתי, גם אנשים באפריקה שאולי לא ראו מחשב ביתי אף פעם, משתמשים במוצרים שפותחו בעזרת מחשב. מצד שני, החשש העיקרי שלי לגבי העתיד הוא שכוח החישוב יפר את האיזון בין ממשלה לאזרח. למשל תארו לעצמכם מדינה שבה כסף מזומן יוצא מחוץ לחוק, ובה כל קנייה חייבת להיות ברטיס אשראי ולהיות במאגר ממוחשב. מצד אחד, במדינה כזו כמעט לא יהיה פשע. מצד שני, אני לא חושב שהייתי רוצה לחיות במקום כזה. חשוב לזכור שהמחשבים נותנים הרבה כח גם לאזרח הקטן, אם זה יכולות להצפין, ואם זה יכולת להוציא מידע לקהל עצום דרך האינטרנט. |
|
|
|
|
|
|
||
|
||||
|
היי, אלון לא אמר שאין בעולם הרבה אלגוריתמים חוץ מ-LP. אמרתי שחלק ניכר מהאלגוריתמים ה*פולינומיאליים* החשובים ניתנים להצגה כ-LP, ואף הדגשתי שלרוב הבעיות בתבל *אין* פתרונות פולינומיאליים. מדוע אתה סבור שכוח-חישוב רב יותר עשוי לקרב את התסריט של הכל-בכרטיסי-אשראי? אם מישהו היה מחליט לעשות זאת היום, איני חושב שזה היה קשה מדי, והמגבלה היתה אולי נפח אחסון, לא כח חישוב. |
|
|
|
|
|
|
||
|
||||
|
עד כמה שידוע לי, כל אלגוריתם פולינומיאלי ניתן להצגה כLP מאחר וזו בעיה P-שלמה, אבל זו לא הצגה מעניינת במיוחד. אני לא מומחה לאלגוריתמים אבל יש הרבה אלגוריתמים שאני מכיר והם לא LP (טרנספורם פוריה וכפל מטריצות מהיר, אדאבוסט, כל מני מבני נתונים). להרבה בעיות יש פתרונות פולינומיאלים ברגע שמבינים טוב יותר מהי משפחת הקלטים שעליה רוצים לעבוד, או שמבינים מה רוצים להשיג (למשל אם רוצים קירוב ולא פתרון מדויק). אני חושב שהבעיה העיקרית בלעשות תסריט כזה היום היא בטיחות (האקרים, התחזות וכו'), וכח חישוב בהחלט ישפר את הבטיחות. אחת הסיבות שמערכות היום לא בטוחות היא שכאשר יש בחירה בין יעילות לבטיחות הרבה פעמים בוחרים ביעילות. אם היו מאפשרים לך לכתוב תוכנה שיכולה להיות פי 10 יותר איטית מאשר המתחרות שלה, ולהשקיע פי 10 יותר משאבים בפיתוחה, היא היתה יכולה להיות גם הרבה יותר בטוחה. מעבר לזה, אחסון לא עוזר לממשלה לשלוט אם היא לא יכולה לסרוק ולהוציא מידע מהמאגר. לכן, אלגוריתמים טובים יותר לזיהוי שפות ותמונות, וכו' בהחלט יכולים לעשות שינוי מהותי במצב. |
|
|
|
|
|
|
||
|
||||
|
נראה לי שקצת התרחקנו ממשמעות הטענה המקורית שלי, ולא התכוונתי ליצור מזה כזה דיון, אבל בכל זאת: אני עדיין סבור שיש *הרבה* יותר בעיות ב-NP מבעיות ב-P, בכל דרך שתנסה לספור; זאת מנסיוני (שאינו רב מדי) אבל גם מנסיונם של אחרים, נדמה לי. אשמח להמשיך לדון בכך ולבסס את הטיעון, אבל חשוב להבהיר שזה לא קשור לשאלה אילו בעיות ניתנות ל*קירוב* בזמן פולינומיאלי - תחום מעניין, חשוב, מאוד פרקטי אבל אחר. בקשר ל-LP, לא הכרתי את ההגדרה של P-שלמות ולא התכוונתי לזה, אלא רק לכך ששאלות רבות הניתנות לפתרון פולינומיאלי זוכות לכך ע"י הצגה "טבעית" כ-LP. אתה צודק שיש עוד הרבה אלגוריתמים פולינומיאליים וממש חבל שנתווכח. נדמה לי שאתה גם מנסה להצביע על העובדה שב"חיים האמיתיים" אין לפעמים חשיבות לשאלה אם הבעייה היא ב-P או לא: לפעמים יש אלגוריתם לא פולינומיאלי אבל מעשי מאוד, ולפעמים האלגוריתם הפולינומיאלי איטי נורא. גם עם זה אני מסכים. לעניינים המעשיים: אין לי איזו דעה מוצקה בנושא, אבל נראה לי שהמחסומים שיעמדו בפני מימשל שינסה להכריח את כולם לעבוד עם כסף אלקטרוני נתון למעקב הם פוליטיים וחברתיים הרבה יותר משהם חישוביים. בעצם, אולי להיפך: שיפורים בכוח חישוב ומזעור יוכלו אולי להפוך פרוטוקולים מוגנים לחלוטין למעשיים יותר, ואולי אז הציבור יתרצה (אם כי לא הייתי בונה על זה). |
|
|
|
|
|
|
||
|
||||
|
יש אמרה "למי שמחזיק פטיש כל העולם הוא מסמר". ייתכן שמי שמומחה בLP ינסה (לאו דווקא באופן מודע) להציג כל אלגוריתם כLP (במיוחד מאחר וזה אפשרי עקרונית תמיד). אני חושב גם שאין לנו באמת וויכוח. רק רציתי להציל את כבודם האבוד של מפתחי האלגוריתמים (שאני לא נמנה עליהם), מאחר ומי שקורא את ההערות שלך עלול היה להבין שכל התחום הזה מורכב רק מהאלגוריתם אחד, שפיתחו אותו כבר לפני כמה עשורים. גם לי אין דעה מוצקה בנושא של העניינים המעשיים. יש סיבה אחת שגורמת לי לחשוב שייתכן והטכנולוגיה היא המכשול ולא המכשולים הפוליטיים או החברתיים. אני כרגע חי בארה"ב ואני רואה איך חברה שהוקמה על בסיס של חשד לממשל מרכזי, עדיין מוכנה לקבל על עצמה המון פגיעות זוחלות בפרטיות. זה מתבטא בכרטיסי אשראי ודירוג אשראי, במאגרי נתונים בבתי מרקחת (פה המחשב של הרשת זוכר מי אתה, מה הכתובת והטלפון שלך, ומה התרופה שרשמו לך), בפלאפונים, ב EZPASS ועוד המון דברים אחרים. |
|
|
|
|
|
|
||
|
||||
|
אה. לא התכוונתי, כמובן, להוליך את כבודם של מפתחי אלגוריתמים לאיבוד (ודווקא נמניתי על שורותיהם, פעם). | |
|
|
|
|
|
||
|
||||
|
זה נכון אם המדד שלך לביצועי מחשב הוא קצב השעון ומספר הטרנזיסטורים שלו. עדיין יש את האפיקים של הארכיטקטורה והרכיבים שמחוץ למעבד שיכולים להמשיך להצעיד את ביצועי המחשבים קדימה בקצב גבוה יותר מהרבה טכנולוגיות אחרות עוד שנים רבות. |
|
|
|
|
|
|
||
|
||||
|
מה עם שיפור על-ידי מקביליות? זה עדיין תחום פתוח לרווחה, לא? | |
|
|
|
|
|
||
|
||||
|
אני חושב שככה בונים היום מחשבי על בדרך כלל - המון פרוססורים במקביל. מה פתוח כאן לרווחה? חוץ מזה, עוד מעבדים זה סתם שיפור פולינומיאלי. מה שלוקח למעבד יחיד 2X זמן, יקח לשני מעבדים X זמן (+ קצת, האמת, אבל לא חשוב). למחשב קוונטי לעומת זאת יש תקווה כמעט בערך קצת פחות מפרקטית - הבנתי שאם נלמד לשתול בסיליקון יונים מזהמים בודדים אז יש מודל יפה מאד למחשב קוונטי שעושה בכך שימוש. (אל תעשה לי כזה פרצוף, אתה אמור לזכור מה זה סימום ממבוא למל"מ). אנחנו מאד רחוקים מזה היום. קודם כל, אנחנו לא יודעים לייצר גביש סיליקון נקי. בסמ"ק סיליקון יש 23^10 אטומים, ואנו יודעים לייצר אותו כיום כך שרק 13^10 אטומים ממנו הם זרים (זה אולי נשמע הרבה, אבל זה אומר שהסיליקון הוא 99.999999% טהור). שנית, אנחנו מזהמים את הסיליקון בדרך כלל בריכוז של 16^10, וזה כבר באמת רחוק מאד מ0^10. (נא לקחת את סדרי הגודל בערבון מוגבל, אני מסתמך על זיכרון בלבד. ה0^10 בטוח). |
|
|
|
|
|
|
||
|
||||
|
(מבוא למל"מ? מה אני נראה לך, חשמלטור? טוב, במקרה עשיתי עבודת גמר בתיכון על מל"מ, כך שידעתי מה זה סימום עוד לפני שידעתי מה זה רקורסיה.) (איכס, גיקים!) |
|
|
|
|
|
|
||
|
||||
|
(אני סבור שיש *הרבה* אנשים, לאו דווקא גיקים, שידעו מה זה סימום לפני שהם ידעו מה זה רקורסיה. חלקם לא יודעים מה זה רקורסיה עד היום). | |
|
|
|
|
|
||
|
||||
|
רקורסיה: אם אינך יודע מה זה רקורסיה, ע"ע רקורסיה. | |
|
|
|
|
|
||
|
||||
|
תגובה 221550 | |
|
|
|
|
|
||
|
||||
|
לרקורסיה צריך להיות תנאי עצירה. ואיך ידעת בדיוק איזה מספר תגובה תקבל ? |
|
|
|
|
|
|
||
|
||||
|
1. איתחול: בדוק מספר של תגובה מהזמן הקרוב (מאוד) והצב ב-n. 2. קרא לפונקציה הרקורסיבית "שטויות של איילים משועממים(n+1,1)". void שטויות_של_איילים_משועממים(n,m) { בדוק אם קיימת התגובה n ע"י הקישור www.haayal.co.il/thread?rep=n אם קיימת התגובה n אז קרא לפונקציה שטויות של איילים משועממים(n+1,0) אחרת הוסף תגובה (ממש מהר) עם קישור לתגובה n אם m=1 אז הוסף חיוך שובב וגיקי על פניך (סיימת!) } ___________ אם זה עדיין לא ברור תגובה 221666 תבהיר כבר הכל. |
|
|
|
|
|
|
||
|
||||
|
לא חשבתי על הצבה ב Url. אכן שיעמום הוא מרכיב הכרחי במתכון הזה. |
|
|
|
|
|
|
||
|
||||
|
הטכנולוגיה של הסיליקון אולי קרובה לסוף כמות האופטימיזציות שלה. אבל זה לא מפריע לטכנולוגיות דטרמניסטיות אחרות להתפתח. יש היום מחקר מסועף לגבי דרכי בניה של מעבדים זעירים יותר (לדוגמה: מחשבי דנ"א). הכיוון הזה נראה היום הרבה יותר ריאלי מאשר מחשבים קוונטיים. | |
|
|
|
|
|
||
|
||||
|
אבל מחשב קוונטי בטח ימצא את השאלה לתשובה 42. | |
|
|
|
|
|
||
|
||||
|
או שממש נשקיע. נבנה את המחשב הכי סופר-דופר-קוונטי שאפשר להעלות על הדעת ונשאל אותו את השאלה החשובה מכל: "יש אלוהים?"1. _____ 1 לאחר מספר שניות של חישובים ורשרושים הוא ידפיס את התשובה: "עכשיו יש! מוהאהאהא...". |
|
|
|
|
|
|
||
|
||||
|
אני לא יודע מה תהיה התשובה שלו, אבל אני בטוח שהוא יצטרף לדיונים באייל. ואני מסופק שתשובתו, לא משנה מה היא תהיה, תשנה במשהו את מסורת הדיון בשאלה זו. |
|
|
|
|
|
|
||
|
||||
|
אסימוב כתב סיפור מוצלח על רעיון דומה (ב''מחר כפול תשע'' אאל''ט). | |
|
|
|
|
|
||
|
||||
|
ופרדריק בראון כתב סיפור _זהה_ ממש, בן עמוד אחד. | |
|
|
|
|
|
||
|
||||
|
אכן (משם אני זוכר את זה). | |
|
|
|
|
|
||
|
||||
|
1. זהה למה? 2. לפני או אחרי אסימוב? (אצל אסימוב המחשב, שממוזער עד שנהיה לקראת קץ היקום ישות אבסטרקטית לא לוקאלית, עונה על השאלה ששאלו אותו במשך דורות "מה יקרה כשהאנטרופיה תגיע למקסימום?" בתשובה "יהי אור!") |
|
|
|
|
|
|
||
|
||||
|
הנה הסיפור של פרדריק בראון. הוא פורסם ב-54, שנתיים לפני "The Last Question" של אסימוב. ANSWER
Dwar Ev ceremoniously soldered the final connection with gold. The eyes of a dozen television cameras watched him and the subether bore through the universe a dozen pictures of what he was doing. He straightened and nodded to Dwar Reyn, then moved to a position beside the switch that would complete the contact when he threw it. The switch that would connect, all at once, all of the monster computing machines of all the populated planets in the universe, ninety-six billion planets, into the supercircuit that would connect them all into the one supercalculator, one cybernetics machine that would combine all the knowledge of all the galaxies. Dwar Reyn spoke briefly to the watching and listening trillions. Then, after a moment's silence, he said, "Now, Dwar Ev." Dwar Ev threw the switch. There was a mighty hum, the surge of power from ninety-six billion planets. Lights flashed and quieted along the miles-long panel. Dwar Ev stepped back and drew a deep breath. "The honor of asking the first question is yours, Dwar Reyn." "Thank you," said Dwar Reyn. "It shall be a question that no single cybernetics machine has been able to answer." He turned to face the machine. "Is there a God?" The mighty voice answered without hesitation, without the clicking of single relay. "Yes, now there is a God." Sudden fear flashed on the face of Dwar Ev. He leaped to grab the switch. A bolt of lightning from the cloudless sky struck him down and fused the switch shut. |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
גרובר מתאר אלגוריתם קוונטי לחיפוש במסדי נתונים בסיבוכיות זמן O(sqrt(n)) ובסיבוכיות מקוםO(log n). זאת בזמן שאלגוריתמים קלאסים קיימים עובדים בסיבוכיות זמןO(n) - הם פשוט עוברים על כל הרשומות.n מציין כאן את מספר הרשומות במסד הנתונים. כבר נבנו מספר מודלים פיזים למסדי נתונים קוונטים, ואפילו הצליחו למצוא את הרשומה הרצוייה מבין 4 רשומות (כן, כן). |
|
|
|
|
|
|
||
|
||||
|
בינתיים מסדי נתונים לא קופאים על שמרייהם, אלא משפרים את הטכנולוגיה. לדוגמה: מנסים לדאוג לכך שכמה שיותר מהנתונים יהיו בזכרון, ולא רק על הדיסק. דואגים גם לעבוד עם אינדקסים, כדי לעבור על כמה שפחות נתונים. ככה שהיום חיפושים הם לא בהכרח O(n). ולסיום, אתגר קטן ולא רלוונטי לנושא: איך אפשר לכתוב, כמו למעלה, O(n) עם סוגריים במקום ובכוון הנכון? |
|
|
|
|
|
|
||
|
||||
|
אתה מבלבל בין הסיבוכיות החישובית ובין החלק הקבוע (כמה זמן לוקח לגשת לדיסק/זיכרון). השימוש בנוטציה: 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 עובדת בזמן אקספוננציאלי...
|
|
|
|
|
|
|
||
|
||||
|
נכון. הזמן הנדרש לכתיבת הפלט נחשב כחלק מזמן החישוב. זה אפילו באמת לוקח זמן. אני זוכר כל מיני שאלות בחישוביות שכדי להמנע מהבעיה הטכנית הזו דרשו שהקלט יהיה מספר אונארי |
|
|
|
|
|
|
||
|
||||
|
תודה. | |
|
|
|
|
|
||
|
||||
|
שלום איזי, תודה על המאמר. אני הבנתי ש: 1)מחשב קוונטי ניתן לסימלוץ ע"י מכונת טיורינג ולכן לא יכול לטפל בבעיות בלתי כריעות (בלתי פתירות). לכל היותר הוא יוכל לפתור בזמן סביר בעיות שאינן פתירות בזמן סביר על מחשב קלאסי, וגם זה עוד לא הוכח. 2)יש הצפנות סימטריות ואסימטריות (כמו RSA) ורק האסימטריות יפלו שדודות מפני המחשב הקוונטי. אתה טוען שלא כך הדברים? |
|
|
|
|
|
|
||
|
||||
|
1. נכון. 2. יש הצפנות א-סימטריות ספציפיות שידוע אלגוריתם למחשב קוונטי שיפצח אותן בזמן סביר, בעוד שנכון להיום לא ידוע אלגוריתם כזה למחשב קלאסי. |
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
ועוד מחדר החדשות: http://hardware.slashdot.org/article.pl?sid=05/06/22... | |
|
|
|
|
|
||
|
||||
|
ועכשיו יש קיובייט (שמונה ביטים קוואנטים): http://science.slashdot.org/article.pl?sid=05/12/02/... | |
|
|
|
|
|
||
|
||||
|
תוסיף לזה את ששה הקיוביטס של האמריקאים, ויש לך 14! |
|
|
|
|
|
|
||
|
||||
|
אני אישית לא מבין מה כל כך טוב בחתול בתוך המחשב בעיקר כשלא יודעים אם הוא מת או חי. | |
|
|
|
|
|
||
|
||||
|
זה ברור לחלוטין מה תפקידו של החתול במחשב: הוא מזיז את העכבר! | |
|
|
|
|
|
||
|
||||
|
מזיז? אני צריך ללכת כל יום ולקנות אחד חדש. ססאמק היפנים האלה והחידושים שלהם. | |
|
|
|
|
|
||
|
||||
|
אז תזרוק את החתול, אתה לא חייב להחזיק אותו. | |
|
|
|
|
|
||
|
||||
|
איך אזרוק ואני בכלל לא בטוח שהחתול קיים? | |
|
|
|
|
|
||
|
||||
|
חשבתי שאתה יודע שהוא קיים, רק לא בטוח אם הוא בחיים. | |
|
|
|
|
|
||
|
||||
|
הוא גם יודע שהוא בחיים. חתול מת לא תופס עכברים. |
|
|
|
|
|
|
||
|
||||
|
אבל חתול שלא קיים בטוח שלא תופס עכברים. | |
|
|
|
|
|
||
|
||||
|
"demonstrated a circuit that can control the state of a pair of elemental particles and how strongly they interact with one another." מרגש - הם הצליחו לבנות מעגל של שני קיוביטים.
|
|
|
|
|
|
|
||
|
||||
|
אני בהחלט מוכן להתרגש אבל כבר בזבזתי את כל האמוציות היום על האף המדמם של נאש. | |
|
|
|
|
|
||
|
||||
|
עוד מאמר מוזר במדור המדע של YNET. בניגוד לכתוב במאמר הנ"ל, מחשב קוונטי לא מפר את תזת צ'רץ'-טיורינג (ניתן להריץ סימולציה של מחשב קוונטי על מכונת טיורינג, במחיר של זמן ריצה ארוך הרבה יותר) ומחשב קוונטי בטח שלא פועל "כמו מעבד מקבילי עצום המותקן על פיסת תוכנה אחת." (אחד המשפטים המוזרים ביותר שנתקלתי בהם, אני מקווה שזה תרגום גרוע ושאין באמת פרופסור בריטי שאמר את זה). זה משתלב טוב עם: http://www.ynet.co.il/articles/0,7340,L-3504880,00.h... ו http://www.ynet.co.il/articles/0,7340,L-3511090,00.h... נראה שמחשב קוונטי (או חישוב קוונטי) זה קצת יותר מסובך מאוסף של קיוביטים ושערים קוונטים-לוגיים. מסתבר, שבמודלים מסויימים של מחשבים קוונטים, אם יש הסתברות לרעש מעל סף מסויים (כלומר ההסתברות לשינוי ספונטני במצב של קיוביט בין השערים או ששער יוציא פלט שגוי היא מעל סף מסויים) אז ניתן לבצע סימולציה קלאסית (הסתברותית) למודל החישובי הזה, כלומר אין לו שום יתרון על חישוב קלאסי. חשוב לציין, שנכון להיום, שערים קוונטים "מושלמים" הם רחוקים מהשגה וחלק מהמודלים חשופים מאוד לרעש. מצד שני נעשים מאמצים לבנות מודלים של תיקון שגיאות ועמידות לשגיאות (בדומה למה שקיים במחשבים קלאסים) ויש סיבות לאופטימיות זהירה. |
|
|
|
|
|
|
||
|
||||
|
אמנם תמוה, אבל ספציפית נראה שלגבי צ'רץ'-טורינג אתה טועה. מתוך המאמר: "מכאן, נראה שלטבע, הפועל על פי מכניקת הקוונטים, יש יתרון ביכולת החישוב שלו מול מחשב "קלאסי" (כלומר, מופרת תזת צ'רץ'-טיורינג הפיזיקלית בגירסתה החזקה)." מתוך ויקיפדיה (http://en.wikipedia.org/wiki/Church%E2%80%93Turing_t...): Another variation is the Strong Church–Turing Thesis (SCTT), which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory. It states (cf. Bernstein, Vazirani 1997):
"Any 'reasonable' model of computation can be efficiently simulated on a probabilistic Turing machine." |
|
|
|
|
|
|
||
|
||||
|
טוב, באמת לא זכרתי את ה-efficiently, ואם הכוונה במילה הזאת היא ל"בזמן ריצה שהוא לכל היותר חזקה קבועה של זמן הריצה המקורי", אז יש סיכוי טוב שהתזה האמורה באמת לא נכונה. מצד שני ב-1997 המחלקה BQP כבר היתה מוכרת ומוגדרת היטב, כך שלפרסם תזה כזאת נראה משונה. אני אשתדל לזכור לשאול את המנחה שלי בפגישתנו הקרובה. | |
|
|
|
|
|
||
|
||||
|
הציטוט הוא ממאמר שפורסם ב-97, אין זה אומר שהתזה החזקה היא מ-97. | |
|
|
|
|
|
||
|
||||
|
יש מסתבר מחשב קוונטי שיודע לעשות פעולות מסויימות, מישהו יכול להסביר איך, ואיזה פעולות? |
|
|
|
|
|
|
||
|
||||
|
מהכתבה לא הבנתי שום דבר לגבי אופן הפעולה של המעבד ויכולותיו. הוזכרו שם מספר מושגים שלא כל כך קשורים זה לזה: * מינהור קוונטי [ויקיפדיה] (tunneling) אפקט קוונטי ידוע שמשמש (בין השאר) לבניית טרנזיסטורים מהירים, אבל לא נראה שזה הסיפור כאן. ביצוע סימולציה של האפקט הקוונטי (באופן קלאסי לחלוטין) מאפשר למצוא מינימום גלובלי של פונקציות מסויימות שיש להן מינימות לוקליות רבות. הטכניקה הזאת (שכאמור, ניתן לבצעה בכל מחשב רגיל) שימושית לפתרון בעיות מסויימות, אבל אין לה שום קשר למחשב קוונטי. * קיוביט [ויקיפדיה] - יחידת המידע הבסיסית בעולם הקוונטי. מחשב קוונטי אמור לבצע פעולות מתמטיות ולוגיות על קיוביטים, לא ברור אם המעבד המוזכר בכתבה מסוגל לבצע דבר כזה. * בעיית הסוכן הנוסע [ויקיפדיה] - בעייה קשה במיוחד לפתרון, שנכון למה שידוע כיום, מחשב קוונטי לא יוכל לפתור ביעילות שעולה על זו של מחשב רגיל. לא נראה לי שמדובר באמת במחשב קוונטי. אני מנחש שמדובר במחשב "קלאסי" שמסוגל לבצע סימולציה של מנהור באופן יעיל במיוחד. |
|
|
|
|
|
|
||
|
||||
|
בעקבות ההפניה של אורי להסברים של סקוט אארונסון, מתברר שלטענת D-Wave הם הצליחו לבצע סימולציה של מנהור קוונטי באמצעות מעבד שמשתמש בקיוביטים וכך למצוא מינימום גלובלי של משפחת פונקציות. אם זה נכון זה הישג מרשים אבל: 1. לא מדובר במחשב קוונטי שמסוגל לבצע חישובים כלליים ולהריץ כל אלגוריתם קוונטי (למשל פירוק לגורמים של מספרים גדולים) אלא במערכת שפותרת בעיה ספציפית. 2. הביצועים של המעבד שלהם בפתרון הבעיה הספציפית נחותים מהביצועים של מחשב רגיל שעולה פחות מאלפית המחיר של המחשב שהם מציעים (כאמור, זאת בעיה שיש לה אלגוריתם קלאסי). שורה תחתונה: מוקדם לפתוח את בקבוקי השמפניה, אבל יש סיכוי שמדובר בעוד צעד בכיוון הנכון. |
|
|
|
|
|
|
||
|
||||
|
"יש סיכוי שמדובר בעוד צעד בכיוון הנכון" זה משפט סיכום נהדר לענייני חישוב קוונטי. | |
|
|
|
|
|
||
|
||||
|
את חדשות הD-WAVE שלי אני לוקח עם קורט סקוט אארונסון. | |
|
|
| חזרה לעמוד הראשי | |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |