שאלה אחת, יום אחד

[MegaMango]

שאלה אחת, יום אחד

מחר ב-6 אני מפרסם את הפיתרון של השאלה הזו. נראה אם מישהו מצליח לפתור אותה לפני. מוהאהא.(סתם בגלל שמשעממם לי) כתוב אלגו'(רעיון יספיק) שמקבל n ובודק האם n הוא מהצורה a בחזקת b כאשר a,b טבעיים ו b>1 . האלגו' חייב לרוץ ביעילות פולינומיאלית ביחס ל - log n כלומר (logn) בחזקת מספר קבוע. טיק טק..

 

[ron369]

חייב להיות דטרמיניסטי?

 

[ron369]

זה יותר קל משחשבתי, אני מכיר את זה

איזה רמאי אני

מנסים לעשות: sqrt_2 ואז sqrt_3 ואז לפי 4, וכולי. וכך ממשיכים עד ללוגריתם של המספר n. הסיבוכיות היא lg^2(2). (חישוב הלוגריתם גם לוקח, כמובן, זמן לוגריתמי) אם באחד מהשלבים קיבלנו מספר שלם, אזי סיימנו, והתשובה היא "כן". ואחרת התשובה היא "לא". אפשר גם להחזיר את a,b. צריך עוד להראות ש x^lgn >= n לכל x בין 2 לבין n. אבל זה ברור, כי המקרה של 2 הוא "הכי גרוע", ובמקרה זה ZZZ 2^lgn = n ZZZ. ונכונות האלגוריתם "הוכחה". מש"ל

 

[MegaMango]

שלילי! יש אלגו' דטר' שלא משתמש

