מציג תוצאות 1 עד 3 מתוך 3

אשכול: אסימפטוטיקה

  1. #1
    משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל אסימפטוטיקה

    בס''ד

    אשמח לפתרון , תודה רבה !
    קבצים מצורפים קבצים מצורפים

  2. #2
    מדריך ויועץ חבר Emath

    פרטי משתמש

    התשובה הטובה ביותר

    ברירת מחדל

    שלום רב,

    סעיף א:

    הטענה נכונה

    היות והטענות דרושות כנראה לחשוב סיבוכיות, נדון במקרה החיובי - ערכי המשתנים והפונקציות הם חיוביים

    מה ההגדרה המתמטית של f שווה ל-o של g?


    $f=o(g(x))\to lim \frac{f(x)}{g(x)}=0, x\to\infty$
    או באופו שקול לכל קבוע c קיים X כך שלכל x>X מתקיים




    $f(x)<c \cdot g(x)$
    או במילים קצב הגידול של f קטן ממש מקצב הגידול של g






    מה ההגדרה המתמטית של f שווה לאומגה קטן של g?
    $f(x)=\omega(h(x))\to lim \frac{f(x)}{g(x)}=\infty, x\to\infty$



    זאת אומרת ש-g זניח אסימפטוטית יחסית ל-f

    בשאלה הנתונה כשנתון
    $h=\omega(1) to lim\frac{h(x)}{1}=\infty, x\to\infty \to limh(x)=\infty, x\to\infty$



    עלינו להוכיח כי
    $f(h(x))=o(g(h(x))$
    או באופן מתמטי
    $lim \frac{f(h(x))}{g(h(x))}=0, x\to\infty$

    נתון כי (h(x שואף לאינסוף כאשר x שואף לאינסוף

    נסמן
    $z=h(x)$
    נקבל שצריך להוכיח כי


    $lim \frac{f(z)}{g(z)}=0, z\to\infty$

    נתון כי










    $f lim \frac{f(x)}{g(x)}=0, x\to\infty$

    מכאן לא משנה איך תתבצע השאיפה לאינסוף. הגבול יהיה 0, בפרט כאשר השאיפה לאינסוף נעשית דרך
    $z=h(x)$



    השואף לאינסוף עש-x שואף לאינסוף

    מכאן
    $lim \frac{f(h(x))}{g(h(x))}=0, x\to\infty \to f(h(x))=o(g(h(x))$

    מש"ל




    סעיף ב:

    הטענה אינה תמיד נכונה

    נסתכל לדוגמא שהפונקציות f ו-g חיוביות(אני מניח שהשאלות נוגעות לחישובי סיבוכיות של אלגוריתמים בהם ערכי המשתנים והפונקציות חיוביים

    כשאומרים

    $f(x)=O(g(x))$
    הכוונה
    $ lim sup \frac{f(x)}{g(x)}<\infty, x\to \infty$



    או באופן שקול קיים קבוע חיובי c כך שעבורו קיים X כך שלכל x>X מתקיים
    $f(x) \leq c \cdot g(x)$

    כלומר עבור ערכי x הולכים וגדולים (f(x קטנה מ-(g(x עד כדי כפל בקבוע


    אפשר להגדיר פונקציה נגדית אט להראות שרטוט גרף

    נגדיר פונקציות f ו-g באופן הבא, כך באינסוף קטעים המנה של f עם g שואפת לאינסוף ואינסוף קטעים בהם המנה של g ו-f שואפת לאינסוף

    לדוגמא נגדיר f,g באופן הבא
    $0 \leq x <1, f(x)=x, g(x)=x^2$
    $1 \leq x <2, f(x)=x^4, g(x)=x^3$
    $2 \leq x <3, f(x)=x^5, g(x)=x^6$
    $3 \leq x <4, f(x)=x^8, g(x)=x^7$


    $...$
    ברור כי הפונקציות מונוטוניות, כאשר x שואף לאינסוף
    $x^{n+1}>x^n$

    אבל רואים מעצם הגדרת הפונקציות ישנם אינסוף קטעים כאשר אם x שואף דרכם לאינסוף
    $\frac{f(x)}{g(x)}\to\infty$

    וישנם אינסוף קטעים כאשר אם x שואף דרכם לאינסוף




    $\frac{g(x)}{f(x)}\to\infty$

    כלומר
    $ lim sup \frac{f(x)}{g(x)}= lim sup \frac{g(x)}{f(x)}=\infty, x\to \infty$

    כלומר לא מתקיים

    $f(x)=O(g(x)), g=O(f(x))$

    אפשר גם לתת דוגמא גרפית בלי לתת ביטוי לפונקציות

    בשרטוט הנ"ל הפונקציות מונוטוניות, אבל השיפועים משתנים לסירוגין. במקטע מסויים f נניח בשיפוע 5 ו-g בשיפוע קטן יותר נניח 2. מנקודת הפגישה השיפוע של g גדול יותר נניח 7 ושל f קטן יותר נניח 5. כלומר לסירוגין פעם הגרף של f מעל הגרף של g ופעם הגרף של g מעל הגרף של f. לכן לא קיים X כזה שהחל ממנו
    (f(x קטנה מ-(g(x עד כדי כפל בקבוע וההפך
    לא מתקיים כאן לפי ההגדרה
    $f(x)=O(g(x))$
    או
    $g(x)=O(f(x))$

    ולכן הטענה אינה נכונה במקרה הזה

    בברכה,
    עמוס

    graph1.jpg
    נערך לאחרונה על ידי am12348, 05-09-2019 בשעה 15:26
    אהבתי Xtazi, אריאל אהב \ אהבו את התגובה
     

  3. #3
    משתמש רשום חבר Emath

    פרטי משתמש

    ברירת מחדל

    תודה רבה על התשובה המפורטת !!!!!

מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 9

הרשאות

  • אתה לא יכול לפרסם אשכולות חדשים
  • אתה לא יכול לפרסם תגובות
  • אתה לא יכול לצרף קבצים להודעותיך
  • אתה לא יכול לערוך את הודעותיך
  •  
אודות Emath
האתר Emath הינו יוזמה פרטית והוקם בתחילת שנת 2008 .
מטרתנו הינה למנף את הישגי התלמידים למתמטיקה ופיסיקה בארץ בכלל ובפרט בקרב תלמידי התיכון .
אנו מספקים מספר שירותים לתלמיד, ביניהם גישה למאות אלפי פתרונות איכותיים לתרגילים, פורום עזרה במתמטיקה ופיסיקה הגדול מסוגו בארץ, מאגר סיכומים, מרתונים בוידאו, פתרונות לבגרויות ועוד.
כלים אלו, מאפשרים לכל אחד, ללא תלות במיקומו, ללמוד, לתרגל ולהתמקצע על-מנת להתכונן בצורה מיטבית לבגרות במתמטיקה או פיסיקה .

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו