הבדלים בין גרסאות בדף "תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר"

@@ שורה 3: / שורה 3: @@
 תאריך עדכון אחרון: 29 ביוני 2013
-='''תוכנה 1: MATLAB'''=
+=='''תוכנה 1: 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
-==(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">