מפתח תשובות · יחידה 5

גרפים ורשתות.

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

קטלוג הטעויות הנפוצות

מפתח תשובות 4

שיעור 1 מתוך 4 · כ־20 דקות

צמתים וקשתות

מעיר לגרף: צמתים, קשתות ודרגה, למה סכום הדרגות הוא תמיד פעמיים מספר הקשתות, ומה קורה לדרגות כשמוסיפים גשר.

לפתוח את השיעור

5 השלבים והתשובות שלהם

שלב 1 מתוך 5
לפתוח את השלב
מעיר לגרף
תרגול · נבאו, ואז הסתכלו
השאלה
ארבע היבשות של קניגסברג יהיו צמתים, ושבעת הגשרים קשתות. הדרגה של צומת היא מספר הקשתות שנוגעות בו. מה הדרגה של האי A?

התשובה הנכונה
5 ± 0.01
ניבוי מספרי נחשב נכון בטווח ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
7קבוע
העיר / הגרף
העירקבוע
אחרי נעילת הניבוי הסצנה משתנה
העיר / הגרף
הגרףקבוע
ואז הסצנה מראה: 5 · Bridges touching the island A, its degree/nodes/town/outputs/degreeA
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
חמישה גשרים יוצאים מהאי: שניים לגדה הצפונית, שניים לדרומית ואחד ליבשה המזרחית. בגרף כל צומת מסומן בדרגה שלו.

פתרון מלא
1. ספרו את הגשרים שנוגעים באי: שניים ל־B, שניים ל־C, אחד ל־D.
2. $2 + 2 + 1 = 5$ ⁠.
שלב 2 מתוך 5
לפתוח את השלב
דרגות
תרגול · חשבו
השאלה
חברו את הדרגות של כל ארבעת הצמתים. מה הסכום?

התשובה הנכונה
14 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
7קבוע
העיר / הגרף
הגרף
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
The four degrees added: twice the bridges/nodes/town/outputs/degreeSum
תשובות שגויות שהשאלה מזהה
- 7 ± 0.01
  טעות נפוצה: Takes the sum of the degrees to be the number of edges, counting each edge once instead of twice.
  משוב מהקטלוג
  לכל קשת יש שני קצוות, וכל קצה נספר בדרגה של הצומת שלו. לכן כשמחברים את כל הדרגות, כל קשת נספרת פעמיים: סכום הדרגות הוא תמיד פעמיים מספר הקשתות. בקניגסברג $5 + 3 + 3 + 3 = 14 = 2 \times 7$ ⁠. ובכיוון ההפוך, ממספר הדרגות לקשתות, מחלקים ב־ $2$ ⁠.
משוב לתשובה נכונה
$5 + 3 + 3 + 3 = 14$ ⁠: פעמיים שבעת הגשרים. כל גשר נספר פעם אחת בכל אחד משני הקצוות שלו.

רמז
הדרגות כתובות ליד הצמתים.

פתרון מלא
1. הדרגות: A ‏ $5$ ⁠, B ‏ $3$ ⁠, C ‏ $3$ ⁠, D ‏ $3$ ⁠.
2. $5 + 3 + 3 + 3 = 14$ ⁠.
3. בדיקה: לכל גשר שני קצוות, $2 \times 7 = 14$ ⁠.
$7$ ⁠ הוא מספר הגשרים: כל אחד מהם תורם $2$ ⁠ לסכום, לא $1$ ⁠.
שלב 3 מתוך 5
לפתוח את השלב
לחיצות ידיים
תרגול · בחרו
השאלה
האם יכול להיות גרף שיש בו בדיוק צומת אחד בעל דרגה אי־זוגית?

התשובה הנכונה
- נכונה לא: מספר הצמתים האי־זוגיים תמיד זוגי
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
7
העיר / הגרף
הגרף
האפשרויות
מוצגות בסדר אקראי.
- נכונה לא: מספר הצמתים האי־זוגיים תמיד זוגי
- שגויה כן, אם בונים אותו נכון
  טעות נפוצה: Thinks a graph can have an odd number of odd-degree nodes, such as exactly one.
  משוב מהקטלוג
  סכום הדרגות הוא פעמיים מספר הקשתות, ולכן הוא תמיד זוגי. צמתים זוגיים תורמים לסכום מספר זוגי, ולכן גם הצמתים האי־זוגיים יחד חייבים לתרום מספר זוגי, וזה קורה רק כשיש מהם מספר זוגי. צומת אי־זוגי אחד לבד, או שלושה, לא יכולים להיות. זו למת לחיצות הידיים.
- שגויה רק בגרף גדול מספיק
  טעות נפוצה: Thinks a graph can have an odd number of odd-degree nodes, such as exactly one.
  משוב מהקטלוג
  סכום הדרגות הוא פעמיים מספר הקשתות, ולכן הוא תמיד זוגי. צמתים זוגיים תורמים לסכום מספר זוגי, ולכן גם הצמתים האי־זוגיים יחד חייבים לתרום מספר זוגי, וזה קורה רק כשיש מהם מספר זוגי. צומת אי־זוגי אחד לבד, או שלושה, לא יכולים להיות. זו למת לחיצות הידיים.
משוב לתשובה נכונה
סכום הדרגות הוא פעמיים מספר הקשתות, ולכן זוגי. צומת אי־זוגי אחד היה הופך אותו לאי־זוגי. נסו כל מספר גשרים בסצנה: תמיד $0$ ⁠, $2$ ⁠ או $4$ ⁠ יבשות אי־זוגיות.

