Tom the Farmer_finding function minimum.ipynb

Kernel: Python 2 (system-wide)

name2-ו name1 הקלידו את שימכם ואת שם בן/בת זוגכם

name1="   "
name2="   "

בעיית טום האיכר

צפו בקטע הווידאו שבהמשך

from IPython.display import YouTubeVideo,HTML
# הצגת הבעיה 
# Video credit:Shlomo Rozenfeld
YouTubeVideo('qJqsDUVuVL4')

תרגיל 1

---

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

_____________

h=2
d=4
H=3

תרגיל 2

הפונקציה home_C_dist שבתא שלמטה צריכה להחזיר את המרחק בין הבית לנקודה C. שיעורי הנקודה C הם (x,0). הפרמטר שהפונקציה מקבלת ההוא שיעור ה-x של מקום הנקודה C. השלימו את הפונקציה כך שבאמת תחזיר את המרחק בין הנקודה C לבית.

from math import sqrt
def home_C_dist(x):
    h=2
    return sqrt(h*h + x*x)

תרגיל 3

כתבו פונקציה בשם farm_C_dist. הפונקציה תקבל את אותה נקודה x כפרמטר ותחזיר את המרחק בין הנקודה C והחווה.

from math import sqrt
def farm_C_dist(x,d):
    H=3
    return sqrt(H*H + (d-x)*(d-x))
farm_C_dist(3,4)

3.1622776601683795

תרגיל 4

במידה והקוד שכתבתם נכון, קטע הקוד שבהמשך יחזיר את אורך הדרך מהבית לנהר ולחווה כתלות בשיעור ה- x של הנקודה C. ליד כל שורה, כתבו הערה המסבירה מה היא עושה. הריצו את הקוד ובידקו שבאמת ישנה נקודה עבורה המסלול הוא הקצר ביותר.

import matplotlib.pyplot as plt
n=1000#מספר הריצות
d=4#המרחק מהבית לחווה בשיעור ה-איקס
dx=d/float(n)#המקטעים בין כל חישוב
x=[ i*dx for i in range(n+1)]#חישוב שיעור האיקס של נקודה סי
s=[home_C_dist(a)+farm_C_dist(a,d) for a in x]#המרחק בין הבית לחווה דרך הנהר
plt.plot(x,s)
plt.xlabel('x[km]',fontsize=16,color=(1,0,1))
plt.ylabel('y[km]',fontsize=16,color=(1,0,1))
plt.title('s-x graph',fontsize=24,color=(0,1,0))
plt.grid(True)
for j in range(n+1):
    if (s[j] == min(s)):
        print(x[j],s[j])

(1.6, 6.4031242374328485)

תרגיל 5

---

אלגוריתם למציאת המסלול הקצר ביותר הוא האלגוריתם הבא:
א. בחרו על גדוד הנהר נקודה ששיעור ה-x שלה הוא מספר אקראי בין 0 ל-d.
ב. חשבו את אורך המסלול.

ג. בשלב זה מבצעים צעד אקראי בשיעור
$$-\delta \le \Delta x \le \delta$$
בחירה נבונה ל- $$\delta$$ היא בשלב ראשון $$\frac{d}{2}$$.
ד. מחשבים מחדש את אורך המסלול. מבצעים את הצעד רק אם המסלול החדש קצר יותר.
ה. חוזרים על שני השלבים הקודמים n פעמים.

ישמו את האלגוריתם שתואר למעלה בפונקציה get_min_path שלמטה. הריצו אותו והשוו למינמום המתקבל בגרף.

from math import sqrt
import random
def home_C_dist(x):
    h=2
    return sqrt(h*h + x*x)
def farm_C_dist(x,d):
    H=3
    return sqrt(H*H + (d-x)*(d-x))
def get_min_path(delta):
    h=2
    d=4
    H=3
    X1=0
    X2=d
    X3=random.uniform(1,d)
    S1=home_C_dist(X1)+farm_C_dist(X1,d)
    S2=home_C_dist(X2)+farm_C_dist(X2,d)
    S3=home_C_dist(X3)+farm_C_dist(X3,d)
    del1=abs(S1-S3)
    del2=abs(S2-S3)
    if (abs(del1)>abs(del2)):
        del3=abs(del2)
    else:
        del3=abs(del1)
    while (abs(del3) > delta):
        print(abs(del3),S1,S2,S3,X3)
        if (S1>S2):
            X1=X3
            X3=float(X1+X2)/2
        else:
            X2=X3
            X3=float(X1+X2)/2
        S1=home_C_dist(X1)+farm_C_dist(X1,d)
        S2=home_C_dist(X2)+farm_C_dist(X2,d)
        S3=home_C_dist(X3)+farm_C_dist(X3,d)
        del1=abs(S1-S3)
        del2=abs(S2-S3)
        if (abs(del1)>abs(del2)):
            del3=abs(del2)
        else:
            del3=abs(del1)
    return S3
