אוספי נתונים

מדעי מחשב A - AP · נושא 4

הצגת שקפים אימון

שיעור וידאו לנושא זה פתח את עמוד הוידאו

4.1

אתיקה באיסוף נתונים

סיילבוס

מטרת הלמידה 4.1.A: הסבר הסיכונים לפרטיות הנובעים מאיסוף ואחסון נתונים אישיים על מערכות מחשב.

4.1.A.1 בעת שימוש במחשב, הפרטיות האישית נמצאת בסכנה. בפיתוח תוכנות חדשות, תוכנתנים צריכים לנסות לשמור על פרטיות המשתמש.

מטרת הלמידה 4.1.B: הסבר החשיבות בהכרה באיכות הנתונים ובבעיות אפשריות בעת שימוש במאגר נתונים.

4.1.B.1 הטיה אלגוריתמית מתארת טעויות מערכתיות ומחוזקות בתוכנה היוצרות תוצאות לא הוגנות עבור קבוצת משתמשים ספציפית.
4.1.B.2 תוכנתנים צריכים להיות מודעים לשיטת איסוף הנתונים ולסיכון ההטיה בעת שימוש בשיטה זו, לפני השימוש בנתונים לחילוץ מידע חדש או למסקנות.
4.1.B.3 חלק ממאגרי הנתונים הם חסרים או מכילים נתונים לא מדויקים. שימוש בנתונים כאלה בפיתוח או בשימוש בתוכנה עלול לגרום לתוכנה לפעול בצורה לא נכונה או לא יעילה.

מטרת הלמידה 4.1.C: זיהוי מאגר נתונים מתאים לשימוש כדי לפתור בעיה או לענות על שאלה ספציפית.

4.1.C.1 תוכן ערכי הנתונים עשוי להיות קשור לשאלה או נושא ספציפי ועשוי לא להיות מתאים למתן תשובות נכונות או להסקת מידע לשאלה או נושא אחרים.

מקור: תיאור הקורס והמבחן של College Board AP

מארזי שרתים במרכז נתונים — אוסף נתונים גדול מעלה שאלות אתיות לגבי איסוף ושימוש

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

4.2

מדוע אנו זקוקים למבני נתונים

סיילבוס

מטרת הלמידה 4.2.A: להציג דפוסים ואלגוריתמים המשתמשים במאגרי נתונים הנמצאים בחיי היומיום באמצעות כתיבה או דיאגרמות.

4.2.A.1 מאגר נתונים הוא אוסף של פרטי מידע או נתונים ספציפיים.
4.2.A.2 ניתן לבצע עיבוד וניתוח על מאגרי נתונים כדי לפתור בעיה או לענות על שאלה. בעת ניתוח מאגרי נתונים, הערכים בתוך המאגר נגישים ומשתמשים בהם אחד-אחד, ולאחר מכן מעובדים בהתאם לתוצאה הרצויה.
4.2.A.3 ניתן לייצג נתונים בדיאגרמה באמצעות טבלה או גרף. תוכן ויזואלי זה יכול לשמש לתכנון האלגוריתם שיישמש לעיבוד הנתונים.

מקור: תיאור הקורס והמבחן של College Board AP

ארון תיקיות: אוספים מאחסנים ערכים רבים תחת שם אחד כדי שהאלגוריתמים יוכלו לעבדם

משתנה אחד מחזיק ערך אחד; בעיות אמיתיות דורשות אחסון של מספר רב של ערכים קשורים – רשימת תלמידים, פיקסלים, קריאות חיישנים. מבנה נתונים מארגן קבוצה כך נוכל לאחסן, למצוא ולעבד פריטים ביעילות. הקורס AP משתמש בשלושה: מערך, ArrayList, ו-מערך דו-ממדי ⟨2⟩.

מילון מונחים אימון

English	עברית
privacy/ˈprɪvəsi/	פרטיות
consent/kənˈsent/	הסכמה
bias/ˈbaɪəs/	שיפוטיות
data structure/ˈdeɪtə ˈstrʌktʃə/	מבנה נתונים
array/əˈreɪ/	מערך
Traverse/trəˈvɜːs/	עבר
ArrayList/əˈreɪ lɪst/	ArrayList
2D array/ˌtuː ˈdiː əˈreɪ/	מערך 2D
row-major order/rəʊ ˈmeɪdʒə ˈɔːdə/	סדר תלת-ממדי לפי שורות (row-major order)

4.3

יצירת וקריאה ממערך

סיילבוס

מטרת הלמידה 4.3.A: פיתוח קוד המשמש לייצוג אוספים של נתונים קשורים באמצעות אובייקטי מערך חד-ממדי (1D).

