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

מתוך Math-Wiki
גרסה מ־17:06, 15 בנובמבר 2011 מאת זיתוני (שיחה | תרומות) (תרגיל 2)

קפיצה אל: ניווט, חיפוש

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


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


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

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

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

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

שאלות

תרגיל 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

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

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



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

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

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

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


  • מה תאריך ההגשה של התרגיל? בקובץ עצמו כתוב 21.11.2011, בעוד שבעמוד התרגילים כתוב 27.11.2011. מה תופס?
  • איזה נתון מוזן קודם: השורות או העמודות? (כל הדוגמאות מראות מטריצה ריבועית)