d=4
get_min_path(0.5*d)

6.404504323044469

תרגיל 6

---

השלימו את הפונקציה שלמטה באופן כזה שהיא תחזיר רשימה של ערכי המינימום שהתקבלו עבור הרצות חוזרות של הפונקציה get_min_path. המשתנים שיועברו לפונקציה הם n_runs שזה מספר ההרצות delta ו- n (שמופיע בתרגיל 4).

def get_min_multirun(n_trials,delta,n=10):
    ls=[get_min_path(delta) for i in range(n_trials)]
    return ls
get_min_multirun(7,0.1)

(0.5156825852967621, 7.0, 7.47213595499958, 6.484317414703238, 2.2533086964564113)
(0.5921078067589169, 7.0, 7.47213595499958, 6.407892193241083, 1.7559639305790353)
(0.10611609601030292, 7.0, 6.407892193241083, 6.514008289251386, 0.8779819652895177)
(0.5855201733494511, 7.0, 7.47213595499958, 6.414479826650549, 1.363205689141941)
(0.17192656069955348, 7.0, 6.414479826650549, 6.586406387350102, 0.6816028445709705)
(0.158908442137502, 7.0, 7.47213595499958, 6.841091557862498, 3.1354321926484743)
(0.4377599980501907, 7.0, 6.841091557862498, 6.403331559812307, 1.5677160963242371)
(0.10677753794573608, 6.403331559812307, 6.841091557862498, 6.510109097758043, 2.3515741444863556)
(0.4018421880984384, 7.0, 7.47213595499958, 6.598157811901562, 2.61962267116233)
(0.17789413118943997, 7.0, 6.598157811901562, 6.420263680712122, 1.309811335581165)

[6.968184066744881,
 7.0275926490937835,
 6.449554538453617,
 6.419417116121501,
 6.473005026271627,
 6.4281288349101064,
 6.428830919412505]

תרגיל 7

העריכו את השגיאה בחישוב שיעור ה-x של הנקודה C עבור n=10 ו-delta=0.5d.

#כאשר delta=0.5d השגיאה בחישוב תיהיה תלויה במספר שנבחר(ע"פ השיטה הנומרית)

תרגיל 8

---

עבור ערכי $\delta$ בתחום שבין d*0.1 ועד ל d בקפיצות של 0.1 , שרטטו גרף של סטיית התקן המתקבלת בחישוב שיעור ה- x של הנקודה בה המסלול הקצר ביותר. עבור איזה ערך של $\delta$ מתקבלת השגיאה הקטנה ביותר?

import py_compile
py_compile.compile('my_statistics.py')

import my_statistics as ms
import matplotlib.pyplot as plt
d=4
i=d*0.1
lsDelta=[]
while i<=d:
    lsDelta.append(i)
    i+=0.1
j=len(lsDelta)
lsStd=[ms.std(get_min_multirun(j,i)) for i in lsDelta]
plt.plot(lsDelta,lsStd,lw=2.5,c='g')
#השגיאה הקטנה ביותר מתקבלת כאשר נק סי מתקרבת ל1ץ6