פתרון מלא
1. סכום הדרגות $= 2 \times$ ⁠ מספר הקשתות, ולכן זוגי.
2. סכום הדרגות הזוגיות זוגי.
3. לכן גם סכום הדרגות האי־זוגיות זוגי, וזה אפשרי רק כשיש מספר זוגי של מחוברים אי־זוגיים.
שלב 4 מתוך 5
לפתוח את השלב
גשר חדש
תרגול · הגיעו למטרה
השאלה
שנו את מספר הגשרים עד שלגדה הצפונית B תהיה דרגה $4$ ⁠, ולחצו על בדיקה.

המטרה
- 4 ± 0.01
  בתחילת השלב: 3
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
7
העיר / הגרף
הגרף
נקרא מהסצנה בנקודה
Bridges touching the north bank B/nodes/town/outputs/degreeB
הגדרה אחת שמגיעה למטרה
גשרים
8
משוב לתשובה נכונה
הגשר השמיני, מערב לאי, מחבר את B ל־C, ומעלה את הדרגה של שתיהן באחד. כל גשר חדש מוסיף $1$ ⁠ לשני צמתים, ולכן $2$ ⁠ לסכום.

משוב לתשובה שגויה
עוד לא. איזה גשר נוסף נוגע ב־B?

פתרון מלא
1. ב־7 גשרים הדרגה של B היא $3$ ⁠.
2. הגשר השמיני מחבר את B ל־C, ולכן ב־8 גשרים הדרגה של B היא $4$ ⁠.
3. גם ב־9 היא $4$ ⁠: הגשר התשיעי מחבר את A ל־D.
שלב 5 מתוך 5
לפתוח את השלב
לספור לאחור
תרגול · חשבו
השאלה
בגרף של ארבעה צמתים הדרגות הן $3$ ⁠, $3$ ⁠, $2$ ⁠ ו־ $2$ ⁠. כמה קשתות יש בו?

התשובה הנכונה
5 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
5
העיר / הגרף
הגרף
מתקבלת בטווח
± 0.01
ערך קבוע בשאלה
תשובות שגויות שהשאלה מזהה
- 10 ± 0.01
  טעות נפוצה: Takes the sum of the degrees to be the number of edges, counting each edge once instead of twice.
  משוב מהקטלוג
  לכל קשת יש שני קצוות, וכל קצה נספר בדרגה של הצומת שלו. לכן כשמחברים את כל הדרגות, כל קשת נספרת פעמיים: סכום הדרגות הוא תמיד פעמיים מספר הקשתות. בקניגסברג $5 + 3 + 3 + 3 = 14 = 2 \times 7$ ⁠. ובכיוון ההפוך, ממספר הדרגות לקשתות, מחלקים ב־ $2$ ⁠.
משוב לתשובה נכונה
$\dfrac{3 + 3 + 2 + 2}{2} = 5$ ⁠. זה בדיוק הגרף של 5 גשרים בסצנה.

רמז
כל קשת נספרת פעמיים בסכום הדרגות.

פתרון מלא
1. סכום הדרגות: $3 + 3 + 2 + 2 = 10$ ⁠.
2. כל קשת תורמת $2$ ⁠ לסכום.
3. $10 \div 2 = 5$ ⁠ קשתות.

שיעור 2 מתוך 4 · כ־25 דקות

מסלולי אוילר

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
החידה
תרגול · נבאו, ואז הסתכלו
השאלה
תושבי קניגסברג שאלו: האם אפשר לטייל בעיר ולעבור על כל אחד משבעת הגשרים בדיוק פעם אחת? נבאו.

התשובה הנכונה
- נכונה לא, אין מסלול כזה
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
7קבוע
העיר / הגרף
העירקבוע
האפשרויות
- נכונה לא, אין מסלול כזה
- שגויה כן, צריך רק למצוא את הסדר הנכון
  טעות נפוצה: Thinks a walk over all seven bridges of Königsberg exists and has just not been found yet.
  משוב מהקטלוג
  זו לא שאלה של חיפוש: אוילר הוכיח שאין מסלול כזה. בכל מעבר בצומת באמצע הדרך נכנסים בקשת אחת ויוצאים באחרת, ולכן צומת שאינו התחלה או סוף צריך דרגה זוגית. בקניגסברג כל ארבע היבשות אי־זוגיות, ורק שתיים יכולות להיות ההתחלה והסוף. לכן הטוב ביותר הוא שישה גשרים מתוך שבעה.
אחרי נעילת הניבוי הסצנה משתנה
העיר / הגרף
הגרףקבוע
ואז הסצנה מראה: 0 · 1 when one walk crosses every bridge exactly once (an Euler path or circuit), else 0/nodes/town/outputs/walkable
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
אוילר הוכיח ב־1736 שאין: כל ארבע היבשות בעלות דרגה אי־זוגית. ההולך על הגרף חוצה שישה גשרים, והגשר השביעי נשאר אדום.

פתרון מלא
1. הדרגות: $5, 3, 3, 3$ ⁠, כולן אי־זוגיות.
2. כל צומת באמצע המסלול צריך דרגה זוגית: נכנסים ויוצאים בזוגות.
3. רק ההתחלה והסוף יכולים להיות אי־זוגיים, ולכן לכל היותר שניים.
4. ארבעה צמתים אי־זוגיים: אין מסלול.
שלב 2 מתוך 6
לפתוח את השלב
המסלול הטוב ביותר
תרגול · חשבו
השאלה
בלי לעבור על אף גשר פעמיים, על כמה גשרים לכל היותר אפשר לעבור בקניגסברג של 1736?

