מערכי תירגול

• תירגול 1
• תירגול 2
• תירגול 3
• תירגול 4
• תירגול 5
• תירגול 6
• תירגול 7
• תירגול 8
• תירגול 9
• תירגול 10

תוספת לשיעור.

הראינו ש-$(N\times N,<_{cart})$ מקיים את תנאי המינימליות. נראה זאת עבור $(N^k,<_{cart})$ ו-$(N^*,<_{cart})$.

ניתן ל NxN להוות את מקרה הבסיס. באינדוקציה, נניח ש $N^{k-1}$ מקיים את תנאי המינימליות ונוכיח עבור $N^k$. כפי שעשינו ב-NxN, נבחר את כל המילים בתת קבוצה A ב-$N^{k}$ אשר יש להן קואורדינאטה מינימלית, ומתוכן נבחר את המילים אשר התת-מילה מאורך k-1 שאינה כוללת קואורדינאטה זאת היא המינימלית. מילים אלו יהיו המינימליות בתת קבוצה A.

עבור $N^*$ (לקבוצה של עדי, למעשה הוכחנו זאת במשפט הראשון, אך בטעות המשכנו לחפש את כל המינימליות, צריך רק להראות שקיימת מינימלית), בכל תת קבוצה A ניתן למצוא תת קבוצה שלה B של המילים בעלות האורך המינימלי. היות ובתת קב' B כולן מאותו אורך, ע"ס החלק הקודם ניתן לבחור מינימלית ביניהן, b,והיא תהיה מינימלית בכל A. (אם יש מילה מחוץ ל-B אשר קטנה מ-b באחת הקואורדינאטות אז הרי שלא ניתן להשוות ביניהן היות ואורכה בוודאי ארוך יותר מאורכה של b, לכן אין מילה שנמצאת מתחת ל-b ביחס)

• תירגול 11

• תירגול 12

• תירגול 13