תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר

חזרה לדף המשתמש

תאריך עדכון אחרון: 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