התשובה הנכונה
6 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
7קבוע
העיר / הגרף
הגרף
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
Bridges in the longest walk that crosses none twice (all of them when walkable)/nodes/town/outputs/longestWalk
תשובות שגויות שהשאלה מזהה
- 7 ± 0.01
  טעות נפוצה: Thinks a walk over all seven bridges of Königsberg exists and has just not been found yet.
  משוב מהקטלוג
  זו לא שאלה של חיפוש: אוילר הוכיח שאין מסלול כזה. בכל מעבר בצומת באמצע הדרך נכנסים בקשת אחת ויוצאים באחרת, ולכן צומת שאינו התחלה או סוף צריך דרגה זוגית. בקניגסברג כל ארבע היבשות אי־זוגיות, ורק שתיים יכולות להיות ההתחלה והסוף. לכן הטוב ביותר הוא שישה גשרים מתוך שבעה.
משוב לתשובה נכונה
שישה. אם מורידים גשר אחד, שני צמתים הופכים לזוגיים ונשארים שניים אי־זוגיים, ואז יש מסלול אוילר על השישה שנשארו.

פתרון מלא
1. כל שבעת הגשרים: בלתי אפשרי, כי ארבעה צמתים אי־זוגיים.
2. בלי גשר אחד, שני הצמתים שבקצותיו הופכים לזוגיים: נשארים שני צמתים אי־זוגיים.
3. עם שני צמתים אי־זוגיים יש מסלול על כל הקשתות שנשארו: $6$ ⁠.
שלב 3 מתוך 6
לפתוח את השלב
לתקן את העיר
תרגול · הגיעו למטרה
השאלה
הוסיפו או הסירו גשרים עד שיש מסלול שעובר על כל גשר בדיוק פעם אחת, ולחצו על בדיקה.

המטרה
- 1 ± 0.01
  בתחילת השלב: 0
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
7
העיר / הגרף
הגרף
נקרא מהסצנה בנקודה
1 when one walk crosses every bridge exactly once (an Euler path or circuit), else 0/nodes/town/outputs/walkable
הגדרה אחת שמגיעה למטרה
גשרים
5
משוב לתשובה נכונה
כל גשר שמוסיפים או מסירים משנה את הזוגיות של שני הקצוות שלו, ולכן מוריד את מספר הצמתים האי־זוגיים מארבעה לשניים. עכשיו ההולך עובר על כולם.

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

רמז
צריך $0$ ⁠ או $2$ ⁠ צמתים אי־זוגיים.

פתרון מלא
1. ב־7 גשרים יש ארבעה צמתים אי־זוגיים.
2. הוספה או הסרה של גשר בין שני צמתים אי־זוגיים הופכת את שניהם לזוגיים.
3. כל מספר אחר בסצנה, 5, ‏6, ‏8 או 9, עובד.
שלב 4 מתוך 6
לפתוח את השלב
איפה להתחיל
תרגול · בחרו
השאלה
ב־8 גשרים הדרגות הן A ‏ $5$ ⁠, ‏B ‏ $4$ ⁠, ‏C ‏ $4$ ⁠, ‏D ‏ $3$ ⁠, ויש מסלול שעובר על כולם. איפה הוא חייב להתחיל?

התשובה הנכונה
- נכונה ב־A או ב־D, ואז הוא מסתיים בשני
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
8
העיר / הגרף
העיר
האפשרויות
מוצגות בסדר אקראי.
- נכונה ב־A או ב־D, ואז הוא מסתיים בשני
- שגויה בכל יבשה
  טעות נפוצה: Thinks an Euler path can start at any node, even when two nodes are odd.
  משוב מהקטלוג
  כשיש בדיוק שני צמתים אי־זוגיים, המסלול חייב להתחיל באחד מהם ולהסתיים בשני. בצומת אי־זוגי נשארת תמיד קשת אחת בלי זוג: אם הוא לא ההתחלה או הסוף, אחרי שנכנסים בפעם האחרונה אין דרך לצאת. רק כשכל הצמתים זוגיים אפשר להתחיל בכל צומת, ואז המסלול חוזר אליו: מעגל אוילר.
- שגויה ב־B או ב־C, היבשות הזוגיות
  טעות נפוצה: Thinks an Euler path can start at any node, even when two nodes are odd.
  משוב מהקטלוג
  כשיש בדיוק שני צמתים אי־זוגיים, המסלול חייב להתחיל באחד מהם ולהסתיים בשני. בצומת אי־זוגי נשארת תמיד קשת אחת בלי זוג: אם הוא לא ההתחלה או הסוף, אחרי שנכנסים בפעם האחרונה אין דרך לצאת. רק כשכל הצמתים זוגיים אפשר להתחיל בכל צומת, ואז המסלול חוזר אליו: מעגל אוילר.
משוב לתשובה נכונה
לצומת אי־זוגי נשארת תמיד קשת בלי זוג, ולכן הוא חייב להיות ההתחלה או הסוף. פתחו את הגרף: ההולך יוצא מ־A ומסיים ב־D.

פתרון מלא
1. הצמתים האי־זוגיים: A ‏( $5$ ⁠) ו־D ‏( $3$ ⁠).
2. בצומת באמצע המסלול נכנסים ויוצאים בזוגות, ולכן הוא זוגי.
3. A ו־D חייבים להיות ההתחלה והסוף.
שלב 5 מתוך 6
לפתוח את השלב
מעגל
תרגול · הגיעו למטרה
השאלה
מעגל אוילר הוא מסלול שעובר על כל קשת פעם אחת וחוזר לנקודת ההתחלה. שנו את הגשרים עד שיש כזה, ולחצו על בדיקה.

