איך מחשב משרטט גרף

[srulikbd]

איך מחשב משרטט גרף../images/Emo35.gif

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

 

[ron369]

יכול להיות

דבר ראשון, שים לב שלא צריך אסימפטוטות, אלא אם כן מדובר במסך אינסופי (נכון?). דבר שני - אין לי ממש מושג

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

 

[vinney]

חישוב נומרי זה בדיוק על ההבדל הדק

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

 

[ron369]

אבל לחשב את הפונקציה בכל נקודה, זה

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

 

[vinney]

מה זה נקודה אצלך?

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

 

[gil levi]

שאלה לך ולרון.

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

 

[gil levi]

בעצם לא נראה שיש דרך אחרת...

 

[vinney]

כמו שאמרתי, אם יש לך פונקציה

אתה יכול להתאים לכל פיקסל אורך את הפיקסל המתאים לגובה. יותר מדויק מזה לא צריך.

 

[גיל14]

ולראיה - זה מה שMatlab עושה.

 

[ron369]

לא צריך יותר מדוייק, אבל זה איטי!

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

 

[vinney]

המון המון? כמה מאות

 

[ron369]

בפונקציה תלת מימדית?

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

(שלא לדבר על אינטגרל של הסינוס של האינטגרל של...)(ולא, אני בהחלט לא ממציא דברים. בהסתברות למשל, שמתי לב שיש חישובים מאדמסובכים)

 

[vinney]

אני לא מבין, מה אתה רוצה להגיד?

חישוב מסובך לוקח זמן לבצע? נכון. אז? שאלת איך עושים את זה, לא כמה זמן זה לוקח.

 

[ron369]

אבל... אנחנו בפורום מדמ"ח.

פה עושים דברים הכי יעיל שאפשר, לא?

 

[vinney]

נכון

גם סיבוכיות של LOG N יכולה לקחת לך שנתיים, השאלה היא מה הN ומה כוח העיבוד שלך

 

[ron369]

אבל LOGN תמיד עדיף על N, לא?

לא חשוב אם N לינארי, אספוננציאלי, כפל אקספוננציאלי, תלת אקספוננציאלי, פונקציית אקרמן, לוגריתמי, lg* , או למשל הפונקציה ההפוכה לפונקציית אקרמן (שאינה lg*!).

 

[ron369]

(וכן-התלהבתי קצת בקורס אלגוריתמיקה)

 

[vinney]

נכון

אבל אתה מדבר על זה שזה לוקח הרבה זמן, לא על עדיפות אסימפטוטית. מעשית גם LOG N יכול לקחת הרבה זמן, אז? על מה כל הדיון הזה שפתחת?

 

[ron369]

שצריך לעשות את זה מהר ככל האפשר

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

 

[ron369]

בעצם, זה איבד כל קשר לדיון המקורי.

צודק.