מצגת ההרצאה

Report
‫הוראת אינדוקציה ורקורסיה‬
‫במדעי המחשב‬
‫הסמינר המיוחד למורי תיכון מובילים במדעי המחשב‬
‫טכניון‪ ,‬חיפה‪ ,‬יולי ‪2012‬‬
‫ראובן בר‪-‬יהודה‬
‫איך מפולת של אבני דומינו קשור לתכנון לולאות?‬
‫‪2‬‬
‫תשובה‪ :‬אינדוקציה‬
‫תנאים מספיקים לנפילת שורת אבני הדומינו‪:‬‬
‫)‪OK(1‬‬
‫בסיס‪ :‬הראשון נופל‪.‬‬
‫צעד‪ :‬אם מישהו נופל‪ ,‬אז זה שאחריו נופל )‪OK(n-1) OK(n‬‬
‫‪...‬‬
‫)‪OK(n-1) OK(n‬‬
‫‪3‬‬
‫)‪OK(1‬‬
‫תכונות אחרות‪...‬‬
‫תנאים מספיקים לחולי של שורת עכברים‪:‬‬
‫בסיס‪ :‬הראשון חולה‪.‬‬
‫צעד‪ :‬אם מישהו חולה‪ ,‬אז זה שאחריו חולה‬
‫)‪Sick(1‬‬
‫)‪Sick(n-1)Sick(n‬‬
‫‪...‬‬
‫)‪Sick(n-1)Sick(n‬‬
‫‪4‬‬
‫)‪Sick(1‬‬
‫צעדים אחרים‬
‫מה לגבי צעדי אינדוקציה אחרים‪ ,‬למשל‪:‬‬
‫צעד‪ :‬המחלה מדבקת בקפיצות של שתיים‬
‫בסיס‪ :‬הראשון חולה‪.‬‬
‫)‪Sick(n-2)Sick(n‬‬
‫)‪Sick(1), Sick(2‬‬
‫‪...‬‬
‫)‪Sick(n‬‬
‫‪5‬‬
‫)‪Sick(n-2‬‬
‫)‪Sick(2‬‬
‫)‪Sick(1‬‬
‫אינדוקציה שלמה‬
‫תנאים מספיקים לנפילת שורת אבני הדומינו‪:‬‬
‫אם כל אלו שלפני נופלים‬
‫) ‪ OK ( n‬‬
‫אז גם אני נופל‬
‫) ‪ i  n OK ( i‬‬
‫‪... ...‬‬
‫) ‪O K ( n  1) O K ( n‬‬
‫‪6‬‬
‫) ‪O K (i‬‬
‫)‪O K (1‬‬
‫אינדוקציה שלמה‪ :‬דוגמא‬
‫טענה‪ :‬דרושים בדיוק ‪ n-1‬חיתוכים כדי להגיע ל‪ n-‬קוביות שוקולד‪.‬‬
‫הוכחה‪ :‬בסיס‪ 0  n = 1 :‬חיתוכים‬
‫צעד‪ :‬נחתוך שרירותית לחלקים לא ריקים‪n = i + j :‬‬
‫‪ i - 1‬חיתוכים ‪i < n ‬‬
‫‪1‬‬
‫חיתוכים‬
‫‪ j - 1‬חיתוכים ‪j < n ‬‬
‫‪i-1 + j-1 + 1 = n - 1‬‬
‫‪7‬‬
‫אינדוקציה לא קווית‬
‫‪DOMINOS‬‬
‫דוגמאות על הלוח‪...‬‬
‫‪8‬‬
‫תכנון לולאות עם מחשבה באינדוקציה‬
‫כתוב פונקציה שמחשבת סכום מערך חד מימדי (ללא שימוש ב ‪) sum‬‬
‫)‪1. function y = my_sum(x‬‬
‫‪2.‬‬
‫;‪y = 0‬‬
‫)‪% OK(0‬‬
‫‪3.‬‬
‫)‪for n = 1:length(x‬‬
‫)‪% OK(n-1‬‬
‫‪4.‬‬
‫;)‪y = y + x(n‬‬
‫)‪% OK(n‬‬
‫‪5.‬‬
‫‪end‬‬
‫טענת האינדוקציה‪.‬‬
‫לאחר ‪ n‬איטרציות‪y = x(1)+x(2)+…+x(n) :‬‬
‫הוכחה באינדוקציה על ‪.n‬‬
‫בסיס‪ n = 0 :‬לאחר ‪ 0‬איטרציות מכיל את ערך האתחול שהוא ‪.0‬‬
‫צעד‪ :‬נניח שלאחר ‪ n-1‬איטרציות )‪y = x(1)+x(2)+…+x(n-1‬‬
‫באיטרציה ה ‪ n‬מוסיפים ל ‪ y‬את )‪ x(n‬וסיימנו‪.‬‬
‫‪9‬‬
‫תכנון לולאות עם מחשבה באינדוקציה‬
‫כתוב פונקציה שמחשבת מכפלת מערך חד מימדי (ללא שימוש ב ‪) prod‬‬
‫)‪1. function y = my_prod(x‬‬
‫‪2.‬‬
‫;‪y = 1‬‬
‫)‪% OK(0‬‬
‫‪3.‬‬
‫)‪for n = 1:length(x‬‬
‫)‪% OK(n-1‬‬
‫‪4.‬‬
‫;)‪y = y * x(n‬‬
‫)‪% OK(n‬‬
‫‪5.‬‬
‫‪end‬‬
‫טענת האינדוקציה‪.‬‬
‫לאחר ‪ n‬איטרציות‪y = x(1)*x(2)*…*x(n) :‬‬
‫הוכחה באינדוקציה על ‪.n‬‬
‫בסיס‪ n = 0 :‬לאחר ‪ 0‬איטרציות מכיל את ערך האתחול שהוא ‪.1‬‬
‫צעד‪ :‬נניח שלאחר ‪ n-1‬איטרציות )‪y = x(1)*x(2)*…*x(n-1‬‬
‫באיטרציה ה ‪ n‬מכפילים את ‪ y‬ב )‪ x(n‬וסיימנו‪.‬‬
‫‪10‬‬
‫תכנון לולאות עם מחשבה באינדוקציה‬
‫כתוב פונקציה שמחשבת ‪ OR‬של מערך חד מימדי (ללא שימוש ב ‪) any‬‬
‫)‪1. function y = my_any(x‬‬
‫‪2.‬‬
‫;‪y = false‬‬
‫)‪% OK(0‬‬
‫‪3.‬‬
‫)‪for n = 1:length(x‬‬
‫)‪% OK(n-1‬‬
‫‪4.‬‬
‫;)‪y = y || x(n‬‬
‫)‪% OK(n‬‬
‫‪5.‬‬
‫‪end‬‬
‫טענת האינדוקציה‪.‬‬
‫לאחר ‪ n‬איטרציות‪y = x(1)x(2)…x(n) :‬‬
‫הוכחה באינדוקציה על ‪.n‬‬
‫בסיס‪ n = 0 :‬לאחר ‪ 0‬איטרציות מכיל את ערך האתחול שהוא ‪.false‬‬
‫צעד‪ :‬נניח שלאחר ‪ n-1‬איטרציות )‪y = x(1)x(2)…x(n-1‬‬
‫באיטרציה ה ‪" n‬מוסיפים" ל ‪ y‬את )‪ x(n‬וסיימנו‪.‬‬
‫‪11‬‬
‫‪if y‬‬
‫‪return‬‬
‫‪end‬‬
‫תכנון לולאות עם מחשבה באינדוקציה‬
‫כתוב פונקציה שמחשבת ‪ AND‬של מערך חד מימדי (ללא שימוש ב ‪) all‬‬
‫)‪% OK(0‬‬
‫)‪% OK(n-1‬‬
‫)‪% OK(n‬‬
‫)‪1. function y = my_all(x‬‬
‫‪2.‬‬
‫;‪y = true‬‬
‫‪3.‬‬
‫)‪for n = 1:length(x‬‬
‫‪4.‬‬
‫;)‪y = y && x(n‬‬
‫‪5.‬‬
‫‪end‬‬
‫טענת האינדוקציה‪.‬‬
‫לאחר ‪ n‬איטרציות‪y = x(1)x(2)…x(n) :‬‬
‫הוכחה באינדוקציה על ‪.n‬‬
‫בסיס‪ n = 0 :‬לאחר ‪ 0‬איטרציות מכיל את ערך האתחול שהוא ‪.true‬‬
‫צעד‪ :‬נניח שלאחר ‪ n-1‬איטרציות )‪y = x(1)x(2)…x(n-1‬‬
‫באיטרציה ה ‪" n‬מכפילים" את ‪ y‬ב )‪ x(n‬וסיימנו‪.‬‬
‫‪12‬‬
‫‪if ~y‬‬
‫‪return‬‬
‫‪end‬‬
‫תכנון לולאות עם מחשבה באינדוקציה‬
‫כתוב פונקציה שמחשבת מקסימום של מערך חד מימדי (ללא שימוש ב‪)max‬‬
‫)‪1. function y = my_max(x‬‬
‫;‪y = - ‬‬
‫)‪% OK(0‬‬
‫)‪for n = 1:length(x‬‬
‫)‪% OK(n-1‬‬
‫)‪if x(n) > y y = x(n); end % OK(n‬‬
‫‪end‬‬
‫טענת האינדוקציה‪.‬‬
‫לאחר ‪ n‬איטרציות‪y = MAX{x(1),x(2),…,x(n)} :‬‬
‫הוכחה באינדוקציה על ‪.n‬‬
‫בסיס‪ n = 0 :‬לאחר ‪ 0‬איטרציות מכיל את ערך האתחול שהוא ‪.-‬‬
‫צעד‪ :‬נניח שלאחר ‪ n-1‬איטרציות })‪y = MAX{x(1),x(2),…,x(n-1‬‬
‫באיטרציה ה ‪" n‬מחליפים‪ ,‬אם גדול יותר" את ‪ y‬ב )‪ x(n‬וסיימנו‪.‬‬
‫‪13‬‬
‫‪2.‬‬
‫‪3.‬‬
‫‪4.‬‬
‫‪5.‬‬
‫תכנון לולאות עם מחשבה באינדוקציה‬
‫כתוב פונקציה שמחשבת מינימום של מערך חד מימדי (ללא שימוש ב ‪) min‬‬
‫)‪1. function y = my_min(x‬‬
‫;‪y = + ‬‬
‫)‪% OK(0‬‬
‫)‪for n = 1:length(x‬‬
‫)‪% OK(n-1‬‬
‫)‪if x(n) < y y = x(n); end % OK(n‬‬
‫‪end‬‬
‫טענת האינדוקציה‪.‬‬
‫לאחר ‪ n‬איטרציות‪y = MIN{x(1),x(2),…,x(n)} :‬‬
‫הוכחה באינדוקציה על ‪.n‬‬
‫בסיס‪ n = 0 :‬לאחר ‪ 0‬איטרציות מכיל את ערך האתחול שהוא ‪.-‬‬
‫צעד‪ :‬נניח שלאחר ‪ n-1‬איטרציות })‪y = MIN{x(1),x(2),…,x(n-1‬‬
‫באיטרציה ה ‪" n‬מחליפים‪ ,‬אם קטן יותר" את ‪ y‬ב )‪ x(n‬וסיימנו‪.‬‬
‫‪14‬‬
‫‪2.‬‬
‫‪3.‬‬
‫‪4.‬‬
‫‪5.‬‬
Sorting
1
77
1
5
2
42
2
12
3
4
5
6
35
12
101
3
4
5
6
35
42
77
101
5
sort-by_max.m
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
function a = sort_by_max( a )
% sort members of array in non decreasing order
for top = length(a):-1:1 % at this point all members above index “top” are in their proper location
i = index_of_max(a,top);
temp = a(i); a(i) = a(top); a(top) = temp; %swap a(i) with a(top)
end
end
function i_max = index_of_max( a, n )
% find the index of the maximum member among a(1:n)
i_max = 1;
for i = 2:n % invariant: at this point a(i_max) = MAXIMUM{a(1), a(2(…a)i-1)}
if a(i) > a(i_max)
i_max = i;
end
end
end
16
‫חיפוש במערכים ממוינים‬
‫‪17‬‬
‫חיפוש בינארי‬
1. function m = bin_search (x, a)
2.
% a is a non decreasing sorted array
3.
% find x in a and return in m its index.
4.
% if x is not there, m = -1
5.
b = 1; t = length(a);
6.
while b <= t
7.
m = floor((b+t)/2);
8.
if a(m) == x
9.
return
10.
elseif a(m) > x
11.
t = m-1;
12.
else
13.
b = m+1;
14.
end
15.
end
16.
m = -1;
18
‫חיפוש בינארי‪ :‬נכונות‬
‫‪t‬‬
‫‪b‬‬
‫שמורות בכל איטרציה‬
‫)‪1. function m = bin_search (x, a‬‬
‫‪ x‬לא נמצא ב )‪a(1 : b-1‬‬
‫‪2.‬‬
‫;)‪b = 1; t = length(a‬‬
‫‪ x‬לא נמצא ב )‪a(t+1: end‬‬
‫הוכחה‪ :‬באינדוקציה על מספר האיטרציות‪:‬‬
‫‪3.‬‬
‫‪while b <= t‬‬
‫בסיס‪ 0 :‬איטרציות‪ -‬נכונות באופן ריק‪.‬‬
‫‪4.‬‬
‫;)‪m = floor((b+t)/2‬‬
‫צעד‪:‬‬
‫‪5.‬‬
‫‪if a(m) == x‬‬
‫אם ‪a(m) > x‬‬
‫‪6.‬‬
‫‪return‬‬
‫אז כל האיברים ב )‪a(m:end‬‬
‫‪7.‬‬
‫‪elseif a(m) > x‬‬
‫גדולים ממש מ‪ x-‬ולכן הוא לא שם‪,‬‬
‫אם ‪a(m) < x‬‬
‫‪8.‬‬
‫;‪t = m-1‬‬
‫אז כל האיברים ב )‪a(1:m‬‬
‫‪9.‬‬
‫‪else‬‬
‫קטנים ממש מ‪ x-‬ולכן הוא לא שם‪.‬‬
‫‪10.‬‬
‫;‪b = m+1‬‬
‫‪11.‬‬
‫‪end‬‬
‫בסיום‪ :‬אם ‪ x‬לא נמצא (שורה ‪)5‬‬
‫‪12.‬‬
‫‪end‬‬
‫אז נגיע לשורה ‪ 13‬בה מתקיים ‪b>t‬‬
‫ומכאן נובע שהאיחוד של‬
‫‪13.‬‬
‫;‪m = -1‬‬
‫)‪ a(t+1: end‬ו )‪a(1 : b-1‬‬
‫מכיל את כל איברי ‪ a‬ולכן‪ ,‬לפי השמורות‪ x ,‬לא נמצא ב‪a-‬‬
‫‪19‬‬
‫חיפוש בינארי‪ :‬סיבוכיות זמן ))‪O(log(n‬‬
‫)‪1. function m = bin_search (x, a‬‬
‫‪2.‬‬
‫;)‪b = 1; t = length(a‬‬
‫‪3.‬‬
‫‪while b <= t‬‬
‫בכל איטרציה האינטרוואל ‪ b:t‬נחצה ב‪.2-‬‬
‫‪4.‬‬
‫;)‪m = floor((b+t)/2‬‬
‫אם אורכו בהתחלה היה ‪n‬‬
‫‪5.‬‬
‫‪if a(m) == x‬‬
‫אז לאחר איטרציה אחת הוא יהיה בערך ‪n/2‬‬
‫‪6.‬‬
‫‪return‬‬
‫לאחר עוד איטרציה הוא יהיה בערך ‪n/4‬‬
‫לאחר עוד איטרציה הוא יהיה בערך ‪n/8‬‬
‫‪7.‬‬
‫‪elseif a(m) > x‬‬
‫ולכן לאחר ‪ k‬איטרציות הוא יקטן ל ‪n/2k‬‬
‫‪8.‬‬
‫;‪t = m-1‬‬
‫‪9.‬‬
‫‪else‬‬
‫ש‪ :‬עבור איזה ‪ k‬הביטוי הנ"ל יהיה קטן מדי?‬
‫‪10.‬‬
‫;‪b = m+1‬‬
‫ת‪ :‬נפתור את אי השוויון‪1 > n/2k :‬‬
‫‪11.‬‬
‫‪end‬‬
‫או‪2k > n :‬‬
‫‪12.‬‬
‫‪end‬‬
‫וזה יקרה כאשר )‪k = log2(n‬‬
‫‪13.‬‬
‫;‪m = -1‬‬
‫מכאן מספר האיטרציות‬
‫(ולכן סיבוכיות הזמן) הוא ()‪O(log (n‬‬
‫‪20‬‬
‫מיזוג מערכים ממוינים‪:‬‬
‫‪21‬‬
Merging two sorted arrays (Silvio Micali MIT)
20 12
13 11
7
9
2
1
…
output array
Merging two sorted arrays (Silvio Micali MIT)
20 12
13 11
7
9
2
1
…
1
output array
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
13 11
13 11
7
9
7
2
1
2
9
…
1
output array
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
13 11
13 11
7
9
7
2
1
2
1
9
…
2
output array
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
13 11
13 11
13 11
7
9
7
7
2
1
2
1
9
9
…
2
output array
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
13 11
13 11
13 11
7
9
7
7
2
1
2
1
9
2
9
7
output array
…
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
20 12
13 11
13 11
13 11
13 11
7
9
7
7
2
1
2
1
9
2
9
7
output array
9
…
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
20 12
13 11
13 11
13 11
13 11
7
9
7
7
2
1
2
1
9
2
9
7
output array
9
9
…
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
20 12
20 12
13 11
13 11
13 11
13 11
13 11
7
9
7
7
2
1
2
1
9
2
9
7
output array
9
9
…
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
20 12
20 12
13 11
13 11
13 11
13 11
13 11
7
9
7
7
2
1
2
1
9
2
9
7
output array
9
9
11
…
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
20 12
20 12
20 12
13 11
13 11
13 11
13 11
13 11
13
7
9
7
7
2
1
2
1
9
2
9
7
output array
9
9
11
…
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
20 12
20 12
20 12
13 11
13 11
13 11
13 11
13 11
13
7
9
7
7
2
1
2
1
9
2
9
7
output array
9
9
11
12
…
Merging two sorted arrays (Silvio Micali MIT)
20 12
20 12
20 12
20 12
20 12
20 12
13 11
13 11
13 11
13 11
13 11
13
7
9
7
7
2
1
2
1
9
2
9
7
9
9
output array
Time = Q(n) to merge a total of n elements
(linear time).
11
12
…
1. function c = merge(a,b)
2.
% given non decreasing sorted arrays a,b
3.
% return in c the sorted merge of a and b
4.
n_a = length(a); n_b = length(b);
5.
n_c = n_a + n_b; c = zeros(1,n_c);
6.
i_a = 1; i_b = 1;
7.
for i_c = 1 : n_c;
8.
if i_b > n_b
9.
c(i_c) = a(i_a);
10.
i_a = i_a +1;
11.
elseif i_a > n_a
12.
c(i_c) = b(i_b);
13.
i_b = i_b +1;
14.
elseif a(i_a) < b(i_b)
15.
c(i_c) = a(i_a);
16.
i_a = i_a +1;
17.
else % a(i_a) >= b(i_b)
18.
c(i_c) = b(i_b);
19.
i_b = i_b +1;
20.
end
21.
end
‫מיזוג‬
35
‫‪a(1:i_a)-1‬‬
‫נכונות‬
‫‪n_a‬‬
‫‪i_a‬‬
‫… ‪1 2 3‬‬
‫שמורות‪:‬‬
‫)‪ c(1:i_c-1‬ממויין‬
‫)‪ c(1:i_c-1‬מכיל את איברי )‪b(1:i_b-1) a(1:i_a-1‬‬
‫כל האיברים ב )‪ c(1:i_c-1‬קטנים או שווים לכל האיברים ב )‪a(i_a,end‬‬
‫כל האיברים ב )‪ c(1:i_c-1‬קטנים או שווים לכל האיברים ב )‪b(i_b,end‬‬
‫באינדוקציה על מספר האיטרציות‬
‫בסיס‪ :‬נכון באופן ריק‬
‫צעד‪.. :‬‬
‫‪36‬‬
1. function c = merge(a,b)
2.
% time complexity
3.
% is O(length(a)+length(b))
4.
n_a = length(a); n_b = length(b);
5.
n_c = n_a + n_b; c = zeros(1,n_c);
?‫קבוע‬
6.
i_a = 1; i_b = 1;
7.
for i_c = 1 : n_c;
 ‫ פעמים‬n_a + n_b
8.
if i_b > n_b
9.
c(i_c) = a(i_a);
10.
i_a = i_a +1;
11.
elseif i_a > n_a
12.
c(i_c) = b(i_b);
13.
i_b = i_b +1;
!‫קבוע‬
14.
elseif a(i_a) < b(i_b)
15.
c(i_c) = a(i_a);
16.
i_a = i_a +1;
17.
else % a(i_a) >= b(i_b)
18.
c(i_c) = b(i_b);
19.
i_b = i_b +1;
20.
end
21.
end
‫סיבוכיות לינארית‬
37
‫רקורסיה‬
‫רקורסיה‬
‫הגדרה רקורסיבית (מתוך ‪)WIKI‬‬
‫• הגדרה היא הגדרה רקורסיבית אם היא מסתמכת על עצמה‪ .‬דוגמאות‪:‬‬
‫• לפי ההלכה היהודית‪" :‬אדם יהודי הוא מי שנולד לאם יהודייה"‪.‬‬
‫משמעות ההגדרה הרקורסיבית הינה שעל מנת לדעת אם אדם פלוני‪,‬‬
‫משה‪ ,‬הוא יהודי יש לדעת אם ִאמו‪ ,‬דבורה‪ ,‬היא יהודייה‪ .‬אך בהתאם‬
‫להגדרה‪ ,‬דבורה יהודייה אם ִאמה‪ ,‬רות‪ ,‬היא יהודייה‪ .‬כדי לבדוק אם‬
‫רות היא יהודייה צריך להשתמש שוב בהגדרה הרקורסיבית‪ ,‬וכך‬
‫הלאה‪ .‬תנאי עצירה יהיה בתחילת קיומו של עמ"י‪.‬‬
‫• הגדרה מילונית־הומוריסטית לערך "רקורסיה"‪" :‬ראו ערך רקורסיה"‪.‬‬
‫‪39‬‬
‫אינדוקציה‬
‫בסיס‪ :‬הראשון נופל‪.‬‬
‫צעד‪ :‬אם מישהו נופל‪ ,‬אז זה שאחריו נופל‬
‫)‪OK(1‬‬
‫)‪OK(n-1) OK(n‬‬
‫‪...‬‬
‫)‪OK(n-1) OK(n‬‬
‫‪40‬‬
‫)‪OK(1‬‬
‫רקורסיה‬
‫דומינו ‪n‬מבקש מדומינו ‪ n-1‬ליפול‬
‫דומינו ‪n-1‬מבקש מדומינו ‪ n-2‬ליפול‬
‫‪...‬‬
‫דומינו ‪2‬מבקש מדומינו ‪ 1‬ליפול‬
‫‪ 1‬נופל ורק אז מפולת הדומינו מתחילה‬
‫האם את‬
‫יהודיה?‬
‫משה‬
‫דבורה‬
‫‪...‬‬
‫רות‬
‫‪41‬‬
‫האם את‬
‫יהודיה?‬
‫האם את‬
‫יהודיה?‬
‫האם את‬
‫יהודיה?‬
‫האם את‬
‫יהודיה?‬
‫שימו לב שיש עץ של דומינו שהרקורסיה הנ"ל‬
‫חשפה בו רק את השרשרת הרלוונטית‪.‬‬
‫משה‬
‫דבורה‬
‫רות‬
‫‪42‬‬
‫שרה‬
‫דוגמאות להגדרות ע"י נוסחת נסיגה‬
‫הסדרה‬
‫נוסחה "סגורה"‬
‫נוסחת נסיגה‬
‫)‪an=f(an-1,.., an-k‬‬
‫)>‪an=f(n,<parameters‬‬
‫סדרה חשבונית‪:‬‬
‫… ‪3, 13, 23, 33,‬‬
‫‪a1‬‬
‫‪an = an-1 + d‬‬
‫‪an = a1 + (n-1(∙d‬‬
‫סדרה הנדסית‬
‫… ‪7, 14, 28, 56,‬‬
‫‪a1‬‬
‫‪an = q∙an-1‬‬
‫‪an=a1∙qn-1‬‬
‫עצרת‬
‫‪ a1 = 1‬אין נוסחה סגורה "יפה"‬
‫‪an = n∙an-1‬‬
‫… ‪1, 2, 6, 24, 120,‬‬
‫פיבונאצ'י‬
‫… ‪1, 1, 2, 3, 5, 8, 13,‬‬
‫‪43‬‬
‫‪a1 = a 2 = 1‬‬
‫‪an = an-1 + an-2‬‬
‫‪an = (φn - (1 - φ)n) / 5‬‬
‫כאשר ‪φ = (1+5) / 2 ~= 1.6180‬‬
‫(המספר ‪ φ‬נקרא "יחס הזהב")‬
function f=myfactr(n)
‫בסיס הרקורסיה‬
if n==1, f=1;
else f=n*myfactr(n-1);
end
‫רקורסיה בחישוב עצרת‬
‫קריאה רקורסיבית‬
:myfactr(5) ‫• נעקב אחרי הביצוע של‬
myfactr(5) n = 5
f= 5 * myfactr(4) n = 4
f= 4 * myfactr(3) n = 3
f= 3 * myfactr(2) n = 2
f= 2 * myfactr(1) n = 1
f= 1
44
‫רקורסיה בחישוב עצרת‬
.‫ "קפול" הרקורסיה‬:‫• המשך ביצוע‬
n=5
myfactr(5)
120
n=4
24
f= 5 * myfactr(4)
6
n=3
f= 4 * myfactr(3)
n=2
2
f= 3 * myfactr(2)
1
n=1
f= 2 * myfactr(1)
f= 1
45
‫הוכחת נכונות של הפונקציה ‪myfactr‬‬
‫• טענה‪ :‬לכל מספר טבעי ‪ ,n‬הפונקציה ‪ myfactr‬עם קלט ‪n‬‬
‫עוצרת כאשר הערך של המשתנה ‪ f‬הוא !‪.n‬‬
‫)‪function f=myfactr(n‬‬
‫;‪if n<2, f=1‬‬
‫;)‪else f=n*myfactr(n-1‬‬
‫‪end‬‬
‫• הוכחת נכונות ע"י אינדוקציה על הקלט ‪:n‬‬
‫– בסיס‪ :‬עבור ‪ ,n<2‬בדיקה ישירה מראה כי )‪ myfactr(1‬תחזיר ‪.1‬‬
‫– צעד‪ :‬נניח כי !)‪ . myfactr(n-1) = (n-1‬אזי‪:‬‬
‫!‪myfactr(n) = n∙myfactr(n-1( = n∙)n-1)! = n‬‬
‫הנחת האינדוקציה‬
‫‪46‬‬
‫‪Recursive Mona Liza‬‬
‫צייר_מונה(מיקום‪ ,‬גודל)‬
‫‪ .1‬צייר_מלבן(מיקום‪ ,‬גודל)‬
‫‪ .2‬אם הגודל קטן מדי‪ ,‬סיים‪.‬‬
‫‪ .3‬צייר_פרצוף(מיקום‪ ,‬גודל)‬
‫‪ .4‬צייר_מונה (מיקום‪ ,‬גודל מוקטן)‬
‫‪47‬‬
Recursive Mona Liza
1. function [] = mona(x,y,r)
2. hold on
3. plot(x+r*[0 2 2 -2 -2 0], y+r*[0 0 4 4 0 0])
40
4. axis equal
35
5. if r < 0.1
6.
return;
30
7. end
25
8. face(x, y+3*r, r)
20
9. mona(x, y, 0.5*r)
15
10.end
10
5
0
-25
-20
-15
-10
-5
0
5
10
15
20
25 48
Face for mona
1. function []=segment(x1,y1,x2,y2)
10
8
2.
3.
6
1. function [] = face(x,y,r)
2.
cycle(x,y,r);
3.
r0 = 0.3975*r;
4.
cycle(x-r/2, y+r/3, r0);
5.
segment(x,y-r/2,x,y+r/2);
6.
cycle(x+r/2, y+r/3, r0);
7.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
8. end
4
2
0
-2
hold on
plot([x1,x2],[y1,y2]);
4. end
-4
-6
-8
-10
-10
-8
-6
-4
-2
0
2
4
6
8
10
1. function []=cycle(x0,y0,r)
2.
arc_cycle(x0,y0,r,0,2*pi);
3. end
1. function []=arc_cycle(x0,y0,r,A,B)
2.
3.
4.
t = linspace(A,B,100);
x = cos(t); y = sin(t);
plot(r*x+x0, r*y+y0);
5. end
49
‫מימוש אינדוקטיבי כנגד רקורסיבי‬
‫כתוב פונקציה שמחשבת סכום של ‪ n‬האיברים הראשונים במערך חד מימדי‬
‫)‪1. function y = my_sum(x, n‬‬
‫‪2.‬‬
‫;‪y = 0‬‬
‫‪3.‬‬
‫‪for k = 1:n‬‬
‫‪4.‬‬
‫;)‪y = y + x(k‬‬
‫‪5.‬‬
‫‪end‬‬
‫מימוש רקורסיבי‬
‫)‪1. function y = my_sum(x, n‬‬
‫‪2.‬‬
‫‪if n==0 y = 0; return; end‬‬
‫‪3.‬‬
‫;)‪y = my_sum(x, n-1) + x(n‬‬
‫‪50‬‬
‫מימוש אינדוקטיבי כנגד רקורסיבי‬
‫כתוב פונקציה שמחשבת מכפלת של ‪ n‬האיברים הראשונים במערך חד מימדי‬
‫)‪1. function y = my_prod(x, n‬‬
‫‪2.‬‬
‫;‪y = 1‬‬
‫‪3.‬‬
‫‪for k = 1:n‬‬
‫‪4.‬‬
‫;)‪y = y * x(k‬‬
‫‪5.‬‬
‫‪end‬‬
‫מימוש רקורסיבי‬
‫)‪1. function y = my_prod(x, n‬‬
‫‪2.‬‬
‫‪if n==0 y = 1; return; end‬‬
‫‪3.‬‬
‫;)‪y = my_prod(x, n-1) * x(n‬‬
‫‪51‬‬
‫מימוש אינדוקטיבי כנגד רקורסיבי‬
‫כתוב פונקציה שמחשבת ‪ OR‬של ‪ n‬האיברים הראשונים במערך חד מימדי‬
‫)‪1. function y = my_any(x, n‬‬
‫‪2.‬‬
‫;‪y = false‬‬
‫‪3.‬‬
‫‪for k = 1:n‬‬
‫‪4.‬‬
‫;)‪y = y || x(k‬‬
‫‪5.‬‬
‫‪end‬‬
‫מימוש רקורסיבי‬
‫)‪1. function y = my_any(x, n‬‬
‫‪2.‬‬
‫‪if n==0 y = false; return; end‬‬
‫‪3.‬‬
‫;)‪y = my_any(x, n-1) || x(n‬‬
‫‪52‬‬
‫מימוש אינדוקטיבי כנגד רקורסיבי‬
‫כתוב פונקציה שמחשבת ‪ AND‬של ‪ n‬האיברים הראשונים במערך חד מימדי‬
‫)‪1. function y = my_all(x, n‬‬
‫‪2.‬‬
‫;‪y = true‬‬
‫‪3.‬‬
‫‪for k = 1:n‬‬
‫‪4.‬‬
‫;)‪y = y && x(n‬‬
‫‪5.‬‬
‫‪end‬‬
‫מימוש רקורסיבי‬
‫)‪1. function y = my_all(x, n‬‬
‫‪2.‬‬
‫‪if n==0 y = true; return; end‬‬
‫‪3.‬‬
‫;)‪y = my_all(x, n-1) || x(n‬‬
‫‪53‬‬
54
80
60
40
20
0
-20
-40
-60
-80
-100
-50
0
50
100
55
Recursive face
Line =2
x=0
y=0
r=100
1. function [] = face(x,y,r)
2. hold on
3.
axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
56
Recursive face
Line =3
x=0
y=0
r=100
1. function [] = face(x,y,r)
2.
hold on
3. axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
57
Recursive face
Line =4
x=0
y=0
r=100
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4. cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
58
Recursive face
Line =5
x=0
y=0
r=100
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.
cycle(x,y,r);
5. if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
59
Recursive face
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8. r0 = 0.4*r;
40
Line =8
x=0
y=0
r=100
r0=40
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
60
Recursive face
Line =9
x=0
y=0
r=100
r0=40
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
face
-100
-50
0
50
100
-50
+33
9.
(x-r/2,
y+r/3, 40
r0);
10.
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
61
Recursive face
-50
+33
40
1. function [] = face(x,y,r)
2. hold on
3.
axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
Line =9
Line =2
x=0
x=-50
y=0
y=33
r=100
r=40
r0=40
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
62
Recursive face
Line =9
Line =3
x=0
x=-50
y=0
y=33
r=100
r=40
r0=40
1. function [] = face(x,y,r)
2.
hold on
3. axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
63
Recursive face
Line =9
Line =4
x=0
x=-50
y=0
y=33
r=100
r=40
r0=40
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4. cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
64
Recursive face
Line =9
Line =5
x=0
x=-50
y=0
y=33
r=100
r=40
r0=40
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.
cycle(x,y,r);
5. if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
65
Recursive face
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
16
8. r0 = 0.4*r;
Line =9
Line =8
x=0
x=-50
y=0
y=33
r=100
r=40
r0=40
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
66
Recursive face
Line=9
=9
Line
x=-50
x=0
y=33
y=0
r=40
r=100
r0=16
r0=40
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
16
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
face
-100
-50
0
50
100
-70
+47
9.
(x-r/2,
y+r/3, 16
r0);
10.
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
67
Recursive face
-70
+47
1. function [] = face(x,y,r)
2.  hold on
3.
axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
16
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
Line=9
=8
Line
Line =2
x=-50
x=0
x=-70
y=33
y=0
y=47
r=40
r=100
r0=16
r0=40
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
68
Recursive face
Line=9
=8
Line
Line =3
x=-50
x=0
x=-70
y=33
y=0
y=47
r=40
r=100
r0=16
r0=40
1. function [] = face(x,y,r)
2.
hold on
3.  axis equal
4.
cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
69
Recursive face
Line=9
=8
Line
Line =4
x=-50
x=0
x=-70
y=33
y=0
y=47
r=40
r=100
r0=16
r0=40
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.  cycle(x,y,r);
5.
if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
70
Recursive face
Line=9
=8
Line
Line =8
x=-50
x=0
x=-70
y=33
y=0
y=47
r=40
r=100
r0=16
r0=40
1. function [] = face(x,y,r)
2.
hold on
3.
axis equal
4.
cycle(x,y,r);
5.  if r < 10
6.
return;
7.
end
8.
r0 = 0.4*r;
80
60
40
20
0
-20
-40
-60
-80
-100
9.
10.
face(x-r/2,
-50
0
50
100
y+r/3, r0);
segment(x,y-r/2,x,y+r/2);
11.
face(x+r/2, y+r/3, r0);
12.
arc_cycle(x,y,.8*r,1.25*pi,1.75*pi);
13.end
71
3D recursive face
1.5
1
z
0.5
0
-0.5
-1
-1
0
1
x
-1
-0.5
0
y
0.5
1
72
3D recursive face
1.5
1
z
0.5
0
-0.5
-1
-1
1. function [] = face3d(x,y,z,r)
2.
hold on
3.
axis equal; grid on
4.
ellipsoid(x,y,z,r,r,r);
5.
if r < 0.1 return; end
6.
r0 = 0.3*r;
7.
face3d(x-r/2,
face3d(x+r/2,
0
1
x
-1
-0.5
0
0.5
1
y
y+r/3,z+0.9*r, r0); %left
recursion
8.
y+r/3,z+0.9*r, r0); %right recursion
9.
ellipsoid(x,y,z+r,r/10,r/4,r/2);
% nose
10.
ellipsoid(x,y-r/2,z+0.8*r,r/2,r/10,r/10); % mouth
11.
xlabel('x'); ylabel('y'); zlabel('z');
12.end
73
‫פתרונות רקורסיביים בזבזניים‬
‫• פתרון רקורסיבי עלול להיות מאד לא יעיל מבחינת סיבוכיות‬
‫זמן (או מקום)‪.‬‬
‫• נדגים זאת על ידי פונקציה רקורסיבית פשוטה לחישוב האבר‬
‫ה ‪-n‬י בסדרת פיבונאצ'י‪.‬‬
‫נוסחה רקורסיבית‬
‫סדרת פיבונאצ'י‬
‫…‪1, 1, 2, 3, 5, 8, 13,‬‬
‫•‬
‫‪74‬‬
‫‪a2 = a1 = 1‬‬
‫‪an = an-1 + an-2‬‬
‫נוסחה סגורה‬
‫‪an = (φn - (1 - φ)n) / 5‬‬
‫כאשר ‪φ = (1+5) / 2 ~= 1.6180‬‬
‫שהוא שורש של ‪x2 – x – 1 = 0‬‬
‫נעיר שהתכנית הכי יעילה לחישוב האבר ה ‪-n‬י היא על ידי שימוש בנוסחה הסגורה‬
‫‪ :rfib‬תכנית רקורסיבית לסדרת פיבונאצ'י‬
‫• להלן פונקציה רקורסיבית לחישוב האבר ה ‪-n‬י בסדרת‬
‫פיבונאצ'י על פי ההגדרה‪.‬‬
‫)‪function f=rfib(n‬‬
‫‪if n<=2‬‬
‫;‪f=1‬‬
‫;)‪else f=rfib(n-1)+rfib(n-2‬‬
‫‪end‬‬
‫• פונקציה זו מאד לא יעילה‪( :‬אקספוננציאלית)‬
‫‪75‬‬
F(6)
n=6
function f=F(n)
if n<=2
f=1;
else f=F(n-1)+F(n-2);
end
f = F(5) + F(4)
n=5
f = F(4)
3 + F(3)
n=4
f = F(3)
2 + F(2)
1
n=3 n=2
f = F(2)
1 f =+21F(1)
1
n=2n=1
f=1 f=1
76
‫הוכחת אקספוננציאליות של ‪ rfib‬באינדוקציה‬
‫יהי ‪Timen‬מספר הפעולות הנדרשות לביצוע‬
‫)‪ .rfib(n‬נוכיח ‪ Timen<φn‬באינדוקציה‪.‬‬
‫בסיס‪Time1 = 3 > φ1, Time2 = 3 > φ2 :‬‬
‫‪.‬‬
‫צעד‪ :‬הזמן לחשב עבור ‪ n‬כרוך בין היתר בקריאה‬
‫לפונקציה עבור ‪ n-2‬ועבור ‪ n-1‬ולכן‪:‬‬
‫)‪function f=rfib(n‬‬
‫‪if n <= 2‬‬
‫;‪f=1‬‬
‫;)‪else f=rfib(n-1)+rfib(n-2‬‬
‫‪end‬‬
‫‪Timen > Timen-1 + Timen-2‬‬
‫מהנחת‬
‫האינדוקציה ‪%‬‬
‫‪+ φn-2‬‬
‫‪> φn-1‬‬
‫)‪> φn-2 (φ + 1‬‬
‫‪ φ‬שורש של ‪– x – 1 = 0‬‬
‫‪%x2‬‬
‫‪= φn-2 φ2‬‬
‫‪= φn‬‬
‫‪77‬‬
rfib(n) = ‫> מספר העלים‬Timen :‫דרך נוספת‬
f(7)
function f=rfib(n)
if n<=2
f=1;
else f=rfib(n-1)+rfib(n-2);
end
f(6)
f(5)
f(4)
f(4)
f(3)
f(2)
f(3)
f(2)
f(2)
f(3)
f(1)
f(2)
f(2)
f(1)
f(1)
78
‫מימוש אינדוקטיבי (תכנון דינאמי) של מספרי פיבונאצ'י‬
‫)‪function fib = myfib0(n‬‬
‫‪% Fibonacci number computation‬‬
‫‪f = zeros(1,n); %memory allocation‬‬
‫;‪f(1)=1;f(2)=1‬‬
‫‪for k=3:n‬‬
‫;)‪f(k)=f(k-1)+f(k-2‬‬
‫‪end‬‬
‫;)‪fib=f(n‬‬
‫מספר הפעולות הוא לינארי‪.‬‬
‫חישוב זה שומר את כל ‪ n‬האברים הראשונים בסדרת פיבונאצ'י בוקטור ‪.f‬‬
‫האם ניתן לחשב את מספר פיבונאצ'י ה ‪-n‬י בפחות זכרון?‬
‫‪79‬‬
‫תכנון דינאמי‬
‫קווי פעולה למציאת אלגוריתם בשיטת התכנון הדינמי‬
‫‪ .1‬מציגים תיאור רקורסיבי לדרך פתרון הבעיה‪.‬‬
‫‪ .2‬מגלים כי זמן ריצת האלגוריתם הרקורסיבי (הפועל "מלמעלה למטה") הוא אקספוננציאלי‪.‬‬
‫‪ .3‬מגלים כי מספר תת‪-‬הבעיות הקיימות הוא פולינומי‪ ,‬והסיבה לסיבוכיות האקספוננציאלית‬
‫היא קריאות חוזרות לאלגוריתם עבור אותה תת‪-‬בעיה‪.‬‬
‫‪ .4‬פותרים את הבעיה על ידי פתרון כל התת‪-‬בעיות – ממקרי הקצה שהפתרונות שלהם‬
‫ידועים מראש "כלפי מעלה" – עד שמגיעים לבעיה המקורית‪.‬‬
‫‪80‬‬
‫מיון מיזוג‬
1. function b = msort(a)
2. if length(a)<2
3.
b = a;
4.
return
5. end
6. m = ceil(length(a)/2);
7. b = merge(msort(a(1:m)), msort(a(m+1:end)));
81
‫הדגמה (ויקיפדיה)‬
‫‪82‬‬
Analyzing merge sort (Silvio Micali MIT)
MERGE-SORT a(1:n)
T(n)
O(1)
1.
2.
If n < 2, done
Recursively sort
a(1 : n/2) and a(n/2 + 1 : n)
3. “Merge” the two sorted lists
O(1)
2T(n/2)
O(n)
if n < 2;
T(n) =
2T(n/2) + O(n) if n > 1.
Recurrence solving (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
T(n)
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
T(n/2)
T(n/2)
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2
cn/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2
cn/2
cn/4
Q(1)
cn/4
cn/4
…
cn/4
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn/2
cn/2
cn/4
Q(1)
cn/4
cn/4
…
cn/4
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2
cn/2
cn/4
Q(1)
cn/4
cn/4
…
cn/4
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2
cn/2
cn/4
Q(1)
cn/4
cn/4
…
cn
cn/4
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2
cn/2
cn/4
cn/4
cn/4
cn
…
cn/4
cn
Q(1)
…
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2
cn/2
cn/4
cn/4
cn/4
cn/4
cn
…
h = lg n
cn
Q(1)
…
#leaves = n
Q(n)
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2
cn/2
cn/4
cn/4
cn/4
cn/4
cn
…
h = lg n
cn
Q(1)
…
Q(n)
Total =
#leaves = n
?
Recursion tree (Silvio Micali MIT)
Solve T(n) = 2T(n/2) + cn, where c > 0 is constant.
cn
cn
cn/2
cn/2
cn/4
cn/4
cn/4
cn/4
cn
…
h = lg n
cn
Q(1)
O(n)
#leaves = n
Total = O(n lg n)
‫תודה‬
‫תודה‬
‫‪96‬‬
‫תודה‬

similar documents