המטרה
- 1 ± 0.01
  בתחילת השלב: 0
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
8
העיר / הגרף
הגרף
נקרא מהסצנה בנקודה
1 when that walk can end where it began (no odd lands), else 0/nodes/town/outputs/circuit
הגדרה אחת שמגיעה למטרה
גשרים
9
משוב לתשובה נכונה
ב־9 גשרים הדרגות $6, 4, 4, 4$ ⁠, כולן זוגיות, וההולך חוזר למקום שממנו יצא.

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

רמז
כדי לחזור להתחלה, אף צומת לא יכול להיות אי־זוגי.

פתרון מלא
1. מעגל צריך $0$ ⁠ צמתים אי־זוגיים.
2. ב־8 גשרים A ו־D אי־זוגיים; הגשר התשיעי מחבר בדיוק אותם.
3. קבעו 9 גשרים.
שלב 6 מתוך 6
לפתוח את השלב
הכלל של אוילר
תרגול · בחרו
השאלה
גרף קשיר. מתי יש בו מסלול שעובר על כל קשת בדיוק פעם אחת?

התשובה הנכונה
- נכונה כשיש בו $0$ ⁠ או $2$ ⁠ צמתים אי־זוגיים
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
גשרים
9
העיר / הגרף
הגרף
האפשרויות
מוצגות בסדר אקראי.
- נכונה כשיש בו $0$ ⁠ או $2$ ⁠ צמתים אי־זוגיים
- שגויה כשמספר הצמתים האי־זוגיים זוגי
  טעות נפוצה: Thinks any even number of odd nodes allows an Euler path, four included.
  משוב מהקטלוג
  הכלל של אוילר הוא $0$ ⁠ או $2$ ⁠, לא “מספר זוגי”. כל צומת אי־זוגי חייב להיות ההתחלה או הסוף של המסלול, ולמסלול אחד יש רק התחלה אחת וסוף אחד. עם ארבעה צמתים אי־זוגיים, כמו בקניגסברג, צריך שני מסלולים נפרדים. (מספר הצמתים האי־זוגיים תמיד זוגי, אז “זוגי” לא אומר כלום.)
- שגויה רק כשאין צמתים אי־זוגיים
  משוב
  $0$ ⁠ צמתים אי־זוגיים נותנים מעגל, אבל גם $2$ ⁠ נותנים מסלול, שמתחיל באחד ומסתיים בשני.
משוב לתשובה נכונה
זה המשפט של אוילר: $0$ ⁠ צמתים אי־זוגיים, מעגל; $2$ ⁠, מסלול מאחד לשני; יותר, אין מסלול. המחשב בסצנה מוצא את המסלול באלגוריתם של הירהולצר.

פתרון מלא
1. כל צומת אי־זוגי חייב להיות קצה של המסלול.
2. למסלול שני קצוות, ולמעגל אף אחד.
3. לכן $0$ ⁠ או $2$ ⁠.
מספר הצמתים האי־זוגיים תמיד זוגי, אבל עם $4$ ⁠, כמו בקניגסברג, אין מסלול.

שיעור 3 מתוך 4 · כ־25 דקות

ניתוב חבילות

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
המסלול הקצר ביותר
תרגול · חשבו
השאלה
ההודעה עוברת מהמחשב הנייד לשרת במסלול הקצר ביותר, המסלול שזוהר. דרך כמה נתבים היא עוברת?

התשובה הנכונה
4 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
קישורים שנחתכו
0קבוע
הודעה אחת / חבילות
הודעה אחתקבוע
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
Network: routers the message passes through on the shortest route, 0 with no route/nodes/mesh/outputs/routers
תשובות שגויות שהשאלה מזהה
- 5 ± 0.01
  טעות נפוצה: Confuses the links on a route with the routers on it, off by one (counting fence posts as gaps).
  משוב מהקטלוג
  מסלול הוא שרשרת: קישור, נתב, קישור, נתב, וכך עד הסוף. בין המחשב לשרת יש קישור אחד יותר מנתבים, כמו בגדר שבה יש עמוד אחד יותר מרווחים. מסלול של חמישה קישורים עובר דרך ארבעה נתבים. כשסופרים, קבעו קודם מה בדיוק סופרים: קשתות או צמתים.
משוב לתשובה נכונה
ארבעה נתבים, וחמישה כבלים ביניהם. כל נתב קורא את כתובת היעד ושולח את ההודעה לשכן הבא בדרך.

רמז
ספרו את הקופסאות שבדרך, בלי המחשב והשרת.

פתרון מלא
1. המסלול: מחשב נייד, ארבעה נתבים, שרת.
2. בין שש התחנות יש חמישה קישורים.
3. הנתבים הם התחנות שבאמצע: $4$ ⁠.
$5$ ⁠ הוא מספר הכבלים: אחד יותר מהנתבים.
שלב 2 מתוך 6
לפתוח את השלב
כבל שנחתך
תרגול · נבאו, ואז הסתכלו
השאלה
נחתוך את הכבל האמצעי במסלול שההודעה עוברת בו עכשיו. מה יקרה להודעה הבאה?

