על מנת לערוך סיכומים נדרש לפתוח חשבון.

סיכום למדעי המחשב ב': הבדלים בין גרסאות בדף

קפיצה לניווט קפיצה לחיפוש

סיכום למדעי המחשב ב' (הצגת מקור)

גרסה מ־14:27, 4 ביולי 2007

נוספו 5,329 בתים ,  4 ביולי 2007
אין תקציר עריכה
אין תקציר עריכה
אין תקציר עריכה
שורה 4: שורה 4:


[[Category:מדעי המחשב]]
[[Category:מדעי המחשב]]
ממשק עברי 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 הן התשובות הסופיות.
אוחזר מתוך "https://www.sikumuna.co.il/wiki/מיוחד:השוואה_ניידת/20895"

תפריט ניווט