|
|
| שורה 3: |
שורה 3: |
| | תאריך עדכון אחרון: 29 ביוני 2013 | | תאריך עדכון אחרון: 29 ביוני 2013 |
| | | | |
| − | ='''תוכנה 1: MATLAB'''= | + | =='''תוכנה 1: MATLAB'''== |
| | | | |
| | ''הערה: ב־MATLAB בסוף כך שורת הוראה יש להוסיף ; על מנת שלא תתבצע הדפסה, אך אם רוצים הדפסה אין להוסיף ; בסוף השורה.'' | | ''הערה: ב־MATLAB בסוף כך שורת הוראה יש להוסיף ; על מנת שלא תתבצע הדפסה, אך אם רוצים הדפסה אין להוסיף ; בסוף השורה.'' |
| | | | |
| − | ==עבודה בסיסית ב־MATLAB==
| |
| | | | |
| − | ===משתנים===
| + | [[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, עבודה בסיסית ב־MATLAB|עבודה בסיסית ב־MATLAB]] |
| | | | |
| − | משתנה הוא סמל המסמן כמות, איבר של קבוצה, או ערך לוגי, העשויים להשתנות (מתוך ויקיפדיה).
| + | [[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, פונקציות|פונקציות]] |
| | | | |
| − | השמה למשתנה - הכנסת ערך אליו. ב־MATLAB (דוגמות): <BR>
| + | [[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, מבני נתונים|מבני נתונים]] |
| − | x=3 <BR>
| + | |
| − | z=pi <BR>
| + | |
| − | w=4+5*i <BR>
| + | |
| | | | |
| − | פעולות בסיסיות עם משתנים (a,b מציינים מספרים):
| + | [[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, יעילות|יעילות]] |
| − | {| border="1" align="center"
| + | |
| − | |-
| + | |
| − | ! הפעולה
| + | |
| − | ! הסימן ב־MATLAB
| + | |
| − | |-
| + | |
| − | | חיבור
| + | |
| − | | a+b
| + | |
| − | |-
| + | |
| − | | חיסור
| + | |
| − | | a-b
| + | |
| − | |-
| + | |
| − | | כפל
| + | |
| − | | a*b
| + | |
| − | |-
| + | |
| − | | חילוק
| + | |
| − | | /
| + | |
| − | |-
| + | |
| − | | חזקה
| + | |
| − | | a^b
| + | |
| − | |-
| + | |
| − | | לוגריתם טבעי (ln)
| + | |
| − | | (log(a
| + | |
| − | |-
| + | |
| − | | שורש ריבועי
| + | |
| − | | (sqrt(a
| + | |
| − | |-
| + | |
| − | | ערך שלם / רצפה
| + | |
| − | | (floor(a
| + | |
| − | |-
| + | |
| − | | שארית חלוקה (רק עבור שלמים)
| + | |
| − | | (mod(a,b
| + | |
| − | |} | + | |
| | | | |
| − | להוספת הערה בסוף שורה כותבים את הסימן % ולאחריו את ההערה.
| + | [[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, רקורסיה|רקורסיה]] |
| | | | |
| − | בחילוק שני מספרים שלמים, המנה היא (floor(x,y והשארית היא (mod(x,y.
| + | [[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, משוואות לינאריות וריבועים מינימליים|משוואות לינאריות וריבועים מינימליים]] |
| − | | + | |
| − | משתנים קבועים: i,j - ה־i המרוכב, <math>\sqrt{-1}</math>, pi - פאי.
| + | |
| − | | + | |
| − | הדפסת ערך משתנה: <BR>
| + | |
| − | (disp(value
| + | |
| − | | + | |
| − | ===מטריצות===
| + | |
| − | | + | |
| − | פעולות בסיסיות עם משתנים (A,B מציינים מטריצות):
| + | |
| − | {| border="1" align="center"
| + | |
| − | |-
| + | |
| − | ! הפעולה
| + | |
| − | ! ההוראה ב־MATLAB
| + | |
| − | |-
| + | |
| − | | הגדרת מטריצת אפסים בגודל <math>m\times n</math>
| + | |
| − | | (A=zeros(m,n
| + | |
| − | |-
| + | |
| − | | איבר בשורה x ובעמודה y
| + | |
| − | | (A(x,y
| + | |
| − | |-
| + | |
| − | | חיבור מטריצות
| + | |
| − | | A+B
| + | |
| − | |-
| + | |
| − | | חיסור מטריצות
| + | |
| − | | A-B
| + | |
| − | |-
| + | |
| − | | כפל במובן מטריצות
| + | |
| − | | A*B
| + | |
| − | |-
| + | |
| − | | כפל איבר־איבר
| + | |
| − | | A.*B
| + | |
| − | |-
| + | |
| − | | חילוק (כפל בהופכית)
| + | |
| − | | A/B
| + | |
| − | |-
| + | |
| − | | חילוק איבר־איבר
| + | |
| − | | A./B
| + | |
| − | |-
| + | |
| − | | מימדי מטריצה (וקטור)
| + | |
| − | | (size(A
| + | |
| − | |-
| + | |
| − | | שחלוף (transpose)
| + | |
| − | | 'A
| + | |
| − | |}
| + | |
| − | | + | |
| − | ועוד...
| + | |
| − | | + | |
| − | הערה 1: האינדקסים במטריצה מתחילים מ־1.
| + | |
| − | | + | |
| − | הערה 2: אם נעשתה פנייה לאיבר שאינו במערך והושם בו ערך, MATLAB ירחיב באופן אוטומטי את המערך, ובמקומות שנוספו יושמו אפסים.
| + | |
| − | | + | |
| − | ===מערכים: מטריצה מגודל nx1===
| + | |
| − | | + | |
| − | פעולות בסיסיות עם מערכים (v מייצג וקטור, m,n,p מייצגים מספר כלשהו):
| + | |
| − | {| border="1" align="center"
| + | |
| − | |-
| + | |
| − | ! הפעולה
| + | |
| − | ! ההוראה ב־MATLAB
| + | |
| − | |-
| + | |
| − | | אתחול (הצבת אפסים)
| + | |
| − | | (v=zeros(n,1
| + | |
| − | |-
| + | |
| − | | האיבר ה־n-י
| + | |
| − | | (v(n
| + | |
| − | |-
| + | |
| − | | אורך הוקטור
| + | |
| − | | (length(v
| + | |
| − | |-
| + | |
| − | | וקטור המכיל את המספרים הטבעיים עד n
| + | |
| − | | v=1:n
| + | |
| − | |-
| + | |
| − | | וקטור המכיל את כל המספרים מ־m עד n בקפיצות p
| + | |
| − | | v=m:p:n
| + | |
| − | |}
| + | |
| − | | + | |
| − | דוגמה: בכתיבה 1:5 יווצר הווקטור [5 4 3 2 1]. בכתיבה 1:2:5 יווצר הוקטור [5 3 1].
| + | |
| − | | + | |
| − | ניתן להגדיר וקטור גם באופן הבא: [w=[3 9 10 11 4 (במקום רווחים ניתן להשתמש בפסיקים). על מנת להגדיר מטריצה באופן דומה מוסיפים ; כדי לרדת שורה.
| + | |
| − | | + | |
| − | ניתן לקבל וקטור מאינדקסים מסוימים. למשל, עבור w שהוגדר, <BR>
| + | |
| − | [w(1:2:5)=w([1 3 5])=[3 10 4
| + | |
| − | | + | |
| − | ===פעולות בוליאניות===
| + | |
| − | | + | |
| − | פעולות בוליאניות מחזירות 0 (שקר) או 1 (אמת). דוגמות (a,b מספרים):
| + | |
| − | {|
| + | |
| − | ! הפעולה
| + | |
| − | ! הסימון ב־MATLAB
| + | |
| − | |-
| + | |
| − | | האם שני ערכים שווים
| + | |
| − | | a==b
| + | |
| − | |-
| + | |
| − | | קטן
| + | |
| − | | a<b
| + | |
| − | |-
| + | |
| − | | גדול
| + | |
| − | | a>b
| + | |
| − | |-
| + | |
| − | | קטן שווה
| + | |
| − | | a<=b
| + | |
| − | |-
| + | |
| − | | גדול שווה
| + | |
| − | | a>=b
| + | |
| − | |-
| + | |
| − | | אינו שווה
| + | |
| − | | =~
| + | |
| − | |}
| + | |
| − | | + | |
| − | && - וגם, || - או
| + | |
| − | | + | |
| − | ===תנאים===
| + | |
| − | | + | |
| − | תנאי פשוט:
| + | |
| − | <div align="left">
| + | |
| − | (תנאי) if <BR>
| + | |
| − | הוראות לביצוע<BR>
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | | + | |
| − | תנאי מורכב:
| + | |
| − | <div align="left">
| + | |
| − | (תנאי) if<BR>
| + | |
| − | (הוראות לביצוע)<BR>
| + | |
| − | else<BR>
| + | |
| − | (הוראות לביצוע)<BR>
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | | + | |
| − | תנאי יותר מורכב:
| + | |
| − | <div align="left">
| + | |
| − | (תנאי) if<BR>
| + | |
| − | (הוראות לביצוע)<BR>
| + | |
| − | elseif<BR>
| + | |
| − | (הוראות לביצוע)<BR>
| + | |
| − | else<BR>
| + | |
| − | (הוראות לביצוע)<BR>
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===לולאת for===
| + | |
| − | | + | |
| − | לולאת for - ביצוע אותו רצף הוראות מספר ידוע מראש של פעמים.
| + | |
| − | | + | |
| − | תכנות: <BR>
| + | |
| − | <div align="left">
| + | |
| − | (וקטור המכיל את ערכי i הדרושים)=for i<BR>
| + | |
| − | (הוראות לביצוע)<BR>
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | הערה: אמנם i הוא קבוע, אך ניתן להציב בו ערך. על מנת להחזירו להיות ה־i המרוכב, נכתוב את ההוראה clear i.
| + | |
| − | | + | |
| − | ===לולאת while===
| + | |
| − | | + | |
| − | לולאת while - ביצוע אותו רצף הוראות מספר שאינו ידוע מראש של פעמים אך עם תנאי לעצירה.
| + | |
| − | | + | |
| − | תכנות:<BR>
| + | |
| − | <div align="left">
| + | |
| − | (תנאי לעצירה, תנאי בוליאני) while<BR>
| + | |
| − | (הוראות לביצוע)<BR>
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===תרגילים===
| + | |
| − | | + | |
| − | ====תרגיל 1 - עצרת====
| + | |
| − | | + | |
| − | חשבו את <math>1000!</math>.
| + | |
| − | | + | |
| − | פתרון 1 - לולאת for:
| + | |
| − | <div align="left">
| + | |
| − | ;n=1
| + | |
| − | for i=2:1000
| + | |
| − | ;n=n*i
| + | |
| − | end
| + | |
| − | ;(disp(n
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | פתרון 2 - לולאת while: <BR>
| + | |
| − | <div align="left">
| + | |
| − | ;n=1
| + | |
| − | ;i=1
| + | |
| − | while i<=1000
| + | |
| − | ;n=n*i
| + | |
| − | ;i=i+1
| + | |
| − | end
| + | |
| − | ;(disp(n
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ====תרגיל 2 - מספרים ראשוניים====
| + | |
| − | | + | |
| − | צרו וקטור המכיל את כל המספרים הראשוניים מ־1 עד 1000
| + | |
| − | | + | |
| − | <div align="left">
| + | |
| − | ;כמה ראשוניים מצאנו % found=0
| + | |
| − | ;וקטור עם המספרים הראשוניים % []=primes
| + | |
| − | for p=1:1000
| + | |
| − | ;yesno=1
| + | |
| − | ;k=2
| + | |
| − | while k<=sqrt(p) && yesno==1
| + | |
| − | if mod(p,k)==0
| + | |
| − | ;yesno=0
| + | |
| − | end
| + | |
| − | ;k=k+1
| + | |
| − | end
| + | |
| − | if yesno==1
| + | |
| − | ;found=found+1
| + | |
| − | ;primes(found)=p
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ====תרגיל 3 - פירוק מספר שלם לגורמים ראשוניים====
| + | |
| − | | + | |
| − | פרקו מספר שלם <math>k\leq 1000</math> לגורמים ראשוניים (אפשר להשתמש בוקטור primes מהתרגיל הקודם).
| + | |
| − | | + | |
| − | <div align="left">
| + | |
| − | ;k=252
| + | |
| − | while k>1
| + | |
| − | ;i=2
| + | |
| − | while mod(k,primes(i))!~=0
| + | |
| − | ;i=i+1
| + | |
| − | end
| + | |
| − | ;((disp(primes(i
| + | |
| − | ;(k=k/primes(i
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===יישומים מתמטיים===
| + | |
| − | | + | |
| − | ====מחלק משותף גדול ביותר gcd====
| + | |
| − | | + | |
| − | עבור <math>m,n</math> שלמים, המספר השלם הגדול ביותר המחלק גם את <math>m</math> וגם את <math>n</math> ייקרא המחלק המשותף הגדול ביותר ויסומן <math>gcd(m,n)</math>.
| + | |
| − | | + | |
| − | <div align="left">
| + | |
| − | ;m=12
| + | |
| − | ;n=30
| + | |
| − | if n<m
| + | |
| − | ;t=m
| + | |
| − | ;m=n
| + | |
| − | ;n=t
| + | |
| − | end
| + | |
| − | for i=1:m
| + | |
| − | if mod(m,i)==0 && mod(n,i)=0
| + | |
| − | ;gcd=i
| + | |
| − | end
| + | |
| − | end
| + | |
| − | ;(disp(gcd
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ====קבלת מינימום====
| + | |
| − | | + | |
| − | ישנן שלוש דרכים לקבל את המספר המינימלי מבין <math>m,n</math>.
| + | |
| − | | + | |
| − | דרך ראשונה - ([min([m,n
| + | |
| − | | + | |
| − | דרך שנייה - תנאי
| + | |
| − | | + | |
| − | דרך שלישית - <math>min=\frac{m+n}{2}-\frac{m-n}{2}</math>
| + | |
| − | | + | |
| − | ====אלגוריתם אוקלידס====
| + | |
| − | | + | |
| − | אלגוריתם אוקלידס נועד למציאת מחלק משותף מקסימלי בין שני מספרים שלמים <math>m,n</math>.
| + | |
| − | | + | |
| − | '''האלגוריתם'''
| + | |
| − | | + | |
| − | נניח <math>m<n</math>. נגדיר:
| + | |
| − | <math>r_0=n</math> <BR>
| + | |
| − | <math>r_1=m</math><BR>
| + | |
| − | <math>r_0=q_1 r_1+r_2</math> כאשר <math>1\leq q_1 \leq r_0</math>, <math>0\leq r_2 <r_1</math><BR>
| + | |
| − | ובאינדוקציה <math>r_k=q_{k+1} r_{k+1}+r_{k+2}</math> <BR>
| + | |
| − | עד שנגיע ל־<math>r_N=0</math>. <BR>
| + | |
| − | בהכרח נעצור כי <math>r_{k+1}<r_k</math>.
| + | |
| − | | + | |
| − | לפי אלגוריתם זה, ה־gcd הינו <math>r_{N-1}</math>.
| + | |
| − | | + | |
| − | '''דוגמה'''
| + | |
| − | | + | |
| − | נבחר <math>r_0=30, r_1=12</math>. <BR>
| + | |
| − | <math>30=2\cdot 12+\underset{r_2}{\underbrace{6}}</math> <BR>
| + | |
| − | <math>12=2\cdot 6+\underset{r_3}{\underbrace{0}}</math><BR>
| + | |
| − | ולכן <math>gcd(30,12)=6</math>
| + | |
| − | | + | |
| − | '''הוכחת האלגוריתם'''
| + | |
| − | | + | |
| − | <math>r_{N-2}=q_{N-1} r_{N-1}+r_N=q_{N-1} r_{N-1}</math> <math>\Leftarrow</math> <math>r_{N-1}|r_{N-2}</math>. <BR> <BR>
| + | |
| − | <math>r_{N-3}=q_{N-2} r_{N-2}+r_{N-1}</math>. <BR>
| + | |
| − | <math>r_{N-1}|r_{N-2}</math> וגם <math>r_{N-1}|r_{N-1}</math> <math>\Leftarrow</math><math>r_{N-1}|r_{N-3}</math> <BR><BR>
| + | |
| − | <math>r_{N-4}=q_{N-3} r_{N-3}+r_{N-2}</math>. <BR>
| + | |
| − | <math>r_{N-1}|r_{N-2}</math> וגם <math>r_{N-1}|r_{N-3}</math> <math>\Leftarrow</math><math>r_{N-1}|r_{N-4}</math> <BR><BR <BR><BR>
| + | |
| − | באינדוקציה, נקבל <math>r_{N-1}|r_1</math> וגם <math>r_{N-1}|r_0</math>.
| + | |
| − | | + | |
| − | מדוע <math>r_{N-1}</math> הוא המחלק המשותף הגדול ביותר? נניח <math>r_k=gcd(m,n)</math>, אזי <math>r_{k-1}=q_{k} r_{k}+0</math>.
| + | |
| − | | + | |
| − | בהכרח נגיע למחלק המשותף המקסימלי מפני שבשלב ה־k־י, <math>r_{k-1}|gcd(m,n)</math> וגם <math>r_k|gcd(m,n)</math>, לכן <math>r_{k+1}|gcd(m,n)</math>.
| + | |
| − | | + | |
| − | '''תכנות'''
| + | |
| − | | + | |
| − | <div align="left">
| + | |
| − | ;m=12
| + | |
| − | ;n=30
| + | |
| − | if n<m
| + | |
| − | ;r1=n
| + | |
| − | ;r0=m
| + | |
| − | else
| + | |
| − | ;r1=m
| + | |
| − | ;r0=n
| + | |
| − | end
| + | |
| − | while r1>0
| + | |
| − | ;(r2=mod(r0,r1
| + | |
| − | ;r0=r1
| + | |
| − | ;r1=r2
| + | |
| − | end
| + | |
| − | ;gcd=r0
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | '''דוגמה'''
| + | |
| − | | + | |
| − | עבור <math>m=169, n=1482</math>
| + | |
| − | {| border="1" align="center"
| + | |
| − | ! <math>r_2</math>
| + | |
| − | ! <math>r_1</math>
| + | |
| − | ! <math>r_0</math>
| + | |
| − | |-
| + | |
| − | |
| + | |
| − | | 169
| + | |
| − | | 1482
| + | |
| − | |-
| + | |
| − | | 130
| + | |
| − | | 130
| + | |
| − | | 169
| + | |
| − | |-
| + | |
| − | | 39
| + | |
| − | | 39
| + | |
| − | | 130
| + | |
| − | |-
| + | |
| − | | 13
| + | |
| − | | 13
| + | |
| − | | 39
| + | |
| − | |-
| + | |
| − | | 0
| + | |
| − | | 0
| + | |
| − | | 13
| + | |
| − | |}
| + | |
| − | gcd(169,1482)=13
| + | |
| − | | + | |
| − | | + | |
| − | עבור <math>m=441, n=42</math>
| + | |
| − | {| border="1" align="center"
| + | |
| − | ! <math>r_2</math>
| + | |
| − | ! <math>r_1</math>
| + | |
| − | ! <math>r_0</math>
| + | |
| − | |-
| + | |
| − | |
| + | |
| − | | 42
| + | |
| − | | 441
| + | |
| − | |-
| + | |
| − | | 21
| + | |
| − | | 21
| + | |
| − | | 42
| + | |
| − | |-
| + | |
| − | | 0
| + | |
| − | | 0
| + | |
| − | | 21
| + | |
| − | |}
| + | |
| − | gcd(42,441)=21
| + | |
| − | | + | |
| − | ====פתרון מערכת משוואות - ניוטון-רפסון====
| + | |
| − | | + | |
| − | תהי <math>f(x)</math> פונקציה, צריך למצוא <math>x</math> כך ש־<math>f(x)=0</math>.
| + | |
| − | | + | |
| − | '''האלגוריתם והוכחתו'''
| + | |
| − | | + | |
| − | נתחיל מנקודה כלשהי, ובכל פעם נעביר דרכה משיק ונקבל נקודה חדשה - ששיעור ה־x שלה זהה לשיעור ה־x של החיתוך עם ציר x של המשיק. [http://upload.wikimedia.org/wikipedia/commons/f/f0/Newton_iteration.png המחשת האלגוריתם]
| + | |
| − | | + | |
| − | נתון <math>x_0</math>. נחשב את משוואת הישר <math>y=ax+b</math>, <math>a=f'(x_0)</math>, עובר בנקודה <math>(x_0,f(x_0))</math> (משוואת המשיק): <BR>
| + | |
| − | <math>f(x_0)=f'(x_0)x_0+b</math> <math>\Leftarrow</math> <math>b=f(x_0)-x_0 f'(x_0)</math>
| + | |
| − | | + | |
| − | | + | |
| − | כלומר, הישר המשיק ל־<math>f(x)</math> הינו <math>y=f'(x_0)x+f(x_0)-x_0 f(x_0)</math>. נמצא את <math>x_1</math>. חיתוך עם ציר <math>x</math>: <BR>
| + | |
| − | <math>x_1=-\frac{f(x_0)-f'(x_0)x_0}{f'(x_0)}=x_0-\frac{f(x_0)}{f'(x_0)}</math>.
| + | |
| − | | + | |
| − | | + | |
| − | לכן, <math>x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}</math>. נמשיך באיטרציות עד ש־<math>|x_k-x_{k-1}|<\Delta=10^{-12}</math>
| + | |
| − | | + | |
| − | | + | |
| − | טענה: <math>|x_{k+1}-\tilde{x}|\leq c|x_k-\tilde{x}|^2</math> עבור <math>c\ge 0</math>, כאשר <math>\tilde{x}</math> הינו השורש האמיתי.
| + | |
| − | | + | |
| − | '''תכנות'''
| + | |
| − | | + | |
| − | נתונה פונקציה f ופונקציה 'g=f. השגיאה הרצויה delta.
| + | |
| − | <div align="left">
| + | |
| − | ;x0=1
| + | |
| − | ;x1=x0+2*delta
| + | |
| − | while abs(x0-x1)>delta
| + | |
| − | ;(x1=x0-f(x0)/g(x0
| + | |
| − | ;t=x1
| + | |
| − | ;x1=x0
| + | |
| − | ;x0=t
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ==פונקציות==
| + | |
| − | | + | |
| − | פונקציה הינה רצף הוראות שנועד להתבצע עם נתונים מסוימים. למשל, פונקציה יכולה לקבל מספר ולהדפיס האם הוא ראשוני. פונקציה יכולה להחזיר ערך (או מערך עם כמה ערכים) או לא להחזיר ערך.
| + | |
| − | | + | |
| − | תכנות ב־MATLAB:
| + | |
| − | <div align="left">
| + | |
| − | (קלט) ''שם הפונקציה'' = [פלט] function
| + | |
| − | (הוראות לביצוע)
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===תרגילים===
| + | |
| − | | + | |
| − | ====תרגיל 1 - האם ראשוני====
| + | |
| − | | + | |
| − | כתבו פונקציה שתקבל מספר טבעי <math>p</math>. הפונקציה תחזיר 1 אם הוא ראשוני ו־0 אחרת.
| + | |
| − | <div align="left">
| + | |
| − | (function [yn]=isprime(p
| + | |
| − | ;yn=1
| + | |
| − | ;k=2
| + | |
| − | while k<=sqrt(p) && yn==1
| + | |
| − | if mod(p,k)==0
| + | |
| − | ;yn=0
| + | |
| − | end
| + | |
| − | ;k=k+1
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | בהסתמך על הפונקציה הנ"ל, כתבו תוכנית שתיצור וקטור של המספרים הראשוניים עד למספר טבעי נתון <math>n</math>.
| + | |
| − | <div align="left">
| + | |
| − | ;[]=primes
| + | |
| − | ;0=found
| + | |
| − | for k=1:n
| + | |
| − | 1==(if isprime(k
| + | |
| − | ;found=found+1
| + | |
| − | ;primes(found)=k
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ====תרגיל 2 - האם וקטור הוא פרמוטציה (תמורה)====
| + | |
| − | | + | |
| − | כתבו פונקציה המקבלת וקטור ובודקת אם הוא פרמוטציה של <math>1,...,n</math>.
| + | |
| − | <div align="left">
| + | |
| − | (function [yn] = ispermut (v
| + | |
| − | ;(n=length(v
| + | |
| − | ;(found=zeros(n,1
| + | |
| − | for i=1:n
| + | |
| − | ;yn=1
| + | |
| − | if v(i)<1 || v(i)>n
| + | |
| − | ;yn=0
| + | |
| − | else
| + | |
| − | ;found(v(i))=1
| + | |
| − | end
| + | |
| − | end
| + | |
| − | ;sum=0
| + | |
| − | for i=1:n
| + | |
| − | ;(sum=sum+found(i
| + | |
| − | end
| + | |
| − | ;(yn=(sum==n
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ==מבני נתונים==
| + | |
| − | | + | |
| − | '''המטרה: לכתוב פונקציות להוספה, למחיקה, לחיפוש ולמיון במערך'''. נחלק את הפעולות לשני מקרים: המערך אינו ממוין והמערך ממוין.
| + | |
| − | | + | |
| − | ===מערך שאינו ממוין===
| + | |
| − | | + | |
| − | נגדיר איזשהו מערך:
| + | |
| − | <div align="left">
| + | |
| − | ;[v=[79,100,31,5,84
| + | |
| − | <div align="right">
| + | |
| − | ונבצע עליו את הפעולות הבאות:
| + | |
| − | | + | |
| − | ====הוספה====
| + | |
| − | | + | |
| − | <div align="left">
| + | |
| − | (function [u] = add2array (v,k
| + | |
| − | הפונקציה מוסיפה איבר k למערך v ומחזירה u %
| + | |
| − | ;u=v
| + | |
| − | ;u(end+1)=k
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ====מחיקה====
| + | |
| − | | + | |
| − | אפשרות 1:
| + | |
| − | <div align="left">
| + | |
| − | (function [u] = deleteFromArray (v,p
| + | |
| − | הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
| + | |
| − | ;(u=zeros(length(v)-1,1
| + | |
| − | ;(u(1:p-1)=v(1:p-1
| + | |
| − | ;(u(p:length(v)-1)=v(p+1:end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | אפשרות 2:
| + | |
| − | <div align="left">
| + | |
| − | (function [u] = deleteFromArray2 (v,p
| + | |
| − | הפונקציה מוחקת את האיבר ה־p־י במערך ומחזירה u %
| + | |
| − | ;(u=zeros(length(v)-1,1
| + | |
| − | for i=1:p-1
| + | |
| − | ;(u(i)=v(i
| + | |
| − | end
| + | |
| − | (for i=p+1:length(v
| + | |
| − | ;(u(i-1)=v(i
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ====חיפוש====
| + | |
| − | | + | |
| − | <div align="left">
| + | |
| − | (function [p] = findInArray (v,x
| + | |
| − | הפונקציה מחזירה את המקום במערך שבו x נמצא או אפס אם x אינו במערך %
| + | |
| − | ;k=1
| + | |
| − | ;p=0
| + | |
| − | ;(n=length(v
| + | |
| − | while p==0 && k<=n
| + | |
| − | if v(k)==x
| + | |
| − | ;p=k
| + | |
| − | else
| + | |
| − | ;k=k+1
| + | |
| − | end
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===מערך ממוין===
| + | |
| − | | + | |
| − | כעת נניח שיש לנו מערך ממוין v, למשל מהקטן לגדול.
| + | |
| − | | + | |
| − | ====מחיקה====
| + | |
| − | | + | |
| − | בדיוק כמו במערך שאינו ממוין.
| + | |
| − | | + | |
| − | ====חיפוש====
| + | |
| − | | + | |
| − | ישנן שתי שיטות חיפוש: חיפוש בינארי ואריה במדבר.
| + | |
| − | | + | |
| − | חיפוש בינארי:
| + | |
| − | <div align="left">
| + | |
| − | (function [p] = binarySearch (v,x
| + | |
| − | ;(n=length(v
| + | |
| − | ;L=1
| + | |
| − | ;H=n
| + | |
| − | while L<H-1
| + | |
| − | ;(M=floor((L+H)/2
| + | |
| − | (if x<v(M
| + | |
| − | ;H=M
| + | |
| − | else
| + | |
| − | ;L=M
| + | |
| − | end
| + | |
| − | end
| + | |
| − | (if x==v(H
| + | |
| − | ;p=H
| + | |
| − | else
| + | |
| − | ;p=L
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | מספר הפעולות בחיפוש בינארי: <math>\log_2 n</math>
| + | |
| − | | + | |
| − | ====הוספה====
| + | |
| − | | + | |
| − | אם x קטן מ־(v(1, נכניס אותו בהתחלה. אחרת נחפש את x ונכניס אותו אחרי L.
| + | |
| − | | + | |
| − | ====מיון פשוט====
| + | |
| − | | + | |
| − | ראשית, נכתוב פונקציית עזר:
| + | |
| − | <div align="left">
| + | |
| − | (function [m,p] = findSmallest (v,k
| + | |
| − | הפונקציה מוצאת את המקום p ואת הערך m הנמצא במערך v והמינימלי מהמקום ה־k־י והלאה %
| + | |
| − | ;p=k
| + | |
| − | ;(m=v(k
| + | |
| − | ;(n=length(v
| + | |
| − | for i=k+1:n
| + | |
| − | if v(i)<m
| + | |
| − | ;p=i
| + | |
| − | ;(m=v(i
| + | |
| − | end
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | כעת, נכתוב את התוכנית למיון:
| + | |
| − | <div align="left">
| + | |
| − | for i=1:n-1
| + | |
| − | ;(m,p]=findSmallest(v,i]
| + | |
| − | ;(v(p)=v(i
| + | |
| − | ;v(i)=m
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ==יעילות==
| + | |
| − | | + | |
| − | אם אנו חושדים שזמן הריצה <math>t</math> כתלות ב־<math>n</math> פרופורציוני ל־<math>n^r</math>:
| + | |
| − | <div align="left">
| + | |
| − | <math>t\propto n^r</math> <BR>
| + | |
| − | <math>\Downarrow</math> <BR>
| + | |
| − | <math>t=cn^r</math> <BR>
| + | |
| − | <math>\ln t=\ln c+r\ln n</math> <BR>
| + | |
| − | <div align="right">
| + | |
| − | לכן <math>\ln t</math> כתלות ב־<math>\ln n</math> הינו קו ישר ששיפועו <math>r</math>, וכך ניתן למצוא את <math>\ln c</math> כחיתוך עם ציר y.
| + | |
| − | | + | |
| − | ===מספר הגדרות ודוגמות===
| + | |
| − | | + | |
| − | <math>f\left ( n \right )=\Theta\left ( g\left ( n \right ) \right )</math> אם <math>\forall n, A\cdot g\left ( n \right )\leq f\left ( n \right )\leq B\cdot g\left ( n \right )</math>.
| + | |
| − | | + | |
| − | <math>f\left ( n \right )=O \left ( g\left ( n \right ) \right )</math> אם <math>\forall n, f\left ( n \right )\leq B\cdot g\left ( n \right )</math>.
| + | |
| − | | + | |
| − | | + | |
| − | ''דוגמה:''
| + | |
| − | | + | |
| − | <math>e^x=1+x+\frac{x^2}{2}+...=\sum_{n=0}^\infty\frac{x^n}{n!}</math>, לכן <math>e^x=1+x+\frac{x^2}{2}+O(x^3)</math>. <BR>
| + | |
| − | באופן מדויק: <math>e^x=1+x+\frac{x^2}{2}+\frac{(x^*)^3}{6}</math> כאשר <math>|x^*|<|x|</math>, ולכן <math>\frac{(x^*)^3}{6}\leq\frac{1}{6} x^3</math>.
| + | |
| − | | + | |
| − | | + | |
| − | ''דוגמה נוספת:''
| + | |
| − | | + | |
| − | בחיפוש בינארי מבוצעות <math>\left \lceil \log_2 n\right \rceil</math> פעולות, ולכן היעילות הינה <math>\left \lceil \log_2 n\right \rceil=O(\log_2 n)=O(\ln n)</math>.
| + | |
| − | | + | |
| − | | + | |
| − | <math>f\left ( n \right )=o\left ( g\left ( n \right ) \right )</math> אם <math>\lim_{n\rightarrow\infty}\frac{f\left ( n \right )}{g\left ( n \right )}=0</math>.
| + | |
| − | | + | |
| − | | + | |
| − | ''דוגמה:''
| + | |
| − | | + | |
| − | <math>e^{-x}=o\left ( x^n \right )</math> כי <math>\lim_{x\rightarrow\infty}\frac{e^{-x}}{x^n}=0</math>
| + | |
| − | | + | |
| − | | + | |
| − | ''דוגמה נוספת:''
| + | |
| − | | + | |
| − | <math>\ln x=o\left ( x \right )</math> וגם <math>\ln x=O\left ( x \right )</math>.
| + | |
| − | | + | |
| − | | + | |
| − | ==רקורסיה==
| + | |
| − | | + | |
| − | מתוך פונקציה שאנו מגדירים ניתן לקרוא לעצמה.
| + | |
| − | | + | |
| − | '''ברקורסיה חשוב לזכור:'''
| + | |
| − | #''' תנאי עצירה
| + | |
| − | #''' "צעד" הרקורסיה - זימון הפעולה בתוך עצמה'''
| + | |
| − | | + | |
| − | ===תרגיל 1 - חישוב עצרת===
| + | |
| − | | + | |
| − | נזכור כי: <BR>
| + | |
| − | <math>\left\{\begin{matrix}n!=\left ( n-1 \right )!\cdot n
| + | |
| − | \\
| + | |
| − | 0!=1 \ \ \ \ \ \ \ \ \ \ \ \
| + | |
| − | \end{matrix}\right.</math>
| + | |
| − | | + | |
| − | ונכתוב פונקציה מתאימה:
| + | |
| − | <div align="left">
| + | |
| − | (function [f] = fact (n
| + | |
| − | if n==0
| + | |
| − | ;f=1
| + | |
| − | else
| + | |
| − | ;(f=n*fact(n-1
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===תרגיל 2 - מקדמים בינומיים===
| + | |
| − | | + | |
| − | המקדם הבינומי <math>\binom{n}{k}</math> מונה כמה אפשרויות יש לנו לבחירת <math>k</math> איברים מתוך <math>k</math> ללא בחירת איבר פעמיים וללא חשיבות לסדר.
| + | |
| − | | + | |
| − | נוסחה סגורה לחישוב: <math>\binom{n}{k}=\frac{n!}{k!\left ( n-k \right )!}</math>
| + | |
| − | | + | |
| − | מ[http://www.mathsisfun.com/images/pascals-triangle-n-choose-k.gif משולש פסקל] אנו מקבלים נוסחת נסיגה לחישובם: <math>\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}</math>.
| + | |
| − | | + | |
| − | נכתוב פונקציה מתאימה:
| + | |
| − | <div align="left">
| + | |
| − | (function [b] = binomial (n,k
| + | |
| − | if k==0 || k==n
| + | |
| − | ;b=1
| + | |
| − | else
| + | |
| − | ;(b=binomial(n-1,k)+binomial(n-1,k-1
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===תרגיל 3 - איחוד מערכים ממוינים===
| + | |
| − | | + | |
| − | '''המטרה: לאחד שני מערכים ממוינים u,v למערך ממוין'''
| + | |
| − | | + | |
| − | הפונקציה המתאימה:
| + | |
| − | <div align="left">
| + | |
| − | (function [w] = merge (u,v
| + | |
| − | ;(nu=length(u
| + | |
| − | ;(nv=length(v
| + | |
| − | ;nw=nu+nv
| + | |
| − | ;(w=zeros(nw,1
| + | |
| − | if nu==0
| + | |
| − | ;w=v
| + | |
| − | elseif nv==0
| + | |
| − | ;w=u
| + | |
| − | else
| + | |
| − | ;ku=1
| + | |
| − | ;kv=1
| + | |
| − | for kw=1:nw
| + | |
| − | ((if (ku<=nu) && (kv>nv || u(ku)<v(kv
| + | |
| − | ;(w(kw)=u(ku
| + | |
| − | ;ku=ku+1
| + | |
| − | else
| + | |
| − | ;(w(kw)=v(kv
| + | |
| − | ;kv=kv+1
| + | |
| − | end
| + | |
| − | end
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ===תרגיל 4 - מיון מערך===
| + | |
| − | | + | |
| − | '''המטרה: למיין מערך ביעילות <math>O(n\cdot\ln n)</math>'''
| + | |
| − | | + | |
| − | הביצוע: כל פעם נחלק לשני תת־מערכים, נמיין אותם ונאחד (באמצעות הפעולה מתרגיל 3)
| + | |
| − | | + | |
| − | הפונקציה המתאימה:
| + | |
| − | <div align="left">
| + | |
| − | (function [w] = mergeSort (v
| + | |
| − | ;(n=length(v
| + | |
| − | if n<=1
| + | |
| − | ;w=v
| + | |
| − | else
| + | |
| − | ;(m=floor(n/2
| + | |
| − | ;((w1=mergeSort(v(1:m
| + | |
| − | ;((w2=mergeSort(v(m+1:n
| + | |
| − | ;(w=merge(w1,w2
| + | |
| − | end
| + | |
| − | end
| + | |
| − | <div align="right">
| + | |
| − | | + | |
| − | ==משוואות לינאריות==
| + | |
| − | | + | |
| − | תהי מערכת משוואות <math>Ax=b</math> כאשר <math>A\in M_{n\times k}\left ( \mathbb{R} \right )</math>, <math>x\in\mathbb{R}^k</math> ו־<math>b\in\mathbb{R}^n</math>. אזי:
| + | |
| − | | + | |
| − | # למערכת אין פתרון אם <math>b\notin C\left ( A \right )</math>.
| + | |
| − | # למערכת יש פתרון יחיד אם <math>rank\left ( A \right )=k</math>, כלומר <math>\det\left ( A \right )\neq 0</math>.
| + | |
| − | # למערכת יש אינסוף פתרונות אם <math>b\in C\left ( A \right )</math>.
| + | |
| − | | + | |
| − | במקרים 1 ו־3 מתקיים <math>rank\left ( A \right )<k</math>, <math>\det\left ( A \right )=0</math>.
| + | |
| − | | + | |
| − | ''הערה: <math>rank\left ( A \right )</math> - מספר העמודות הבת"ל ב־<math>A</math>.''
| + | |
| − | | + | |
| − | ===מקרה 2: פתרון יחיד===
| + | |
| − | | + | |
| − | שלוש אפשרויות לחישוב הפתרון על ידי MATLAB:
| + | |
| − | # x=inv(A)*b
| + | |
| − | # x=A\b
| + | |
| − | # x=pinv(A)*b
| + | |
| − | | + | |
| − | אפשרויות 2 ו־3 מתאימה גם אם <math>A</math> אינה הפיכה / ריבועית.
| + | |
| − | | + | |
| − | ===מקרה 1: אין פתרון===
| + | |
| − | | + | |
| − | ====התאמת קו ישר לאוסף נקודות====
| + | |
| − | | + | |
| − | עבור סדרת N נקודות, <math>\left \{ \left ( x_i,y_i \right ) \right \}_{i=1}^N</math>, ננסה להתאים ישר <math>y=c_1 x+c_2</math> הקרוב להן ביותר (קו מגמה).
| + | |
| − | | + | |
| − | נגדיר מטריצה <math>A</math>:
| + | |
| − | <math>A=\begin{pmatrix}
| + | |
| − | x_1 & 1 \\
| + | |
| − | x_2 & 1 \\
| + | |
| − | \vdots & \vdots \\
| + | |
| − | x_N & 1
| + | |
| − | \end{pmatrix}</math>
| + | |
| − | | + | |
| − | ו־וקטור <math>y</math>:
| + | |
| − | <math>y=\begin{pmatrix}
| + | |
| − | y_1 \\
| + | |
| − | y_2 \\
| + | |
| − | \vdots \\
| + | |
| − | y_N
| + | |
| − | \end{pmatrix}</math>
| + | |
| − | | + | |
| − | ונפתור את מערכת המשוואות <math>Ac=y</math>. הפתרון <math>c</math> שנקבל הינו הווקטור <math>\begin{pmatrix}
| + | |
| − | c_1 \\
| + | |
| − | c_2
| + | |
| − | \end{pmatrix}</math>
| + | |
| − | | + | |
| − | | + | |
| − | '''פתרון המערכת: ניעזר ברגרסיה לינארית'''
| + | |
| − | | + | |
| − | נגדיר פונקציה <math>R=\sum_{i=1}^Nd_i^2</math> כאשר <math>d_i</math> הינו המרחק של הנקודה ה־i־ית מהישר (אנך לציר x), שהוא בעצם הפרשי ה־y. כלומר, <math>R\left ( c_1,c_2 \right )=\sum_{i=1}^N \left ( y_i-c_ix_i-c_2 \right )^2</math>. המינימום של הפונקציה הזו ייתן לנו את הפתרון המקורב ביותר לנקודות, כזה שסכום ריבועי המרחקים שלו מהנקודות הנתונות מינימלי - הכי קרוב.
| + | |
| − | | + | |
| − | נגזור ונקבל נגזרות חלקיות:
| + | |
| − | | + | |
| − | <math>\frac{\partial R}{\partial c_1}=\sum_{i=1}^N 2\cdot \left ( y_i-c_ix_i-c_2 \right ) \cdot \left (-x_i \right )=-\sum_{i=1}^{N}2x_i \left ( y_i-c_ix_i-c_2 \right )=0</math>
| + | |
| − | | + | |
| − | <math>\frac{\partial R}{\partial c_2}=\sum_{i=1}^N 2\cdot \left ( y_i-c_ix_i-c_2 \right ) \cdot \left (-1 \right )=-\sum_{i=1}^{N}2 \left ( y_i-c_ix_i-c_2 \right )=0</math>
| + | |
| − | | + | |
| − | נמשיך לפתור:
| + | |
| − | | + | |
| − | <math>c_1\sum_{i=1}^N x_i^2+c_2 \sum_{i=1}^N x_i=\sum_{i=1}^{N} x_i y_i</math>
| + | |
| − | | + | |
| − | <math>c_1\sum_{i=1}^{N}x_i+Nc_2=\sum_{i=1}^{N}y_i</math>
| + | |
| − | | + | |
| − | בעצם, קיבלנו מערכת משוואות השקולה למערכת <math>A^t A c=A^t y</math> (למי שאינו מאמין, ניתן לבדוק).
| + | |
| − | | + | |
| − | נחשב את <math>\det(A^t A)</math> כדי לדעת מתי אין פתרון יחיד למערכת:
| + | |
| − | | + | |
| − | <math>\det\left ( A^t A \right )=N\sum_{i=1}^{N}x_i^2-\left ( \sum_{i=1}^{N}x_i \right )^2=N^2 \left [ \frac{\sum_{i=1}^{N}x_i^2}{N}-\left ( \frac{\sum_{i=1}^{N}x_i}{N} \right )^2 \right ]</math>
| + | |
| − | | + | |
| − | למה: <math>\frac{\sum_{i=1}^{N}x_i^2}{N}-\left ( \frac{\sum_{i=1}^{N}x_i}{N} \right )^2=\frac{1}{N}\sum_{i=1}^{N}\left ( x_i-\frac{\sum_{i=1}^{N}x_i}{N} \right )^2</math>
| + | |
| − | | + | |
| − | הוכחה: נסמן את הממוצע <math>\bar{x}=\frac{\sum_{i=1}^{N}x_i}{N}</math>. אזי:
| + | |
| − | | + | |
| − | <math>\frac{1}{N}\sum_{i=1}^{N}\left ( x_i-\bar{x} \right )^2=\frac{1}{N}\sum_{i=1}^{N} \left (x_i^2-2x_i\bar{x} +\bar{x}^2 \right )=\frac{1}{N}\sum_{i=1}^{N} x_i^2-2\bar{x}\underset{\bar{x}}{\underbrace{\frac{1}{N}\sum_{i=1}^{N}x_i}}+\underset{\bar{x}^2}{\underbrace{\frac{1}{N}\sum_{i=1}^{N}\bar{x}^2}}=\frac{1}{N}\sum_{i=1}^{N} x_i^2-\bar{x}^2</math>
| + | |
| − | | + | |
| − | | + | |
| − | מסקנה: <math>\det (A^t A)=0</math> אם ורק אם <math>x_1=x_2=...=x_N=\bar{x}</math>. לכן, קיים '''פתרון ריבועים מינימליים (Least squares solution)'''.
| + | |