התשובה הנכונה
- נכונה היא תעבור בדרך אחרת, קצת ארוכה יותר
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
קישורים שנחתכו
0קבוע
הודעה אחת / חבילות
הודעה אחתקבוע
האפשרויות
- נכונה היא תעבור בדרך אחרת, קצת ארוכה יותר
- שגויה היא לא תגיע
  טעות נפוצה: Thinks that cutting a link on the route loses the message, as if a network had only one path.
  משוב מהקטלוג
  האינטרנט בנוי כרשת עם מסלולים רבים בין כל שתי נקודות. כשקישור נחתך, הנתבים מגלים את זה ומחשבים מחדש את המסלול הקצר ביותר על מה שנשאר, וההודעה עוברת בדרך עוקפת, קצת ארוכה יותר. הרשת מתנתקת רק כשנחתכים כל הקישורים שמחברים בין שני חלקיה.
- שגויה היא תעבור בדרך אחרת, קצרה יותר
  משוב
  אילו הייתה דרך קצרה יותר, ההודעה הייתה עוברת בה מלכתחילה: זו הייתה הקצרה ביותר.
אחרי נעילת הניבוי הסצנה משתנה
קישורים שנחתכו
1קבוע
ואז הסצנה מראה: 1 · Network: 1 while a route from the laptop to the server is left, 0 when the cuts sever it/nodes/mesh/outputs/reachable
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
הנתבים חישבו מחדש את המסלול הקצר ביותר בלי הכבל החתוך, וההודעה עוקפת. הדרך החדשה ארוכה בכ־3%.

פתרון מלא
1. ברשת יש הרבה מסלולים בין המחשב לשרת.
2. החיתוך מוחק קשת אחת מהגרף.
3. המסלול הקצר ביותר בגרף שנשאר הוא לכל היותר ארוך כמו הקודם, וכאן ארוך יותר, כי הקודם היה היחיד הקצר מכולם.
שלב 3 מתוך 6
לפתוח את השלב
לנתק את השרת
תרגול · הגיעו למטרה
השאלה
הגדילו את קישורים שנחתכו עד שהשרת מנותק לגמרי מהמחשב הנייד, ולחצו על בדיקה.

המטרה
- 0 ± 0.01
  בתחילת השלב: 1
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
קישורים שנחתכו
0
הודעה אחת / חבילות
הודעה אחת
נקרא מהסצנה בנקודה
Network: 1 while a route from the laptop to the server is left, 0 when the cuts sever it/nodes/mesh/outputs/reachable
הגדרה אחת שמגיעה למטרה
קישורים שנחתכו
4
משוב לתשובה נכונה
ארבעה חיתוכים, ועוד 18 קישורים שלמים, ובכל זאת אין דרך: נחתכו כל הקישורים שעוברים מהחצי השמאלי של הרשת לימני.

משוב לתשובה שגויה
עוד לא. כל עוד ההודעה מגיעה, יש דרך עוקפת. המשיכו לחתוך.

פתרון מלא
1. כל חיתוך פוגע בקישור שבמסלול הקצר ביותר הנוכחי, וההודעה עוקפת.
2. רק ארבעה קישורים מחברים את החצי השמאלי של הרשת לימני.
3. אחרי החיתוך הרביעי כולם חתוכים: קבעו את קישורים שנחתכו על 4.
שלב 4 מתוך 6
לפתוח את השלב
חתך
תרגול · בחרו
השאלה
אחרי ארבעה חיתוכים נשארו 18 מתוך 22 הקישורים, ובכל זאת השרת מנותק. למה?

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

פתרון מלא
1. כדי שתהיה דרך, צריך לפחות קישור אחד שעובר מהחלק של המחשב לחלק של השרת.
2. יש בדיוק ארבעה כאלה, וכולם נחתכו.
3. שאר הקישורים מחברים צמתים באותו חלק, ולכן לא עוזרים.
שלב 5 מתוך 6
לפתוח את השלב
חבילות
תרגול · נבאו, ואז הסתכלו
השאלה
את ההודעה מחלקים לחבילות, שש חבילות ממוספרות, ושולחים אותן אחת אחרי השנייה. האם כולן יעברו באותו מסלול?

התשובה הנכונה
- נכונה לא, הן יתפזרו על כמה מסלולים
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
קישורים שנחתכו
0קבוע
הודעה אחת / חבילות
הודעה אחתקבוע
האפשרויות
- נכונה לא, הן יתפזרו על כמה מסלולים
- שגויה כן, כולן בדרך הקצרה ביותר
  טעות נפוצה: Thinks a message's packets all follow one route and arrive in the order they were sent.
  משוב מהקטלוג
  כל חבילה מנותבת בנפרד. הנתבים מפזרים חבילות על כמה מסלולים שאורכם דומה, כדי לא להעמיס על אחד, ולכן חבילות של אותה הודעה עוברות בדרכים שונות ומגיעות בסדר אחר מזה שבו נשלחו. לכל חבילה יש מספר סידורי, והשרת מסדר אותן לפיו ומבקש מחדש כל חבילה שלא הגיעה.
אחרי נעילת הניבוי הסצנה משתנה
הודעה אחת / חבילות
חבילותקבוע
ואז הסצנה מראה: 4 · Network: distinct routes the message's packets actually take/nodes/mesh/outputs/packetRoutes
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
החבילות מתפזרות על ארבעה מסלולים שאורכם דומה, כדי לא להעמיס על אחד. כל נתב מחליט לכל חבילה בנפרד.

