توپ و جعبه چیست؟ توضیح بده.
مسئله توپ-و-جعبه یک مسئله کلاسیک در نظریه احتمال است که کاربردهای بسیاری در علوم کامپیوتر دارد. این مسئله شامل "m" توپ و "n" جعبه (یا "سطل") است. هر بار یک توپ در یک جعبه قرار داده می‌شود. پس از آنکه همه توپ‌ها در جعبه‌ها قرار گرفت، تعداد هر جعبه را بار (load) آن جعبه می‌نامیم. در این مسئله یافتن مقدار یا یک کران برای بیشینه (ماکزیمم) بار حائز اهمیت است.بدیهی است که می‌توان با قرار دادن توپ در جعبه با کمترین بار به بار m/n رسید. در انتخاب جعبه‌ها مسئله وقتی در حوزه احتمالات قرار می‌گیرد که جعبه‌ها کاملاً (تخصیص تصادفی کامل) یا بعضاً (تخصیص تصادفی جزئی) به صورت تصادفی انتخاب شوند.تخصیص تصادفی کامل.زمانی که برای هر توپ، جعبه به‌طور تصادفی و مستقل از دیگر انتخاب‌ها، انتخاب می‌شود، بیشینه بار ممکن است به بزرگی formula_1. هرچند می‌توان یک کران محدود برای «حداکثر بار» که با احتمال بالا صادق است، به‌دست آورد. یک «احتمال بالا» یک احتمال formula_2 یعنی زمانی که n به سمت بینهایت میل می‌کند، احتمال به formula_3 میل خواهد کرد.برای مورد formula_4 با احتمال بالا حداکثر بار:formula_5.Gonnet یک کران محدود برای امید ریاضی بیشینه بار به‌دست آورد که برای formula_4 برابر formula_7. formula_8 معکوس تابع گاماست و برابراست با formula_9بیشینه بار همچنین می‌تواند برای formula_10 محاسبه شود. به عنوان مثال برای formula_11 مقدار بیشینه بار با احتمال بالا برابر است با formula_12و برای formula_13 با احتمال بالا برابر است با formula_14.تخصیص تصادفی جزئی.به‌جای انتخاب تصادفی جعبه برای هر توپ، می‌توان دو جعبه یا بیشتر به صورت تصادفی انتخاب کرد و توپ را در جعبه با بار کمتر قرار داد. تخصیص تصادفی جزئی، بین حالت تخصیص قطعی که در آن جعبهٔ با بار کمتر انتخاب می‌شود و حالت کاملاً تصادفی قرار دارد که در آن جعبه به صورت کاملاً تصادفی بدون توجه به بار جاری آن انتخاب می‌شود.در این حالت اگر m توپ و n جعبه داشته باشیم (که m=n) و برای هر توپ formula_15 جعبه به صورت تصادفی در هر مرحله انتخاب شود و سپس توپ در جعبه با بار کمتر از بین d جعبه قرار داده شود، آنگاه با احتمال بالا بیشینه بار برابر است با:formula_16که به صورت نمایی کمتر از تخصیص تصادفی کلی است.می‌توان برای formula_17 (که formula_15) نیز این نتیجه را تعمیم داد، که با احتمال بالا بیشینه بار برابر است با:formula_19توجه شود که برای formula_11 formula_12 را به‌دست می‌دهد. بهبود بین این دو فرایند به ویژه برای formula_1.جریان بی‌نهایت از توپ‌ها.به جای قرار دادن m توپ، می‌توان حالتی را در نظر گرفت که در آن در یک فرایند نامحدود، یک توپ قرار داده شود و یک توپ برداشته شود به نحوی که تعداد توپ‌ها همواره ثابت بماند. برای m=n، پس از یک زمان طولانی، با احتمالاً بالا بار بیشینه شبیه نسخه نامتناهی مسئله، هم برای تخصیص تصادفی کلی و هم برای تخصیص تصادفی جزئی می‌شود.کاربردها.تخصیص پویای منابع: تعداد n دستگاه کامپیوتر یکسان را در نظر بگیرید. n کاربر هم وجود دارند. کاربران با یکدیگر هماهنگ نیستند و هر کاربر کامپیوتری را که می‌خواهد انتخاب می‌کند. هر کاربر منطقا کامپیوتر با بار کمینه را انتخاب خواهد کرد، که البته لازمه آن این است که بار روی هر کامپیوتر محاسبه شود و این خود ممکن است زمان طولانی ای نیاز داشته باشد. راه دیگر این است که هر کاربر کامپیوتری را به صورت تصادفی انتخاب کند، که در این حالت با احتمال بالا بار بیشینه formula_23formula_24درهم سازی (Hashing): یک جدول درهم سازی را در نظر بگیرید که در آن همه کلیدهایی که به یک محل نگاشت شده‌اند در یک لیست پیوندی ذخیره می‌شوند. بازدهی دسترسی به کلید به طول لیست بستگی دارد. اگر از "یک "تابع درهم سازی استفاده کنیم که که مکان‌ها را با احتمال یکنوا انتخاب می‌کند، با احتمال بالا طولانی‌ترین زنجیره (لیست) formula_25 کلید دارد. یک بهبود برای این وضعیت استفاده از دو تابع درهم سازی و قرار دادن کلید در لیست کوتاه‌تر است. در این حالت با احتمال بالا طولانی‌ترین زنجیره فقط formula_26 عنصر دارد.Proportional division.