שיחה:88-280 מבני נתונים ואלגוריתמים

חזרה לדף הקורס

גלול לתחתית העמוד

הוספת שאלה חדשה

הוסף שאלה חדשה (רשום כותרת לשאלה, רשום את תוכן השאלה ולחץ על שמירה למטה מימין לסיום).

-עזרה על עיצוב הטקסט וכתיב מתמטי תוכלו למצוא כאן

אם אתם רוצים לשאול שאלה עליכם ליצור חשבון משתמש באתר.

שאלות

תרגיל 1

שאלה 4 סעיף 3, יש שיטה פרט לאינטרציות עבור שני גורמים בתוך רקורסיה? כי לא ברור לי איך להציג שלב סופי? עבור איזה k ומה הוא הסוף במקרה זה?

זכור שאתה צריך רק לתת $\Theta$ של התשובה. מספיק למצוא חסם תחתון וחסם עליון. --אוריה 15:54, 3 בנובמבר 2011 (IST)

בסעיף 2 תשובה לפי אינטרציות ולפי משפט master שונות מדי, האם יתכן דבר כזה?

אם התשובות שקיבלת הן $\Theta$ אחת של השנייה זה בסדר. אחרת כנראה יש לך טעות. --אוריה 15:54, 3 בנובמבר 2011 (IST)

שאלה 5 לא ברורה לי השאלה. אם כפל a ב-a נחשב לפעולה, אז איך ניתן להפחית במספר פעולות. בסופו של דבר אני עדיין אמור לכפול a בעצמו n פעמיים...

רמז: מה אם n חזקה של 2? --אוריה 15:54, 3 בנובמבר 2011 (IST)

ומזה "סיבוכיות זיכרון" ?

נגיע לזה בתרגול הקרוב. זו כמות התאים בזיכרון שהאלגוריתם צריך. --אוריה 15:54, 3 בנובמבר 2011 (IST)

שאלה 6 אסימפטותית?

סיבוכיות זמן\זיכרון אסימפטוטית אומר $\Theta$ של הזמן\זיכרון.

לגבי שאלה 5 לדעתי צריך לחשוב קיבוצית - נניח יש לך איקס בשמינית לחשב, ויש לך פונקציה של חזקה, אתה מכניס שלם חיובי, ומספר ומקבל חזרה את המספר בחזקה: x^8 = x^4*x^4 = x^2*x^2 * x^2*x^2 = ... כלומר כל פעם קוראים לפונקציית חזקה עם בלוק קטן יותר. לדעתי זה אמור להקטין. סלבה.

אבל מה עושים עם מה שנשאר? נגיד- x^116=x^64*x^50. מה עושים עם הx^50? אחרת, זה יוצא שרצים על הרבה..

x^116=(x^58)^2

שאלה 6

יכול להיות שיש טעות באלגוריתם? ז"א במקום for i = 2 to n-1: צריך להיות for i = 0 to n-1:

אין טעות. אם יתחילו את הלולאות מ-0 האלגוריתם יעשה פעולה אחרת. --אוריה 15:54, 3 בנובמבר 2011 (IST)

בשאלה 2 הכוונה לפונקציות אי שליליות?

כן. הכוונה היא לפונקציות אי שליליות.--אוריה 20:32, 6 בנובמבר 2011 (IST)

שאלה 5

אם בתוך האלגוריתם אני משתמש בערך של log(n האם זה נחשב לפעולה אחת?

לצורך התרגיל, כן.--אוריה 20:32, 6 בנובמבר 2011 (IST)

מצאתי דרך שתפתור את הרקורסיה מהסוג של 4ג ממש ביעילות ולהלן הקישור לאלגוריתם זה. סלבה.

שאלה 6: מה זאת אומרת אסימפטוטית?

תרגיל 2

• כמה שאלות לגבי חלק 1 -

1) האם מותר להוסיף תאים מסביב למטריצה (כך שהיא תהיה בגודל (m+1)*(n+1) ) ?

כן. אבל אל תדפיס אותם בפלט. כתוב בתיעוד שאתה שם תאים מיותרים במטריצה אם אתה אכן עושה זאת. --אוריה 15:06, 18 בנובמבר 2011 (IST)

2) אם יש שני פתרונות (אם למשל בדרך לפתרון יש לולאה שאפשר לעבור מכל צד שלה) אז האלגוריתם צריך לפלוט 1- ? או שאני מניח שהקלט אמור להיות כזה שאין בו שני פתרונות?

לא יהיה קלט עם שני פתרונות בחלק הראשון של התרגיל. --אוריה 15:06, 18 בנובמבר 2011 (IST)

3) בקשר לשני החלקים - אם אני עושה את התרגיל בC, אני צריך לעשות ADT של מחסנית (או תור) בקבצי קוד נפרדים, או לדחוס הכל בקובץ אחד?

אתה יכול לשים הכל בקובץ אחד. --אוריה 15:06, 18 בנובמבר 2011 (IST)

• מה תאריך ההגשה של התרגיל? בקובץ עצמו כתוב 21.11.2011, בעוד שבעמוד התרגילים כתוב 27.11.2011. מה תופס?

ה-27.11.2011. --אוריה 15:06, 18 בנובמבר 2011 (IST)

• איזה נתון מוזן קודם: השורות או העמודות? (כל הדוגמאות מראות מטריצה ריבועית)

השורות קודם. --אוריה 15:06, 18 בנובמבר 2011 (IST)