פתרון מלא
1. כל חבילה היא הודעה קטנה עם כתובת יעד משלה.
2. כל נתב מחליט לכל חבילה לאן לשלוח אותה, לפי העומס ולפי אורך הדרך.
3. לכן חבילות של אותה הודעה יכולות לעבור בדרכים שונות: כאן ארבע.
שלב 6 מתוך 6
לפתוח את השלב
להרכיב מחדש
תרגול · בחרו
השאלה
החבילות הגיעו לשרת בסדר אחר מזה שבו נשלחו. איך השרת מרכיב את ההודעה?

התשובה הנכונה
- נכונה לפי המספר הסידורי שכל חבילה נושאת
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
קישורים שנחתכו
0
הודעה אחת / חבילות
חבילות
האפשרויות
מוצגות בסדר אקראי.
- נכונה לפי המספר הסידורי שכל חבילה נושאת
- שגויה לפי סדר ההגעה, כי הן מגיעות בסדר שבו נשלחו
  טעות נפוצה: Thinks a message's packets all follow one route and arrive in the order they were sent.
  משוב מהקטלוג
  כל חבילה מנותבת בנפרד. הנתבים מפזרים חבילות על כמה מסלולים שאורכם דומה, כדי לא להעמיס על אחד, ולכן חבילות של אותה הודעה עוברות בדרכים שונות ומגיעות בסדר אחר מזה שבו נשלחו. לכל חבילה יש מספר סידורי, והשרת מסדר אותן לפיו ומבקש מחדש כל חבילה שלא הגיעה.
- שגויה לפי המסלול שבו כל חבילה עברה
  משוב
  השרת לא יודע באיזה מסלול חבילה עברה, וזה גם לא משנה. מה שקובע הוא המספר שעליה.
משוב לתשובה נכונה
כל חבילה ממוספרת, והשרת מסדר אותן לפי המספרים ומבקש מחדש כל חבילה חסרה. זה חלק מהפרוטוקול TCP.

פתרון מלא
1. מסלולים שונים לוקחים זמנים שונים, ולכן הסדר מתבלבל.
2. כל חבילה נושאת מספר סידורי.
3. השרת ממיין לפי המספרים, ויודע לפי מספר חסר שחבילה עוד לא הגיעה.

שיעור 4 מתוך 4 · כ־25 דקות

דירוג דפים

איך מנוע חיפוש יודע מה חשוב: הגולש האקראי, PageRank כחלק מהזמן בכל דף, למה קישור מדף חשוב שווה יותר, מקדם הדעיכה, וביקורים שמתייצבים.

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
הגולש האקראי
תרגול · נבאו, ואז הסתכלו
השאלה
עכשיו הגולש אף פעם לא לוחץ על קישורים, רק קופץ לדף אקראי, ולכן לכל שמונת הדפים אותו דירוג. כשנעלה את הסיכוי ללחוץ על קישור ל־85%, איזה דף יעלה למקום הראשון?

התשובה הנכונה
- נכונה הפורטל, שכמעט כל הדפים מקשרים אליו
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
דפים שמקשרים לדף שלכם
0קבוע
הסיכוי ללחוץ על קישור
0 %קבוע
דירוגים / גולש אקראי
דירוגיםקבוע
האפשרויות
- נכונה הפורטל, שכמעט כל הדפים מקשרים אליו
- שגויה הבלוג, שנותן הכי הרבה קישורים
  משוב
  קישורים יוצאים לא מעלים דף; הם מעלים את הדפים שהוא מקשר אליהם.
- שגויה הדף שלכם, כי הגולש מתחיל בו
  משוב
  נקודת ההתחלה נשכחת אחרי כמה צעדים. מה שקובע הוא לאן הקישורים מובילים.
אחרי נעילת הניבוי הסצנה משתנה
הסיכוי ללחוץ על קישור
85 %קבוע
ואז הסצנה מראה: 31.43 · The hub’s PageRank, percent/nodes/web/outputs/hubRank
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
לפורטל יש שבעה קישורים נכנסים, מכל דף אחר, והוא עולה לכשליש מהדירוג. כל לחיצה על קישור מעבירה את הגולש לדף שמקושר, ולכן דף שהרבה דפים מקשרים אליו מבוקר יותר.

פתרון מלא
1. PageRank הוא החלק מהזמן שהגולש האקראי מבלה בכל דף.
2. כשהוא לוחץ על קישורים, הוא מגיע לדפים שמקשרים אליהם.
3. כל שבעת הדפים האחרים מקשרים לפורטל, ולכן הוא מגיע אליו הכי הרבה.
שלב 2 מתוך 6
לפתוח את השלב
קישורים שקטים
תרגול · נבאו, ואז הסתכלו
השאלה
אף דף לא מקשר לדף שלכם, והדירוג שלו כ־1.9%. עכשיו הבלוג, התמונות והחנות, שלושה דפים שקטים, יקשרו אליו. לאן יגיע הדירוג?

התשובה הנכונה
- נכונה יעלה מעט, לכ־5%
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
דפים שמקשרים לדף שלכם
0קבוע
הסיכוי ללחוץ על קישור
85 %קבוע
דירוגים / גולש אקראי
דירוגיםקבוע
האפשרויות
- נכונה יעלה מעט, לכ־5%
- שגויה יעלה הרבה, מעל 10%: שלושה קישורים זה הרבה
  טעות נפוצה: Thinks every link counts the same in PageRank, so more links always beat fewer.
  משוב מהקטלוג
  ב־PageRank לא סופרים קישורים, שוקלים אותם. כל דף מחלק את הדירוג שלו בין הקישורים שהוא נותן, ולכן קישור מדף חשוב שווה הרבה יותר מקישור מדף שאיש לא מבקר בו. קישור אחד מהפורטל, שהדירוג שלו כשליש מכלל הרשת, מעלה את הדף שלכם יותר משלושה קישורים מדפים שקטים יחד.
