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

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

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

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

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

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

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

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

شکل :

AmirDe.jpg

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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