4.3.A.1 מערך מאחסן מספר ערכים מאותו סוג. הערכים יכולים להיות ערכים ראשוניים או הפניות לאובייקטים.
4.3.A.2 אורך המערך נקבע בזמן היצירה ואינו ניתן לשינוי. ניתן לגשת לאורך המערך באמצעות ה-stalength attribute.
4.3.A.3 כאשר מערך נוצר באמצעות המילה new, כל האלמנטים שלו מוגדרים לערכים ברירת מחדל של סוג הנתונים של האלמנט. הערך הרירת מחדל עבור int הוא 0, עבור double הוא 0.0, עבור boolean הוא false, ועבור סוג הפניה הוא null.
4.3.A.4 ניתן להשתמש ברשימות מתחילים (initializer lists) ליצור ולאתחל מערכים.
4.3.A.5 סוגריים מרובעים [ ] משמשים לגישה ולשינוי של אלמנט במערכת בעל-ממד 1 באמצעות אינדקס.
4.3.A.6 ערכי האינדקס תקפים למערך הם 0 ועד אחת פחות מאורך המערך, כולל. שימוש בערך אינדקס מחוץ לטווח זה יוביל ל-staArrayIndexOutOfBoundsException.

מקור: תיאור הקורס והמבחן של College Board AP

מערך הוא אוסף מסודר בגודל קבוע של ערכים מאותו סוג. האינדקסים נעים מ-0 עד length - 1:

מערך חד-ממדי (רשימה) עם האינדקסים והגבולות שלו

int[] nums = new int[5];        // five zeros
int[] vals = {3, 1, 4, 1, 5};   // initialized
int first = vals[0];            // 3
int n = vals.length;            // 5 (a field, not a method)

ניסיון לגשת לאינדקס מחוץ ל-0..length-1 גורם לשגיאת ArrayIndexOutOfBoundsException.

4.4

ביקור בכל אלמנט במערך

סיילבוס

מטרת למידה 4.4.A: פיתוח קוד המשמש לעבור על אלמנטים במערכת בעל-ממד 1 וקביעת תוצאת מעברים אלו.

4.4.A.1 עברת מערך היא שימוש בפקודות חזרה כדי לגשת לכל האלמנטים או לסדרה מסודרת של אלמנטים במערך.
4.4.A.2 עברת מערך באמצעות לולאת אינדקס for או לולאת while דורשת גישה לאלמנטים באמצעות האינדקסים שלהם.
4.4.A.3 ראש לולאת增强ed (enhanced) for כולל משתנה, המכונה משתנה לולאת增强ed (enhanced) for. בכל איטרציה של לולאת增强ed (enhanced) for, משתנה לולאת增强ed (enhanced) for מקבל העתק של אלמנט ללא שימוש באינדקס שלו.
4.4.A.4 הקצאת ערך חדש למשתנה לולאת增强ed (enhanced) for אינה משנה את הערך המאוחסן במערך.
4.4.A.5 כאשר מערך מאחסן רפרנסים לאובייקטים, ניתן לשנות את התכונות על ידי קריאת מეთודים על משתנה לולאת增强ed (enhanced) for. הדבר אינו משנה את הרפרנסים לאובייקטים המאוחסנים במערך.
4.4.A.6 קוד שכתוב באמצעות לולאת增强ed (enhanced) for לעבור על אלמנטים במערך יכול להיות מושב באמצעות לולאת אינדקס for או לולאת while.

מקור: תיאור הקורס והמבחן של College Board AP

מעבר במערך באמצעות לולאת for (נותנת את האינדקס) או לולאת enhanced for / for-each (נותנת כל ערך, לקריאה בלבד):

for (int i = 0; i < a.length; i++) { a[i] *= 2; }   // can modify
for (int v : a) { System.out.println(v); }          // read each value

4.5

אלגוריתמים סטנדרטיים למערכות

סיילבוס

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

4.5.A.1 קיימים אלגוריתמים סטנדרטיים המשתמשים בעברות מערך עבור:
- קביעת ערך מינימום או מקסימום
- חישוב סכום או ממוצע
- לקבוע אם לפחות אלמנט אחד בעל תכונה מסוימת
- לקבוע אם לכל האלמנטים יש תכונה מסוימת
- לקבוע את מספר האלמנטים שיש להם תכונה מסוימת
- לגשת לכל הזוגות הרצופים של אלמנטים
- לקבוע את נוכחותם או היעדרם של אלמנטים כפולים
- להזיז או לסובב אלמנטים שמאלה או ימינה
- להפוך את הסדר של האלמנטים

מקור: תיאור הקורס והמבחן של College Board AP

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

int sum = 0;
for (int v : a) sum += v;
double avg = (double) sum / a.length;

4.6

קריאת נתונים מקובץ טקסט

סיילבוס

מטרת הלמידה 4.6.A: פיתוח קוד לקריאת נתונים מקובץ טקסט.

