stanford-oval/wikipedia huggingface dataset:
אנליזה של אלגוריתמים

אנליזה (ניתוח) של אלגוריתמים הוא תחום במדעי המחשב, העוסק בגילוי מאפיינים שונים באלגוריתמים, וסיווג רמת החיסכון שלהם במשאבים, כלומר קביעת כמות המשאבים הנדרשים עבור ביצועו.
בדרך-כלל, יעילותו של אלגוריתם תלויה במספר הצעדים (זמן המורכבות) ובשטח האחסון (מורכבות אחסון) הנדרשים.
המונח "ניתוח אלגוריתמים" נטבע על ידי דונלד קונת'. ניתוח אלגוריתמים הוא חלק חשוב של תאוריה רחבה יותר הנקראת תורת הסיבוכיות, אשר מספקת הערכות תאורטיות לכמות המשאבים הדרושים לכל אלגוריתם הפותר בעיה חישובית נתונה. הערכות אלו מספקות תובנות חשובות באשר לחיפוש אחר אלגוריתמים יעילים יותר ויותר.
בניתוח תאורטי של אלגוריתמים, נהוג להעריך את המורכבות שלהם במובן אסימפטוטי. כלומר, להעריך את מורכבות האלגוריתם עבור קלט שרירותי גדול. סימון O גדולה [ O], סימון אומגה גדול [ \Omega ] וסימון טטא גדול [ \Theta ] משמשים למטרה זו. למשל, חיפוש בינארי הוא חיפוש האמור לרוץ מספר צעדים, יחסי ללוגריתם של אורך הרשימה הממוינת שבה מתבצע החיפוש, או ב-  O(log(n)), ב"זמן לוגריתמי".
ממד יעילות מדיוק (לא אסימפטוטי) ניתן לחישוב במקרים מסוימים אך בדרך כלל הוא דורש הנחות מסוימות לגבי יישום מסוים של האלגוריתם, הנקרא מודל של מחשוב. מודל של מחשוב עשוי להיות מוגדר במונחים של מחשב אבסטרקטי, למשל, מכונת טיורינג, או על ידי הנחה כי פעולות מסוימות מבוצעות ביחידת זמן.
לדוגמה, אם ברשימה הממוינת עליה אנו מריצים חיפוש בינארי יש n אלמנטים, ואנחנו יכולים להבטיח כי כל בדיקה של אלמנט ברשימה יכולה להתבצע תוך יחידת זמן, אז צריך לכל היותר log2 n + 1 יחידות זמן להחזיר תשובה.
דגמי עלויות

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

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

כיוון שאלגוריתמים הם תלויי פלטפורמה (כלומר, אלגוריתם נתון יכול להיות מיושם בשפת תכנות שרירותית במחשב שרירותי ועל מערכת ההפעלה שרירותית), יש חסרונות משמעותיים לשימוש בגישה אמפירית למדידת הביצועים היחסיים של סט נתון של אלגוריתמים.
ניתן לקחת כדוגמה תוכנה המחפשת ערך מסוים רשימה ממוינת בגודל n. נניח שתכנה זו הושמה על מחשב א', מחשב חדיש עם חומרה מרמה גבוהה, תוך שימוש באלגוריתם חיפוש ליניארי, ועל מחשב ב', אשר איטי בהרבה מן המחשב הקודם, באמצעות אלגוריתם חיפוש בינארי. בוחן ביצועים על שני המחשבים המריצים את התוכנה בהתאמה עשוי לקבל את הממצאים הבאים:
| n (גודל רשימה) | זמן ריצה של מחשב א'  (ננו שניות) | זמן ריצה של מחשב ב'  (ננו שניות) |
| --- | --- | --- |
| 16 | 8 | 100,000 |
| 63 | 32 | 150,000 |
| 250 | 125 | 200,000 |
| 1,000 | 500 | 250,000 |
בהתבסס על ערכים אלה, זה ניתן לקפוץ למסקנה כי על מחשב א' פועל אלגוריתם יעיל בהרבה מיעילות של האלגוריתם של מחשב ב'. עם זאת, אם נגדיל את גודל הקלט בצורה מספקת, מסקנה זו הוא מוכחת להיות שגיאה:
| n (גודל רשימה) | זמן ריצה של מחשב א'   (ננו שניות) | זמן ריצה של מחשב ב'  (ננו שניות) |
| --- | --- | --- |
| 16 | 8 | 100,000 |
| 63 | 32 | 150,000 |
| 250 | 125 | 200,000 |
| 1,000 | 500 | 250,000 |
...
1,000,000: 500,000
| 4,000,000 | 2,000,000 | 550,000 |
| 16,000,000 | 8,000,000 | 600,000 |
...
| 63,072 × 1012 | 31,536 × 1012 ns,  או 1 שנה | 1,375,000 ns,  או 1.375 מילישניות. |
מחשב א', מריץ את תוכנת החיפוש הליניארי, ומראה קצב גידול ליניארי. זמן הריצה של התוכנה הוא בעל יחס ישיר לגודל הקלט שלה. הכפלת גודל הקלט מכפיל את זמן הריצה, הכפלה פי ארבעה של גודל הקלט מכפילה פי ארבעה את זמן הריצה וכו' . מצד שני, מחשב ב', מריץ תוכנת חיפוש בינארי, ומראה קצב גידול לוגריתמי. הכפלת גודל הקלט פי ארבעה מגדיל את זמן הריצה על ידי קבוע בלבד (בדוגמה זו, 50,000 ns). אף על פי שמחשב א' מהיר יותר, מאשר מחשב ב'. מחשב ב' יתגבר על מחשב א' באופן בלתי נמנע ביעילות זמן ריצה מפני שהאלגוריתם שהוא מריץ בעל קצב גידול נמוך בהרבה.
ניתוח זמן ריצה > רמות של קצב גידול