• האם אפשר להניח שכל הקלטים בפורמט הנכון (רק 0,1 במטריצה, אכן מטריצה וכו'), וגם האם ניתן להניח שנקודות ההתחלה והסיום שתיהן בתוך המטריצה (שלא יתנו לי למשל נקודת התחלה (5,5) למטריצה 2X2)?

אין צורך לבדוק את תקינות הקלט. אבדוק בכל אופן ואם צריך אז אציין זאת כאן. --אוריה 15:06, 18 בנובמבר 2011 (IST)

• האם ניתן להניח שהנקודת ההתחלה והסיום שנקבל הן נקודות שאפשר ללכת בהן? (שהן לא קיר).

כדאי לבדוק. --אוריה 15:06, 18 בנובמבר 2011 (IST)

• האם ניתן לממש את המחסנית (ותור) בעזרת מערך ולא רשימה מקושרת? אם כן, ניתן להניח שגודלו (n*m) יהיה חסום במספר מאוד גדול? (לדוגמא, 1024)

אפשר לממש במערך בכמה תנאים: 1. תתעד מה אתה עושה. 2. הכנסה והוצאה חייבות להיות ב-$O(1)$ בממוצע. 3. גודל התור לא חסום ע"י מספר קבוע. אם התור או המטריצה הם בגודל קבוע מראש יורדו נקודות בבדיקה הידנית גם אם הבדיקה האוטומטית עברה בהצלחה. --אוריה 17:17, 27 בנובמבר 2011 (IST)

• האם ניבדק על שחרור כל הזכרון שהקצאנו דינמית במהלך התרגיל? (האם צריך לשחררו?)

צריך לשחרר כל זיכרון שהוקצה. כנראה ירדו נקודות על זיכרון לא משוחרר, אבל לא הרבה, כי זה לא העיקר בקורס הזה. --אוריה 17:17, 27 בנובמבר 2011 (IST)

• האם מותר לממש את המחסנית כך שמהתוכנית הראשית יש לכאורה גישה לנתוני המחסנית (לא רק לאיבר העליון), אך שבתוכנית הראשית אני משתמש רק בפונקציות המיועדות למחסנית (PUSH ,POP, וכו')? (במקום שאממש את המחסנית באופן שמסתיר את נתוניו באופן מוחלט מהקוד הראשי)

אין צורך "להסתיר" את תוכן המחסנית, אך אין לגשת אל המחסנית שלא בעזרת POP, PUSH וכיו"ב. (אני מבין שאתה מתכנת ב-c++ אם אתה שואל זאת.) --אוריה 17:17, 27 בנובמבר 2011 (IST)

האם תוכלו להעלות את כל קבצי הבדיקה האוטומטית הראשוניים (וגם לחלק ב')?

הבקשה הזו היא לא לעניין. עליך להסתדר עם הדוגמא שיש בנוסח התרגיל. --אוריה 15:41, 15 בנובמבר 2011 (IST)

כל הרעיון של קבצי הפידבק זה שנוכל לוודא שהתוכנית שלנו פועלת כמו שצריך על מקרים בסיסיים. ברגע שאין לנו את הקבצים, אין לנו דרך לדעת איפה הבעיה, והאם בכלל הבעיה אצלנו. אני אישית חיפשתי את הטעות שלי המון זמן ובסוף גיליתי שהייתה טעות בקבצים. דרך אגב, אני עדיין מקבל 10 ואין לי מושג איפה הטעות שלי (אם בכלל הטעות אצלי). בקורסים קודמים קיבלנו את קבצי הקלט/פלט וגם פירטו איך הפלט אמור להיראות, וכאן ההסבר הוא חלקי ביותר. אנחנו גם ככה לא נבחנים על הקלטים האלה.

תרגיל ראשון עובד על דוגמאות שפירסמת ועל כל דוגמא אחרות שיכלתי לחשוב עליהם. אך בכל זאת ציון בבדיקה אוטומתית הוא אפס... ולכן בעיה היא כנראה במספר רווחים, הורדות שורה וכו.. בבקשה תפרסמו קבצים של בדיקת פיתבק. והשאלות (תרגיל ב C++: 1) האם סינטקסיס using namespace std; יכול לא לעבוד בשרתים של בר אילן? אם כן מה הוא סינטקסיס הישן לספריה קלט פלט והקצאת זיכרון 2)האם מודפסים מילים input output? 3) האם יש שורה ריקה בין קלט לפלט? 4)האם יש רווחים פרט לרווחים בין איברי המטריצה? בסןף המטריצות? חבל שנשרף כל כך הרבה שעות על ניסיונות לקבל יותר מאפס על תרגיל שעובד..

האם בקלט יש רווח בין אינדקס שורה לאינדקס עמודה? כלומר גודל מטריצה הוא 44 או 4רווח4?

יש רווח (אחד) בין כל זוג מספרים בקלט. (אחרת, המספרים לא יוכלו להיות גדולים מ-9.) --אוריה 11:57, 24 בנובמבר 2011 (IST)

• בסעיף ב', הצלחתי לממש את האלגוריתם בלי שימוש במטריצת עזר ששומרת עבור כל אחד מהתאים את מספר התאים עד אליו. האם אני חייב לשנות את המימוש שלי (מכיון שכתוב בתרגיל שיש להשתמש במטריצה כזו)?

זה בסדר בתנאי שממשת והשתמשת בתור. --אוריה 11:57, 24 בנובמבר 2011 (IST)

תרגיל 3

בשאלה 1 (וגם למעשה 2) האם ניתן להניח שאנו מקבלים את העץ במימוש של מערך ואנחנו מקבלים את המערך? או שמקבלים פוינטר לשורש והוא ממומש בתור פוינטרים?