סיבוכיות תקשורת – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תרגום המבוא מאנגלית. |
הגדרה בסיסית |
||
שורה 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) תוך כדי קיום [[תקשורת]] מינמלית בין המשתתפים. יש לציין שבהגדרה זו אין התחשבות ב[[סיבוכיות זמן|מספר הצעדים החישוביים]] או ב[[סיבוכיות מקום|זכרון]] הדרוש לכל אחד מהמשתתפים.
[[סיבוכיות]] תקשורת נועדה לכמת את כמות המידע שנדרש להעביר על מנת לבצע [[חישוב מבוזר]] שכזה.
|