دنباله دبروین

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در ترکیبیات، به دنباله‌ای با درجهٔ n از ۰ و ۱، دنباله دبروین می‌گویند که طول برابر است با ۲n.

این دنباله به افتخار ریاضیدان هلندی، نیکلاس گاورت دبروین، نامگذاری شده‌است. این دنباله تشکیل شده از زیردنباله‌های n حرفی از ۰ و ۱ که هر کدام از این زیردنباله‌ها به عنوان یک کاراکتر در نظر گرفته می‌شوند.

مثلاً به ازای n=۳ زیردنباله‌های دبروین را به این صورت خواهیم داشت: ۰۰۰٬۰۰۱٬۰۱۰٬۱۰۰٬۰۱۱٬۱۰۱٬۱۱۰٬۱۱۱ و هر کلمهٔ ۸ حرفی متشکل از ۰ و ۱ را می‌توان به کمک این ۸ واژه ساخت. نمایش این دنباله (واژه)ها به کمک گراف دبروین که یکی از کاربردهای گراف‌های جهت دار اویلری است انجام می‌شود.

گراف دبروین دوتایی[ویرایش]

طبق تعریف دنباله دبروین، ۲n-1 واژهٔ دوتایی به طول n-۱ وجود دارد. گراف جهت داری با ۲n-1 رأس را به شکل زیر می‌سازیم.

فرض می‌کنیم هر واژهٔ به طول n-۱ یک رأس باشد. از هر رأسی به صورت v=a۱a۲...an دو یال رسم می‌کنیم: یکی به سوی a۲a۳an-1۰ و دیگری به سوی a۲a۳an-1۱، تا نمایندهٔ دو واژهٔ n حرفی، به ترتیب، v۰ و v۱ باشند. از این رو، ۲n یال گراف جهت داری که از این طریق ساخته می‌شوند مجموعهٔ واژه‌های دوتایی به طول n را نمایش می‌دهند. این گراف جهت دار(۲،n)، که به گراف (جهت دار) دبروین مشهور است، ضیفاً همبند و اویلری است؛ زیرا درجهٔ ورودی هر رأس برابر با درجهٔ خروجی آن است.

شکل:

تعریف کلی گراف دبروین[ویرایش]

بطور کلی، برای الفبایی مرکب از p حرف، G(p,n) گراف جهت دار دبروینی با pn-1 رأس و pn کمان است؛ به طوری که درجهٔ ورودی و درجهٔ خروجی هر رأس برابر با p است. G(p,n)، یک گراف اویلری است. حال مسیر بستهٔ اویلری دلخواهی را در این گراف جهت دار در نظر می‌گیریم که دنباله وار شامل همهٔ این pn کمان باشدو دنبالهٔ حروف نخست همهٔ این واژه‌ها را می‌سازیم. این دنباله را با a۱a۲...ar، که در آن pn = r، نشان می‌دهیم. آنگاه همهٔ این r واژهٔ متمایز به طول n به صورت aiai+1...ai+n-۱اند که در آن عمل جمع تعریف شده روی اندیسها به پیمانهٔ r است.

مثال[ویرایش]

مثلاً، اگر p=۲ و n=۳، آنگاه a۹ همان a۱ است. در گراف جهت دار … مدار اویلری جهت داری مه از ۰۰ شروع می‌شود مرکب از دنبالهٔ هشت کمان بعدی است: ۰۰۰، ۰۰۱، ۰۱۱، ۱۱۱، ۱۱۰، ۱۰۱، ۰۱۰، ۱۰۰. حروف نخست این کمان‌ها واژۀٔ ۰۰۰۱۱۱۰۱ را می‌سازند که در نتیجه a۸ = ۰، a۷ = ۰، a۶ = ۰، a۵ = ۰، a۴ = ۰، a۳ = ۰، a۲ = ۰، a۱ = ۰.

اینک هر واژهٔ سه حرفی به صورت ai ai+1 ai+2 است:

a۷ a۸ a۹ = a۷ a۸ a۱ = ۰۱۰ و غیره.

تعریف کلی دنباله دبروین[ویرایش]

می‌توانیم به ازای دو عدد صحیح مثبت p و n یک دنبالهٔ دبروین را به طور صوری تعریف کنیم. اگر S الفبایی مرکب از p حرف باشد، آنگاه دنباله‌ای مانند a۱a۲...ar از (r = pn)r حرف را دنبالهٔ دبروین می‌نامند و آن را با B(p,n) نشان می‌دهند هرگاه، بتوان هر واژهٔ به طول n مرکب از حروف S را به صورت aiai+1...ai+n-۱ درآورد که در آن عمل جمع بین اندیس‌ها به پیمانهٔ r است.

طول هر B=(p,n) برابر pn است.

به ازای هر B=(p,n)، k! k (n − ۱)/kn دنبالهٔ دبروین متمایز وجود دارد.

قضیه[ویرایش]

به ازای هر جفت از اعداد صحیح مثبت، یک دنبالهٔ دبروین وجود دارد. این قضیه را نخست دبروان (۱۹۴۶) به ازای p=۲ ثابت کرد و سپس گود(۱۹۴۶) آن را به ازای p دلخواهی تعمیم داد.

کاربردها[ویرایش]

این دنباله‌ها در نظریهٔ کدگذاری بسیار سودمندند. نمودار حالت یک ثبات انتقالی بازخوردی (FSR) زیرگراف گراف دبروین مشخصی است. FSRها به ویژه به سبب خواص تصادفی دنباله‌هایی که پدیدمی‌آورند کاربردهای وسیعی در مخابرات، رمزنگاری و علم کامپیوتر دارند.

همچنین در حمله با زور خشن (Brute-force attack) می‌توان برای کوتاه کردن کدهایی استفاده کرد که دکمهٔ Enter نداشته و n حرف آخر را به عنوان رمز درست قبول می‌کنند. بری مثال، برای رمزگشایی یک در دیجیتالی با رمز ۴ رقمی، (۱۰٬۴)B حالت مختلف وجود دارد. یعنی حداکثر ۱۰۰۰۰ + ۳ = ۱۰۰۰۳ دکمه را باید فشار دهیم (دنباله چرخشی است). در حالیکه امتحان جداگانهٔ تمام کدها به ۴*۱۰۰۰۰ = ۴۰۰۰۰ بار فشار دادن دکمه نیاز دارد.

از دیگر کاربردهای دنبالهٔ دبروین، یافتن سریع اولین و آخرین بیت از یک کلمه، و همچنین کد گری است.

منابع[ویرایش]