4.6.A.1 קובץ הוא אחסון לנתונים הנשמר גם כאשר התוכנית אינה פעילה. הנתונים בקובץ יכולים להיות נגישים במהלך ביצוע התוכנית.
4.6.A.2 קובץ יכול להתחבר לתוכנית באמצעות מחלקות ה-File וה-Scanner.
4.6.A.3 ניתן לפתוח קובץ על ידי יצירת אובייקט File, תוך שימוש בשם הקובץ כארגומנט לבונה.
- File(String str) הוא הבונה File המקבל שם קובץ String לפתיחה לקריאה, כאשר str הוא נתיב הקובץ.
4.6.A.4 בשימוש במחלקה File, יש להצביע על מה לעשות אם לא ניתן לפתוח את הקובץ עם השם שסופק. אחד הדרכים לעשות זאת הוא להוסיף throws IOException לראש המيثוד המשמש את הקובץ. אם שם הקובץ לא תקין, התוכנית תופסק.
4.6.A.5 מחלקות ה-File וה-IOException הן חלק ממארז ה-java.io. יש להשתמש בפקודה import כדי להפוך מחלקות אלו לזמינות לשימוש בתוכנית.
4.6.A.6 המيثודים הבאים והבונה Scanner—כולל תיאור הפעולה שלהם ומועד השימוש בהם—נכללים ברפרנס מהיר ל-Java:
- Scanner(File f) הוא הבונה Scanner המקבל ⟨File לקריאה.
- int nextInt() מחזיר את ה-int הבא שנקרא מהקובץ או מקור הכניסה אם הוא קיים. אם ה-int הבא לא קיים או מחוץ לטווח, הדבר יוביל ל-InputMismatchException.
- double nextDouble() מחזיר את ה-double הבא שנקרא מהקובץ או ממקור הקלט. אם ה-double הבא לא קיים, יוביל זאת ל-InputMismatchException.
- boolean nextBoolean() מחזיר את ה-boolean הבא שנקרא מהקובץ או ממקור הקלט. אם ה-boolean הבא לא קיים, יוביל זאת ל-InputMismatchException.
- String nextLine() מחזירה את השורה הבאה של טקסט כמחרוזת String שנקראה מהקובץ או ממקור הקלט; יכולה להחזיר מחרוזת ריקה אם נקראה מיד לאחר שיטה Scanner אחרת שקוראת מקובץ או ממקור קלט.
- String next() מחזיר את ה-String הבא שנקרא מהקובץ או ממקור הקלט.
- boolean hasNext() מחזיר true אם קיים פריט נוסף לקריאה בקובץ או במקור הקלט; מחזיר false אחרת.
- void close() סוגר את הסקנר הזה.
- הערה: קבלת קלט מהמקלדת היא מחוץ לתחום ההסתכלות של קורס ובחינת AP Computer Science A.
4.6.A.7 השימוש בnextLine ובשיטות Scanner האחרות יחד על אותו מקור קלט דור לעיתים קודם להתאמה עבור האופן השונה שבו שיטות אלו מטפלות בפסיקאות.
- פקודת הרחקה: כתיבה או ניתוח קוד המשמש גם nextLine וגם שיטות Scanner אחרות על אותו מקור קלט נמצא מחוץ לתחום הסמכות של קורס AP Computer Science A ובחינה.
4.6.A.8 שיטת String נוספת זו – כולל מה שהיא עושה ומתי משתמשים בה – נכללת באוסף העזרה המהיר של Java:
- String[] split(String del) מחזירה מערך String שבו כל אלמנט הוא תת-מחרוזת של this String, שהופרדה סביב התאמות של הביטוי הנתון del.
- הערה: הפרמטר del משתמש בפורמט הנקרא ביטוי רגיל (regular expression). כתיבה או ניתוח קוד המשמש כל אחת מהתכונות המיוחדות של ביטויים רגילים (למשל, \\*, \\.), היא מחוץ לתחום ההסתכלות של קורס ובחינת AP Computer Science A.
4.6.A.9 לולאת while יכולה לשמש לגילוי אם הקובץ עדיין מכיל אלמנטים לקריאה, על ידי שימוש בשיטת hasNext כתנאי הלולאה.
4.6.A.10 יש לסגור קובץ כאשר הגימור של התוכנית. שיטת close מתוך Scanner נקראת כדי לסגור את הקובץ.

מקור: תיאור הקורס והמבחן של College Board AP

File ו-IOException חיים ב-java.io, לכן תוכנית הקוראת קובץ זקוקה ל-import java.io.*;. פתיחת קובץ עלולה להיכשל (הוא עשוי לא להיות קיים), ו-Java מחייבת אותך לטפל בכך – הדרך הפשוטה ביותר היא להוסיף throws IOException לחתימת המетודה. Scanner קורא אחר כך את הקובץ שורה בשורה, תוך שימוש ב-hasNext... לבדיקה לפני הקריאה:

import java.io.*;
...
public static void readFile() throws IOException {
    Scanner f = new Scanner(new File("data.txt"));
    while (f.hasNextLine()) {
        String line = f.nextLine();
    }
}

קריאת טוקנים מעוגנים עם nextInt(), nextDouble() או nextBoolean() מייצרת InputMismatchException אם הטוקן הבא הוא מהסוג הלא נכון – לדוגמה קריאת nextInt() כאשר הדבר הבא בקובץ הוא המילה cat.

4.7

עטיפת מספר באובייקט

סיילבוס

