תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר
תאריך עדכון אחרון: 29 ביוני 2013
תוכנה 1: MATLAB
הערה: ב־MATLAB בסוף כך שורת הוראה יש להוסיף ; על מנת שלא תתבצע הדפסה, אך אם רוצים הדפסה אין להוסיף ; בסוף השורה.
עבודה בסיסית ב־MATLAB
משתנים
משתנה הוא סמל המסמן כמות, איבר של קבוצה, או ערך לוגי, העשויים להשתנות (מתוך ויקיפדיה).
השמה למשתנה - הכנסת ערך אליו. ב־MATLAB (דוגמות):
x=3
z=pi
w=4+5*i
פעולות בסיסיות עם משתנים (a,b מציינים מספרים):
| הפעולה | הסימן ב־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]\displaystyle{ \sqrt{-1} }[/math], pi - פאי.
הדפסת ערך משתנה:
(disp(value
מטריצות
פעולות בסיסיות עם משתנים (A,B מציינים מטריצות):
| הפעולה | ההוראה ב־MATLAB |
|---|---|
| הגדרת מטריצת אפסים בגודל [math]\displaystyle{ 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 מייצגים מספר כלשהו):
| הפעולה | ההוראה ב־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 שהוגדר,
[w(1:2:5)=w([1 3 5])=[3 10 4
פעולות בוליאניות
פעולות בוליאניות מחזירות 0 (שקר) או 1 (אמת). דוגמות (a,b מספרים):
| הפעולה | הסימון ב־MATLAB |
|---|---|
| האם שני ערכים שווים | a==b |
| קטן | ab |
| קטן שווה | a<=b |
| גדול שווה | a>=b |
| אינו שווה | =~ |
&& - וגם, || - או
תנאים
תנאי פשוט:
(תנאי) if
הוראות לביצוע
end
תנאי מורכב:
(תנאי) if
(הוראות לביצוע)
else
(הוראות לביצוע)
end
תנאי יותר מורכב:
(תנאי) if
(הוראות לביצוע)
elseif
(הוראות לביצוע)
else
(הוראות לביצוע)
end
לולאת for
לולאת for - ביצוע אותו רצף הוראות מספר ידוע מראש של פעמים.
תכנות:
(וקטור המכיל את ערכי i הדרושים)=for i
(הוראות לביצוע)
end
הערה: אמנם i הוא קבוע, אך ניתן להציב בו ערך. על מנת להחזירו להיות ה־i המרוכב, נכתוב את ההוראה clear i.
לולאת while
לולאת while - ביצוע אותו רצף הוראות מספר שאינו ידוע מראש של פעמים אך עם תנאי לעצירה.
תכנות:
(תנאי לעצירה, תנאי בוליאני) while
(הוראות לביצוע)
end
תרגילים
תרגיל 1 - עצרת
חשבו את [math]\displaystyle{ 1000! }[/math].
פתרון 1 - לולאת for:
;n=1 for i=2:1000 ;n=n*i end ;(disp(n
פתרון 2 - לולאת while:
;n=1 ;i=1 while i<=1000 ;n=n*i ;i=i+1 end ;(disp(n
תרגיל 2 - מספרים ראשוניים
צרו וקטור המכיל את כל המספרים הראשוניים מ־1 עד 1000
;כמה ראשוניים מצאנו % 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
תרגיל 3 - פירוק מספר שלם לגורמים ראשוניים
פרקו מספר שלם [math]\displaystyle{ k\leq 1000 }[/math] לגורמים ראשוניים (אפשר להשתמש בוקטור primes מהתרגיל הקודם).
;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
יישומים מתמטיים
מחלק משותף גדול ביותר gcd
עבור [math]\displaystyle{ m,n }[/math] שלמים, המספר השלם הגדול ביותר המחלק גם את [math]\displaystyle{ m }[/math] וגם את [math]\displaystyle{ n }[/math] ייקרא המחלק המשותף הגדול ביותר ויסומן [math]\displaystyle{ gcd(m,n) }[/math].
;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
קבלת מינימום
ישנן שלוש דרכים לקבל את המספר המינימלי מבין [math]\displaystyle{ m,n }[/math].
דרך ראשונה - ([min([m,n
דרך שנייה - תנאי
דרך שלישית - [math]\displaystyle{ min=\frac{m+n}{2}-\frac{m-n}{2} }[/math]
אלגוריתם אוקלידס
אלגוריתם אוקלידס נועד למציאת מחלק משותף מקסימלי בין שני מספרים שלמים [math]\displaystyle{ m,n }[/math].
האלגוריתם
נניח [math]\displaystyle{ m\lt n }[/math]. נגדיר:
[math]\displaystyle{ r_0=n }[/math]
[math]\displaystyle{ r_1=m }[/math]
[math]\displaystyle{ r_0=q_1 r_1+r_2 }[/math] כאשר [math]\displaystyle{ 1\leq q_1 \leq r_0 }[/math], [math]\displaystyle{ 0\leq r_2 \lt r_1 }[/math]
ובאינדוקציה [math]\displaystyle{ r_k=q_{k+1} r_{k+1}+r_{k+2} }[/math]
עד שנגיע ל־[math]\displaystyle{ r_N=0 }[/math].
בהכרח נעצור כי [math]\displaystyle{ r_{k+1}\lt r_k }[/math].
לפי אלגוריתם זה, ה־gcd הינו [math]\displaystyle{ r_{N-1} }[/math].
דוגמה
נבחר [math]\displaystyle{ r_0=30, r_1=12 }[/math].
[math]\displaystyle{ 30=2\cdot 12+\underset{r_2}{\underbrace{6}} }[/math]
[math]\displaystyle{ 12=2\cdot 6+\underset{r_3}{\underbrace{0}} }[/math]
ולכן [math]\displaystyle{ gcd(30,12)=6 }[/math]
הוכחת האלגוריתם
[math]\displaystyle{ r_{N-2}=q_{N-1} r_{N-1}+r_N=q_{N-1} r_{N-1} }[/math] [math]\displaystyle{ \Leftarrow }[/math] [math]\displaystyle{ r_{N-1}|r_{N-2} }[/math].
[math]\displaystyle{ r_{N-3}=q_{N-2} r_{N-2}+r_{N-1} }[/math].
[math]\displaystyle{ r_{N-1}|r_{N-2} }[/math] וגם [math]\displaystyle{ r_{N-1}|r_{N-1} }[/math] [math]\displaystyle{ \Leftarrow }[/math][math]\displaystyle{ r_{N-1}|r_{N-3} }[/math]
[math]\displaystyle{ r_{N-4}=q_{N-3} r_{N-3}+r_{N-2} }[/math].
[math]\displaystyle{ r_{N-1}|r_{N-2} }[/math] וגם [math]\displaystyle{ r_{N-1}|r_{N-3} }[/math] [math]\displaystyle{ \Leftarrow }[/math][math]\displaystyle{ r_{N-1}|r_{N-4} }[/math]
<BR
באינדוקציה, נקבל [math]\displaystyle{ r_{N-1}|r_1 }[/math] וגם [math]\displaystyle{ r_{N-1}|r_0 }[/math].
מדוע [math]\displaystyle{ r_{N-1} }[/math] הוא המחלק המשותף הגדול ביותר? נניח [math]\displaystyle{ r_k=gcd(m,n) }[/math], אזי [math]\displaystyle{ r_{k-1}=q_{k} r_{k}+0 }[/math].
בהכרח נגיע למחלק המשותף המקסימלי מפני שבשלב ה־k־י, [math]\displaystyle{ r_{k-1}|gcd(m,n) }[/math] וגם [math]\displaystyle{ r_k|gcd(m,n) }[/math], לכן [math]\displaystyle{ r_{k+1}|gcd(m,n) }[/math].
תכנות
;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
דוגמה
עבור [math]\displaystyle{ m=169, n=1482 }[/math]
| [math]\displaystyle{ r_2 }[/math] | [math]\displaystyle{ r_1 }[/math] | [math]\displaystyle{ r_0 }[/math] |
|---|---|---|
| 169 | 1482 | |
| 130 | 130 | 169 |
| 39 | 39 | 130 |
| 13 | 13 | 39 |
| 0 | 0 | 13 |
gcd(169,1482)=13
עבור [math]\displaystyle{ m=441, n=42 }[/math]
| [math]\displaystyle{ r_2 }[/math] | [math]\displaystyle{ r_1 }[/math] | [math]\displaystyle{ r_0 }[/math] |
|---|---|---|
| 42 | 441 | |
| 21 | 21 | 42 |
| 0 | 0 | 21 |
gcd(42,441)=21
פתרון מערכת משוואות - ניוטון-רפסון
תהי [math]\displaystyle{ f(x) }[/math] פונקציה, צריך למצוא [math]\displaystyle{ x }[/math] כך ש־[math]\displaystyle{ f(x)=0 }[/math].
האלגוריתם והוכחתו
נתחיל מנקודה כלשהי, ובכל פעם נעביר דרכה משיק ונקבל נקודה חדשה - ששיעור ה־x שלה זהה לשיעור ה־x של החיתוך עם ציר x של המשיק. המחשת האלגוריתם
נתון [math]\displaystyle{ x_0 }[/math]. נחשב את משוואת הישר [math]\displaystyle{ y=ax+b }[/math], [math]\displaystyle{ a=f'(x_0) }[/math], עובר בנקודה [math]\displaystyle{ (x_0,f(x_0)) }[/math] (משוואת המשיק):
[math]\displaystyle{ f(x_0)=f'(x_0)x_0+b }[/math] [math]\displaystyle{ \Leftarrow }[/math] [math]\displaystyle{ b=f(x_0)-x_0 f'(x_0) }[/math]
כלומר, הישר המשיק ל־[math]\displaystyle{ f(x) }[/math] הינו [math]\displaystyle{ y=f'(x_0)x+f(x_0)-x_0 f(x_0) }[/math]. נמצא את [math]\displaystyle{ x_1 }[/math]. חיתוך עם ציר [math]\displaystyle{ x }[/math]:
[math]\displaystyle{ 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]\displaystyle{ x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)} }[/math]. נמשיך באיטרציות עד ש־[math]\displaystyle{ |x_k-x_{k-1}|\lt \Delta=10^{-12} }[/math]
טענה: [math]\displaystyle{ |x_{k+1}-\tilde{x}|\leq c|x_k-\tilde{x}|^2 }[/math] עבור [math]\displaystyle{ c\ge 0 }[/math], כאשר [math]\displaystyle{ \tilde{x} }[/math] הינו השורש האמיתי.
תכנות
נתונה פונקציה f ופונקציה 'g=f. השגיאה הרצויה delta.
;x0=1 ;x1=x0+2*delta while abs(x0-x1)>delta ;(x1=x0-f(x0)/g(x0 ;t=x1 ;x1=x0 ;x0=t end
פונקציות
פונקציה הינה רצף הוראות שנועד להתבצע עם נתונים מסוימים. למשל, פונקציה יכולה לקבל מספר ולהדפיס האם הוא ראשוני. פונקציה יכולה להחזיר ערך (או מערך עם כמה ערכים) או לא להחזיר ערך.
תכנות ב־MATLAB:
(קלט) שם הפונקציה = [פלט] function (הוראות לביצוע) end
תרגילים
תרגיל 1 - האם ראשוני
כתבו פונקציה שתקבל מספר טבעי [math]\displaystyle{ p }[/math]. הפונקציה תחזיר 1 אם הוא ראשוני ו־0 אחרת.
(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
בהסתמך על הפונקציה הנ"ל, כתבו תוכנית שתיצור וקטור של המספרים הראשוניים עד למספר טבעי נתון [math]\displaystyle{ n }[/math].
;[]=primes
;0=found
for k=1:n
1==(if isprime(k
;found=found+1
;primes(found)=k
end
end
תרגיל 2 - האם וקטור הוא פרמוטציה (תמורה)
כתבו פונקציה המקבלת וקטור ובודקת אם הוא פרמוטציה של [math]\displaystyle{ 1,...,n }[/math].
(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
מבני נתונים
המטרה: לכתוב פונקציות להוספה, למחיקה, לחיפוש ולמיון במערך. נחלק את הפעולות לשני מקרים: המערך אינו ממוין והמערך ממוין.
מערך שאינו ממוין
נגדיר איזשהו מערך:
;[v=[79,100,31,5,84
ונבצע עליו את הפעולות הבאות:
הוספה
(function [u] = add2array (v,k הפונקציה מוסיפה איבר k למערך v ומחזירה u % ;u=v ;u(end+1)=k end
מחיקה
אפשרות 1:
(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
אפשרות 2:
(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
חיפוש
(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
מערך ממוין
כעת נניח שיש לנו מערך ממוין v, למשל מהקטן לגדול.
מחיקה
בדיוק כמו במערך שאינו ממוין.
חיפוש
ישנן שתי שיטות חיפוש: חיפוש בינארי ואריה במדבר.
חיפוש בינארי:
(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
מספר הפעולות בחיפוש בינארי: [math]\displaystyle{ \log_2 n }[/math]
הוספה
אם x קטן מ־(v(1, נכניס אותו בהתחלה. אחרת נחפש את x ונכניס אותו אחרי L.
מיון פשוט
ראשית, נכתוב פונקציית עזר:
(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
כעת, נכתוב את התוכנית למיון:
for i=1:n-1 ;(m,p]=findSmallest(v,i] ;(v(p)=v(i ;v(i)=m end
יעילות
אם אנו חושדים שזמן הריצה [math]\displaystyle{ t }[/math] כתלות ב־[math]\displaystyle{ n }[/math] פרופורציוני ל־[math]\displaystyle{ n^r }[/math]:
[math]\displaystyle{ t\propto n^r }[/math]
[math]\displaystyle{ \Downarrow }[/math]
[math]\displaystyle{ t=cn^r }[/math]
[math]\displaystyle{ \ln t=\ln c+r\ln n }[/math]
לכן [math]\displaystyle{ \ln t }[/math] כתלות ב־[math]\displaystyle{ \ln n }[/math] הינו קו ישר ששיפועו [math]\displaystyle{ r }[/math], וכך ניתן למצוא את [math]\displaystyle{ \ln c }[/math] כחיתוך עם ציר y.
מספר הגדרות ודוגמות
[math]\displaystyle{ f\left ( n \right )=\Theta\left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \forall n, A\cdot g\left ( n \right )\leq f\left ( n \right )\leq B\cdot g\left ( n \right ) }[/math].
[math]\displaystyle{ f\left ( n \right )=O \left ( g\left ( n \right ) \right ) }[/math] אם [math]\displaystyle{ \forall n, f\left ( n \right )\leq B\cdot g\left ( n \right ) }[/math].