באופן לא רשמי, ניתן לומר כי אלגוריתם מציג צמיחה בשיעור מסדר גודל של פונקציות מתמטיות אם עבור קלט מסוים בגודל n, פונקציה  f(n) כפול קבוע חיובי מספקת את החסם העליון או הגבול של זמן הריצה של האלגוריתם. במילים אחרות, עבור גודל קלט n אשר גדול יותר מ-n0 וקבוע c, זמן הריצה של אלגוריתם לעולם לא יהיה גדול מאשר  c\times f(n). ביטוי זה מיוצג לעיתים קרובות על ידי סימון O גדולה. לדוגמה, כיוון שזמן הריצה של מיון הכנסה גדל בצורה מרובעת כמו שלה הקלט גדל, ההכנסה סוג יכול להיות אמר להיות של סדר O(n2).
סימון O גדולה הוא דרך נוחה כדי לבטא את התרחיש הגרוע ביותר עבור אלגוריתם נתון, אף על פי שזה יכול לשמש גם כדי להביע את המקרה הממוצע — לדוגמה, התרחיש הגרוע ביותר עבור quicksort הוא O(n2), אבל זמן הריצה עבור המקרה הממוצע הוא O(n log n).
ניתוח זמן ריצה > רמות אמפיריות של קצב גידול

תחת ההנחה שזמן הביצוע עוקב אחר כלל הכוח, t\approx k*n^{a}, ניתן למצוא את המקדם על ידי לקיחת מדידות אמפיריות של זמן ריצה  \{t_{1},t_{2}\} על נקודות בעלות גודל בעייתי  \{n_{1},n_{2}\} וחישוב  t_{2}/t_{1}=(n_{2}/n_{1})^{a} כך  a=\log(t_{2}/t_{1})/\log(n_{2}/n_{1}). במילים אחרות, זה מודד את השיפוע של קו אמפירי על log-log plot של זמן הביצוע לעומת גודל הבעיה, בנקודת גודל כלשהי. אם רמת הצמיחה אכן מלווה את כלל הכוח (אזי הקו על log-log-plot אכן קו ישר), הערך האמפירי של a יישאר קבוע בטווחים שונים, ואם לא, הוא ישתנה (ואז הקו הוא קו מעוגל) - אבל זה עדיין יכול לשמש להשוואה של כל שני אלגוריתמים נתונים בהתחשבות בהתנהגות של רמות קצב גידול מקומיות אמפיריות. ובהחלה על הטבלה מלעיל:
| n (גודל רשימה) | זמן הריצה של מחשב A  (ננו שניות) | רמת קצב גידול מקומית  (n^_) | זמן הריצה של מחשב B  (ננו שניות) | רמת קצב גידול מקומית  (n^_) |
| --- | --- | --- | --- | --- |
| 15 | 7 | 100,000 |  |  |
| 65 | 32 | 1.04 | 150,000 | 0.28 |
| 250 | 125 | 1.01 | 200,000 | 0.21 |
| 1,000 | 500 | 1.00 | 250,000 | 0.16 |
| ... | ... | ... |  |  |
| 1,000,000 | 500,000 | 1.00 | 500,000 | 0.10 |
| 4,000,000 | 2,000,000 | 1.00 | 550,000 | 0.07 |
| 16,000,000 | 8,000,000 | 1.00 | 600,000 | 0.06 |
| ... | ... | ... |  |  |
קל לראות כי האלגוריתם הראשון מראה קצב גידול ליניארי אשר בבירור עוקב אחרי כלל הכוח. הערכים האמפיריים עבור השני הולכים ופוחתים במהירות, מה שרומז כי האלגוריתם השני עוקב אחרי חוק אחר של קצב גידול ובכל מקרה יש לו רמות קצב גידול מקומיות הרבה יותר נמוכות (אשר עדיין משתפרות), באופן אמפירי, מאשר לאלגוריתם הראשון.
ניתוח זמן ריצה > הערכת סיבוכיות זמן ריצה