בשורשים. הבעיה עם שורשים היא שהדיוק שלהם סופי. אם רוצים דיוק אינסופי, הפעולה רחוקה מלהיות o(1) או o(logn( ייתכן שיצא לך מספר בסנגון 4.000000000000000000000000000001 והאלגו' יטעה. למה שיצא לך מספר כזה? בגלל ש-n סתם מספר נבזי ומרושע. קיצר, בלי שורשים. אין חוכמות. כלומר, יש חוכמות, אבל צריך בעזרתן לתת פיתרון מגניב ולא מעורער P: אל תיכנע עדיין ^^

 

[ron369]

לא בהכרח, כי אפשר לבדוק בחזרה

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

 

[MegaMango]

מעורר תהיה.

אני בטוח שעבור n ים גדולים מספיק, כל טור סופי לא ייתן משהו בסדר גודל logn. למשל, 4.000000000000000000000000000000001 4.000000000000000000000000000000002 4.00000000000000000000000000000000001 4.000000000000000000000000000000000003 מובן שכדי להגיע למספרים כאלה אתה צריך n שטני ממש, אבל אני עדיין מתקשה להאמין שתוכל עם שורשים בלבד להבטיח את הנכונות של האלגו' ואם כן את הנכונות, אז לא את היעילות המתבקשת. אולי אני טועה...למה שלא תוכיח שעבור טור מסויים(שאיתו תחשב את השורש) תוכל להסתדר עם כל ?n D: יהיה הרבה יותר קל לפתור את השאלה כמו שצריך P:

 

[גיל14]

אפשר להגיע לדיוק מספיק, לא אינסופי

 

[ron369]

אגב, אם לא הייתי יודע,

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

 

[MegaMango]

XD

צירוף מקרים?

 

[sagima]

רעיון...?

אם n הוא מהצורה a בחזקת b, אז n מתחלק ב a , אפשר לרוץ עבור a מ 2 עד שורש n (ואפשר לדלג על כל המספרים הלא ראשוניים), ולחפש את b (ע"י חלוקה של n ב a ).

 

[ron369]

הסיבוכיות של זה היא שורש-n,

לדעתי.

 

[MegaMango]

שלילי.

ריצה על המספרים הראשונים הייתה יוצרת לך אלגו' שבממוצע רץ באמת ב-logn כי זו הצפיפות שלהם ביחס למספרים הלא ראשוניים... הבעיה היא שהאלגו' לבדיקת ראשוניות היחיד שיעיל מספיק הוא הסתברותי וזה הופך גם את האלגו' שלך להסתברותי. לא תוכל לייצר טבלה שמכילה את כל המספרים הראשוניים בעולם כי מן הסתם, יש אינסוף כאלה ובחישוב סיבוכיות משאיפים את n לאינסוף. אם לא נדלג על המספרים הלא ראשוניים, אז אתה רץ n בחזקת חצי שזה..נאיבי למדי ורחוק מאוד יעילות של logn \=

 

[ron369]

יש או-n/lgn מספרים בקטע [0,n], אאלט

[1][2][3] (השלישי סתם נראה מעניין

3.gif> )

 

[ron369]

אה, ההמשך

הייתי עסוק בלמצוא הוכחות, ששכחתי ממנו

ולכן נראה לי שצריך לעבור על ZZZ sqrt/lg(sqrt) = O(sqrt/lgn)ZZZ ולא על O(lgn) מספרים. כך ש, גם אם היו נתונים לנו המספרים הראשוניים, עדיין זה לא היה עוזר. (אגב, השגיאה בהודעה הקודמת היא, לדעתי, של תפוז (או שזה רק אצלי?). נראה שקודם הם מחליפים בטקסט את האייקונים : - ) בתמונות

, ורק אז את הקישורים)

 

[cohenman]

נכון P: הניסיון הזה היה חסר גאולה

תנטשו את המספרים הראשוניים כל עוד אתם יכולים.

 

[cohenman]

XD לא שמתי לב לשם משתמש . זה מגה

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

 

[yossiea]

נראה לי...

שהבעייה הזו מוכרת לי קצת מתורת המספרים. למספר מהצורה n=x^k קוראים perfect power, והפתרון לבעיה כזאת לא קשה הבעיה קרויה: testing perfect powers שכחתי את התרגום ההולם למילה הזו, אני יבדוק אח"כ, בכל אופן הסיבוכיות של אלגוריתם כזה היא: O((lg^3 n) lg lg lg n) וחייבים לבצע את זה עם כל הראשוניים עד lg n עבור n שאנחנו בודקים. הרעיון הוא לעשות חיפוש בינארי של x כזה שמקיים: n = x^p בטווח: [2, 2^(lg n / p + 1)] כדי למצוא ערך מקורב ל-n^(1/p). לבעיה זו יש זיקה לקריפטוגרפיה, ככלל לא משתמשים במספרים כאלו כי זה קל לפתור את זה. אם תרצה פרטים נוספים עיין בספרים על קריפטוגרפיה.

 

[MegaMango]

לא ._.

יש פיתרון שלא דורש שום טבלה של מספרים ראשוניים לפני. אגב, lg lg lg n יותר יעיל מ- (log n) בחזקת שלוש. אם אני אתן לך n שהוא מכפלה של כל המספרים הראשוניים הידועים בעולם בעלי מיליון-תאלאפים ספרות(הגיעו ל-400 ספרות בערך, נכון?) ואוסיף לו x חיובי כלשהו, אעשה לזה חזקת גוגל פלקס ואז אעשה גוגל פלקס בחזקת כל המספר הזה, ואז אני אוסיף 17(סתם בשביל העיקרון), כדי לחשב את המספרים הראשוניים עד למספר הזה תצטרך יותר מ logn פעולות. גם יותר מ log log log n פעולות. נכון, ייתכן שגם עם האגו' שאין לו הנחות שפועל ב log n בחזקת משהו לא יסיים במיליניום הקרוב או זה שאחריו, אבל לא עקרוני D: קיבלתי את זה כאחת השאלות בתרגיל 2 של קורס אלגוריתמים 2 במכללה למינהל לפני כמה שבועות ועוד לא למדנו קריפטוגרפיה(סימסטר הבא, אם אני לא טועה) ותורת מהספרים...ממ...לא התעסקנו עם אלגוריתמים מתורת המספרים (רק אלגו' אחד מגניב לקידוד שלוקח מספר ומחלק אותו כל פעם במקום אחר. שכחתי את השם של זה)

 

[yossiea]

אני חושש...

שאם הבעיה שלך אכן מקבילה לנושא perfect power אזי זה לא נשמע מציאותי שישנו אלגוריתם שעובד בלי רשימת ראשוניים (אגב לא קשה להכין רשימה כזאת יש אלגורתמים די פשוטים בסיבוכיות נמוכה ראה נפה של ארטוסטנס למשל). אבל אתה מרחיק לכת עם הסדר גודל שאתה מציין זה לא ממש רלוונטי, כי אם יש כלים שיכולים לבצע חישובים בסיסיים בסדר גודל כזה אז האלגוריתם הנ"ל יעבוד הכי טוב שאפשר פלוס מינוס במסגרת הכלים הללו) ובמיוחד שיש לזה השלכות על הנושא שהזכרתי. אלא אם כן הבעיה שלך שונה. אמנם ראיתי אלגוריתם בסיבוכיות טובה יותר אבל הוא משתמש בפרוצדורות מסובכות, תוכל לקרוא על זה כאן: http://cr.yp.to/lineartime/powers2-20050509.pdf ובעוד מקומות. יכול להיות שתמצא משהו קרוב מעט משופר. אבל לא יותר מזה. אשמח לשמוע על דרך טובה יותר.

 

[MegaMango]

הפיתרון שלי. אל תסקלו אותי, בבקשה.

יש לי תחושה שעכשיו תמצאו בו פגמים...לא חשבתי שזו שאלה קשה. בכל מקרה, הרעיון הוא במקום למצוא את a ואז לחפש את b , למצוא את b ואז לחפש את a . איך מוצאים את b? ובכן, אי אפשר ממש למצוא אותו, אבל אפשר להניח מה הוא. נתון לנו ש a,b מספרים טבעיים אחרי הכל. אם n שווה לאחד אז האלגו' יחזיר מן הסתם a=1 ו b=2 ופתרנו את הבעיה. אם n לא שווה לאחד, אז מובן שגם a גדול מאחד. אם a גדול מאחד, בטוח שהמספר b קטן או שווה ל log n בבסיס 2 (כי 2 זהו הבסיס האפשרי הקטן ביותר). אז נעשה לולאה שרצה מ-1 עד logn(חישוב לוג עולה לוג) ובכל איטרציה מניחים שמס' האיטרציה זה ה-b הנכון. כעת, משיש לנו הנחה לגבי b , איך מוצאים את a ? חיפוש בינארי! נעשה חיפוש בינארי מ-2 עד n . כל פעם נבחר a אחר. את ההשוואה ושינוי Imax ו Imin נעשה אחרי שנעלה את a בחזקת b . העלאת a בחזקת b עולה לנו לוג בשלישית. אם המספר שיצא לנו, ה-a שיצא לנו בחזקת ה b שהנחנו קטן מ-n(השוואה גם עולה לנו לוג ) אז נגדיל את Imin . אם הוא גדול מ- n , נקטין את Imax. בסופו של דבר או שנמצא a שיהיה שווה לn בדיוק, או שנגיע למסקנה בחיפוש הבינארי שאין a כזה ונעבור בחינניות לb הבא. שום פרוצדורות מורכבות ושום הנחות, ובלי מספר ראשוני שיקוצי אחד! הדבר הזה עולה לנו משהו כמו log n בחזקת 4 בגלל הלולאה שכל פעם עושה העלאה בריבוע. (פלוס לוג להשוואות, פלוס לוג לשינוי האינדקסים,פלוס לוג לחיפוש הבינארי המאולתר)