سایت جامع در باب کتب و جزوات رشته های ریاضی و کامپیوتر با دانلود مستقیم.
در ترکیبیات، به دنبالهای با درجه ی n از ۰ و ۱، دنباله دبروین میگویند که طول برابر است با ۲n.
این دنباله به افتخار ریاضیدان آلمانی، نیکلاس گاورت دبروین، نامگذاری شدهاست. این دنباله تشکیل شده از زیردنبالههای nحرفی از ۰ و ۱ که هر کدام از این زیردنبالهها به عنوان یک کاراکتر در نظر گرفته میشوند.
مثلا به ازای n=۳ زیردنبالههای دبروین را به این صورت خواهیم داشت: ۰۰۰٬۰۰۱٬۰۱۰٬۱۰۰٬۰۱۱٬۱۰۱٬۱۱۰٬۱۱۱ و هر کلمه ی ۸ حرفی متشکل از ۰ و ۱ را میتوان بکمک این ۸ واژه ساخت.نمایش این دنباله (واژه)ها به کمک گراف دبروین که یکی از کاربردهای گرافهای جهت دار اویلری است انجام میشود.
فرض میکنیم هر واژه ی به طول n-۱ یک رأس باشد. از هر رأسی به صورت v=a۱a۲...an دو یال رسم میکنیم: یکی به سوی a۲a۳an-۱۰ و دیگری به سوی a۲a۳an-۱۱، تا نمایندۀ دو واژه ی n حرفی، به ترتیب، v۰ و v۱ باشند. از این رو، ۲n یال گراف جهت داری که از این طریق ساخته میشوند مجموعه ی واژههای دوتایی به طول n را نمایش میدهند. این گراف جهت دار(۲،n)، که به گراف (جهت دار) دبروین مشهور است، ضیفاً همبند و اویلری است؛ زیرا درجه ی ورودی هر رأس برابر با درجه ی خروجی آن است.
شکل :
اینک هر واژه ی سه حرفی به صورت ai ai+۱ ai+۲ است :
a۷ a۸ a۹ = a۷ a۸ a۱ = ۰۱۰ و غیره.
طول هر B=(p,n) برابر pn است.
به ازای هر B=(p,n)، k! k (n − ۱)/kn دنباله ی دبروین متمایز وجود دارد.
همچنین در حمله با زور خشن (Brute-force attack) میتوان برای کوتاه کردن کدهایی استفاده کرد که دکمه ی Enter نداشته و n حرف آخر را به عنوان رمز درست قبول میکنند. بری مثال، برای رمزگشایی یک در دیجیتالی با رمز ۴ رقمی، (۱۰،۴)B حالت مختلف وجود دارد. یعنی حداکثر ۱۰۰۰۰ + ۳ = ۱۰۰۰۳ دکمه را باید فشار دهیم (دنباله چرخشی است). در حالیکه امتحان جداگانه ی تمام کدها به ۴*۱۰۰۰۰ = ۴۰۰۰۰ بار فشار دادن دکمه نیاز دارد.
از دیگر کاربردهای دنباله ی دبروین، یافتن سریع اولین و آخرین بیت از یک کلمه، و همچنین کد گری است.