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