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)-ক্রম বলা হয়। দৈর্ঘ্যের সীমা ডিএস (এন, এস)-অনুক্রমের জটিলতা সীমাতে অ্যাসিম্পটোটিকভাবে বিশ্লেষণ করা হয়েছে কারণ এন অসীমের দিকে যায়, এই অনুমানের সাথে যে এস একটি নির্দিষ্ট ধ্রুবক, এবং প্রায় আঁটসাঁট সীমানা সমস্ত এস-এর জন্য পরিচিত। ধরা যাক λs (এন) দীর্ঘতম ডিএস (এন, এস)-অনুক্রমের দৈর্ঘ্য নির্দেশ করে। λs-এ পরিচিত সর্বোত্তম সীমার মধ্যে রয়েছে বিপরীত অ্যাকারম্যান ফাংশন α (n) = ন্যূনতম {m। A (m, m) ≤ n}, যেখানে A হল অ্যাকারম্যান ফাংশন। একারম্যান ফাংশনের খুব দ্রুত বৃদ্ধির কারণে, এর বিপরীত α খুব ধীরে ধীরে বৃদ্ধি পায় এবং যে কোনও ব্যবহারিক আকারের সমস্যার জন্য সর্বাধিক চারটি হয়। বড় ও এবং বড় θ স্বরলিপি ব্যবহার করে, নিম্নলিখিত সীমা জানা যায়ঃ । । । এই জটিলতার বন্ধনকে 2 বাই লাইন সেগমেন্টের একটি ফ্যাক্টরের মধ্যে উপলব্ধি করা যেতে পারেঃ সমতলে n লাইন সেগমেন্টের ব্যবস্থা রয়েছে যার নীচের খামগুলিতে জটিলতা ω (nα (n)) রয়েছে। । । s ≤ 6 এর জোড় এবং বিজোড় উভয় মানের জন্য, যেখানে। λs (n)-এর মান তখনও জানা যায় যখন s পরিবর্তনশীল হয় কিন্তু n একটি ছোট ধ্রুবকঃ যখন s n-এর একটি ফাংশন হয় তখন ডেভেনপোর্ট-শচিনজেল ক্রমের উপরের এবং নীচের সীমানা আঁটসাঁট হয় না। কখন, এবং। কখন, কখন, নীচের খামগুলিতে প্রয়োগ একটি বাস্তব চলক x-এর ফাংশনের একটি সেটের নীচের খামটি তাদের পয়েন্টওয়াইজ ন্যূনতম দ্বারা প্রদত্ত ফাংশনঃ f (x) = মিনিফাই (x)। মনে করুন যে এই ফাংশনগুলি বিশেষভাবে ভাল আচরণ করেঃ এগুলি সবই অবিচ্ছিন্ন, এবং তাদের মধ্যে যে কোনও দুটি সর্বাধিক s মানগুলিতে সমান। এই অনুমানগুলির সাহায্যে, বাস্তব রেখাকে সীমাবদ্ধভাবে অনেকগুলি বিরতিতে ভাগ করা যেতে পারে যার মধ্যে একটি ফাংশনের মান অন্যান্য সমস্ত ফাংশনের চেয়ে ছোট। প্রতিটি ব্যবধানের মধ্যে মিনিমাইজিং ফাংশন দ্বারা চিহ্নিত এই ব্যবধানগুলির ক্রম, ক্রম s-এর একটি ডেভেনপোর্ট-শিনজেল ক্রম গঠন করে। সুতরাং, এই ক্রমের ডেভেনপোর্ট-শিনজেল ক্রমের জটিলতার উপরের যে কোনও সীমানা নীচের খামের এই উপস্থাপনায় ব্যবধানের সংখ্যাকেও সীমাবদ্ধ করে। ডেভেনপোর্ট এবং শিনজেলের মূল প্রয়োগে, বিবেচনাধীন ফাংশনগুলি ছিল ক্রম s-এর একই সমজাতীয় রৈখিক ডিফারেনশিয়াল সমীকরণের বিভিন্ন সমাধানের একটি সেট। যে কোনও দুটি স্বতন্ত্র সমাধানের সর্বাধিক s মান থাকতে পারে, তাই n স্বতন্ত্র সমাধানের একটি সেটের নীচের খামটি একটি DS (n, s)-ক্রম গঠন করে। একটি নিম্ন খামের একই ধারণা এমন ফাংশনের ক্ষেত্রেও প্রয়োগ করা যেতে পারে যা শুধুমাত্র পিসওয়াইজ কন্টিনিউয়াস বা যা শুধুমাত্র বাস্তব রেখার ব্যবধানের উপর সংজ্ঞায়িত করা হয়; যাইহোক, এই ক্ষেত্রে, ফাংশনের বিচ্ছিন্নতার পয়েন্ট এবং প্রতিটি ফাংশন সংজ্ঞায়িত করা হয় এমন ব্যবধানের শেষ পয়েন্টগুলি ক্রমের ক্রমে যোগ করে। উদাহরণস্বরূপ, সমতলে একটি অ-উল্লম্ব রেখা অংশকে একটি ফাংশনের গ্রাফ হিসাবে ব্যাখ্যা করা যেতে পারে যা তাদের সংশ্লিষ্ট y মানগুলির সাথে x মানগুলির ব্যবধানকে ম্যাপিং করে এবং লাইন বিভাগগুলির সংগ্রহের নীচের খামটি তৃতীয় ক্রমের একটি ডেভেনপোর্ট-শচিনজেল ক্রম গঠন করে কারণ যে কোনও দুটি লাইন বিভাগ সর্বাধিক চারটি দৈর্ঘ্যের সাথে একটি বিকল্প ক্রম তৈরি করতে পারে। আরও দেখুন স্কোয়ারফ্রি ওয়ার্ড নোটস রেফারেন্স। । । । । । । । । । । । । । । ম্যাথওয়ার্ল্ড থেকে ডেভেনপোর্ট-শচিনজেল সিকোয়েন্সের বাহ্যিক সংযোগ। স্টিভেন এম. লাভালে রচিত মোশন প্ল্যানিং বইয়ের একটি অংশ ডেভেনপোর্ট-শচিনজেল সিকোয়েন্সেস। শব্দের উপর ক্রম এবং সিরিজ সংমিশ্রণ বিচ্ছিন্ন জ্যামিতি