קונבולוציות, DFT, FFT

Question 1

מהן שתי הדרכים לייצג פולינום?

Answer 1

ניתן לייצג פולינום בעזרת ייצוג מקדמים ובעזרת ערכי נקודות.

Question 2

איך נראה ייצוג על פי ערכים של פולינום?

Answer 2

Question 3

מהו הייתרון הגדול בייצוג פולינומים על פי ערכי נקודות?

Answer 3

Question 4

מהו שורש יחידה מסדר n?

Answer 4

שורש יחידה מסדר n הוא מספר z המקיים: zⁿ = 1.

נוסחת דה-מואבר מאפשר חישוב קל של שורשי יחידה.

Question 5

מהו DFT?

Answer 5

Question 6

מהו אלגוריתם FFT?

Answer 6

Question 7

מהו האלגוריתם FFT^-1?

Answer 7

Question 8

מהו האלגוריתם לכפל מהיר של פולינומים?

Answer 8

Question 9

בכמה זמן נוכל לכפול שני פולינומים?

Answer 9

האלגוריתם לכפל מהיר של פולינומים בעזרת FFT כופל פולינומים ב:

((O(nlog(n.

Question 10

הגדירו:

קונובולוציה

Answer 10

Question 11

מה הקשר בין קונבולוציות וחישוב כפל פולינומים?

Answer 11

Question 12

כמה זמן לוקח לחשב קונבולוציה של שני וקטורים?

Answer 12

Question 13

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

(כאשר שתי המחרוזות מורכבות מהאיברים 1 או (1-) בלבד.)

Answer 13

Question 14

במהלך האלגוריתם שמחזיר את המקומות בהם מחרוזת אחת מופיעה במחרוזת אחרת -

מדוע הופכים את המחרוזת הקטנה?

Answer 14

Question 15

מהו זמן הריצה של האלגוריתם שמוצא את מיקומי הופעות מחרוזת ברציפות בתבנית?

Answer 15

O(nlog(n))

Question 16

יהי j מספר, ויהיו A,B שתי קבוצות מספרים. תהי D הקבוצה המכילה את כל המספרים שהם סכום של איבר מA ואיבר מB.

מה התנאי לכך שj יהיה שייך לD?

Answer 16

Question 17

יהי j מספר, ויהיו A,B שתי קבוצות מספרים.

איך נבטא את מספר הדרכים עבורן j הוא סכום של איבר מA ואיבר מB?

Answer 17

Question 18

יהיו A,B שתי קבוצות מספרים.

תהי D הקבוצה המכילה את כל המספרים שהם סכום של איבר מA ואיבר מB.

תהי i מספר.

תהי m_i מספר הדרכים עבורן i הוא סכום של איבר מA ואיבר מB.

מהו האלגוריתם שמוצא את D ואת m_i?

Answer 18

בבעיות של סכום מהצורה הזו נחשוב להשתמש בקובולוציה.

Question 19

יהיו:

a וקטור עם n איברים

b וקטור עם m איברים

כמה איברים יהיו בקונבולוציה (a♦b)?

Answer 19

m+n

Question 20

Answer 20