מרצה : פרופ ’חנוך לוי [email protected] ד”ר יוסי מטיאס [email protected]: מתרגלים : גיא קינדלר [email protected] ערן הלפרין [email protected] דרישות : • %10 תרגילי בית • %10 פרויקט (משולב עם מעבדה) • %80 בחינה סופית 1 Data Structures, CS.

Report
‫מרצה‪:‬‬
‫פרופ ’חנוך לוי‬
‫‪[email protected]‬‬
‫ד”ר יוסי מטיאס‬
‫‪[email protected]:‬‬
‫מתרגלים‬
‫‪:‬‬
‫גיא קינדלר‬
‫‪[email protected]‬‬
‫ערן הלפרין‬
‫‪[email protected]‬‬
‫דרישות‪:‬‬
‫• ‪ %10‬תרגילי בית‬
‫• ‪ %10‬פרויקט (משולב עם מעבדה)‬
‫• ‪ %80‬בחינה סופית‬
‫‪1‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
:‫ספרים‬
Introduction to Algorithms by:
T. H. Cormen, C. E. Leiserson, R. L. Rivest
:‫ספרי עזר‬
Data Structures and Algorithms by:
Aho, Hopcroft, Ulman
:‫ספר מומלץ‬
T.H. Cormen
:‫חומר חובה‬
: ‫פרקים‬Cormen
I. 2, 4
II. 7, 8, 9 10
III. 11, 12, 13
V. 19, 22
‫כל החומר הנלמד בכיתה‬
11/7/2015
Data Structures, CS TAU
2
‫• נושא בסיסי ועקרוני‬
‫שימוש בסברוטינות( שגרות)‪ :‬בצוע תפקידי משנה‬
‫דוגמה‪:‬‬
‫)‪Procedure SUM(i,j,k‬‬
‫)‪Procedure MULT(i,j,prod‬‬
‫;‪k:=i+j‬‬
‫;‪prod:=0‬‬
‫;‪return‬‬
‫‪for k=1 to j‬‬
‫;‪end‬‬
‫;)‪call SUM(prod,i,prod‬‬
‫;‪end‬‬
‫עקרון‪ :‬בקריאה לשגרה חשוב ה”מה”‪ ,‬לא ה”איך!”‬
‫דוגמה‪ :‬בצוע קורס “מבנה נתונים”‬
‫השג את הספר‬‫למד את החומר‬‫הגש עבודות‬‫הגש בחינה‬‫‪3‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
‫• שגרות שקוראות לעצמן!‬
‫דוגמה ‪ :1‬חישוב עצרת‬
‫‪Iterative‬‬
‫;)‪Procedure factor(n‬‬
‫;‪x = 1‬‬
‫‪for I:1 to n‬‬
‫;‪x = x * I‬‬
‫;)‪return(x‬‬
‫;‪end‬‬
‫‪Recursive‬‬
‫;)‪Procedure factor1(n‬‬
‫;)‪if n = 1 return(1‬‬
‫‪else‬‬
‫;)‪x = factor1(n-1‬‬
‫;)‪return(n * x‬‬
‫;‪end‬‬
‫;‪end‬‬
‫• רקורסיה‪ :‬שיטה כללית‬
‫נתונה‪ :‬בעיה גדולה‬
‫שיטת פתרון ‪ :‬א) שבור הבעיה לבעיה(יות) קטנה(ות)‬
‫ב) פתור את הבעיה(יות) הקטנה(ות)‬
‫ג) “הדבק” הפתרונות הקטנים ליצירת הפתרון הגדול‬
‫נוסחה להצלחה‪ :‬אמונה!!!‬
‫‪4‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
:2 ‫דוגמה‬
‫ מקל‬:‫נתון‬
‫ לחתוך את המקל לחתיכות של ס”מ ומטה‬:‫צריך‬
‫פתרון איטרטיבי‬
Proc CUT1(stick)
while length(stick)>1 do:
chop a piece of 1 cm from stick
end;
return;
end;
‫פתרון רקורסיבי‬
Proc CUT2(stick)
If length(stick)<1 return;
else do:
chop a piece of 1 cm from stick
let s-stick be the remaining part
CALL CUT2(s-stick)
end;
return;
end;
11/7/2015
Data Structures, CS TAU
5
‫פתרון רקורסיבי נוסף‬
Proc CUT3(stick)
If length(stick)<1 return
else do:
cut stick to two parts: stick1 and stick2
CALL CUT3(stick1)
CALL CUT3(stick2)
return;
end;
end;
:‫תשומת לב‬
‫ הם פתרונות תקיפים‬CUT3 ‫ו‬CUT2
CUT2!‫ לקרוא ל‬CUT3 ‫אפשר בתוך‬
CUT3!‫ לקרוא ל‬CUT2 ‫אפשר בתוך‬
11/7/2015
Data Structures, CS TAU
6
:3 ‫דוגמה‬
.‫ לחסר ולמנות‬,‫נתון מחשב שיודע רק לחבר‬)‫ שלם‬X ‫( עבור‬SQUARE(X ‫ בנה שיגרה‬X2 (‫חשב את‬-
‫פתרון רקורסיבי‬
(n+1)2 = n2+n+n+1
n2 = (n-1)2+n+n-1
Procedure SQUARE(N)
if N = 1 return (1)
else do
M = SQUARE(N-1);
return (M+N+N-1);
end;
end;
‫פתרון איטרטיבי‬
Procedure SQUARE2(N)
M = 0;
for I = 1 to N
M = M + N;
end;
return (M);
end;
11/7/2015
Data Structures, CS TAU
7
:4 ‫דוגמה‬
:‫מגדלי האנוי‬
- C‫תוך שימוש ב‬- B ‫ל‬- A ‫• העבר מ‬
!‫• אסור שגדול יהיה על קטן‬
‫פתרון רקורסיבי‬
Proc HANOI(From, To, By, N)
(* move top N rings from From to To using By*)
if N = 1 move ring from From to top
of To end return;
else do:
CALL HANOI(From, By, To, N - 1);
move top of From to To
CALL HANOI(By, To, From, N - 1);
return;
end;
end;
11/7/2015
Data Structures, CS TAU
8
:5 ‫דוגמה‬
A1,…,AN‫ איבריםבמערך‬N ‫ של‬MAXALL ‫מציאת‬- N ‫השמת המקסימום במקום ה‬-
‫פתרון איטרטיבי‬
temp:= A(1);
itemp:= 1;
for j=1 to N do
if A(j) > temp
itemp:= j;
temp:= A(j);
end;
end;
A(itemp): = A(N);
A(N):= temp;
‫פתרון רקורסיבי‬
if N=1 return
else begin
CALL MAXALL(N-1);
if A(N)<A(N-1) then
temp= A(N);
A(N)= A(N-1);
A(N-1)= temp;
end;
return;
end;
11/7/2015
Data Structures, CS TAU
9
:6 ‫דוגמה‬
MAXALL‫( בהנחה שממומשת השגרה‬SORT(N ‫מיון מערך‬
‫פתרון איטרטיבי‬
Do I= N to 1 by -1
CALL MAXALL(I)
end;
‫פתרון רקורסיבי‬
Proc SORT(N)
/* sorts the elements A(1)….A(N) */
if N = 1 return
else begin
CALL MAXALL(N);
CALL SORT(N-1);
end;
end;
11/7/2015
Data Structures, CS TAU
10
‫תרגיל בית ‪:1‬‬
‫‪1) -‬הבא דוגמא לבעיה‬
‫‪-‬‬
‫פתור את הבעיה בצורה רקורסיבית‬
‫‪-‬‬
‫פתור את הבעיה בצורה לא רקורסיבית‬
‫‪-‬‬
‫הגש למתרגלים בשבוע הבא‬
‫)‪2‬בונוס‪:‬‬
‫האם ישנן בעיות שניתן לפתור בעזרת שפה‬
‫רקורסיבית ולא ניתן בעזרת שפה לא‬
‫רקורסיבית?‬
‫האם יש בעיות שניתן לפתור איטרטיבית אך‬
‫לא רקורסיבית?‬
‫‪11‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
‫מטרה‪ :‬לקחת בעיה ולכתוב לה פתרון שיטתי באמצעות המחשב‬
‫כלים‪ :‬מבנה נתונים ‪ +‬אלגוריתם‬
‫אלגוריתם‪ :‬שיטה‪ ,‬סכמה‪“ ,‬מתכון”‬
‫מבנה נתונים‪ :‬חלק אינטגרלי של האלגוריתם‬
‫אלגוריתם ‪ -‬תלוי במבנה הנתונים‬
‫דוגמה לבעיה ופתרונה‬
‫‪E‬‬
‫‪D‬‬
‫‪AB+DC‬מותר‬
‫‪AB+EB‬מותר‬
‫‪AC+EB‬אסור‬
‫‪C‬‬
‫‪A‬‬
‫נתון‪ :‬צומת דרכים עם כיווני נסיעה‬
‫‪B‬‬
‫צריך‪ :‬לתכנן פעולות רמזור כך שלא יהיו התנגשויות‬
‫‪12‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
‫שיטה‪ :‬נרשום את כל הקומבינציות האסורות בצורת גראף‬
‫)‪GRAPH(VERTICES, EDGES‬‬
‫צמתים)‬
‫( קשתות‪,‬‬
‫צמתים‪ :‬פניות אפשריות‬
‫קשתות‪ :‬מחברות צמדי פניות אסורות‬
‫‪ED‬‬
‫‪13‬‬
‫‪AD‬‬
‫‪AC‬‬
‫‪AB‬‬
‫‪BD‬‬
‫‪BC‬‬
‫‪BA‬‬
‫‪DC‬‬
‫‪DB‬‬
‫‪DA‬‬
‫‪EC‬‬
‫‪EB‬‬
‫‪EA‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
‫אחסנת האינפורמציה‬
‫ייצוג האינפורמציה באמצעות טבלה‬
‫(ייצוג גראף בטבלה)‬
‫= ‪1‬קשת (פניה אסורה)‬
‫‪14‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
‫פתרון הבעיה במודל הנ”ל‬
‫• רמזור בעל ‪ k‬צבעים‬
‫• כשצבע ‪ i‬דולק הפניות של צבע ‪ i‬מבוצעות‬
‫• באותו צבע אסור שתהינה שתי פניות סותרות‬
‫תרגום לגראף‬
‫צבע את צבעי הגראף ב ‪ k‬צבעים‪ ,‬כך‬
‫ששני שכנים לא יהיו באותו צבע‬
‫רצוי‪ :‬מזעור‪k‬‬
‫בעיה קלאסית‪ :‬צביעת גראף‬
‫הבעיה היא‪NP-COMPLETE‬‬
‫כדי לפתור יש “לבדוק את כל האפשרויות”‬
‫(או מספר עצום של אפשרויות)‬
‫‪15‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
‫פתרונות‪:‬‬
‫)‪1‬קטן ==> חפש את כל האפשרויות‬
‫)‪2‬אולי קיימת אינפורמציה נוספת‬
‫)‪3‬פתרון “קרוב לאופטימלי ‪” -‬היוריסטי)‪(heuristic‬‬
‫פתרון היוריסטי( תאוותני)‪- greedy‬‬
‫)‪1‬בחר צומת לא צבוע‪ ,‬וצבע בצבע החדש‬
‫)‪2‬עבור על רשימת הלא צבועים‪ ,‬ואם לצומת אין שכן‬
‫בצבע הנוכחי‪ -‬צבע אותו‪.‬‬
‫לא אופטימלי!‬
‫‪3‬‬
‫‪2‬‬
‫‪5‬‬
‫‪1‬‬
‫‪4‬‬
‫אופטימלי‪}4,3,1{ }5,2{ :‬‬
‫היוריסטי}‪: {5} {3,4} {1,2‬‬
‫‪16‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬
‫צביעת הגראף של הבעיה‬
‫אופטימליות‪:‬‬
‫הקבוצה ‪ AC, DA, BD, EB‬הינה ‪ 4 -‬קליק‬
‫(כל פניה אסורה עם כל ‪ 3‬האחרות)‬
‫לכן צריך לפחות ‪ 4‬צבעים‬
‫תרגום הפתרון לרמזור‬
‫צבע‬
‫‪17‬‬
‫פניות‬
‫אדום‬
‫‪AB, AC, BC‬‬
‫ירוק‬
‫‪DC, AD, BD‬‬
‫כחול‬
‫‪DA, EC, BA‬‬
‫סגול‬
‫‪EA, EB, DB, ED‬‬
‫‪Data Structures, CS TAU‬‬
‫‪11/7/2015‬‬

similar documents