Description

יש לקרוא היטב לפני תחילת העבודה!
מבוא:
במעבדה זו נלמד סוג נוסף של מטריצות מיוחדות – מטריצות דלילות ונראה כיצד ניתן לממש אותן בעזרתרשימות מקושרות.
תיאור:
מטריצה ריבועיתn*n בה רוב האיברים שווים לאפס, נקראת מטריצה דלילה. למשל:
0 1 0 4
0 0 0 0
0 0 0 0
0 6 0 0
היא מטריצה דלילה בגודל 4*4 .במטריצה זאת מספר האיברים השונים מאפס שווה ל-3.
מקובל להגדיר מטריצה דלילה ע”י כך שמספר האיברים השונים מאפסr הרבה יותר קטן מn*n , כלומרr<< n*n
גם מטריצה כזאת ניתן לראות כמטריצה דלילה:
3 1 3 4
3 3 3 3
3 3 3 3
3 6 3 3
במקרה זה רוב האיברים של המטריצה הנ”ל שווים ל – 3. ויש מעט איברים השונים מ – 3.
1). מימוש סטנדרטי , באמצעות מערך דו-מימדי, מאפשר ביצוע פעולות בסיבוכיות:
– 𝑂(1) -ב 𝑔𝑒𝑡(𝑖, 𝑗)
– .𝑂(1) -ב 𝑠𝑒𝑡(𝑖, 𝑗, 𝑥)
𝑂(𝑛 * 𝑛)
– אך סיבוכיות המקום הינה גבוהה .
נציע מימוש חלופי באמצעות רשימה מקושרת:
לכל איבר השונה מהאיבר הנפוץ (0 או 3 בדוגמאות הנ”ל) נחזיק צומת בעל 3 שדות: אינדקסi , אינדקסj ,וערך האיבר. כמובן, נוסיף עוד משתנה שיחזיק את הערך של שאר האברים.
לדוגמא, עבור המטריצות בדוגמה לעיל, ניתן להחזיק את הרשימה המקושרת הבאה:
[1, 2, 1] → [1, 4, 4] → [4, 2, 6]
במימוש זה, הסיבוכיות תהיה כדלקמן:
–סיבוכיות מקום: (𝑂(𝑟
–סיבוכיות (𝑔𝑒𝑡(𝑖, 𝑗 היא (𝑂(𝑟 (במקרה הגרוע יש לעבור על כל הרשימה)–סיבוכיות (𝑠𝑒𝑡(𝑖, 𝑗, 𝑥 היא (𝑂(𝑟 (יש לבדוק האם האיבר כבר קיים ברשימה)
המימוש המוצע חוסך הרבה מקום.
1) כתבו מחלקה בשם >SparseMatrix<T המממשת את הממשק >Matrix<T הנתון לכם (שימו לבשגםtranspose צריך להיות בסיבוכיות זמן קבועה), ומשתמשת במחלקה הגנרית
>DLinkedList<T שכתבתם במעבדה קודמת. (העתיקו את המחלקה ממעבדה קודמת לפרוייקטהמעבדה הזו).
עם הבנאים:
SparseMatrix (T defaultValue);
SparseMatrix (int size, T defaultValue);
הבנאי הראשון בונה מטריצה שבה האיבר המצוי הואdefaultValue , וגודל המטריצה (מספרהשורות) שווה לקבוע הנתון ב-Matrix.הבנאי השני בונה מטריצהsize×size שבה האיבר המצוי הואdefaultValue .
בתוך המחלקה >SparseMatrix<T, הגדירו מחלקה פרטיתSparseMatrixEntry כדלהלן:
private class SparseMatrixEntry { private T value; private int row; private int col; public SparseMatrixEntry(int row, int col, T val) { … }
public int getRow() { … } public void setRow(int row) { … } public int getCol() { … } public void setCol(int col) { … } public T getValue() { … }
public void setValue(T newVal) { … }
}
2) נתונה לכם מחלקת בדיקה 4Junit בשםMatrixTest הבודקת מימוש של >Matrix<Integer.השלימו את המחלקהMatrixTest הנתונה לכם ע״י הוספת בדיקות.
השתמשו ב->MatrixFactory<T על מנת לקבל מופע של >Matrix<Integer. אין לקבל מופע של>Matrix<Integer בדרך אחרת.
סדר העבודה ופרטים טכניים
● :GITHUB מתוךDS-Lab04-SparseMatrix שליפת הפרויק
https://github.com/ykanizo/DSLab2022-2023Public
השתמשו בFile->Import->Git->CloneURI בתוך התפריט שלEclipse ,או שהעתיקו את הקבצים שיש שם לתיקיית ה-src של הפרוייקט שלכם (שימו לב לא לשים אתהקבצים בתוךpackage אחר מלבד ה-default).
אם אתם עובדים בVDI , מומלץ לשנות את המיקום המוצע לפרויקט בתיקייה כלשהי בכונןH .
● הוסיפו את המחלקה >DLinkedList<T שמימשתם במעבדה קודמת.
● הוסיפו את המחלקה >SparseMatrix<T.
● השלימו את המחלקהMatrixTest .
● וודאו כי הרצתMatrixTest עוברת בהצלחה.
● יש להגיש את קבצי ה-java.
פורמט קובץ ההגשה ובדיקתו:
בשםZIP פורמט : יש להגיש קובץ43_lab04_123456789_987654321.zip
(כמובן, יש להחליף את המספרים עם מספרי ת.ז. של המגישים).
על הקובץ להכיל את כל קבצי הJAVA שכתבתם. שימו לב: הקובץ לא יכיל את התיקיה שבההקבצים נמצאים, רק את הקבצים עצמם (אם לא ברור מה ההבדל, ראו סרטון הדגמה מטה).
שימו לב כי קובץ ה-zip שאתם מגישים מכיל את הקובץ עם הטבלאות!
בדיקת קובץ ההגשה: בדקו את הקובץ שיצרתם בתוכנת הבדיקה בקישור:
https://csweb.telhai.ac.il/ראו סרטון הדגמה של השימוש בתוכנת הבדיקה.
הסבר על תוצאות הבדיקה האוטומטית בתרגיל זה:
במעבדה זו, יש מספר סוגי בדיקות, וזאת במטרה שתוכלו לבדוק את עצמכם היטב לפני ההגשה.
לכלtest הוספנו שם ותיאור המסבירים מה הוא בודק. יש 3 סוגים שלtests :
1.tests שבודקים את המחלקה >SparseMatrix<T שמימשתם, עבורT=Integer .עבור טסטים אלו תקבלו 30 נקודות בבודק האוטומטי
2.tests הבודקים את המחלקהMatrixTest שרשמתם, עבור המימוש שלכם ל >SparseMatrix<T.
עבור טסטים אלו תקבלו 15 נקודות.
3.tests הבודקים את המחלקהMatrixTest שרשמתם,
עבור מימוש שגוי של >SparseMatrix<T. המטרה במקרים אלו, שהבדיקות שלכם יתפסו אתהשגיאה.
הטסטים מסוג 3 מגלים בעיות חוסר שלמות בבדיקות שאתם רשמתם. בעיות אלו מאד קשות לזיהויולפיכך הרבה יותר קשה יהיה לתקן בעיות כאלו.
יש שני סטים של בדיקות כאלו (עבור 2 מימושים שגויים שלSparseMatrix ),
סך הכל 15 נק (7 לסט הראשון ו-8 לסט השני). הנקודות ינתנו במלואן עבור סט של בדיקות אםלפחות אחת מהבדיקות בסט נכשלה.
חשוב !!!
בדיקת ההגשות תבוצע ברובה ע”י תוכנית הבדיקה האוטומטית הנ”ל. תוצאת הבדיקה תהייהבעיקרון זהה לתוצאת הבדיקה הנ”ל שאתם אמורים לערוך בעצמכם . כלומר, אם ביצעתם אתהבדיקה באתר החוג, לא תקבלו הפתעות בדיעבד. אחרת, ייתכן שתרגיל שעבדתם עליו קשהייפסל בגלל פורמט הגשה שגוי וכו.’ דבר שהיה ניתן לתקנו בקלות אם הייתם מבצעים את הבדיקה.
היות ואין הפתעות בדיעבד, לא תינתן אפשרות של תיקונים, הגשות חוזרות וכד.’
הגשה שלא מגיעה לשלב הקומפילציה תקבל ציון 0.
הגשה שלא מתקמפלת תקבל ציון נמוך מ- 40 לפי סוג הבעיה.
הגשה שמתקמפלת תקבל ציון 40 ומעלה בהתאם לתוצאות הריצה, ותוצאת הבדיקה הידנית שלהקוד (חוץ ממקרה של העתקה).
תכנית הבדיקה האוטומטית מכילה תוכנה חכמה המגלה העתקות. מקרים של העתקות יטופלו בחומרה
עבודה נעימה!