משהו שמעניין אותי random בתכנות?

[elixvx]

אלהן, יש יש לי שאלה קצת מוזרה שמאוד מעניינת אותי.

אני כרגע לומד תכנות בC# לבגרות (מדעי המחשב ב')

וסתם אתמול יצא לי להשתמש במחלקה "random"

(שכאמור נותנת לך מספר אקרעי בין 0 ל-n-1)

ומאוד מעניין אותי איך המחלה הזאת בעצם עובדת?

בכללי איך גורמים למחשב לעשות משהו אקראי?

הרי המחשב מתוכנן לעשות דברים מוגדרים, קצת קשה לי להסביר עצמי.

כלומר הוא הרי לא יכול "לבחור"? אז איך זה בעצם עובד?

[TheReaper]

מתוך MSDN

Pseudo-random numbers are chosen with equal probability from a finite set of numbers. The chosen numbers are not completely random because a definite mathematical algorithm is used to select them, but they are sufficiently random for practical purposes. The current implementation of the Random class is based on a modified version of Donald E. Knuth's subtractive random number generator algorithm. For more information, see D. E. Knuth. "The Art of Computer Programming, volume 2: Seminumerical Algorithms". Addison-Wesley, Reading, MA, second edition, 1981.

The random number generation starts from a seed value. If the same seed is used repeatedly, the same series of numbers is generated. One way to produce different sequences is to make the seed value time-dependent, thereby producing a different series with each new instance of Random. By default, the parameterless constructor of the Random class uses the system clock to generate its seed value, while its parameterized constructor can take an Int32 value based on the number of ticks in the current time. However, because the clock has finite resolution, using the parameterless constructor to create different Random objects in close succession creates random number generators that produce identical sequences of random numbers. The following example illustrates that two Random objects that are instantiated in close succession generate an identical series of random numbers.

[שניצל]

הסבר שלי בעברית כאן:

http://hwzone.co.il/community/index.php?topic=524569.msg4479414#msg4479414

[Maor_Splinter]

תהנה:

http://www.gadial.net/?p=189

[elixvx]

תהנה:

http://www.gadial.net/?p=189

תודה רבה! למרות שלא ממש הבנתי עד הסוף זה בהחלט מעניין.

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

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

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

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

[שניצל]

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

http://he.wikipedia.org/wiki/%D7%9E%D7%9B%D7%95%D7%A0%D7%AA_%D7%98%D7%99%D7%95%D7%A8%D7%99%D7%A0%D7%92

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

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

[elixvx]

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

http://he.wikipedia.org/wiki/%D7%9E%D7%9B%D7%95%D7%A0%D7%AA_%D7%98%D7%99%D7%95%D7%A8%D7%99%D7%A0%D7%92

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

הבנתי.

ועוד שאלה שעלתה לי הרגע.

איך בעצם ייתכן שהסרט של מוכנת טיורינג הוא אינסופי? האם זה כך רק בתאורייה?

כלומר לא ייתכן שמחשב כלשהו יוכל לשמור קלט\רצף אינסופי של תווים או כל דבר אחר.

(כמובן שאני מאמין שהיום אפשרי להגיע לכמויות עצומות אך בכל זאת זה ממש לא אינסופי)

ואם באמת יוצא שהסרט הוא אינסופי אז בתאוריה היא תוכל לבצע כל כחישוב (סופי) אם רק יהיה לה מספיק מצבים לא?

אני ממש מבולבל...

[Maor_Splinter]

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

http://he.wikipedia.org/wiki/%D7%9E%D7%9B%D7%95%D7%A0%D7%AA_%D7%98%D7%99%D7%95%D7%A8%D7%99%D7%A0%D7%92

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

אני מוכרח לתקן אותך:

המודל האי-דטרמיניסטי לא מוסיף שום "חוזק", לא "חוזק" חישובי ולא "חוזק" סיבוכי.

יש למחלקה NP הגדרה נוספת: "מחלקת הבעיות שניתן לוודא בזמן פולינומיאלי" - כלומר, בעיה A שייכת ל-NP אם קיימת מכונת טיורינג דטרמיניסטית M שמקיימת את התכונה הבאה:

בהינתן קלט x, x שייך ל-A אם ורק אם קיים עד w (מלשון "נותן עדות"); כאשר הגודל של w הוא פולינומיאלי בגודל של x (זה חשוב ביותר!!), כך ש-M מחזירה "אמת" בריצתה על הזוג (x,w) בזמן ריצה פולינומיאלי בגודל הקלט.