את מורכבות זמן הריצה למקרה הגרוע ביותר של אלגוריתם נתון ניתן לעיתים להעריך על ידי בחינת המבנה של האלגוריתם ולקיחת מספר הנחות מפשטות. נתבונן ב-pseudocode הבא:
(* get a positive integer from input *)
if n > 10
 write 'This might take a while...'
for i = 1 to n
 for j = 1 to i
 write i * j
write 'Done!'
מחשב נתון ייקח כמות הזמן בדידה לביצוע כל הפקודות המעורבות עם ביצוע האלגוריתם הזה. כמות הזמן המסוימת כדי לבצע פקודה נתונה ישתנו בהתאם לפקודה אשר מתבצעת, ועל פי איך המחשב מבצע אותה, אבל על מחשב רגיל, כמות זמן זו היא דטרמיניסטית (המקרה שונה במקרה של מחשב קוונטי). נניח כי הפעולות שבוצעו בשלב 1 נחשבות צורכות זמן T1, אלה שבשלב 2 צורכות זמן T2, וכך הלאה.
באלגוריתם לעיל, שלבים 1, 2 ו-7 ירוצו פעם אחת בלבד. עבור הערכה של המקרה הגרוע ביותר, יש להניח כי שלב 3 יורץ גם הוא. לפיכך, הסכום הכולל של זמן כדי להריץ את צעדים 1–3 וצעד 7 הוא:
את הלולאות בשלבים 4, 5 ו-6 יותר מסובך להעריך. החיצונית בשלב 4 תרוץ (n + 1)
פעמים (שימו לב כי צעד נוסף נדרש כדי לסיים את ללולאה, ולכן 1 + n ולא n ריצות), אשר יצרכו T4(n + 1) זמן. הלולאה הפנימית, לעומת זאת, נשלטת על ידי הערך של i, אשר נע מ-1 עד i. במעבר הראשון דרך הלולאה החיצונית. j. נע מ-1 ל-1: הלולאה הפנימית רצה פעם אחת, אז הרצת הלולאה הפנימית (שלב 6) צורכת T6, והלולאה הפנימית (שלב 5) צורכת 2T5. זמן. במעבר הבא דרך הלולאה החיצונית. j. נע מ-1 ל-2: לולאה הפנימית רצה פעמיים, אז הרצת הלולאה הפנימית (שלב 6) צורכת 2T6, והלולאה הפנימית (שלב 5) צורכת 3T5 זמן.
בסך הכל, כל הזמן הנדרש כדי להפעיל את הלולאה הפנימית יכול לבוא לידי ביטוי כהתקדמות אריתמטית:
אשר יכול להתווסף כפקטור כך
 1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}
את הסך כל הזמן הנדרש כדי להפעיל את הלולאה החיצונית ניתן להעריך באופן דומה:
אשר יכול להתווסף כפקטור כך
לכן, סה"כ זמן ריצה עבור אלגוריתם זה הוא:
אשר יורד עד כדי
ככלל אצבע, ניתן להניח שהסדר הגבוה ביותר בכל פונקציה שולט בקצב הצמיחה, ובכך מגדיר את סדר זמן הריצה. בדוגמה זו, n^2 הוא הסדר הגבוה ביותר, אז ניתן להסיק כי f(n) = O(n2). באופן רשמי, זה יכול להיות מוכח, כדלקמן:
Prove that  \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}
{\begin{aligned}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\\leq &(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ ({\text{for }}n\geq 0)\end{aligned}}
Let k be a constant greater than or equal to [T1..T7]
{\begin{aligned}&T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k\\=&2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}
Therefore  \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1
גישה יותר אלגנטית לניתוח אלגוריתם זה תהיה להכריז כי [T1..T7] כל אחד שווים יחידת זמן אחת, במערכת של יחידות שנבחרו, כך שיחידה אחת הוא גדול או שווה לזמן בפועל פעמים של שלבים אלה. כלומר שזמן הריצה של האלגוריתם מחושב כדלקמן:
4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}n\geq 1)=O(n^{2}).
ניתוח זמן ריצה > ניתוח קצב גידול של משאבים אחרים

