סיכום למדעי המחשב ב'

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

סיכום למדעי המחשב ב'

ממשק עברי C סבוכיות רשימה - list 1 אתחל_רשימה ß L L=list_init(); O(1) 2 עוגן_רשימה(L) ß p p=list_anchor(L); O(1) 3 סוף_רשימה(L) ß q q=list_end(L); O(1) 4 עוקב_ברשימה(L,p) ß p p=list_next(L,p); O(1) 5 קודם_ברשימה(L,p) ß p p=list_prev(L,p); O(n) 6 הכנס_לרשימה(L,p,x) list_insert(&L,p,x); O(1) 7 הוצא_מרשימה(L,p) list_delete(&L,&p); O(n) 8 עדכן_רשימה(L,p,x) list_update(&L,p,x); O(1) 9 אחזר_מרשימה(L) ß x list_retrieve(L,p,&x); O(1) 10 רשימה_ריקה?(L) ß f f=list_is_empty(L); O(1) מחסנית - stack 11 אתחל_מחסנית(s) ß s s=stack_init(s); O(1) 12 שלוף_ממחסנית(s) ß x x=stack_pop(&s); O(1) 13 הצץ_למחסנית(s) ß x x=stack_top(s); O(1) 14 דחוף_למחסנית(s,x) stack_push(&s,x); O(1) 15 מחסנית_ריקה?(s) ß f f=stack_empty(s); O(1) תור – queue 16 אתחל_תור() ß q q=queue_init(); O(1) 17 הוצא_מתור(q) ß x x=queue_remove(&q); O(1) 18 ראש_התור(q) ß x x=queue_head(q); O(1) 19 הכנס_לתור(x,q) queue_insert(&q,x); O(1) 20 תור_ריק?(q)ß f f=queue_empty(q); O(1)

סיכום פעולות טיפוסי נתונים מופשטים וסבוכיותיהן

ייצוג רשימה

הגדרת טיפוס שדה האינפורמציה: typedef SOMETHING list_info_type;

הגדרת חוליה: struct link_type { list_info_type info; struct link_type *next; }; הגדרת מצביע הרשימה:

typedef struct link_type *pos_type;

הגדרת הרשימה עצמה: typedef struct { pos_type anchor; /* אם צריך יהיו כאן שדות נוספים */ } list_type;

ייצוג מחסנית באמצעות רשימה

הגדרת טיפוס שדה האינפורמציה: typedef list_info_type stack_info_type;

הגדרת המחסנית עצמה typedef list_type stack_type;

ייצוג תור

typdef int queue_info_type;

שיטת המלבנים

הקטע שבו אנו מעוניינים לחשב את השטח שבין גרף הפונקציה לציר הx הוא (a,b) נסמן את מספר המלבנים בN. נסמן בΔx את רוחבו של כל מלבן. מכיוון שכל המלבנים שווים ברוחבם, רוחבו של כל מלבן יהיה Δx=(b-a)/N

נשים לב שגובהו של כל מלבן שווה לערכה של הפונקציה בנקודה שבה נמצא צדו השמאלי של המלבן. לדוג', גובהו של המלבן הראשון שווה לערכה של הפונקציה בנקודה a. מכן נוכל לחשב את השטח:

S = Δx [ƒ(a)+ ƒ(a + Δx)+ ƒ(a + 2Δx )+ … + ƒ(a + (N - 1)Δx)]

מציאת הדיוק E : E ≤ [Max a≤x≤b | ƒ′ (x) | * (b-a) ²] / 2N

או

E ≤ (1/N) * [Max a≤x≤b | ƒ′ (x) | /2] * (b-a)

• בחלק Max a≤x≤b | ƒ′ (x) | מציבים את a ואת b בערך המוחלט של נגזרת הפונקציה ומקבלים את הערך הגבוה מבניהם.

מציאת מספר המלבנים N על מנת להגיע לדיוק E :

N ≥ [Max a≤x≤b | ƒ′ (x) | * (b-a)² ] / 2E

שיטת הטרפזים

הקטע שבו אנו מעוניינים לחשב את השטח שבין גרף הפונקציה לציר הx הוא (a,b) נסמן את מספר המלבנים בN. נסמן בΔx את רוחבו של כל טרפז. מכיוון שכל הטרפזים שווים ברוחבם, רוחבו של כל טרפז יהיה Δx=(b-a)/N

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

Sm = [ƒ(a + (m-1)* Δx) + ƒ(a + m* Δx)] * Δx / 2

S = S1 + S2 + …+ SN

מציאת הדיוק E :

E ≤ √ { [Max a≤x≤b | ƒ″(x) | * (b-a) ³] / 12N }

גלעד וינטרפלד י"א 3

חישוב משוואות

האלימינציה של גאוס-ז'ורדן

צריך להגיע מהמערכת המקורית למטריצת היחידה :

X Y Z X1 Y1 Z1 A X2 Y2 Z2 B X3 Y3 Z3 C X Y Z 1 0 0 X 0 1 0 Y 0 0 1 Z

X, Y ו-Z הן התשובות הסופיות.

שיטת המטריצה ההפוכה

צריך להגיע ממטריצה שצד האחד הוא המשוואה וצדה השני מטריצת יחידה, למטריצה שצדה האחד (שהיה קודם המשוואה) למטריצת היחידה :

X Y Z X1 Y1 Z1 1 0 0 X2 Y2 Z2 0 1 0 X3 Y3 Z3 0 0 1 X Y Z 1 0 0 A1 B1 C1 0 1 0 A2 B2 C2 0 0 1 A3 B3 C3

לאחר שהגענו לשלב השני, אנו כופלים את המטריצה הימנית בוקטור התשובות המקוריות:

A1 * A + A2 * B + A3 * C = X B1 * A + B2 * B + B3 * C = Y C1 * A + C2 * B + C3 * C = Z

כאשר A, B ו-C הן התשובות מוקטור התשובות, וX, Y ו-Z הן התשובות הסופיות.