אופסשםמשתמש פורסם אוקטובר 6, 2012 דיווח שיתוף פורסם אוקטובר 6, 2012 מכירים את האלגוריתם הנאיבי להתאמת מחרוזות ? נניח יש לי טקסט ארוך T , ומחרוזת קצרה S .. אני רץ עד שאני שם לב שהאות הראשונה בS מתאימה לאות שאני נמצא בה בT. אם זה מתאים ,אני ממשיך לאות השניה .. נניח באות החמישית זה נדפק .. אני ממשיך בT מהמקום שבו מצאתי את ההתאמה הראשונה. לכן בהנתן והאורך של S זה m והאורך של T זה n הסיבוכיות היא : O(n*m) dd כל זה לידע כללי, עכשיו השאלה : נניח שהמחרוזת P והטקסט T הם מחרוזות באורך m וn בהתאמה, שנבחרו באקראי מאלפבית בין d תווים , כאשר d מכיל יותר מ2 תווים. הראה כי תוחלת ההשוואות בין תווים בודדים (באלגוריתם הנאיבי) היא : [jstex](n-m-1)*\frac{(1-d^{-m})}{(1-d^{-1})}<= 2(n-m+1) [/jstex] אין לי מושג איך להתחיל לחשב את זה.. אפשר קצת כיוון או עזרה ? אגב, איך אני הופך את זה שיראה כמו נוסחא ? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
Boris פורסם אוקטובר 6, 2012 דיווח שיתוף פורסם אוקטובר 6, 2012 בשביל שזה יראה כמו נוסחה אתה צריך להשתמש בטאג [jstex] ואז לכתוב את זה בקודי tex ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
אופסשםמשתמש פורסם אוקטובר 6, 2012 מחבר דיווח שיתוף פורסם אוקטובר 6, 2012 בשביל שזה יראה כמו נוסחה אתה צריך להשתמש בטאג [jstex] ואז לכתוב את זה בקודי tex איפה יש tutorial לגבי איך לרשום את זה ? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
QuatzeQuatel פורסם אוקטובר 6, 2012 דיווח שיתוף פורסם אוקטובר 6, 2012 אתה יכול לתת את ההגדרה של "תוחלת השוואה בין תווים בודדים"? מכל מקום, באגף שמאל יש לך (n-m-1) מוכפל בסכום של סדרה גיאומטרית סופית, שהמנה שלה היא d^-1. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
Boris פורסם אוקטובר 6, 2012 דיווח שיתוף פורסם אוקטובר 6, 2012 בשביל שזה יראה כמו נוסחה אתה צריך להשתמש בטאג [jstex] ואז לכתוב את זה בקודי tex איפה יש tutorial לגבי איך לרשום את זה ? יש כזה עורך שנותן לך קוד (אם שאתה יכול להשתמש בתמונה שהוא יוצר) כאן: http://www.codecogs.com/latex/eqneditor.php פה יש רשימה ארוכה של קודים http://web.ift.uib.no/Teori/KURS/WRK/TeX/symALL.html ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
אופסשםמשתמש פורסם אוקטובר 6, 2012 מחבר דיווח שיתוף פורסם אוקטובר 6, 2012 אתה יכול לתת את ההגדרה של "תוחלת השוואה בין תווים בודדים"? מכל מקום, באגף שמאל יש לך (n-m-1) מוכפל בסכום של סדרה גיאומטרית סופית, שהמנה שלה היא d^-1. לא ממש "הראה כי תוחלת מספר ההשוואות בין תווים בודדים " בהנחה ואתה מבין אתה מבין כמה השוואות הוא עושה.. הוא משווה תו תו את התו הראשון, אם יש התאמה הוא ממשיך "פנימה" עד שהוא מגלה שאין התאמה. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
QuatzeQuatel פורסם אוקטובר 6, 2012 דיווח שיתוף פורסם אוקטובר 6, 2012 אתה ניגש אות כלשהי במחרוזת הגדולה ומתחיל לבדוק התאמה. הסיכוי שהאות הראשונה תתאים הוא d^-1. הסיכוי שגם האות השניה תתאים הוא d^-2. הסיכוי שכל m האותיות יתאימו הוא d^-m. מה ההסתברות הממוצעת? זה הממוצע המשוקלל לכל אחת מהאפשרויות (התאמה של אות אחת, של שתי אותיות...של m אותיות). באופן כללי ההסתברות להתאים k אותיות ברצף היא d^-k ולכן צריך לסכום על k מ1 עד m וכך מקבלים את המנה באגף שמאל. כמה פעמים תעשה חישוב כזה? עד שלא תמצא התאמה אתה עובר איבר איבר במחרוזת הגדולה עד שאתה מגיע לאיבר m-n-1 מהסוף. אחריו אין טעם להשוואה כי נשארו פחות מm איברים להשוות למחרושת של m איברים - כשלון ברור. כך מקבלים את אגף שמאל. כדי להוכיח את אי השיויון, תזכור שהמנה באגף שמאל קטנה/שווה מ1 ולכן כל אגף שמאל קטן מאגף ימין. ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
GIR פורסם אוקטובר 6, 2012 דיווח שיתוף פורסם אוקטובר 6, 2012 נגיד שM=N אז התוחלת שלילית? וגם הקטע של הסכום לא מסתדר לי אני אכתוב P במקום ddd 1/D הסיכוי שתהיה בדיוק השוואה אחת הוא ddd 1-P ז"א האותיות הראשונות הושוו - והן שונות הסיכוי שיהיו 2 השוואות הוא (ddd p*(1-p ז"א האותיות הראשונות שוות - והשניות שונות בשביל לעשות תוחלת על מס' ההשוואות צריך לעשות סכום על הסיכוי למס' השוואות מסוים כפול המס' עצמו אז יוצא לי משהו כמו http://www4a.wolframalpha.com/Calculate/MSP/MSP113671a3a8iaai76644e600002a8g9ifib0i87b55?MSPStoreType=image/gif&s=16&w=301&h=47 ואיך זה שתוחלת ההשואות לא תלויה באורך המחרוזות המושוות ורק בהפרש ביניהן? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
אופסשםמשתמש פורסם אוקטובר 6, 2012 מחבר דיווח שיתוף פורסם אוקטובר 6, 2012 אתה ניגש אות כלשהי במחרוזת הגדולה ומתחיל לבדוק התאמה. הסיכוי שהאות הראשונה תתאים הוא d^-1. הסיכוי שגם האות השניה תתאים הוא d^-2. הסיכוי שכל m האותיות יתאימו הוא d^-m. מה ההסתברות הממוצעת? זה הממוצע המשוקלל לכל אחת מהאפשרויות (התאמה של אות אחת, של שתי אותיות...של m אותיות). באופן כללי ההסתברות להתאים k אותיות ברצף היא d^-k ולכן צריך לסכום על k מ1 עד m וכך מקבלים את המנה באגף שמאל. כמה פעמים תעשה חישוב כזה? עד שלא תמצא התאמה אתה עובר איבר איבר במחרוזת הגדולה עד שאתה מגיע לאיבר m-n-1 מהסוף. אחריו אין טעם להשוואה כי נשארו פחות מm איברים להשוות למחרושת של m איברים - כשלון ברור. כך מקבלים את אגף שמאל. כדי להוכיח את אי השיויון, תזכור שהמנה באגף שמאל קטנה/שווה מ1 ולכן כל אגף שמאל קטן מאגף ימין. אני לא מבין את החישוב שלך בהתחלה חישבת את ההסתברות שk איברים יתאימו ואחרי זה ספרת כמה פעמים מחשבים שk איברים יתאימו שלא ברור לי איך מה שחישבת מתאר כמה פעמים יחשבו את ההסתברות ... שכן אף אחד לא הולך לחשב את ההסתברות צריך לספור כמה פעמים צריך יהיה להשוות אותיות .. לא ברור לי איך החישוב שלך סופר את זה. אולי לא הסברתי את האלגוריתם טוב ? נניח מחפשים aab בתוך aaaaab אז יהיו 3 השוואות 4 פעמים סה"כ 12 פעמים. אם מחפשים bbc בתוך aaaabbc יהיו בהתחלה 4 השוואות עד שנגיע לb , ואז עוד 3 סה"כ 7 ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
QuatzeQuatel פורסם אוקטובר 6, 2012 דיווח שיתוף פורסם אוקטובר 6, 2012 אני עונה מהחוקרים אז זה יהיה בקצרה. יש כנראה טעות בתשובה שלי. Took a note with my Note ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
StoryTeller פורסם אוקטובר 7, 2012 דיווח שיתוף פורסם אוקטובר 7, 2012 אופס, הניסוח שנתת גרוע. אלה אמורים להיות חסמים לתוחלת!? או שהביטוי הקטן הוא התוחלת? ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
-ליאור פורסם אוקטובר 8, 2012 דיווח שיתוף פורסם אוקטובר 8, 2012 דווקא הוא ענה נכון בגדול - מן הסתם תוחלת מספר ההשוואות תלויה בהסתברות של כל השוואה להצליח מכיוון שעל כל התאמה של אות אתה מתקדם במחרוזת השניה (מה שאומר שאתה "מבזבז" השוואה אם זו לא המחרוזת הנכונה, כי תצטרך לחזור אחורה אח"כ). בגדול - יש לך m-n+1 אפשרויות למיקום ההתחלתי (נראה לי שהתפלק לך המינוס בצד שמאל - זה גם עונה על השאלה של GIR על תוחלת שלילית), בכל אחת מהן תצטרך לעשות השוואה מול האות הראשונה של המחרוזת השניה. הסיכוי שההשוואה הזו תצליח הוא 1 ל-d, ואם כן אתה תצטרף לעשות השוואה נוספת. אם שתי השוואות תצלחנה, אז נוספת, וכו'. לצרכי התוחלת, אתה בעצם מוסיף את מספר ההשוואות בכל מקרה כשכל מקרה מנורמל לפי הסבירות שלו, כלומר מספר ההשוואות עבור כל נקודת התחלה הוא סכום של סדרה הנדסית באורך m, וזה כבר מתחיל להיות דומה לנוסחה שנתת. (לא ניסיתי לחשב עד הסוף, אבל זה נראה לי הכיוון) ציטוט קישור לתוכן שיתוף באתרים אחרים More sharing options...
הודעות מומלצות
הצטרפות לשיח
באפשרותך לשלוח הודעה כעת ולהירשם מאוחר יותר. אם ברשותך חשבון, ניתן להתחבר עכשיו לשליחת הודעה דרך חשבונך.
הערה: הודעתך דרושה לאישור הנהלה לפני הצגתה.