מטרת למידה 4.7.A: פיתוח קוד לשימוש בInteger ובאובייקטי Double ממקבילותיהן הפרימיטיביות וקביעת תוצאת השימוש באובייקטים אלו.

4.7.A.1 המחלקה Integer והמחלקה Double הן חלק מארכיון java.lang. אובייקט Integer הוא בלתי-מתחלף (immutable), כלומר לאחר יצירת אובייקט Integer, תכונותיו אינן ניתנות לשינוי. אובייקט Double הוא בלתי-מתחלף, כלומר לאחר יצירת אובייקט Double, תכונותיו אינן ניתנות לשינוי.
4.7.A.2 Autoboxing הוא ההמרה האוטומטית שמבצע מחלקת Java בין סוגים פרימיטיביים למחלקות העטיפה המתאימות שלהן. הדבר כולל המרת int לInteger והמרת double לDouble. מחלקת Java מפעילה autoboxing כאשר ערך פרימיטיבי הוא:
- עובר כפרמטר לשיטה שמצפה לאובייקט מהמחלקה העטיפה (wrapper class) המתאימה
- מוקצה למשתנה מהמחלקה העטיפה (wrapper class) המתאימה
4.7.A.3 Unboxing הוא ההמרה האוטומטית שמבצע מחלקת Java ממחלקת העטיפה לסוג הפרימיטיבי. הדבר כולל המרת Integer לint והמרת Double לdouble. מחלקת Java מפעילה unboxing כאשר אובייקט ממחלקת עטיפה הוא:
- עובר כפרמטר לשיטה שמצפה לערך מהסוג הגולמי (primitive type) המתאים
- מוקצה למשתנה מהסוג הגולמי (primitive type) המתאים
4.7.A.4 מתודת Integer הקלאס הבאה—כולל מה היא עושה ומתי משתמשים בה—חלק מההפניה המהירה ל-Java:
- static int parseInt(String s) מחזירה את הארגומנט String כ-int.
4.7.A.5 מתודת Double הקלאס הבאה—כולל מה היא עושה ומתי משתמשים בה—חלק מההפניה המהירה ל-Java:
- static double parseDouble(String s) מחזירה את הארגומנט String כ-double.

מקור: תיאור הקורס והמבחן של College Board AP

ArrayList מאחסן אובייקטים, ולא טיפים ראשוניים, ולכן טיפ ראשוני מועטף בתוך אובייקט: Integer מעטף את int, Double מעטף את double. Java עושה זאת באמצעות autoboxing (מ-int ל-Integer) ו-unboxing (חזרה לאחור) אוטומטית, כך שניתן לכתוב list.add(5) ו-int x = list.get(0).

מילון מונחים אימון

English	עברית
autoboxing/ˌɔːtəʊˈbɒksɪŋ/	אוטובוקסינג

4.8

ערכת הכלים של ArrayList

סיילבוס

מטרת הלמידה 4.8.A: פיתוח קוד לקולקציות של אובייקטים קשורים באמצעות אובייקטי ArrayList וקביעת התוצאה של קריאת מתודות על אובייקטים אלו.

4.8.A.1 אובייקט ArrayList הוא משתנה בגודלו ומכיל רעיונות לאובייקטים.
4.8.A.2 בונה ArrayList ArrayList() בונה רשימה ריקה.
4.8.A.3 Java מאפשרת את הסוג הגנרי ArrayList<E>, שבו הפרמטר E מצין את סוג האלמנטים. כאשר ArrayList<E> מצויין, סוגי פרמטרי הרעיון והסוג ההחזרתי בעת שימוש במתודות ArrayList הם סוג E. ArrayList<E> מועדף על פני ArrayList. לדוגמה, ArrayList<String> names = new ArrayList<String>(); מאפשר למורכב להציג שגיאות שהיו נמצאות רק בזמן הרצה.
4.8.A.4 הקלאס ArrayList חלק ממארגון java.util. צריך להשתמש בהצהרה import כדי להפוך קלאס זה לזמין לשימוש בתוכנית.
4.8.A.5 מתודות ArrayList הבאות—כולל מה הן עושות ומתי משתמשים בהן—חלק מההפניה המהירה ל-Java:
- int size() מחזירה את מספר האלמנטים ברשימה.
- boolean add(E obj) מוסיף obj בסוף הרשימה; מחזיר true.
- void add(int index, E obj) מכניס obj במיקום index (0 <= index <= size), מזיז אלמנטים במיקום index ובגבוה יותר ימינה (מוסיף 1 למדגמאות שלהם) ומוסיף 1 לגודל.
- E get(int index) מחזירה את האלמנט במיקום index ברשימה.
- E set(int index, E obj) מחליף את האלמנט במיקום index ב-obj; מחזיר את האלמנט ששכן בעבר במיקום index.
- E remove(int index) מסיר אלמנט ממיקום index, מזיז אלמנטים במיקום index + 1 ובגבוה יותר שמאלה (מפחית 1 מדגמאות שלהם) ומפחית 1 מגודל; מחזיר את האלמנט שהיה במקום index לפני כן.
4.8.A.6 הדגמאות עבור ArrayList מתחילות ב-0 ומסתיימות במספר האלמנטים - 1.