אחרי נעילת הניבוי הסצנה משתנה
דפים שמקשרים לדף שלכם
3קבוע
ואז הסצנה מראה: 5.064 · The reader’s page’s PageRank, percent/nodes/web/outputs/yourRank
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
כ־5.1%. לשלושת הדפים האלה דירוג קטן משלהם, וכל אחד מחלק אותו בין כמה קישורים, ולכן הם מעבירים מעט.

פתרון מלא
1. קישור מעביר $d \cdot \dfrac{PR}{L}$ ⁠: חלק מהדירוג של הדף שנותן אותו, מחולק במספר הקישורים שלו.
2. לבלוג, לתמונות ולחנות דירוג של כמה אחוזים בלבד.
3. לכן שלושתם יחד מעבירים רק כמה אחוזים.
שלב 3 מתוך 6
לפתוח את השלב
קישור מהפורטל
תרגול · נבאו, ואז הסתכלו
השאלה
שלושה דפים שקטים כבר מקשרים לדף שלכם. עכשיו הפורטל יוסיף קישור אחד. האם הדף שלכם ירוויח מזה יותר או פחות ממה שהרוויח משלושת הקישורים?

התשובה הנכונה
- נכונה יותר
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
דפים שמקשרים לדף שלכם
3קבוע
הסיכוי ללחוץ על קישור
85 %קבוע
דירוגים / גולש אקראי
דירוגיםקבוע
האפשרויות
- נכונה יותר
- שגויה פחות: קישור אחד מול שלושה
  טעות נפוצה: Thinks every link counts the same in PageRank, so more links always beat fewer.
  משוב מהקטלוג
  ב־PageRank לא סופרים קישורים, שוקלים אותם. כל דף מחלק את הדירוג שלו בין הקישורים שהוא נותן, ולכן קישור מדף חשוב שווה הרבה יותר מקישור מדף שאיש לא מבקר בו. קישור אחד מהפורטל, שהדירוג שלו כשליש מכלל הרשת, מעלה את הדף שלכם יותר משלושה קישורים מדפים שקטים יחד.
אחרי נעילת הניבוי הסצנה משתנה
דפים שמקשרים לדף שלכם
4קבוע
ואז הסצנה מראה: 11.94 · The reader’s page’s PageRank, percent/nodes/web/outputs/yourRank
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
מ־5.1% ל־11.9%: יותר מכפליים מכל מה ששלושת הקישורים נתנו. לפורטל כשליש מהדירוג, וגם אחרי שהוא מחלק אותו בין ארבעה קישורים, החלק שלכם גדול.

פתרון מלא
1. שלושת הקישורים השקטים העלו את הדף מכ־1.9% לכ־5.1%: כ־ $3$ ⁠ נקודות.
2. הפורטל מעביר בכל אחד מארבעת הקישורים שלו $0.85 \times \dfrac{33}{4} \approx 7$ ⁠ נקודות.
3. קישור אחד מהפורטל שווה יותר משלושת השקטים יחד.
שלב 4 מתוך 6
לפתוח את השלב
לטפס
תרגול · הגיעו למטרה
השאלה
שנו את דפים שמקשרים לדף שלכם עד שהדף שלכם במקום השני בדירוג, אחרי הפורטל בלבד, ולחצו על בדיקה.

המטרה
- 2 ± 0.01
  בתחילת השלב: 7
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
דפים שמקשרים לדף שלכם
0
הסיכוי ללחוץ על קישור
85 %קבוע
דירוגים / גולש אקראי
דירוגים
נקרא מהסצנה בנקודה
The reader’s page’s place in the ranking, 1 the highest (1 + pages ranked strictly above it)/nodes/web/outputs/yourPlace
הגדרה אחת שמגיעה למטרה
דפים שמקשרים לדף שלכם
5
משוב לתשובה נכונה
עם קישורים מהפורטל ומאתר החדשות הדף שלכם מגיע לכ־16%, מעל החדשות עצמה. קישורים מדפים חשובים עושים דף חשוב.

משוב לתשובה שגויה
עוד לא. הוסיפו קישורים, ושימו לב מאיזה דף כל אחד מגיע.

רמז
אילו דפים כדאי שיקשרו אליכם?

פתרון מלא
1. הדפים הבאים בתור מוסיפים קישורים: שלושה שקטים, אחר כך הפורטל, אחר כך החדשות.
2. עם ארבעה קישורים הדף שלכם בכ־11.9%, עדיין אחרי החדשות והוויקי.
3. עם החמישי, מהחדשות, הוא בכ־16.1%, שני רק לפורטל: קבעו 5.
שלב 5 מתוך 6
לפתוח את השלב
מה קישור מעביר
תרגול · חשבו
השאלה
הפורטל מקשר לארבעה דפים, והגולש לוחץ על קישור ב־85% מהצעדים. קראו את הדירוג של הפורטל על הלוח. כמה נקודות אחוז מעביר כל אחד מהקישורים שלו?

