הבדלים בין גרסאות בדף "מערכי תירגול"
| (17 גרסאות ביניים של 2 משתמשים אינן מוצגות) | |||
| שורה 2: | שורה 2: | ||
* [[מדיה:T2.doc|תירגול 2]] | * [[מדיה:T2.doc|תירגול 2]] | ||
* [[מדיה:T3.doc|תירגול 3]] | * [[מדיה:T3.doc|תירגול 3]] | ||
| + | * [[מדיה:T4.doc|תירגול 4]] | ||
| + | * [[מדיה:T5.doc|תירגול 5]] | ||
| + | * [[מדיה:T6.doc|תירגול 6]] | ||
| + | * [[מדיה:T7.doc|תירגול 7]] | ||
| + | * [[מדיה:T8.doc|תירגול 8]] | ||
| + | * [[מדיה:T9.doc|תירגול 9]] | ||
| + | * [[מדיה:T10.doc|תירגול 10]] | ||
| + | |||
| + | '''תוספת לשיעור. | ||
| + | |||
| + | הראינו ש-<math>(N\times N,<_{cart})</math> מקיים את תנאי המינימליות. | ||
| + | נראה זאת עבור <math>(N^k,<_{cart})</math> ו-<math>(N^*,<_{cart})</math>. | ||
| + | |||
| + | ניתן ל 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 ביחס) | ||
| + | |||
| + | * [[מדיה:T11.doc|תירגול 11]] | ||
| + | |||
| + | * [[מדיה:T12.doc|תירגול 12]] | ||
| + | |||
| + | * [[מדיה:T13.doc|תירגול 13]] | ||
גרסה אחרונה מ־07:02, 15 בינואר 2013
תוספת לשיעור.
הראינו ש-
מקיים את תנאי המינימליות.
נראה זאת עבור 
ו-
.
ניתן ל NxN להוות את מקרה הבסיס. באינדוקציה, נניח ש 
מקיים את תנאי המינימליות ונוכיח עבור 
. כפי שעשינו ב-NxN, נבחר את כל המילים בתת קבוצה A ב-
אשר יש להן קואורדינאטה מינימלית, ומתוכן נבחר את המילים אשר התת-מילה מאורך k-1 שאינה כוללת קואורדינאטה זאת היא המינימלית. מילים אלו יהיו המינימליות בתת קבוצה A.
עבור 
(לקבוצה של עדי, למעשה הוכחנו זאת במשפט הראשון, אך בטעות המשכנו לחפש את כל המינימליות, צריך רק להראות שקיימת מינימלית), בכל תת קבוצה A ניתן למצוא תת קבוצה שלה B של המילים בעלות האורך המינימלי. היות ובתת קב' B כולן מאותו אורך, ע"ס החלק הקודם ניתן לבחור מינימלית ביניהן, b,והיא תהיה מינימלית בכל A. (אם יש מילה מחוץ ל-B אשר קטנה מ-b באחת הקואורדינאטות אז הרי שלא ניתן להשוות ביניהן היות ואורכה בוודאי ארוך יותר מאורכה של b, לכן אין מילה שנמצאת מתחת ל-b ביחס)
