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

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

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

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

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

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

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

שאלות

תרגיל 1

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

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

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

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

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

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

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

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

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

סיבוכיות זמן\זיכרון אסימפטוטית אומר [math]\displaystyle{ \Theta }[/math] של הזמן\זיכרון.

לגבי שאלה 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

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

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

• כמה שאלות לגבי חלק 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)

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

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