מקור: תיאור הקורס והמבחן של College Board AP

מהו reallyArrayList

ArrayList גדל וקטן כשמוסיפים או מורידים פריטים. הצהר אותו עם סוג האלמנט ב-<>:

ArrayList<String> names = new ArrayList<String>();
names.add("Amy");           // append
names.add(0, "Bob");        // insert at index
names.get(0);               // read
names.set(1, "Cara");       // replace
names.remove(0);            // delete, shifts the rest left
names.size();               // count (a method, unlike array.length)

4.9

סיור בכל רכיב של ArrayList

סיילבוס

מטרת למידה 4.9.A: פיתוח קוד לביצוע איטרציה על מילויי ArrayList וקביעת תוצאות האיטרציות הללו.

4.9.A.1 ביצוע איטרציה על ArrayList מתרחש כאשר משתמשים בפקודות איטרציה או רקורסיביות כדי לגשת לכל המילויים או לסדרה מסודרת מהם ב-ArrayList.
4.9.A.2 מחיקת מילויים במהלך איטרציה על ArrayList דורשת שימוש בטכניקות ייעודיות כדי למנוע דילוג על מילויים.
4.9.A.3 ניסיון לגשת לערך אינדקס החוצה מתחום התקף שלו יוביל ל-IndexOutOfBoundsException.
4.9.A.4 שינוי גודל של ArrayList במהלך איטרציה באמצעות לולאת for מוגברת עשויה להוביל ל-ConcurrentModificationException. לכן, בעת שימוש בלולאת for מוגברת לביצוע איטרציה על ArrayList, אין להוסיף או להסיר מילויים.

מקור: תיאור הקורס והמבחן של College Board AP

טרברס עם לולאת אינדקס או לולאת for-each, בדיוק כמו במערכות (שתמש ב-size() ו-get(i)):

for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }
for (String s : list) { ... }

מיומנות לבחינה: כאשר מסיר פריטים בלולאת אינדקס, או שמלולאת הפוכה או שלא מעלים את i לאחר הרדה – אחרת ההסרה מזיזה רכיבים שמאלה ומדלגים על אחד. ואין להוסיף או להסיר רכיבים בזמן טרברסיה של ArrayList עם לולאת for-each: שינוי הגודל במהלך הלולאה מייצר ConcurrentModificationException, לכן השתמש בלולאת אינדקס (הפוכה, כפי שצוין לעיל) בכל פעם שיש להסיר.

4.10

אלגוריתמים סטנדרטיים של ArrayList

סיילבוס

מטרות למידה 4.10.A: פיתוח קוד לאלגוריתמים סטנדרטיים וחדשניים עבור הקשר או מפרט מסוים המעורבים בArrayList אובייקטים והחלטת התוצאה של אלגוריתמים אלו.

4.10.A.1 ישנם אלגוריתמים סטנדרטיים ArrayList המשתמשים במעברים כדי:
- קביעת ערך מינימום או מקסימום
- חישוב סכום או ממוצע
- לקבוע אם לפחות אלמנט אחד בעל תכונה מסוימת
- לקבוע אם לכל האלמנטים יש תכונה מסוימת
- לקבוע את מספר האלמנטים שיש להם תכונה מסוימת
- לגשת לכל הזוגות הרצופים של אלמנטים
- לקבוע את נוכחותם או היעדרם של אלמנטים כפולים
- להזיז או לסובב אלמנטים שמאלה או ימינה
- להפוך את הסדר של האלמנטים
- להכניס אלמנטים
- למחוק אלמנטים
4.10.A.2 חלק מהאלגוריתמים דורשים מעבר סימולטני על מספר String, אובייקט מארץ, או ArrayList.

מקור: תיאור הקורס והמבחן של College Board AP

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

4.11

רשתות: מערכות דו-ממדיות

סיילבוס

Learning Objective Essential Knowledge

4.11.A
Develop code used to represent collections of related data using two-dimensional (2D) array objects.

4.11.A.1 A 2D array is stored as an array of arrays. Therefore, the way 2D arrays are created and indexed is similar to 1D array objects. The size of a 2D array is established at the time of creation and cannot be changed. 2D arrays can store either primitive data or object reference data.
- Exclusion statement: Nonrectangular 2D array objects are outside the scope of the AP Computer Science A course and exam.
4.11.A.2 When a 2D array is created using the keyword new, all of its elements are initialized to the default values for the element data type. The default value for int is 0, for double is 0.0, for boolean is false, and for a reference type is null.
4.11.A.3 The initializer list used to create and initialize a 2D array consists of initializer lists that represent 1D arrays; for example, int[][] arr2D = { {1, 2, 3}, {4, 5, 6} };.
4.11.A.4 The square brackets [row][col] are used to access and modify an element in a 2D array. For the purposes of the exam, when accessing the element at arr[first][second], the first index is used for rows, the second index is used for columns.
4.11.A.5 A single array that is a row of a 2D array can be accessed using the 2D array name and a single set of square brackets containing the row index.
4.11.A.6 The number of rows contained in a 2D array can be accessed through the length attribute. The valid row index values for a 2D array are 0 through one less than the number of rows or the length of the array, inclusive. The number of columns contained in a 2D array can be accessed through the length attribute of one of the rows. The valid column index values for a 2D array are 0 through one less than the number of columns or the length of any given row of the array, inclusive. For example, given a 2D array named values, the number of rows is values.length and the number of columns is values[0].length. Using an index value outside of these ranges will result in an ArrayIndexOutOfBoundsException.

