دانشنامه ریاضی و کامپیوتر

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

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

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

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

گراف دبروین دوتایی

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

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

شکل :

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

بطور کلی، برای الفبایی مرکب از p حرف، G(p,n) گراف جهت دار دبروینی با p^n-۱ رأس و pⁿ کمان است؛ به طوری که درجه ی ورودی و درجه ی خروجی هر رأس برابر با p است. G(p,n)، یک گراف اویلری است. حال مسیر بسته ی اویلری دلخواهی را در این گراف جهت دار در نظر می‌گیریم که دنباله وار شامل همه ی این pⁿ کمان باشدو دنباله ی حروف نخست همه ی این واژه‌ها را می‌سازیم. این دنباله را با a_۱a_۲...a_r، که در آن pⁿ = r، نشان می‌دهیم. آنگاه همه ی این r واژه ی متمایز به طول n به صورت a_ia_i+۱...a_i+n-۱اند که در آن عمل جمع تعریف شده روی اندیسها به پیمانه ی r است.

مثال

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

اینک هر واژه ی سه حرفی به صورت a_i a_i+۱ a_i+۲ است :

a

_۷

 a

_۸

 a

_۹

 = a

_۷

 a

_۸

 a

_۱

 = ۰۱۰ و غیره. 

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

می‌توانیم به ازای دو عدد صحیح مثبت p و n یک دنباله ی دبروین را به طور صوری تعریف کنیم. اگر S الفبایی مرکب از p حرف باشد، آنگاه دنباله‌ای مانند a_۱a_۲...a_r از (r = pⁿ )r حرف را دنباله ی دبروین می‌نامند و آن را با B(p,n) نشان می‌دهند هرگاه، بتوان هر واژه ی به طول n مرکب از حروف S را به صورت aⁱa^i+۱...a^i+n-۱ در آورد که در آن عمل جمع بین اندیس‌ها به پیمانه ی r است.

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

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

قضیه

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

کاربردها

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

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

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