רוטר - שאלה בקשר להוכחות בקורס 'מבני נתונים'

האשכול	מחבר	תאריך כתיבה	מספר
אתה יכול להראות בעזרת חישוב גבול...	IDAN_500	16.10.13 18:41	1
תודה אבל שאלתי לגבי מונוטוניות מסיבה מסויימת..	כובען	16.10.13 18:42	2
אוקיי, שאתה אומר מונוטוניות, אתה צריך להראות בעצם ש f(n) ''גדולה'' אסימפטוטית	IDAN_500	16.10.13 18:56	3
תשמע זה בסה''כ השבוע הראשון של הקורס אז יכול להיות שאני מבלבל במוח	כובען	16.10.13 19:13	4
את האמת שזה תלוי בתרגיל, אבל	IDAN_500	16.10.13 20:43	5
תודה רבה :-)	כובען	16.10.13 23:27	6
אגב, לא צריך להצביע על n0 ו-c ספציפיים בהוכחת קיימות?	כובען	16.10.13 23:41	7
אצלינו לפחות לא היה צריך...	IDAN_500	17.10.13 00:00	8
שלחתי מייל אם צריך להצביע על ספציפיים או שאפשר להוכיח שקיימים בלי להראות דוגמה	כובען	17.10.13 00:18	9
בכיף	IDAN_500	17.10.13 00:32	10
באופן כללי, אפשר גם להוכיח באמצעות חדוא	zman	17.10.13 01:53	11
אומגה קטן..	inno3D	17.10.13 11:05	12
כן נותנים לנו להוכיח לפי הגדרה לפני שעושים את החיים קלים עם גבולות	כובען	18.10.13 17:58	13

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

18:41 16.10.13

1. אתה יכול להראות בעזרת חישוב גבול...
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
25341 הודעות, 21 פידבק, 10 נקודות

18:42 16.10.13

2. תודה אבל שאלתי לגבי מונוטוניות מסיבה מסויימת..
בתגובה להודעה מספר 1

נשלח ע"י הסלולרי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

18:56 16.10.13

3. אוקיי, שאתה אומר מונוטוניות, אתה צריך להראות בעצם ש f(n) ''גדולה'' אסימפטוטית
בתגובה להודעה מספר 2

מ g(n)
וכן, בדרך כלל צריך להוכיח את זה, בכל דרך שהיא...
אם עדיין לא קלעתי למה ששאלת, אז אשמח אם תוכל להסביר את עצמך שוב

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
25341 הודעות, 21 פידבק, 10 נקודות

19:13 16.10.13

4. תשמע זה בסה''כ השבוע הראשון של הקורס אז יכול להיות שאני מבלבל במוח
בתגובה להודעה מספר 3

אבל מבקשים ממני להוכיח http://i.imgur.com/9XFNRtI.png
לכן לפי הגדרה בעצם עלי להוכיח כי קיימים c,n0 > 0 כך ש:
http://i.imgur.com/KTRyAUX.png
הפונקציה http://i.imgur.com/OxZQZfU.png מונוטונית עולה וחיובית החל מ- n=3
לכן אם נבחר n0 = 3 ו- http://i.imgur.com/XAk4w84.png נקבל שלכל n >= 3
מתקיים http://i.imgur.com/KTRyAUX.png כדרוש.

האם ההוכחה נכונה ומספקת? האם אני צריך להוכיח את המונוטוניות?
או שצריך להגיד שכש-n שואף לאינסוף הביטוי http://i.imgur.com/95VjnMB.png
ולכן עבור הפרמטרים שבחרתי הביטוי נכון?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

20:43 16.10.13

5. את האמת שזה תלוי בתרגיל, אבל
בתגובה להודעה מספר 4

ההוכחה שלך נראית בסדר גמור,
למרות שהיית יכול גם לקצר, ברגע שהגעת לשלב של :c =< n^2/5-1 (סליחה שיצא קצת הפוך),אתה יכול להביא חישוב של הגבול ולהראות שהוא שווה ל 1, ולציין שהחל מ n0 כלשהו, ו c=1 הביטוי הזה יתקיים לכל n>n0.
הקטע פה, שאתה לא חייב בהכרח למצוא את ה n0 הכי קטן ואת c0 הכי קטן.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
25341 הודעות, 21 פידבק, 10 נקודות

23:27 16.10.13

6. תודה רבה :-)
בתגובה להודעה מספר 5

ערכתי לאחרונה בתאריך 16.10.13 בשעה 23:30 בברכה, כובען

אגב C יכול להיות שווה ל-1?
כי LHS רק שואף ל-1 ולא יהיה שווה לו בחיים

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
25341 הודעות, 21 פידבק, 10 נקודות

23:41 16.10.13

7. אגב, לא צריך להצביע על n0 ו-c ספציפיים בהוכחת קיימות?
בתגובה להודעה מספר 5

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

00:00 17.10.13

8. אצלינו לפחות לא היה צריך...
בתגובה להודעה מספר 7

וגם אני לא חושב שתמיד תוכל להצביע על כאלה,
והתבלבלתי סליחה, אתה יכול להגיד ש c שווה לכל מספר שקטן מ 1 (וכמובן גדול מ 0), כי הגבול שם רק ישאף אליו. ובשלב מסויים (כלומר, ב n0 כלשהו) יהיה גדול מ c תמיד לכל n>n0.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
25341 הודעות, 21 פידבק, 10 נקודות

00:18 17.10.13

9. שלחתי מייל אם צריך להצביע על ספציפיים או שאפשר להוכיח שקיימים בלי להראות דוגמה
בתגובה להודעה מספר 8

תודה רבה!

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות, דרג אמינות חבר זה

00:32 17.10.13

10. בכיף
בתגובה להודעה מספר 9

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

zman
חבר מתאריך 18.3.02
974 הודעות, דרג אמינות חבר זה

01:53 17.10.13

11. באופן כללי, אפשר גם להוכיח באמצעות חדוא
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 17.10.13 בשעה 01:57 בברכה, zman

אתה עושה f חלקי g כאשר n שואף לאינסוף
אם יצא לך אינסוף f חזקה יותר
אם יוצא 0 אז g חזקה יותר
אם יוצא מספר קבוע אז זה טטה

בשאלה שלך ייצא 1, לכן זה טטה, ולכן זה אומגה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

inno3D
חבר מתאריך 21.4.02
4544 הודעות, דרג אמינות חבר זה

11:05 17.10.13

12. אומגה קטן..
בתגובה להודעה מספר 11

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
25341 הודעות, 21 פידבק, 10 נקודות

17:58 18.10.13

13. כן נותנים לנו להוכיח לפי הגדרה לפני שעושים את החיים קלים עם גבולות
בתגובה להודעה מספר 11

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד