Shattered set
بکھرے ہوئے سیٹوں کا تصور ویپنک-چیروونینکس تھیوری میں ایک اہم کردار ادا کرتا ہے، جسے وی سی تھیوری بھی کہا جاتا ہے۔ بکھرنے اور وی سی تھیوری کا استعمال تجرباتی عمل کے مطالعہ کے ساتھ ساتھ شماریاتی کمپیوٹیشنل لرننگ تھیوری میں بھی کیا جاتا ہے۔ تعریف فرض کریں کہ A ایک سیٹ ہے اور C سیٹوں کی ایک کلاس ہے۔ کلاس C سیٹ A کو ٹکڑے ٹکڑے کر دیتی ہے اگر A کے ہر ذیلی سیٹ a کے لیے، C کا کچھ عنصر c ایسا ہو کہ مساوی طور پر، C A کو تب ٹکڑے ٹکڑے کر دیتا ہے جب ان کا چوراہا A کے پاور سیٹ کے برابر ہو: P (A) = {c ≤ A | c ≤ C}۔ ہم سیٹوں کے "کلاس" یا "مجموعہ" کا حوالہ دینے کے لیے حرف سی کا استعمال کرتے ہیں، جیسا کہ ویپنک-چیروونینکس کلاس (وی سی-کلاس) میں ہوتا ہے۔ سیٹ اے کو اکثر محدود سمجھا جاتا ہے کیونکہ تجرباتی عمل میں، ہم ڈیٹا پوائنٹس کے محدود سیٹوں کے بکھرنے میں دلچسپی رکھتے ہیں۔ مثال ہم دکھائیں گے کہ طیارہ (دو جہتی خلا) میں موجود تمام ڈسکس کی کلاس یونٹ سرکل پر موجود چار پوائنٹس کے ہر سیٹ کو نہیں توڑتی، پھر بھی طیارہ میں موجود تمام کنویکس سیٹس کی کلاس یونٹ سرکل پر موجود پوائنٹس کے ہر محدود سیٹ کو توڑ دیتی ہے۔ فرض کریں کہ A یونٹ سرکل پر چار پوائنٹس کا مجموعہ ہے اور C کو تمام ڈسکس کی کلاس ہونے دیں۔ یہ جانچنے کے لیے کہ سی اے کو کہاں ٹکڑے ٹکڑے کرتا ہے، ہم اے میں پوائنٹس کے ہر ذیلی سیٹ کے ارد گرد ایک ڈسک کھینچنے کی کوشش کرتے ہیں۔ سب سے پہلے، ہم ہر الگ تھلگ نقطہ کے ذیلی سیٹوں کے ارد گرد ایک ڈسک کھینچتے ہیں۔ اگلا، ہم پوائنٹ جوڑوں کے ہر ذیلی سیٹ کے ارد گرد ایک ڈسک کھینچنے کی کوشش کرتے ہیں۔ یہ ملحقہ پوائنٹس کے لیے قابل عمل ثابت ہوتا ہے، لیکن دائرے کے مخالف اطراف کے پوائنٹس کے لیے ناممکن ہے۔ جیسا کہ نیچے دیکھا گیا ہے: کیونکہ کچھ ذیلی سیٹ ہے جسے C میں کسی بھی ڈسک سے الگ نہیں کیا جا سکتا، اس لیے ہم یہ نتیجہ اخذ کرتے ہیں کہ A کو C سے ٹکڑے ٹکڑے نہیں کیا جا سکتا۔ اور تھوڑی سی سوچ کے ساتھ، ہم یہ ثابت کر سکتے ہیں کہ چار پوائنٹس کا کوئی سیٹ اس C سے ٹکڑے ٹکڑے نہیں ہوتا ہے۔ تاہم، اگر ہم C کو تمام الپٹیکل ڈسکس کی کلاس کے طور پر دوبارہ بیان کرتے ہیں، تو ہمیں معلوم ہوتا ہے کہ ہم اب بھی اوپر سے تمام ذیلی سیٹس کے ساتھ ساتھ ان پوائنٹس کو بھی الگ کر سکتے ہیں جو پہلے پریشان کن تھے۔ اس طرح، 4 پوائنٹس کا یہ مخصوص سیٹ ایلیپٹیکل ڈسکس کی کلاس سے بکھر جاتا ہے۔ ذیل میں تصور کیا گیا: تھوڑی سی سوچ کے ساتھ، ہم عام کر سکتے ہیں کہ اکائی دائرے پر محدود پوائنٹس کے کسی بھی سیٹ کو تمام کنویکس سیٹوں کی کلاس کے ذریعے بکھرایا جا سکتا ہے (نقطوں کو جوڑنے کا تصور کریں)۔ بکھر گتانک سیٹوں کے مجموعہ سی کی دولت کی مقدار کے لیے، ہم بکھر گتانک کا تصور استعمال کرتے ہیں (جسے گروتھ فنکشن بھی کہا جاتا ہے)۔ سیٹوں کے مجموعے کے لیے، کوئی بھی جگہ ہونے کے ناطے، اکثر ایک نمونے کی جگہ ہونے کے ناطے، ہم سی کے nth بکھرنے والے گتانک کی وضاحت کرتے ہیں جہاں سیٹ کی بنیادی حیثیت کی نشاندہی ہوتی ہے اور یہ n پوائنٹس کا کوئی سیٹ ہوتا ہے۔ یہ n پوائنٹس کے کسی بھی سیٹ A کے سب سیٹوں کی سب سے بڑی تعداد ہے جو مجموعہ C میں موجود سیٹوں کے ساتھ A کو کاٹ کر تشکیل دی جا سکتی ہے۔ اس بارے میں کچھ حقائق یہ ہیں: تمام n کے لیے کیونکہ کسی بھی کے لیے۔ اگر، اس کا مطلب ہے کہ کارڈینالیٹی n کا ایک مجموعہ موجود ہے، جسے C سے توڑا جا سکتا ہے۔ اگر کچھ کے لیے تو سب کے لیے۔ تیسری خاصیت کا مطلب یہ ہے کہ اگر C کارڈینالیٹی N کے کسی بھی سیٹ کو توڑ نہیں سکتا تو یہ بڑی کارڈینالیٹیز کے سیٹ کو توڑ نہیں سکتا۔ کلاس سی کے وی سی طول و عرض کو یا، متبادل طور پر، کے طور پر بیان کیا گیا ہے۔ نوٹ کریں کہ اگر کسی بھی n کے لیے کارڈینالیٹی n کا ایک مجموعہ ہے جسے C سے ٹکڑے ٹکڑے کیا جا سکتا ہے، تو اس کلاس C کے تمام n اور VC طول و عرض کے لیے لامحدود ہے۔ محدود وی سی طول و عرض والی کلاس کو ویپنک-چیروونینکس کلاس یا وی سی کلاس کہا جاتا ہے۔ کلاس سی "یکساں طور پر گلیوینکو-کینٹیلی ہے اگر اور صرف اس صورت میں جب وہ وی سی کلاس ہو۔ سوئر-شیلا لیما بھی دیکھیں، جو سیٹوں کے ایک خاندان کی بنیادی حیثیت کو اس کے سب سے بڑے بکھرے ہوئے سیٹ کے سائز سے متعلق ہے۔ حوالہ جات ۔ بیرونی روابط "بکھرے ہوئے سیٹوں" کی اصطلاحات کی ابتدا، جے اسٹیل تجرباتی عمل کمپیوٹیشنل لرننگ تھیوری کے ذریعہ