מקור: תיאור הקורס והמבחן של College Board AP

מערכת 2D היא רשת (שורות ועמודות) – מערכת של מערכות:

מערכת דו-ממדית (טבלה) עם אינדקסים לשורה ועמודה

int[][] grid = new int[3][4];   // 3 rows, 4 columns
grid[r][c] = 7;                 // row r, column c
int rows = grid.length;         // 3
int cols = grid[0].length;      // 4

חקור

מדד מערך דו-ממדי 2 לפי שורה ועמודה

מערך D-2 הוא רשת המיועדת ב[row][col]. הזז את האינדקסים וצפה איזה תא הם בוחרים — שורה קודם, ואז עמודה, שניהם סופרים מ0.

4.12

הליכה דרך רשת

סיילבוס

Learning Objective Essential Knowledge

4.12.A
Develop code used to traverse the elements in a 2D array and determine the result of these traversals.

4.12.A.1 Nested iteration statements are used to traverse and access all or an ordered sequence of elements in a 2D array. Since 2D arrays are stored as arrays of arrays, the way 2D arrays are traversed using for loops and enhanced for loops is similar to 1D array objects. Nested iteration statements can be written to traverse the 2D array in row-major order, column-major order, or a uniquely defined order. Row-major order refers to an ordering of 2D array elements where traversal occurs across each row, whereas column-major order traversal occurs down each column.
4.12.A.2 The outer loop of a nested enhanced for loop used to traverse a 2D array traverses the rows. Therefore, the enhanced for loop variable must be the type of each row, which is a 1D array. The inner loop traverses a single row. Therefore, the inner enhanced for loop variable must be the same type as the elements stored in the 1D array. Assigning a new value to the enhanced for loop variable does not change the value stored in the array.

מקור: תיאור הקורס והמבחן של College Board AP

עבודה על מערך 2-D

ביקור בכל תא באמצעות לולאות פנימיות – החיצונית על שורות, הפנימית על עמודות (סדר טור-עיקרי):

for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
        System.out.print(grid[r][c]);

4.13

אלגוריתמי מערך דו-ממדי ⟨2⟩ סטנדרטיים

סיילבוס

מטרת למידה 4.13.A: פיתוח קוד לאלגוריתמים סטנדרטיים וחדשניים בהקשר או מפרט מסוים המשתמש במערכים בעל-ממד 2 וקביעת תוצאת האלגוריתמים הללו.

4.13.A.1 קיימים אלגוריתמים סטנדרטיים המשתמשים במעבר (traversal) על מערכים בעל-ממד 2 כדי:
- לקבוע ערך מינימום או מקסימום של כל האלמנטים או עבור שורה, עמודה או תת-אזור מוגדר אחר
- לחשב סכום או ממוצע של כל האלמנטים או עבור שורה, עמודה או תת-אזור מוגדר אחר
- לקבוע אם לפחות אלמנט אחד בעל מאפיין מסוים בכל המערכת בעל-ממד 2 או בשורה, עמודה או תת-חלק אחר ממוינת
- לקבוע אם כל האלמנטים במערכת בעל-ממד 2 או בשורה, עמודה או תת-חלק אחר ממוינים הם בעלי מאפיין מסוים
- לקבוע את מספר האלמנטים במערכת בעל-ממד 2 או בשורה, עמודה או תת-חלק אחר ממוינים המצוינים במאפיין מסוים
- לגשת לכל הזוגות הרצופים של אלמנטים
- לקבוע את נוכחותם או היעדרם של אלמנטים כפולים במערכת בעל-ממד 2 או בשורה, עמודה או תת-חלק אחר ממוינים
- להזיז או לסובב אלמנטים בשורה שמאלה או ימינה או בעמודה למעלה או למטה
- להפוך את סדר האלמנטים בשורה או בעמודה

מקור: תיאור הקורס והמבחן של College Board AP

משימות רשת נפוצות: חיבור שורה או עמודה, מציאת הערך המקסימום ברשת, ספירת תאים תואמים, או חיבור אלכסון (כאן r == c). כל אחת מהן היא טרברס פנימי עם תוצאה מצטברת.

4.14

מציאת ערך: חיפוש ליני ואינסולטיבי

סיילבוס

Learning Objective Essential Knowledge

4.14.A
Develop code used for linear search algorithms to search for specific information in a collection and determine the results of executing a search.

4.14.A.1 Linear search algorithms are standard algorithms that check each element in order until the desired value is found or all elements in the array or ArrayList have been checked. Linear search algorithms can begin the search process from either end of the array or ArrayList.
4.14.A.2 When applying linear search algorithms to 2D arrays, each row must be accessed then linear search applied to each row of the 2D array.

מקור: תיאור הקורס והמבחן של College Board AP

חיפוש בינארי: חלוקה לשתיים וכיבוש

חיפוש ליני בודק כל אלמנט בסדר – עובד על כל רשימה, לוקח עד $n$ צעדים.
חיפוש אינסולטיבי עובד רק על רשימה מוסדרת: בודק את האמצע, ולאחר מכן מתעלם מחצית שאינה יכולה להכיל את המטרה, ומשחזר. לוקח כ-$\log_2 n$ צעדים – הרבה מהיר יותר על נתונים גדולים.

חיפוש אינסולטיבי חוצה את הטווח במחצית בכל צעד

חיפוש ליני בודק כל אלמנט בסדר עד שמצוי המטרה

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

מיומנות לבחינה: חיפוש אינסולטיבי דורש נתונים מסודרים; יש לדעת כמה השוואות הוא מבצע וכיצב lo, hi, mid מתעדכנים.

דוגמה מפורטת. חפש את target = 40 ברשימה המוסדרת {3, 9, 14, 23, 31, 42, 55} (אינדקסים 0–6). התחל ב-lo=0, hi=6:

mid = (0+6)/2 = 3, a[3]=23 < 40, ולכן lo = 4;
mid = (4+6)/2 = 5, a[5]=42 > 40, ולכן hi = 4;
mid = (4+4)/2 = 4, a[4]=31 < 40, ולכן lo = 5;
עכשיו lo (5) > hi (4), ולכן הלולאה נגמרת – 40 לא קיים.

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

חקור

השוו חיפוש ליניארי לחיפוש בינארי

חיפוש ליניארי בודק כל אלמנט בתורו; חיפוש בינארי מחצית רשימה מוערכת בכל צעד. צפו כיצד החיפוש הבינארי מגיע למטרה במספר השוואות פחות משמעותי.

מילון מונחים אימון

English	עברית
Linear search/ˈlɪnɪə sɜːtʃ/	חיפוש ליניארי
Binary search/ˈbaɪnəri sɜːtʃ/	חיפוש ביינארי
Selection sort/sɪˈlekʃn sɔːt/	מיון בחירה

4.15

סידור נתונים: מיון בחירה ומיון הכנסה

סיילבוס

מטרות למידה 4.15.A: לקבוע את התוצאה של ביצוע כל שלב באלגוריתמי מיון כדי למיין את אלמנטיה של אוסף.

4.15.A.1 מיון בחירה ומיון הכנסה הם אלגוריתמי מיון איטרטיביים (איטרטיביים) שניתן להשתמש בהם למיין אלמנטים במערך או ArrayList.
4.15.A.2 מיון בחירה בוחר באופן חוזר את האלמנט הקטן ביותר (או הגדול ביותר) מהחלק הלא-מומין של הרשימה ומחליף אותו למיקומו הנכון (וגם הסופי) בחלק המומין של הרשימה.
4.15.A.3 מיון הכנסה מכניס אלמנט מהחלק הלא-מומין של רשימה למיקומו הנכון (אולם לא נרחב הסופי) בחלק המומין של הרשימה על ידי הזזת אלמנטים מהחלק המומין כדי לפנות מקום לאלמנט החדש.

מקור: תיאור הקורס והמבחן של College Board AP

מיון הכנסה

מיון בועות, מעבר אחר מעבר

מיון בחירה מוצא שוב ושוב את הקטן ביותר שנותר ומחליף אותו למקומו.
מיון הכנסה בונה חזית מסודרת, ומכניס כל אלמנט חדש למיקומו הנכון.

מיון הכנסה, המעביר כל מפתח למקומו מעבר לעבר

שניהם פשוטים ודורשים כ-$n^2$ צעדים בממוצע – מתאימים לאריי קטנים. יש להצליח לעקוב אחרי האריי לאחר כל מעבר.

חקור

צפו אלגוריתם מיון מסדר רשימה

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

מילון מונחים אימון

English	עברית
Insertion sort/ɪnˈsɜːʃn sɔːt/	מיון הכנסה

4.16

שיטות הקוראות את עצמן: רקורסיה

סיילבוס

מטרות למידה 4.16.A: לקבוע את התוצאה של קריאת מתודות רקורסיביות.

4.16.A.1 מתודה רקורסיבית היא מתודה הנקראת לעצמה. מתודות רקורסיביות מכילות לפחות מקרה בסיס אחד, המעצור את הרקורסיה, ולפחות קריאה רקורסיבית אחת. רקורסיה היא צורה אחרת של חזרה.
4.16.A.2 לכל קריאה רקורסיבית ישנו ערך עצמי של משתנים מקומיים, כולל הפרמטרים. ערכי הפרמטרים תופסים את התקדמות תהליך רקורסיבי, בדומה לכך שערכי משתנה בקרת מחזור תופסים את התקדמות מחזור.
4.16.A.3 כל פתרון רקורסיבי ניתן לשחזר באמצעות גישת איטרציה ולהפך.
- הצהרת יציאה: כתיבת קוד רקורסיבי אינה בטווח הלימודים של קורס ובחינת AP Computer Science A.

מקור: תיאור הקורס והמבחן של College Board AP

רקורסיה ותור הפקודות

רקורסיה היא שיטה הקוראת את עצמה על קלט קטן יותר. היא דורשת מקרה בסיס שמפסיק את ההתקשרויות, ומקרה רקורסיבי שמקרב אותן למקרה הבסיס:

public static int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

ללא מקרה בסיס הניתן להישג, הרקורסיה לעולם אינה נפסקת (שפל עומס).

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

public static int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;   // same answer, no self-call
    return result;
}

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

חקור

פרקו קריאה רקורסיבית

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

מילון מונחים אימון

English	עברית
Recursion/rɪˈkɜːʃn/	רקורסיה
base case/beɪs keɪs/	מקרה בסיסי

4.17

חיפוש רקורסיבי ומיון מיזוג

סיילבוס

מטרות למידה 4.17.A: לקבוע את התוצאה של ביצוע אלגוריתמים רקורסיביים המשתמשים במילים או באוספים.

4.17.A.1 ניתן להשתמש ברקורסיה כדי לעבור על String אובייקטים, מערכים וArrayList אובייקטים.

מטרות למידה 4.17.B: לקבוע את התוצאה של כל איטרציה של אלגוריתם חיפוש בינארי המשמש לחיפוש מידע באוסף.

4.17.B.1 נתונים חייבים להיות במיון כדי להשתמש באלגוריתם חיפוש בינארי. חיפוש בינארי מתחיל באמצע מערך ממוין או ArrayList ומסיר חצי מהמערך או ArrayList בכל קריאה רקורסיבית עד שמצאים את הערך הרצוי או שנכלו כל האלמנטים.
4.17.B.2 חיפוש בינארי הוא בדרך כלל יעיל יותר מחיפוש ליניארי.
- הצהרת יציאה: אלגוריתמי חיפוש אחרים מחיפוש ליניארי ובינארי אינם בטווח הלימודים של קורס ובחינת AP Computer Science A.
4.17.B.3 אלגוריתם החיפוש הבינארי יכול להיות מוגדר באופן איטרטיבי או רקורסיבי.

מטרת הלמידה 4.17.C: לקבוע את התוצאה של כל איטרציה של אלגוריתם ה-Merge Sort בעת מיון קבוצת נתונים.

4.17.C.1 Mergesort הוא אלגוריתם מיון רקורסיבי שיכול לשמש למיון אלמנטים במערכת או במערכת בעל-ממד ArrayList.
- הערה על היקף: אלגוריתמי מיון אחרים מאלו שנקראו (Selection Sort, Insertion Sort, Merge Sort) אינם נכללים בקורס ובמבחן AP Computer Science A.
4.17.C.2 Merge Sort מחלק באופן חוזר מחדש את המערך לזרים קטנים יותר עד שכל זר מכיל אלמנט אחד בלבד, ולאחר מכן מאחד רקורסיבית את הזרים הממוינים יחד בסדר ממוין כדי ליצור את המערך הסופי הממוין.

מקור: תיאור הקורס והמבחן של College Board AP

מיזוג-סידור: פיצול, ואז מיזוג

רקורסיה מניעה אלגוריתמים יעילים. חיפוש בינארי ניתן לכתיבה רקורסיבית (חיפוש בחצי הנכון). מיזוג מחלק את האריי לחציים, ממין כל חצי רקורסיבית, ולאחר מכן ממזג את שני החצאים הממוינים – תוך כ-$n\log_2 n$ צעדים, מהיר משמעותית מאיחוי או מיון הכנסה על נתונים גדולים.

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

דוגמה פעילה. עקוב אחרי factorial(4). כל קריאה מעוכבת לקריאה קטנה יותר: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) פוגש את המקרה הבסיס ומחזיר 1, ולכן הקריאות מתפרקות פנימה: 2 * 1 = 2, ולאחר מכן 3 * 2 = 6, ולאחר מכן 4 * 6 = 24. כתיבת כל קריאה מעל הערך שהוחזר היא הדרך האמינה לעקוב אחר רקורסיה.

מיומנות במבחן: עקוב אחר שיטה רקורסיבית על ידי כתיבת כל קריאה וערך ההחזרה שלה, ודע כי יעילות המיזוג ($n\log n$) עולה על סיווג פשוטים כמו $n^2$.

מילון מונחים אימון

English	עברית
Merge sort/mɜːdʒ sɔːt/	מיון מיזוג

4.17

טיפים לבחינות

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

שיעורים אינטראקטיביים בנושא זה

לעבור על הדברים צעד אחר צעד, עם תרגילים לבדיקה מיידית.

מבחני עבר

נושאים נוספים במדעי מחשב A - AP