(0.4238434980453114, 7.0, 7.47213595499958, 6.576156501954689, 2.559504824055603)
(0.5454350954409097, 7.0, 7.47213595499958, 6.45456490455909, 1.1023840742324047)
(0.4993453113317612, 7.0, 7.47213595499958, 6.500654688668239, 2.3170650753825566)
(0.47257631911386255, 7.0, 7.47213595499958, 6.5274236808861374, 2.411093023937246)
(0.5749031067470014, 7.0, 7.47213595499958, 6.425096893252999, 1.2720251682898682)
(0.5576788154076953, 7.0, 7.47213595499958, 6.442321184592305, 2.051533561425629)
(0.5856452560132581, 7.0, 7.47213595499958, 6.414354743986742, 1.3644993851133842)
(0.5632377841403438, 7.0, 7.47213595499958, 6.436762215859656, 2.0178792294707795)
(0.5869049613295569, 7.0, 7.47213595499958, 6.413095038670443, 1.8261059924170637)
(0.5376426949688113, 7.0, 7.47213595499958, 6.462357305031189, 2.1566721933638227)
(0.5592600727310755, 7.0, 7.47213595499958, 6.4407399272689245, 1.1729544122741207)
(0.5640523590481159, 7.0, 7.47213595499958, 6.435947640951884, 2.012725151325888)
(0.5725207091206537, 7.0, 7.47213595499958, 6.427479290879346, 1.9548902348129638)
(0.5884558148240036, 7.0, 7.47213595499958, 6.4115441851759964, 1.8076445618010224)
(0.5648568598044541, 7.0, 7.47213595499958, 6.435143140195546, 1.205368405729327)
(0.4847544016992664, 7.0, 7.47213595499958, 6.515245598300734, 2.369695341157361)
(0.5672404645951854, 7.0, 7.47213595499958, 6.432759535404815, 1.2200666059786422)
(0.5953938300650634, 7.0, 7.47213595499958, 6.404606169934937, 1.6867246766406256)
(0.5518085823925958, 7.0, 7.47213595499958, 6.448191417607404, 1.1334928520838317)
(0.5511060488983386, 7.0, 7.47213595499958, 6.448893951101661, 1.1299550332775075)
(0.547118714779268, 7.0, 7.47213595499958, 6.452881285220732, 1.1103949750798465)
(0.5968452020707398, 7.0, 7.47213595499958, 6.40315479792926, 1.5875949397829552)
(0.5221148870946877, 7.0, 7.47213595499958, 6.477885112905312, 2.2264948167055785)
(0.5298029172940737, 7.0, 7.47213595499958, 6.470197082705926, 1.0337912937911131)
(0.5931389661111499, 7.0, 7.47213595499958, 6.40686103388885, 1.4635477622362236)
(0.5269366131497213, 7.0, 7.47213595499958, 6.473063386850279, 1.0221701986515401)
(0.5946702919305302, 7.0, 7.47213595499958, 6.40532970806947, 1.495027080940331)
(0.5962025107675757, 7.0, 7.47213595499958, 6.403797489232424, 1.5418856749874947)
(0.5967277563093951, 7.0, 7.47213595499958, 6.403272243690605, 1.6273436963607972)
(0.5909459737461908, 7.0, 7.47213595499958, 6.409054026253809, 1.7740458859619168)
(0.5912104640050284, 7.0, 7.47213595499958, 6.408789535994972, 1.4322202292649697)
(0.5740073689614382, 7.0, 7.47213595499958, 6.425992631038562, 1.2655117459740728)
(0.5633451236350009, 7.0, 7.47213595499958, 6.436654876364999, 1.1963400154636084)
(0.5596669752756167, 7.0, 7.47213595499958, 6.440333024724383, 2.0397832611803812)
(0.541261988978305, 7.0, 7.47213595499958, 6.458738011021695, 1.0831042311506227)
(0.591176754258294, 7.0, 7.47213595499958, 6.408823245741706, 1.431725525076462)
(0.5899177818544779, 7.0, 7.47213595499958, 6.410082218145522, 1.4142114648849444)
(0.5380801078876232, 7.0, 7.47213595499958, 6.461919892112377, 2.1545827418555614)
(0.596687402125399, 7.0, 7.47213595499958, 6.403312597874601, 1.6308512558807748)

[<matplotlib.lines.Line2D at 0x7f119de23a10>]

תרגיל 9

---

התרשים שבהמשך מגדיר שתי זוויות alpha ו-beta. הראו מה המסלול המינימאלי כאשר alpha=beta. עשו זאת באופן חישובי ובאמצעות הוכחה גיאומטרית (במקרה זה אתם יכולים לעשות על דף ולעלות אותו).

#ההוכחה נמצאת בתוך המשימה בתיקייה נרדפת

תרגיל 10

צפו בסרטון שבהמשך. מה המסקנה שתוכלו להסיק מהעבודה לגבי המסלול בו "בוחרת" קרן אור לנוע?

YouTubeVideo('OrRMKbwzgSg')

#הקרן נוטה לנוע במסלול הקצר ביותר