מערכי תירגול: הבדלים בין גרסאות בדף
אין תקציר עריכה |
אין תקציר עריכה |
||
| שורה 15: | שורה 15: | ||
נראה זאת עבור <math>(N^k,<_{cart})</math> ו-<math>(N^*,<_{cart})</math>. | נראה זאת עבור <math>(N^k,<_{cart})</math> ו-<math>(N^*,<_{cart})</math>. | ||
ניתן ל NxN להוות את מקרה הבסיס. באינדוקציה, נניח ש <math>N^{k-1}</math> מקיים את תנאי המינימליות ונוכיח עבור <math>N^k</math>. כפי שעשינו ב-NxN, נבחר את כל המילים אשר יש להן קואורדינאטה מינימלית, ומתוכן נבחר את המילים אשר התת-מילה מאורך k-1 שאינה כוללת קואורדינאטה זאת היא המינימלית. מילים אלו יהיו המינימליות | ניתן ל NxN להוות את מקרה הבסיס. באינדוקציה, נניח ש <math>N^{k-1}</math> מקיים את תנאי המינימליות ונוכיח עבור <math>N^k</math>. כפי שעשינו ב-NxN, נבחר את כל המילים בתת קבוצה A ב-<math>N^{k}</math> אשר יש להן קואורדינאטה מינימלית, ומתוכן נבחר את המילים אשר התת-מילה מאורך k-1 שאינה כוללת קואורדינאטה זאת היא המינימלית. מילים אלו יהיו המינימליות בתת קבוצה A. | ||
עבור <math>N^*</math> (לקבוצה של עדי, למעשה הוכחנו זאת במשפט הראשון, אך בטעות המשכנו לחפש את כל המינימליות, צריך רק להראות שקיימת מינימלית), בכל תת קבוצה A ניתן למצוא תת קבוצה שלה B של המילים בעלות האורך המינימלי. היות ובתת קב' B כולן מאותו אורך, ע"ס החלק הקודם ניתן לבחור מינימלית ביניהן, b,והיא תהיה מינימלית בכל A. (אם יש מילה מחוץ ל-B אשר קטנה מ-b באחת הקואורדינאטות אז הרי שלא ניתן להשוות ביניהן היות ואורכה בוודאי ארוך יותר מאורכה של b, לכן אין מילה שנמצאת מתחת ל-b ביחס) | עבור <math>N^*</math> (לקבוצה של עדי, למעשה הוכחנו זאת במשפט הראשון, אך בטעות המשכנו לחפש את כל המינימליות, צריך רק להראות שקיימת מינימלית), בכל תת קבוצה A ניתן למצוא תת קבוצה שלה B של המילים בעלות האורך המינימלי. היות ובתת קב' B כולן מאותו אורך, ע"ס החלק הקודם ניתן לבחור מינימלית ביניהן, b,והיא תהיה מינימלית בכל A. (אם יש מילה מחוץ ל-B אשר קטנה מ-b באחת הקואורדינאטות אז הרי שלא ניתן להשוות ביניהן היות ואורכה בוודאי ארוך יותר מאורכה של b, לכן אין מילה שנמצאת מתחת ל-b ביחס) | ||
גרסה מ־14:31, 25 בדצמבר 2012
תוספת לשיעור.
הראינו ש-[math]\displaystyle{ (N\times N,\lt _{cart}) }[/math] מקיים את תנאי המינימליות. נראה זאת עבור [math]\displaystyle{ (N^k,\lt _{cart}) }[/math] ו-[math]\displaystyle{ (N^*,\lt _{cart}) }[/math].
ניתן ל NxN להוות את מקרה הבסיס. באינדוקציה, נניח ש [math]\displaystyle{ N^{k-1} }[/math] מקיים את תנאי המינימליות ונוכיח עבור [math]\displaystyle{ N^k }[/math]. כפי שעשינו ב-NxN, נבחר את כל המילים בתת קבוצה A ב-[math]\displaystyle{ N^{k} }[/math] אשר יש להן קואורדינאטה מינימלית, ומתוכן נבחר את המילים אשר התת-מילה מאורך k-1 שאינה כוללת קואורדינאטה זאת היא המינימלית. מילים אלו יהיו המינימליות בתת קבוצה A.
עבור [math]\displaystyle{ N^* }[/math] (לקבוצה של עדי, למעשה הוכחנו זאת במשפט הראשון, אך בטעות המשכנו לחפש את כל המינימליות, צריך רק להראות שקיימת מינימלית), בכל תת קבוצה A ניתן למצוא תת קבוצה שלה B של המילים בעלות האורך המינימלי. היות ובתת קב' B כולן מאותו אורך, ע"ס החלק הקודם ניתן לבחור מינימלית ביניהן, b,והיא תהיה מינימלית בכל A. (אם יש מילה מחוץ ל-B אשר קטנה מ-b באחת הקואורדינאטות אז הרי שלא ניתן להשוות ביניהן היות ואורכה בוודאי ארוך יותר מאורכה של b, לכן אין מילה שנמצאת מתחת ל-b ביחס)