Davenport–Schinzel sequence
امتزاج میں، ڈیوینپورٹ-شنزل ترتیب علامتوں کا ایک سلسلہ ہے جس میں کسی بھی دو علامتوں کی باری باری ظاہر ہونے کی تعداد محدود ہوتی ہے۔ ڈیوینپورٹ-شنزل ترتیب کی زیادہ سے زیادہ ممکنہ لمبائی اس کی الگ الگ علامتوں کی تعداد سے محدود ہوتی ہے جسے ایک چھوٹے لیکن غیر مستقل عنصر سے ضرب دی جاتی ہے جو اجازت شدہ متبادلات کی تعداد پر منحصر ہوتی ہے۔ ڈیوینپورٹ-شنزل ترتیبات کی تعریف پہلی بار 1965 میں ہیرالڈ ڈیوینپورٹ اور آندریج شنزل نے لکیری تفریقی مساوات کا تجزیہ کرنے کے لیے کی تھی۔ ان ترتیبات اور ان کی لمبائی کی حدود کی پیروی کرنا مجرد جیومیٹری اور ہندسی الگورتھم کے تجزیے میں بھی ایک معیاری ذریعہ بن گیا ہے۔ تعریف ایک محدود ترتیب U = u1، u2، u3، کو ترتیب s کی ڈیوینپورٹ-شنزل ترتیب کہا جاتا ہے اگر یہ مندرجہ ذیل دو خصوصیات کو مطمئن کرتی ہے: ترتیب میں کوئی بھی دو مسلسل اقدار ایک دوسرے کے برابر نہیں ہیں۔ اگر x اور y ترتیب میں پائے جانے والے دو الگ الگ اقدار ہیں، تو ترتیب میں ایک تسلسل نہیں ہوتا ہے۔ x،. y،.., x،.., y،.. جس میں x اور y کے درمیان باری باری s + 2 اقدار ہوتی ہیں۔ مثال کے طور پر، ترتیب 1، 2، 1، 3، 1، 3، 2، 4، 5، 5، 2، 3 ترتیب 3 کی ڈیوینپورٹ-شنزل ترتیب ہے: اس میں لمبائی چار کے متبادلات ہوتے ہیں، جیسے. 1،. 2،. 1،. 2،. (جو پوری ترتیب کے تسلسل کے طور پر چار مختلف طریقوں سے ظاہر ہوتا ہے) لیکن اس میں لمبائی پانچ کے کوئی متبادلات نہیں ہوتے ہیں۔ اگر آرڈر s کی ڈیوینپورٹ-شنزل ترتیب میں n الگ الگ اقدار شامل ہیں، تو اسے (n، s) ڈیوینپورٹ-شنزل ترتیب، یا DS (n، s)-ترتیب کہا جاتا ہے۔ لمبائی کی حدود DS (n, s)-تسلسل کی پیچیدگی کا تجزیہ اس حد میں غیر علامتی طور پر کیا گیا ہے کیونکہ n لامحدود کی طرف جاتا ہے، اس مفروضے کے ساتھ کہ s ایک مقررہ مستقل ہے، اور تقریبا تنگ حدود تمام s کے لیے جانی جاتی ہیں۔ آئیے λs (n) طویل ترین DS (n, s)-تسلسل کی لمبائی کو ظاہر کرتا ہے۔ λs پر معلوم بہترین حدود میں الٹا ایکرمن فنکشن α (n) = min {m | A (m, m) ≤ n} شامل ہے، جہاں A ایکرمن فنکشن ہے۔ ایکرمن فنکشن کی بہت تیز ترقی کی وجہ سے، اس کا الٹا α بہت آہستہ آہستہ بڑھتا ہے، اور کسی بھی عملی سائز کے مسائل کے لیے زیادہ سے زیادہ چار ہوتا ہے۔ بگ O اور بگ θ نوٹیشن کا استعمال کرتے ہوئے، درج ذیل حدود معلوم ہیں: ۔ ۔ ۔ اس پیچیدگی کے پابند ہونے کا احساس لائن کے حصوں کے لحاظ سے 2 کے عنصر کے اندر کیا جا سکتا ہے: ہوائی جہاز میں n لائن کے حصوں کے انتظامات موجود ہیں جن کے نچلے لفافوں میں پیچیدگی ω (nα (n)) ہوتی ہے۔ ۔ ۔ s ≤ 6 کی یکساں اور عجیب دونوں اقدار کے لیے، جہاں۔ λs (n) کی قدر اس وقت بھی معلوم ہوتی ہے جب s متغیر ہوتا ہے لیکن n ایک چھوٹا مستقل ہوتا ہے: جب s n کا فعل ہوتا ہے تو ڈیوینپورٹ-شنزل ترتیبات پر اوپری اور نچلی حدود تنگ نہیں ہوتی ہیں۔ کب، اور۔ کب۔ کب۔ نچلے لفافوں پر اطلاق ایک حقیقی متغیر x کے افعال کے ایک سیٹ fi (x) کا نچلا لفافہ ان کے نقطہ وار کم از کم کے ذریعہ دیا گیا فنکشن ہے: f (x) = منی fi (x)۔ فرض کریں کہ یہ افعال خاص طور پر اچھی طرح سے برتاؤ کرتے ہیں: وہ سب مسلسل ہیں، اور ان میں سے کوئی بھی دو زیادہ سے زیادہ s اقدار پر برابر ہیں۔ ان مفروضوں کے ساتھ، حقیقی لکیر کو محدود طور پر بہت سے وقفوں میں تقسیم کیا جا سکتا ہے جس کے اندر ایک فنکشن کی اقدار دیگر تمام افعال سے کم ہوتی ہیں۔ ان وقفوں کی ترتیب، جو ہر وقفے کے اندر کم سے کم فنکشن کے ذریعہ لیبل کی جاتی ہے، ترتیب s کی ڈیوینپورٹ-شنزل ترتیب بناتی ہے۔ اس طرح، اس ترتیب کی ڈیوینپورٹ-شنزل ترتیب کی پیچیدگی پر کوئی بھی اوپری حد بھی نچلے لفافے کی اس نمائندگی میں وقفوں کی تعداد کو محدود کرتی ہے۔ ڈیوینپورٹ اور شنزل کے اصل اطلاق میں، زیر غور افعال ترتیب s کی ایک ہی یکساں لکیری تفریق مساوات کے مختلف حلوں کا ایک مجموعہ تھے۔ کسی بھی دو الگ الگ حلوں میں زیادہ سے زیادہ s اقدار مشترک ہو سکتی ہیں، لہذا n الگ الگ حلوں کے سیٹ کا نچلا لفافہ DS (n, s)-تسلسل بناتا ہے۔ نچلے لفافے کا وہی تصور ان افعال پر بھی لاگو کیا جا سکتا ہے جو صرف ٹکڑے ٹکڑے مسلسل ہوتے ہیں یا جن کی وضاحت صرف حقیقی لکیر کے وقفوں پر کی جاتی ہے۔ تاہم، اس معاملے میں، افعال کے منقطع ہونے کے نکات اور وقفے کے اختتامی نکات جس کے اندر ہر فنکشن کی وضاحت کی جاتی ہے، ترتیب کی ترتیب میں اضافہ کرتے ہیں۔ مثال کے طور پر، طیارہ میں ایک غیر عمودی لکیر کے حصے کی تشریح کسی فنکشن کے گراف کے طور پر کی جا سکتی ہے جو x اقدار کے وقفے کو ان کی متعلقہ y اقدار سے جوڑتا ہے، اور لکیر کے حصوں کے مجموعے کا نچلا لفافہ ڈیوینپورٹ-شنزل ترتیب بناتا ہے کیونکہ کوئی بھی دو لکیر کے حصے زیادہ سے زیادہ چار لمبائی کے ساتھ ایک متبادل تسلسل تشکیل دے سکتے ہیں۔ اسکوائر فری ورڈ نوٹس حوالہ جات بھی دیکھیں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ بیرونی روابط ڈیوینپورٹ-شنزل سیکوینس، میتھ ورلڈ سے۔ ڈیوینپورٹ-شنزل سیکوینسز، سٹیون ایم لا ویلے کی کتاب موشن پلاننگ کا ایک حصہ۔ الفاظ پر ترتیبات اور سیریز کا امتزاج مجرد جیومیٹری