דוגמא להמחשה: "קבוצת הגרפים שיש בהם מעגל המילטון (מעגל שמבקר בכל קודקודי הגרף בדיוק פעם אחת)" היא ב-NP. כי בהינתן גרף (הקלט x שלנו) וסדרה של קשתות (העד w) ניתן "בקלות" (בזמן פולינומיאלי) להחזיר "אמת"/"שקר" בהתאם לשאלה "האם בגרף שלנו x יש מעגל המילטוני". המכונה M בסך הכל צריכה לבדוק האם סדרת הקשתות מהווה מעגל המילטוני.

בהגדרה הזאת אין שום אלמנט אי-דטרמיניסטי שבד"כ מקושר למחלקה NP.

לשאלות של elixvx:

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

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

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

[שניצל]

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

(כמובן, כל זה תחת ההנחה ש-P != NP, מה שאנחנו עדיין לא יודעים)

[Maor_Splinter]

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

(כמובן, כל זה תחת ההנחה ש-P != NP, מה שאנחנו עדיין לא יודעים)

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

אני חושב שהתכוונת לכך שניתן לסמלץ מכונה אי-דטרמיניסטית ע"י מכונה דטרמיניסטית (ובכך לקבל מכונה ש"תפתור" את הבעיה בצורה הדטרמיניסטית) אבל אז נקבל מכונה שזמן ריצתה הוא אקספוננטצילי (מעריכי); זאת תחת ההנחה ש-P שונה מ-NP כמובן.

[שניצל]

הבעיה במשפט שלךנובעת מכך שההגדרות של "לפתור בעיה" במכונה אי-דטרמיניסטית ובמכונה דטרמיניסטית הן שונות.

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

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

[Maor_Splinter]

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

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

אני לא דיברתי על ההבדל (או הקשר) בין בעיות הכרעה לבעיות חיפוש.

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

הכרעה במודל הא"ד היא תחת תנאים "מקלים יותר" (כל מכונה דטרמיניסטית היא בפרט א"ד).

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

מה שכן אפשר להגיד אוליי בכל זאת (ואוליי זאת הייתה הכוונה שלך) הוא שהמודל הא"ד יכול לספק לנו בפועל מימושים ואלגוריתמים יעילים יותר מהמודל הדטרמיניסטי, אבל עדיין מימושים אלה אינם מוגדרים להיות דטרמיניסטים. (http://www.gadial.net/?p=202)

[שניצל]

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

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

ההגדרה של "לפתור" בעיה היא פשוטה מאוד: אם מדובר בבעיית הכרעה, לדוגמה, אז "לפתור" בעיה זה לענות על השאלה "בהינתן שפה L, האם הקלט x שייך לשפה".

[Maor_Splinter]

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

ההגדרה של "לפתור" בעיה היא פשוטה מאוד: אם מדובר בבעיית הכרעה, לדוגמה, אז "לפתור" בעיה זה לענות על השאלה "בהינתן שפה L, האם הקלט x שייך לשפה".

אתה טועה ומטעה.

כמובן שלא ההבדל בין שני המודלים הוא מה שהופך את הגדרת ה"לפתור" (ומעכשיו "להכריע בעיה") לשונה בכל אחד מהם.

הנקודה היא שההגדרה של "להכריע בעיה" בכל אחד מהמודלים היא שונה ומכאן נובעת השגיאה שלך במשפט ההוא.

האם אתה רואה שקילות בהגדרות הבאות:

א. נאמר שמכונה דטרמיניסטית M מכריעה בעיה A אם בהינתן קלט x מתקיים ש:

x שייך ל-A אם ורק אם M בריצתה על x מחזירה "אמת". (הדרישה פה היא שהמכונה תמיד תחזיר תשובה נכונה)

ב. נאמר שמכונה אי-דטרמיניסטית M מכריעה בעיה A אם בהינתן קלט x מתקיים ש:

x שייך ל-A אם ורק אם קיימת ריצה כלשהי של המכונה M על x שבה היא תחזיר "אמת".

ובנוסף, בשתי ההגדרות קיים האילוץ שזמן הריצה של המכונה הוא פולינומיאלי בגודל של x.

?

[שניצל]

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