ניתן להשתמש במתודולוגיה של ניתוח זמן ריצה לחישוב וחיזוי של קצבי הגידול של משאבים אחרים כגון צריכת זיכרון. כדוגמה, נתבונן ב־pseudocode אשר מנהל וממקם מחדש את השימוש בזיכרון על ידי תכנה, בהתבסס על הגודל של הקובץ אשר התכנה מנהלת:
()
במקרה הזה, ככל שגודל הקובץ n גדל, הזיכרון נצרך בקצב גידול מעריכי, אשר מסדר O(2n). זה מאוד מהיר ורוב הסיכויים קצב גידול לא ניתן לניהול של שימוש משאבי זיכרון.
רלוונטיות

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

אנליזה של אלגוריתמים בדרך כלל מתמקדת בביצועים אסימפטוטיים, במיוחד ברמה הבסיסית, אבל ביישומים מעשיים גורמים קבועים הם חשובים, ונתונים בעולם האמיתי תמיד מוגבלים בגודל בפועל. הגבול הוא בדרך כלל בגודל של זיכרון השמיש, אז על מערכות של 32 סיביות 232 = 4 GiB (או יותר אם מזיכרון מקוטע), ובמערכות של-64 סיביות 264 = 16 EiB. לפיכך תחת גודל מוגבל, סדר הגודל (זמן או מקום) יכול להיות מוחלף על ידי גורם קבוע, ובמובן זה כל האלגוריתמים המעשיים הם O(1) עבור קבוע מספיק גדול, או גודל נתונים קטן מספיק.
פרשנות זו היא יעילה בעיקר עבור פונקציות הגדלות לאט מאוד: (בינארית) הלוגריתם החוזר (log*) הוא פחות מ-5 לכל כמות נתונים מעשית (265536 ביטים); (בינארי) log-log (log log n) הוא פחות מ-6 לכמעט כל כמות נתונים מעשית (264 סיביות); ובינארית (log (log n) הוא פחות מ-64 לכמעט כל כמות נתונים מעשית (264 סיביות). אלגוריתם עם מורכבות שאינה קבועה עשוי בכל זאת להיות יותר יעיל מאשר אלגוריתם קבוע על נתונים פרקטיים אם החסם העליות של הזמן הקבוע יוצר תוצאה קבועה גדולה יותר לדוגמה יכול להיות  K>k\log \log n כל עוד  K/k>6 ו- n<2^{2^{6}}=2^{64}.
עבור כמות גדולה של מידע לא ניתן להתעלם מגורמים ליניאריים או ריבועיים, אבל עבור כמויות קטנות של מידע אלגוריתם לא יעיל אסימפטוטית להיות יעיל יותר. זה במיוחד בשימוש במקרה של אלגוריתמים היברידיים, כמו Timsort, אשר משתמש באלגוריתם לא יעיל אסימפטוטית (כאן במיון מיזוג, עם מורכבות הזמן  n\log n), אבל מחליף לאלגוריתם יעיל אסימפטוטית (כאן מיון החדרה, עם מורכבות הזמן  n^{2}) עבור כמות נתונים קטנה, כיוון שהאלגוריתם הפשוט יותר הוא מהיר יותר על כמות קטנה של נתונים.
ראו גם

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

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Chapter 1: Foundations (Second ed.). Cambridge, MA: MIT Press and McGraw-Hill. pp. 3–122. ISBN 0-262-03293-7.
Sedgewick, Robert (1998). Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-31452-6.
Knuth, Donald. The Art of Computer Programming. Addison-Wesley.
Greene, Daniel A.; Knuth, Donald E. (1982). Mathematics for the Analysis of Algorithms (Second ed.). Birkhäuser. ISBN 3-7643-3102-X.
Goldreich, Oded (2010). Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0.
הערות שוליים

↑  Donald Knuth, Recent News
↑  Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The design and analysis of computer algorithms. Addison-Wesley Pub. Co.
↑  Juraj Hromkovič (2004). Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. pp. 177–178. ISBN 978-3-540-14015-3.
↑  Giorgio Ausiello (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. pp. 3–8. ISBN 978-3-540-65431-5.
↑  Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, p. 20, ISBN 978-3-540-21045-0
↑  Robert Endre Tarjan (1983). Data structures and network algorithms. SIAM. pp. 3–7. ISBN 978-0-89871-187-5.
↑  Examples of the price of abstraction?, cstheory.stackexchange.com
↑  How To Avoid O-Abuse and Bribes, at the blog "Gödel’s Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick
| תחומים במדעי המחשב |
| --- | --- | --- |
| יסודות מתמטים | לוגיקה מתמטית • תורת הקבוצות • תורת המספרים • תורת הגרפים  • תורת הטיפוסים •  תורת הקטגוריות  • אנליזה נומרית • תורת האינפורמציה |  |
| תורת החישוביות | תורת האוטומטים • תורת הרקורסיה • תורת הסיבוכיות • מחשוב קוונטי |  |
| אלגוריתמים ומבנה נתונים | אנליזה של אלגוריתמים • גאומטריה חישובית |  |
| שפות תכנות ומהדרים | מפרש • פרדיגמת תכנות (תכנות פרוצדורלי • תכנות מונחה עצמים • תכנות פונקציונלי • תכנות לוגי) |  |
| חישוב מבוזר ועיבוד מקבילי | עיבוד מקבילי • מחשוב סריגי • בקרת מקביליות |  |
| הנדסת תוכנה | ניתוח מערכות מידע • עיצוב תוכנה • תכנות מחשבים • שיטות פורמליות • בדיקות תוכנה • מתודולוגיית פיתוח תוכנה |  |
| תקשורת | ניתוב • טופולוגיית רשת • קריפטוגרפיה |  |
| מסד נתונים | מסד נתונים יחסי • SQL • תנועה • אינדקסים • כריית מידע • CAP theorem |  |
| בינה מלאכותית | חשיבה אוטומטית • בלשנות חישובית • ראייה ממוחשבת • עיבוד שפה טבעית • בינה חישובית • מערכת מומחה • למידה חישובית • רובוטיקה |  |
| גרפיקה | הדמיה ממוחשבת • הנפשה ממוחשבת • עיבוד תמונה |  |
| שפות פורמליות | שפה רגולרית • שפה חסרת הקשר • שפה תלוית הקשר • ההיררכיה של חומסקי |  |
| שימושים במדע | ביואינפורמטיקה • מדעים קוגניטיביים • כימיה חישובית • פיזיקה חישובית • אנליזה נומרית |  |
השוואת סיבוכיות
צ'חצ'ח

צ'חצ'ח הוא כינוי גנאי בסלנג שמייחס התנהגות פרחחית, שובבה וחסרת נימוס – ילד, נער או אדם צעיר בריון ופרוע חסר דרך ארץ. הכינוי הוא ספציפי ליוצאי אזור מסוים, ובעיקר התהווה למול עולים יוצאי עיראק, שהדיאלקט הערבי שלהם מבטא את האות ك (כאף- כ') כהגייה צ', וכן בשל השימוש בח' גרונית, ולאחר מכן הורחב לעולים מארצות ערב (באופן דומה, המילה "ווזווז", מתארת עולים דוברי יידיש)
הכינוי ככל הנראה מבוסס על האופן שבו נשמע דיבורם של עולים מארצות האסלאם, שבו בולטות אותיות כמו צ' ו-ח', באוזני העולים מיהדות אירופה. במובן זה, הכינוי דומה לכינוי ברברים שהמציאו היוונים ביוון העתיקה להגדרת מי שאינם יוונים.[דרוש מקור] בשני המקרים, התבסס הכינוי על רעיון אונומטופאי דומה של חיקוי להג בלתי מוכר ("ווזווז" - מלשון המילה היידית וואָס [מבוטאת אצל יוצאי פולין ווּס - vus], שפירושה "מה", הוא שם גנאי לאשכנזי, שנוצר בדרך דומה). במילונם של דן בן אמוץ ונתיבה בן-יהודה, "מילון עולמי לעברית מדוברת", מוגדרת המילה צ'חצ'ח כ"כינוי ליוצא צפון אפריקה".
"נאום הצ'חצ'חים"

הכינוי רווח בישראל לפחות משנות השבעים וזכה לפרסום רב במהלך הבחירות לכנסת העשירית בשנת 1981, כאשר הבדרן דודו טופז השתמש בו בנאום בעצרת בחירות של המערך שנערכה בכיכר מלכי ישראל ב-26 ביוני 1981 (שלושה ימים לפני הבחירות). טופז אמר: "תענוג לראות את הקהל הזה, ותענוג לראות שאין כאן צ'חצ'חים שהורסים אספות בחירות... הצ'חצ'חים הם במצודת זאב. הם בקושי שין גימלים, אם הם בכלל הולכים לצבא. כאן נמצאים החיילים ומפקדי היחידות הקרביות". דבריו זכו לתשואות בעצרת. "הארץ" דיווח על דבריו הבוטים של טופז ועמד על משמעותם, והיה העיתון היחיד שעשה זאת.
למחרת נערכה במקום עצרת בחירות של המפלגה המתחרה, הליכוד, שבה מתח מנחם בגין ביקורת חריפה על האמירה הזו באומרו: "עד אתמול לא הכרתי את המלה צ'חצ'חים, אך אמש שמעתי את הבדרן..." וכאן הסתכל בגין בדף להיזכר בשם שקרא במלעיל ובעילגות מכוונת "דודו טופז", והמשיך: "...מכנה את אנשי הליכוד צ'חצ'חים". בגין פירש את דבריו של דודו טופז כמופנים בעיקר כלפי עדות המזרח, שנתפשו באותה תקופה כמצביעי ליכוד, והבליט בדבריו את היחס השונה של מפלגתו לעולים מארצות המזרח. הוא סיפר על עולי הגרדום, פיינשטיין וברזני - "הם פתחו בלבותיהם רימון יד: לחצו! אשכנזים? עיראקים? יהודים! אחים! לוחמים!". הוא אף קרא לנוכחים להתקשר אל כל מכריהם ברחבי הארץ: "רק תספרו להם מה אמר פה דודו טופז, כל העם חייב לדעת את זאת. זה משפט אחד בסך-הכל: הצ'חצ'חים כולם במצודת זאב. אשרינו שהם במצודת זאב".
בגין גם תקף את חברי המערך מעדות המזרח, ובמיוחד את חברת הכנסת שושנה ארבלי-אלמוזלינו, אשר לטענתו היו צריכים למחות על הפגיעה בעדות המזרח כפגיעה אישית. דבריו של בגין באו כשמן על מדורת עימות שיסודו עדתי במהלך מערכת הבחירות של 1981, שהייתה מערכת בחירות מהאלימות ביותר. יש המייחסים לדבריו תרומה מסוימת לניצחונו של הליכוד בבחירות אלו.
שימושים בולטים נוספים

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

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

ערס
פרחה
פקצה
ווזווז
חוליגניות
לקריאה נוספת

רפי מן, לא יעלה על הדעת – ציטוטים, ביטויים, כינויים ומטבעות לשון, הד ארצי הוצאה לאור, 1998, הערך "צ'חצ'חים", עמ' 253-252
הערות שוליים

↑  אמנון ברזילי, אמת, באתר העין השביעית, 30 ביוני 2011
↑  אחרי ההתבטאות הגזענית: משפחתו של גרוניך מסבירה שהוא סובל מדמנציה, נבדק ב-2022-04-21
שמחה

.
.
ילדה מביעה שמחה באמצעות חיוך
נזיר בודהיסטי שמח
שִׂמְחָה היא רגש חיובי שבו האדם נתון במצב רוח טוב ומרומם. לרוב בעקבות התרחשות או חוויה אותה הוא מפרש כחיובית מבחינתו באחד מהיבטי חייו, או בעקבות היזכרות בחוויה כזו.
השמחה יכולה להשתנות בעוצמתה לפי עוצמת ההתרחשות או הרגש – משמחה פשוטה המתבטאת כשביעות רצון עבור דבר שיכול להיות בעל משמעות קטנה בחיי האדם, ועד שמחה עוצמתית ומציפה, למשל אדם שפוגש אהוב אחרי שנים רבות, או אדם שצפייה מאוד משמעותית בחייו מתגשמת.
השמחה מקושרת עם רגשות חיוביים אחרים ועוצמתה תהיה קשורה בהם, כמו תחושת חופש, עצמאות, הגשמה עצמית, אהבה, אנרגטיות, תחושה של מוגנות ושייכות, ועוד. הרגש ההופכי לשמחה הוא העצב.
השפה העברית עשירה במילים המתארות שמחה: ששון, גילה, דיצה, רינה, עליזות, עליצות, צהלה, חדווה ועוד.
מאפיינים

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

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

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

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

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

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

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