התשובה הנכונה
7.116 ± 0.15
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
דפים שמקשרים לדף שלכם
4קבוע
הסיכוי ללחוץ על קישור
85 %קבוע
דירוגים / גולש אקראי
דירוגים
מתקבלת בטווח
± 0.15
מחושבת מהסצנה בהגדרה של השלב
The hub’s PageRank, percent/nodes/web/outputs/hubRank
תשובות שגויות שהשאלה מזהה
- 8.372 ± 0.15
  טעות נפוצה: Forgets that the surfer follows a link only part of the time (the damping factor) when working out what a link passes on.
  משוב מהקטלוג
  הגולש האקראי לוחץ על קישור רק ב־85% מהצעדים; בשאר הוא קופץ לדף אקראי. לכן דף מעביר דרך הקישורים שלו רק $0.85$ ⁠ מהדירוג שלו, מחולק ביניהם: $d \cdot \dfrac{PR}{L}$ ⁠. ה־15% הנותרים מתחלקים שווה בשווה בין כל הדפים, וזה מה שנותן גם לדף בלי קישורים אליו דירוג קטן.
- 28.46 ± 0.15
  טעות נפוצה: Thinks each of a page's links passes on the page's whole rank, instead of a share of it.
  משוב מהקטלוג
  דף לא מכפיל את הדירוג שלו כשהוא מוסיף קישורים; הוא מחלק אותו. הגולש שעומד בדף עם ארבעה קישורים יוצאים בוחר אחד מהם, ולכן כל קישור מקבל רבע מהזרימה. דף שמקשר לכל העולם נותן לכל אחד מעט מאוד.
משוב לתשובה נכונה
$0.85 \times \dfrac{33.5}{4} \approx 7.1$ ⁠ נקודות לכל קישור. אחד מהם מגיע לדף שלכם.

רמז
$d \cdot \dfrac{PR}{L}$ ⁠, עם $d = 0.85$ ⁠ ו־ $L = 4$ ⁠.

פתרון מלא
1. הדירוג של הפורטל: כ־33.5%.
2. ב־85% מהצעדים הגולש עוזב אותו בקישור, ובוחר אחד מארבעה.
3. $0.85 \times 33.5 \div 4 \approx 7.1$ ⁠.
בלי ה־ $0.85$ ⁠ יוצא כ־ $8.4$ ⁠; בלי החלוקה בארבעה יוצא כ־ $28$ ⁠.
שלב 6 מתוך 6
לפתוח את השלב
הגולש מתייצב
תרגול · נבאו, ואז הסתכלו
השאלה
הגולש האקראי עשה רק כמה קליקים, ועמודות הביקורים ליד הבסיסים רחוקות מהדירוגים. מה יקרה לעמודות כשהוא יעשה עשרים אלף קליקים?

התשובה הנכונה
- נכונה הן יתייצבו בגובה הבסיסים
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
דפים שמקשרים לדף שלכם
4קבוע
הסיכוי ללחוץ על קישור
85 %קבוע
דירוגים / גולש אקראי
0.3 (דירוגים → גולש אקראי)קבוע
האפשרויות
- נכונה הן יתייצבו בגובה הבסיסים
- שגויה הן ימשיכו לקפוץ, כי הגולש אקראי
  טעות נפוצה: Thinks a random walk cannot give a definite answer: its share of visits will keep jumping however long it runs.
  משוב מהקטלוג
  כל צעד של הגולש אקראי, אבל אחרי הרבה צעדים המקריות מתמצעת. השבר של הביקורים בכל דף מתקרב לערך קבוע, ההסתברות לעמוד שם בטווח הארוך, והוא בדיוק ה־PageRank. אחרי עשרה קליקים העמודות קופצות; אחרי עשרים אלף הן כמעט לא זזות. זה חוק המספרים הגדולים.
אחרי נעילת הניבוי הסצנה משתנה
דירוגים / גולש אקראי
גולש אקראיקבוע
ואז הסצנה מראה: 0.3331 · Largest visits-to-rank gap, points/nodes/web/outputs/gap
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
אחרי עשרים אלף קליקים הפער הגדול ביותר בין חלק הביקורים לדירוג הוא פחות מנקודת אחוז. PageRank הוא בדיוק החלק מהזמן שהגולש מבלה בכל דף בטווח הארוך.

פתרון מלא
1. כל צעד אקראי, אבל ההסתברות לעמוד בכל דף בטווח הארוך קבועה.
2. ככל שיש יותר צעדים, החלק של הביקורים בכל דף מתקרב להסתברות הזאת.
3. ההסתברות הזאת היא ה־PageRank, ולכן העמודות מתייצבות בגובה הבסיסים.

בכל היחידה · 12 טעויות נפוצות

קטלוג הטעויות הנפוצות

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

תוכן העניינים

צמתים וקשתות

מעיר לגרף

השאלה

התשובה הנכונה

הסצנה בשלב הזה

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא

דרגות

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז

פתרון מלא

לחיצות ידיים

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

פתרון מלא

גשר חדש

השאלה

המטרה

הסצנה בשלב הזה

הגדרה אחת שמגיעה למטרה

פתרון מלא

לספור לאחור

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז

פתרון מלא

מסלולי אוילר

החידה

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא

המסלול הטוב ביותר

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

פתרון מלא

לתקן את העיר

השאלה

המטרה

הסצנה בשלב הזה

הגדרה אחת שמגיעה למטרה

רמז

פתרון מלא

איפה להתחיל

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

פתרון מלא

מעגל

השאלה

המטרה

הסצנה בשלב הזה

הגדרה אחת שמגיעה למטרה

רמז

פתרון מלא

הכלל של אוילר

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

פתרון מלא

ניתוב חבילות

המסלול הקצר ביותר

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז