Israel Bagrut Computer Science 5 Units key terms

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

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

כתיב חסם עליון אסימפטוטי: f(n)=O(g(n)) אם קיימים קבועים c ו-n0 כך שלכל n>n0 מתקיים f(n)≤c·g(n). משמש לתיאור גידול זמן או זיכרון.

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

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

אלגוריתם למציאת איבר במערך ממוין החוצה את הטווח לחצי בכל צעד. זמן ריצה O(log n) אך דורש מיון מוקדם וגישה ישירה לאיברים.

אלגוריתם מיון רקורסיבי הבוחר איבר ציר, מחלק את המערך לאיברים קטנים וגדלים ממנו, וממיין כל חלק בנפרד. ממוצע O(n log n), מקרה גרוע O(n²).

אלגוריתם מיון המאתר בכל מעבר את האיבר הקטן ביותר ומחליף אותו עם האיבר במקום הנוכחי. זמן ריצה תמיד O(n²) וכמעט ללא זיכרון נוסף.

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

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

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

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

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

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

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

מנגנון שבו מחלקה (בת) מקבלת שדות ושיטות ממחלקה אחרת (אב) ומרחיבה או משנה אותם. מאפשר שימוש חוזר ופולימורפיזם.

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

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

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

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

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

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

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

מבנה נתונים הפועל לפי עקרון נכנס אחרון יוצא ראשון (LIFO). הפעולות הבסיסיות הן דחיפה לראש וה�וצאה מהראש.

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

עץ בינארי שבו כל איבר בצומת שמאלי קטן מהשורש וכל איבר בצומת ימני גדול ממנו. חיפוש ממוצע O(log n) בעץ מאוזן.

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

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

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

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

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

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

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

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

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

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

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

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

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

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