
EITC/IS/CCTF Computational Complexity Theory Fundamentals היא תוכנית הסמכת ה-IT האירופית על היבטים תיאורטיים של יסודות מדעי המחשב, שהם גם בסיס להצפנה קלאסית א-סימטרית מפתח ציבורי בשימוש נרחב באינטרנט.
תכנית הלימודים של EITC/IS/CCTF Computational Complexity Theory Fundamentals מכסה ידע תיאורטי על יסודות של מדעי המחשב ומודלים חישוביים על מושגים בסיסיים כגון מכונות מצב סופי דטרמיניסטיות ולא דטרמיניסטיות, שפות רגילות, תיאוריית דקדוק חופשי הקשר ותיאוריית שפות, תורת האוטומטים, טיורינג. מכונות, יכולת הכרעה של בעיות, רקורסיה, היגיון ומורכבות של אלגוריתמיקה עבור יישומי אבטחה בסיסיים בתוך המבנה הבא, הכוללות חומרי למידה עצמית מקיפים ומובנים של תוכנית לימודים להסמכת EITCI הנתמכים על ידי תוכן דידקטי מוזכר בגישה פתוחה לווידאו, כבסיס להכנה לקראת קבלת זה אישור EITC על ידי מעבר בחינה מתאימה.
המורכבות החישובית של אלגוריתם היא כמות המשאבים הנדרשים להפעלתו. משאבי זמן וזיכרון מקבלים תשומת לב מיוחדת. המורכבות של בעיה מוגדרת כמורכבות האלגוריתמים הטובים ביותר לפתרון שלה. ניתוח אלגוריתמים הוא חקר המורכבות של אלגוריתמים שניתנו במפורש, בעוד שתיאוריית המורכבות החישובית היא חקר המורכבות של פתרונות בעיות עם האלגוריתמים הידועים ביותר. שני התחומים שלובים זה בזה מכיוון שמורכבות האלגוריתם היא תמיד מגבלה עליון על מורכבות הבעיה שהוא פותר. יתר על כן, לעתים קרובות יש צורך להשוות את המורכבות של אלגוריתם מסוים למורכבות הבעיה שיש לפתור תוך בניית אלגוריתמים יעילים. ברוב הנסיבות, המידע היחיד הזמין לגבי הקושי של בעיה הוא שהוא קטן מהמורכבות של הטכניקות היעילות ביותר הידועות. כתוצאה מכך, יש חפיפה רבה בין ניתוח אלגוריתמים לתיאוריית המורכבות.
תורת המורכבות משחקת חשיבות לא רק ביסודות של מודלים חישוביים כבסיס למדעי המחשב, אלא גם ביסודות של קריפטוגרפיה א-סימטרית קלאסית (מה שנקרא קריפטוגרפיה של מפתח ציבורי) המופצת באופן נרחב ברשתות מודרניות, במיוחד באינטרנט. הצפנת המפתח הציבורי מבוססת על קושי חישובי של בעיות מתמטיות אסימטריות מסוימות, כמו למשל פירוק של מספרים גדולים לגורמים הראשוניים שלו (פעולה זו היא בעיה קשה בסיווג תיאוריית המורכבות, מכיוון שאין ידועים אלגוריתמים קלאסיים יעילים לפתרון זה עם משאבים בקנה מידה פולינומי ולא אקספוננציאלי עם הגדלת גודל הקלט של הבעיה, וזה בניגוד לפעולה הפוכה מאוד פשוטה של הכפלה לגורמים ראשוניים ידועים כדי לתת את המספר הגדול המקורי). שימוש באסימטריה זו בארכיטקטורה של קריפטוגרפיה של מפתח ציבורי (על ידי הגדרת יחס א-סימטרי חישובי בין המפתח הציבורי, שניתן לחשב בקלות ממפתח פרטי, בעוד שהמפתח הפרטי לא יכול להיות מחשב בקלות ממפתח ציבורי, אפשר באופן ציבורי להכריז על המפתח הציבורי ולאפשר לצדדי תקשורת אחרים להשתמש בו להצפנה א-סימטרית של נתונים, אשר לאחר מכן ניתן לפענח רק באמצעות המפתח הפרטי המצורף, שאינו זמין מבחינה חישובית לצדדים שלישיים, ובכך להפוך את התקשורת למאובטחת).
תיאוריית המורכבות החישובית פותחה בעיקר על הישגיהם של חלוצי מדעי המחשב והאלגוריתמיקה, כמו אלן טיורינג, שעבודתו הייתה קריטית לשבירת צופן האניגמה של גרמניה הנאצית, שמילאה תפקיד עמוק בזכייה של בני ברית במלחמת העולם השנייה. ניתוח קריפטוגרפי שמטרתו לתכנן ואוטומציה של תהליכים חישוביים של ניתוח נתונים (בעיקר תקשורת מוצפנת) על מנת לחשוף את המידע הנסתר שימשה לפריצת מערכות הצפנה ולקבלת גישה לתכנים של תקשורת מוצפנת, בדרך כלל בעלת חשיבות צבאית אסטרטגית. זו הייתה גם ניתוח הצפנה אשר זירזה את הפיתוח של המחשבים המודרניים הראשונים (אשר יושמו בתחילה למטרה אסטרטגית של שבירת קוד). לקולוסוס הבריטי (שנחשב למחשב האלקטרוני והתוכנתי המודרני הראשון) קדמה ה"פצצה" הפולנית, מכשיר חישובי אלקטרוני שתוכנן על ידי מריאן רג'בסקי כדי לסייע בשבירת צופי אניגמה, ונמסר לבריטניה על ידי המודיעין הפולני יחד עם מכונת ההצפנה הגרמנית Enigma שנתפסה, לאחר שפולין נפלטה על ידי גרמניה בשנת 1939. על בסיס מכשיר זה פיתח אלן טיורינג את המקבילה המתקדמת יותר שלו כדי לשבור בהצלחה תקשורת מוצפנת גרמנית, שפותחה מאוחר יותר למחשבים מודרניים.
מכיוון שכמות המשאבים הנדרשת להפעלת אלגוריתם משתנה בהתאם לגודל הקלט, המורכבות מתבטאת בדרך כלל כפונקציה f(n), כאשר n הוא גודל הקלט ו-f(n) הוא המורכבות הגרועה ביותר ( כמות המשאבים המקסימלית הנדרשת על פני כל התשומות בגודל n) או מורכבות המקרה הממוצעת (הממוצע של כמות המשאבים על פני כל התשומות בגודל n). מספר הפעולות היסודיות הנדרשות על קלט בגודל n מקובל להגדיר כמורכבות זמן, כאשר מאמינים שפעולות אלמנטריות לוקחות פרק זמן קבוע במחשב מסוים ומשתנות רק על ידי גורם קבוע כשהן פועלות במכונה אחרת. כמות הזיכרון הנדרשת על ידי אלגוריתם בקלט בגודל n ידועה בשם מורכבות החלל.
זמן הוא המשאב הנחשב לרוב. כאשר משתמשים במונח "מורכבות" ללא מוקדמות, זה בדרך כלל מתייחס למורכבות הזמן.
יחידות הזמן המסורתיות (שניות, דקות וכן הלאה) אינן מועסקות בתורת המורכבות מאחר והן נשענות מדי על המחשב הנבחר ועל התקדמות הטכנולוגיה. לדוגמה, מחשב כיום יכול להפעיל אלגוריתם במהירות רבה יותר ממחשב משנות ה-1960, ובכל זאת, זה נובע מפריצות דרך טכנולוגיות בחומרת המחשב ולא מאיכות אינהרנטית של האלגוריתם. המטרה של תיאוריית המורכבות היא לכמת את צורכי הזמן המובנים של אלגוריתמים, או את מגבלות הזמן הבסיסיות שאלגוריתם יטיל על כל מחשב. זה מושג על ידי ספירה של כמה פעולות בסיסיות מבוצעות במהלך החישוב. נהלים אלה נקראים בדרך כלל שלבים מכיוון שהם נחשבים כעבור זמן קבוע במכונה מסוימת (כלומר, הם אינם מושפעים מכמות הקלט).
משאב חשוב נוסף הוא כמות זיכרון המחשב הנדרשת לביצוע אלגוריתמים.
משאב נוסף המשמש לעתים קרובות הוא כמות הפעולות האריתמטיות. בתרחיש זה, נעשה שימוש במונח "מורכבות אריתמטית". מורכבות הזמן היא בדרך כלל מכפלה של המורכבות האריתמטית בגורם קבוע אם ידוע אילוץ עליון על גודל הייצוג הבינארי של המספרים המתרחשים במהלך חישוב.
גודל המספרים השלמים המשמשים במהלך חישוב אינו מוגבל עבור שיטות רבות, ואין זה ריאלי להניח שפעולות אריתמטיות דורשות פרק זמן קבוע. כתוצאה מכך, מורכבות הזמן, המכונה גם מורכבות סיביות, עשויה להיות גבוהה משמעותית מהמורכבות האריתמטית. הקושי האריתמטי של חישוב הקובע של מטריצה שלמה nn, למשל, הוא O(n^3) עבור טכניקות סטנדרטיות (חיסול גאוסי). מכיוון שגודל המקדמים עשוי להתרחב באופן אקספוננציאלי במהלך החישוב, מורכבות הסיביות של אותן שיטות היא אקספוננציאלית ב-n. אם נעשה שימוש בטכניקות אלה בשילוב עם חשבון רב מודולרי, ניתן להקטין את מורכבות הסיביות ל-O(n^4).
מורכבות הסיביות, במונחים פורמליים, מתייחסת למספר הפעולות בסיביות הנדרשות להפעלת אלגוריתם. זה שווה את המורכבות הזמנית עד לגורם קבוע ברוב פרדיגמות החישוב. מספר הפעולות על מילות מכונה הנדרשות על ידי מחשבים הוא פרופורציונלי למורכבות הסיביות. עבור מודלים ריאליסטיים של חישוב, מורכבות הזמן ומורכבות הסיביות זהות.
המשאב שנחשב לרוב במיון ובחיפוש הוא כמות השוואות הערכים. אם הנתונים מסודרים היטב, זהו אינדיקטור טוב למורכבות הזמן.
בכל התשומות הפוטנציאליות, ספירת מספר השלבים באלגוריתם היא בלתי אפשרית. מכיוון שהמורכבות של קלט עולה עם גודלו, היא מיוצגת בדרך כלל כפונקציה של גודל הקלט n (בסיביות), ולכן המורכבות היא פונקציה של n. עם זאת, עבור קלט בגודל זהה, המורכבות של אלגוריתם יכולה להשתנות באופן מהותי. כתוצאה מכך, מגוון פונקציות מורכבות מועסקות באופן שגרתי.
המורכבות במקרה הגרוע היא סכום כל המורכבות עבור כל התשומות בגודל n, בעוד שמורכבות המקרים הממוצעת היא סכום כל המורכבות עבור כל התשומות בגודל n (זה הגיוני, מכיוון שמספר התשומות האפשריות בגודל נתון הוא סוֹפִי). כאשר נעשה שימוש במונח "מורכבות" מבלי להיות מוגדר יותר, נלקחת בחשבון מורכבות הזמן הגרועה ביותר.
ידוע לשמצה שקשה לחשב נכון את מורכבות המקרה הגרוע והממוצע. יתר על כן, לערכים המדויקים הללו יש מעט יישום מעשי מכיוון שכל שינוי במכונה או בפרדיגמת החישוב ישנה מעט את המורכבות. יתר על כן, שימוש במשאבים אינו חשוב עבור ערכים קטנים של n, לכן קלות היישום מושכת לעתים קרובות יותר ממורכבות נמוכה עבור n קטן.
מסיבות אלו, רוב תשומת הלב מוקדשת להתנהגות המורכבות עבור n גבוה, כלומר ההתנהגות האסימפטוטית שלה כאשר n מתקרב לאינסוף. כתוצאה מכך, סימון O גדול משמש בדרך כלל כדי לציין מורכבות.
מודלים חישוביים
הבחירה במודל חישוב, המורכב מציון הפעולות החיוניות המבוצעות ביחידת זמן, חשובה בקביעת המורכבות. זה מכונה לפעמים מכונת טיורינג ריבוי קלטות כאשר פרדיגמת החישוב אינה מתוארת באופן ספציפי.
מודל חישוב דטרמיניסטי הוא מודל שבו המצבים הבאים של המכונה והפעולות שיש לבצע מוגדרים במלואם על ידי המצב הקודם. פונקציות רקורסיביות, חשבון למבדה ומכונות טיורינג היו המודלים הדטרמיניסטיים הראשונים. מכונות בגישה אקראית (הידועים גם בתור מכונות RAM) הן פרדיגמה פופולרית להדמיית מחשבים בעולם האמיתי.
כאשר מודל החישוב אינו מוגדר, בדרך כלל מניחים מכונת טיורינג מרובה קלטות. במכונות טיורינג מרובות קלטות, מורכבות הזמן זהה למורכבות הזמן במכונות RAM עבור רוב האלגוריתמים, אם כי ייתכן שתידרש תשומת לב רבה באופן שבו הנתונים מאוחסנים בזיכרון כדי להשיג שוויון זה.
בחירות שונות עשויות להיעשות בשלבים מסוימים של החישוב במודל לא דטרמיניסטי של מחשוב, כגון מכונות טיורינג לא דטרמיניסטיות. בתורת המורכבות, כל האפשרויות האפשריות נבחנות בו-זמנית, ומורכבות זמן לא דטרמיניסטית היא משך הזמן הנדרש כאשר הבחירות הטובות ביותר נעשות תמיד. במילים אחרות, החישוב נעשה במקביל על כמה מעבדים (זהים) הנדרשים, וזמן החישוב הלא דטרמיניסטי הוא הזמן שלוקח למעבד הראשון להשלים את החישוב. ניתן להשתמש בהקבלה זו במחשוב קוונטי על ידי שימוש במצבים מסובכים על גבי בעת הפעלת אלגוריתמים קוונטיים מיוחדים, כמו הפירוק של שור לגורמים של מספרים שלמים זעירים למשל.
גם אם מודל חישוב כזה אינו מעשי כיום, יש לו משמעות תיאורטית, במיוחד ביחס לבעיית P = NP, ששואלת אם מחלקות המורכבות המיוצרות על ידי שימוש ב"זמן פולינומי" ו"זמן פולינומי לא דטרמיניסטי" לפחות עליונות הגבולות זהים. במחשב דטרמיניסטי, הדמיה של אלגוריתם NP דורש "זמן אקספוננציאלי". אם ניתן לפתור משימה בזמן פולינומי על מערכת לא דטרמיניסטית, היא שייכת למחלקת הקושי NP. אם בעיה היא ב-NP ואינה קלה יותר מכל בעיית NP אחרת, אומרים שהיא NP-שלמה. בעיית ה-Napsack, בעיית איש המכירות הנודד ובעיית שביעות הרצון הבוליאנית הן כולן בעיות קומבינטוריות של NP. לאלגוריתם הידוע ביותר יש מורכבות אקספוננציאלית לכל הבעיות הללו. אם ניתן לפתור כל אחת מהבעיות הללו בזמן פולינומי במכונה דטרמיניסטית, אז כל בעיות ה-NP יכולות להיפתר גם בזמן פולינומי, ו-P = NP ייקבע. נכון לשנת 2017, ההנחה הרווחת היא ש-P NP, מה שמרמז שקשה לפתור את המצבים הגרועים ביותר של בעיות NP, כלומר, לוקחים הרבה יותר זמן מכל טווח זמן אפשרי (עשורים) בהינתן אורכי קלט מעניינים.
מחשוב מקביל ומבוזר
מחשוב מקביל ומבוזר כרוך בחלוקת עיבוד על פני מספר מעבדים שכולם פועלים בו זמנית. ההבחנה הבסיסית בין הדגמים השונים היא שיטת שליחת הנתונים בין המעבדים. העברת נתונים בין מעבדים היא בדרך כלל מהירה מאוד במחשוב מקביל, בעוד שהעברת נתונים בין מעבדים במחשוב מבוזר נעשית על פני רשת ולכן היא איטית יותר.
חישוב על N מעבדים לוקח לפחות את המנה ב-N מהזמן שהוא לוקח על מעבד בודד. במציאות, מכיוון שלא ניתן לבצע מקבילות לחלק מהמשימות וייתכן שחלק מהמעבדים יצטרכו להמתין לתוצאה ממעבד אחר, הגבול האידיאלי התיאורטי הזה לעולם לא יושג.
סוגיית המורכבות המרכזית היא לפיכך לפתח אלגוריתמים כך שתוצר זמן המחשוב לפי מספר המעבדים יהיה קרוב ככל האפשר לזמן הדרוש לביצוע אותו חישוב על מעבד בודד.
חישוב קוונטי
מחשב קוונטי הוא מחשב עם מודל חישוב מבוסס מכניקת קוונטים. התזה של Church-Turing נכונה לגבי מחשבים קוונטיים, מה שמרמז שכל בעיה שמחשב קוונטי יכול לפתור עשויה להיפתר גם על ידי מכונת טיורינג. עם זאת, משימות מסוימות עשויות להיפתר באופן תיאורטי באמצעות מחשב קוונטי ולא במחשב קלאסי עם מורכבות זמנית נמוכה משמעותית. לעת עתה, זה תיאורטי לחלוטין, מכיוון שאיש אינו יודע כיצד לפתח מחשב קוונטי מעשי.
תורת המורכבות הקוונטית נוצרה כדי לחקור את סוגי הבעיות השונים שניתן לפתור באמצעות מחשבים קוונטיים. זה מנוצל בהצפנה פוסט-קוונטית, שהיא תהליך של יצירת פרוטוקולים קריפטוגרפיים עמידים בפני התקפות מחשב קוונטיות.
מורכבות הבעיה (גבול תחתון)
עיקר המורכבות של האלגוריתמים שעשויים לפתור את הבעיה, כולל טכניקות שלא התגלו, הוא מורכבות הבעיה. כתוצאה מכך, המורכבות של בעיה שווה למורכבות של כל אלגוריתם שפותר אותה.
כתוצאה מכך, כל מורכבות הניתנת בסימון O גדול מייצגת מורכבות הן של האלגוריתם והן של הבעיה הנלווית.
מצד שני, השגת גבולות נמוכים לא טריוויאליים לגבי מורכבות הנושא היא לעתים קרובות קשה, ויש מעט אסטרטגיות לעשות זאת.
על מנת לפתור את רוב הבעיות, יש לקרוא את כל נתוני הקלט, מה שלוקח זמן פרופורציונלי לגודל הנתונים. כתוצאה מכך, לבעיות כאלה יש לפחות מורכבות לינארית, או, בתווי אומגה גדול, מורכבות של Ω(n).
לבעיות מסוימות, כמו אלו באלגברה ממוחשבת ובגיאומטריה אלגברית חישובית, יש פתרונות גדולים מאוד. מכיוון שהפלט חייב להיכתב, המורכבות מוגבלת על ידי הגודל המרבי של הפלט.
למספר ההשוואות הנדרש עבור אלגוריתם מיון יש גבול תחתון לא ליניארי של Ω(nlogn). כתוצאה מכך, אלגוריתמי המיון הטובים ביותר הם היעילים ביותר מכיוון שהמורכבות שלהם היא O(nlogn). העובדה שיש n! דרכים לארגן n דברים מובילות לגבול התחתון הזה. כי כל השוואה מחלקת את האוסף הזה של n! הזמנות לשני חלקים, מספר ה-N השוואות הנדרשות כדי להבחין בין כל הסדרים חייב להיות 2N > n!, מה שמרמז על O(nlogn) לפי הנוסחה של סטירלינג.
הפחתת בעיה לבעיה אחרת היא אסטרטגיה נפוצה להשגת אילוצי מורכבות מופחתים.
פיתוח אלגוריתם
הערכת המורכבות של אלגוריתם היא מרכיב חשוב בתהליך העיצוב מכיוון שהוא מספק מידע שימושי על הביצועים הצפויים.
זוהי אי הבנה תכופה שכתוצאה מחוק מור, החוזה את הצמיחה האקספוננציאלית של כוח המחשב המודרני, הערכת מורכבות האלגוריתמים תהיה פחות רלוונטית. זה לא נכון מכיוון שההספק המוגבר מאפשר עיבוד של כמויות אדירות של נתונים (ביג דאטה). לדוגמה, כל אלגוריתם אמור לתפקד היטב תוך פחות משנייה בעת מיון אלפביתי של רשימה של כמה מאות ערכים, כגון הביבליוגרפיה של ספר. מצד שני, עבור מיליון ערכים (לדוגמה, מספרי טלפון של עיר גדולה), האלגוריתמים הבסיסיים הדורשים השוואות O(n2) יצטרכו לבצע טריליון השוואות, שייקח שלוש שעות במהירות של 10 מיליון השוואות בשנייה. מיון Quicksort ומיון, לעומת זאת, דורשים רק השוואות nlogn (כמורכבות המקרה הממוצעת עבור הראשון, כמורכבות המקרה הגרוע ביותר עבור האחרון). זה מייצר בערך 30,000,000 השוואות עבור n = 1,000,000, מה שייקח רק 3 שניות ב-10 מיליון השוואות בשנייה.
כתוצאה מכך, הערכת מורכבות עשויה לאפשר ביטול של אלגוריתמים לא יעילים רבים לפני היישום. זה יכול לשמש גם כדי לכוונן אלגוריתמים מורכבים מבלי לבדוק את כל הגרסאות האפשריות. חקר המורכבות מאפשר למקד את המאמץ להגברת היעילות של יישום על ידי קביעת השלבים היקרים ביותר של אלגוריתם מורכב.
כדי להכיר את עצמכם באופן מפורט עם תכנית הלימודים להסמכה תוכלו להרחיב ולנתח את הטבלה שלהלן.
תכנית הלימודים של יסודות ההסמכה של EITC/IS/CCTF Computational Complexity Theory מתייחסת לחומרים דידקטיים בגישה פתוחה בצורת וידאו. תהליך הלמידה מחולק למבנה שלב אחר שלב (תוכניות -> שיעורים -> נושאים) המכסה חלקים רלוונטיים בתכנית הלימודים. המשתתפים יכולים לגשת לתשובות ולשאול שאלות רלוונטיות יותר בחלק השאלות והתשובות של ממשק הלמידה האלקטרונית תחת נושא תכנית הלימודים המתקדם כעת של תוכנית EITC. ייעוץ ישיר וללא הגבלה עם מומחי תחום נגיש גם באמצעות מערכת ההודעות המשולבת המקוונת של הפלטפורמה, כמו גם דרך טופס יצירת הקשר.
לפרטים על הליך ההסמכה בדוק איך זה עובד?.
חומרי קריאה תומכים בתכנית לימודים ראשונית
ש' ערורה, ב' ברק, מורכבות חישובית: גישה מודרנית
https://theory.cs.princeton.edu/complexity/book.pdf
חומרי קריאה תומכים בתכנית לימודים משנית
O. Goldreich, מבוא לתורת המורכבות:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
חומרי קריאה תומכים בתכנית לימודים בנושא מתמטיקה בדידה
J. Aspnes, הערות על מתמטיקה בדידה:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
חומרי קריאה תומכים בתכנית לימודים על תורת הגרפים
ר. דיסטל, תורת הגרפים:
https://diestel-graph-theory.com/
הורד את חומרי ההכנה המלאים ללמידה עצמית לא מקוונת עבור תוכנית יסודות התיאוריה של מורכבות חישובית EITC/IS/CCTF בקובץ PDF