تسلسل الإشارات

الموسوعة الحرة

في الرياضيات ، تُعرف متتالية الإشارات ، أو متتالية ±1 أو متتالية ثنائية القطب ، بأنها متتالية من الأرقام، كل منها إما 1 أو -1. ومن الأمثلة على ذلك المتتالية (1، -1، 1، -1، ...).

تُدرس هذه المتتاليات عادةً في نظرية التباين .

مشكلة التناقض في إردوش

في حوالي عام 1932، افترض عالم الرياضيات بول إيردوس أنه بالنسبة لأي متتالية لانهائية من ±1(x1،x2،...){\displaystyle (x_{1},x_{2},\ldots )}وأي عدد صحيح C ، يوجد عددان صحيحان k و d بحيث

|∑أنا=1كxأنا⋅د|>ج.{\displaystyle \left|\sum _{i=1}^{k}x_{i\cdot d}\right|>C.}

تطلب مسألة التناقض في إردوش إثبات أو دحض هذه الفرضية.

في فبراير 2014، أثبت أليكسي ليسيتسا وبوريس كونيف من جامعة ليفربول أن أي متتالية مكونة من 1161 عنصرًا أو أكثر تحقق الفرضية في الحالة الخاصة C  =  2، مما يثبت صحة الفرضية عندما C  ≤  2. [ 1 ] كان هذا أفضل حد متاح في ذلك الوقت. اعتمد برهانهما على خوارزمية حاسوبية لحل مسألة SAT، بلغ حجم مخرجاتها 13 غيغابايت من البيانات، أي أكثر من حجم نص ويكيبيديا بأكمله آنذاك، لذا لا يمكن التحقق منها بشكل مستقل من قبل علماء الرياضيات دون استخدام الحاسوب. [ 2 ]

في سبتمبر 2015، أعلن تيرينس تاو عن برهانٍ للفرضية، مستندًا إلى عملٍ أُنجز عام 2010 خلال مؤتمر Polymath5 (وهو شكلٌ من أشكال التعهيد الجماعي المُطبَّق على الرياضيات) واقتراحٍ قدّمه عالم الرياضيات الألماني أوفه ستروينسكي على مدونة تاو. [ 3 ] [ 4 ] نُشر برهانه عام 2016، كأول ورقة بحثية في مجلة التحليل المنفصل الجديدة . [ 5 ]

تم اقتراح تباين إردوش للتسلسلات المحدودة كمقياس للعشوائية المحلية في تسلسلات الحمض النووي . [ 6 ] يستند هذا إلى حقيقة أن التباين في حالة التسلسلات ذات الطول المحدود يكون محدودًا، وبالتالي يمكن تحديد التسلسلات المحدودة التي يكون تباينها أقل من قيمة معينة. ستكون هذه التسلسلات أيضًا هي تلك التي "تتجنب" بعض الدورات. من خلال مقارنة التوزيع المتوقع بالتوزيع الملاحظ في الحمض النووي أو باستخدام مقاييس ارتباط أخرى، يمكن استخلاص استنتاجات تتعلق بالسلوك المحلي لتسلسلات الحمض النووي.

رموز باركر

رمز باركر هو سلسلة من N قيمة من +1 و -1 ،

xج ل ج=1،...،شمال،{\displaystyle x_{j}{\text{ for }}j=1,\ldots ,N,}

بحيث

|∑ج=1شمال-vxجxج+v|≤1{\displaystyle \left|\sum _{j=1}^{Nv}x_{j}x_{j+v}\right|\leq 1}

للجميع1≤v<شمال{\displaystyle 1\leq v<N}[ 7 ]​

تُستخدم رموز باركر ذات الأطوال 11 و 13 في أنظمة الرادار ذات الطيف المنتشر بالتسلسل المباشر وأنظمة الرادار ذات ضغط النبض نظرًا لخصائص الارتباط الذاتي المنخفضة .

انظر أيضاً

ملحوظات

  1. ↑ كونيف، بوريس؛ ليسيتسا، أليكسي (2014). "هجوم SAT على حدسية التناقض لإردوش". في: سينز، كارستن؛ إيغلي، أوفه (محرران). نظرية وتطبيقات اختبار الإرضاء - SAT 2014 - المؤتمر الدولي السابع عشر، الذي عُقد كجزء من صيف فيينا للمنطق، VSL 2014، فيينا، النمسا، 14-17 يوليو 2014، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  8561. سبرينغر. الصفحات 219-226 . arXiv : 1402.2184 . doi : 10.1007/978-3-319-09284-3_17 . ISBN  978-3-319-09283-6.
  2. ↑ آرون، جاكوب (17 فبراير 2014). "برهان رياضي بحجم ويكيبيديا أكبر من أن يتحقق منه البشر" . مجلة نيو ساينتست . تم الاطلاع عليه في 18 فبراير 2014 .
  3. ↑ "حل مسألة رياضية شهيرة بفضل التعهيد الجماعي" . يو إس إيه توداي . 28 سبتمبر 2015.
  4. ↑ آرون، جاكوب (30 سبتمبر 2015). "الجماهير تتغلب على الحواسيب في حل مسألة رياضية بحجم ويكيبيديا" . مجلة نيو ساينتست . تم الاطلاع عليه بتاريخ 21 أكتوبر 2015 .
  5. ^ تاو ، تيرينس (2016). “مشكلة التناقض في Erdős”. التحليل المنفصل : 1– 29. أرخايف : 1509.05363 . دوى : 10.19086/da.609 . ردمك 2397-3129 . السيد 3533300 . S2CID 59361755 .   
  6. ↑ لي، وينتيان؛ ثانوس، ديميتريوس؛ بروفاتا، أستيرو (14 يناير 2019). "قياس العشوائية الموضعية في تسلسلات الحمض النووي DNA والحمض النووي الريبوزي RNA البشري باستخدام أنماط إردوش". مجلة البيولوجيا النظرية . 461 : 41-50 . arXiv : 1805.10248 . Bibcode : 2019JThBi.461...41L . doi : 10.1016/j.jtbi.2018.09.031 . ISSN 0022-5193 . PMID 30336158. S2CID 52901027 .   
  7. ↑ باركر، آر إتش (1953). "مزامنة المجموعات للتسلسلات الرقمية الثنائية". نظرية الاتصالات . لندن: باتروورث. ص 273-287 . 

مراجع