סיבוכיות תקשורת – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
מ שינוי סדר הפרקים (בוט סדר הפרקים)
מאין תקציר עריכה
שורה 1:
המונח '''סיבוכיות תקשורת''' היא מונח ב[[מדעי המחשב]]: [[סיבוכיות]] שבה המדד הוא כמות המידע המועברת בתקשורת בין שני צדדים. המונח הוצג על ידי [[אנדרו יאו|יאו]] בשנת 1979{{הערה|Yao, A. C. (1979), "Some Complexity Questions Related to Distributed Computing", Proc. of 11th STOC, 14: 209–213}}.
 
סיבוכיות התקשורת בוחנת את המצב הבא: ישנם שני משתתפים [[אליס ובוב]], אליס מקבלת [[מחרוזת (מדעי המחשב)|מחרוזת]] של n-[[סיבית|ביטים]] x ובוב מקבל מחרוזת ביטים אחרת y באותו האורך. מטרתם היא שאחד מהמשתתפים (נניח בוב) יחשב פונקציה מסוימת (''f''(''x'',''y)'' תוך כדי קיום [[תקשורת]] מינמלית בין המשתתפים. יש לציין שבהגדרה זו אין התחשבות ב[[סיבוכיות זמן|מספר הצעדים החישוביים]] או ב[[סיבוכיות מקום|זיכרון]] הדרוש לכל אחד מהמשתתפים.
[[סיבוכיות]] תקשורת נועדה לכמת את כמות המידע שנדרש להעביר על מנת לבצע [[חישוב מבוזר]] שכזה.
 
כמובן, אליס ובוב יכולים לחשב את (''f''(''x'',''y)'' ע״י כך שאליס תשלח את כל n הביטים שהיא קיבלה לבוב, שלאחר קבלתם יוכל לחשב באופן מקומי את ה[[פונקציה]] (''f''(''x'',''y)'' ללא עזרה נוספת מאליס. המטרה בחקר סיבוכיות תקשורת היא למצוא שיטות מתקדמות לחישוב f שדורשות העברה של פחות מ-n ביטים, או להוכיח שכמות מסוימת של ביטים הכרחית לחישוב ''f''.
 
הבעיה, והכללותיה למצבים בהם יותר משני משתתפים באה לידי ביטוי בהקשרים רבים: בעיצוב מעגלי [[VLSI]] למשל, רוצים למזער את האנרגיה שהמעגל צורך על ידי הפחתת מספר האותות המועברים בין רכיבים שונים. תחומים נוספים בהם באה הבעיה לידי ביטוי הם למשל [[מבני נתונים]] ו[[אופטימיזציה של רשתות תקשורת]].