Sekvence znamení - Sign sequence - Wikipedia
V matematice, a posloupnost znakůnebo ± 1 – sekvence nebo bipolární sekvence, je sekvence čísel, z nichž každé je buď 1 nebo -1. Jedním příkladem je posloupnost (1, −1, 1, −1 ...).
Takové sekvence jsou běžně studovány v teorie nesrovnalostí.
Erdőův problém s nesrovnalostmi
Kolem roku 1932, matematik Paul Erdős domníval se, že pro jakoukoli nekonečnou ± 1 sekvenci a jakékoli celé číslo C, existují celá čísla k a d takhle
Erdőův problém s nesrovnalostí vyžaduje důkaz nebo vyvrácení této domněnky.
V únoru 2014 Alexej Lisitsa a Boris Konev z University of Liverpool ukázal, že každá posloupnost 1161 nebo více prvků splňuje domněnku ve zvláštním případě C = 2, což dokazuje domněnku pro C ≤ 2.[1] To byla v té době ta nejlepší vazba, která byla k dispozici. Jejich důkaz se opíral o a SAT-řešič počítačový algoritmus, jehož výstup zabírá 13 gigabajty dat, více než celý text Wikipedie v té době, takže to nelze nezávisle ověřit lidskými matematiky bez dalšího použití počítače.[2]
V září 2015 Terence Tao oznámil důkaz domněnky, navazující na práci provedenou v roce 2010 během roku 2006 Polymath5 (forma crowdsourcing aplikovaný na matematiku) a návrh německého matematika Uwe Stroinského na Taově blogu.[3][4] Jeho důkaz byl publikován v roce 2016 jako první příspěvek v novém časopise Diskrétní analýza.[5]
Erdőův nesoulad konečných sekvencí byl navržen jako měřítko lokální náhodnosti v sekvencích DNA.[6] To je založeno na skutečnosti, že v případě posloupností konečné délky je nesrovnalost omezená, a proto lze určit konečné posloupnosti s nesrovnalostí menší než určitá hodnota. Těmito sekvencemi budou také ty, které se „vyhýbají“ určitým periodicitám. Porovnáním očekávané a pozorované distribuce v DNA nebo použitím jiných korelačních opatření lze vyvodit závěry týkající se místního chování sekvencí DNA.
Barkerovy kódy
A Barkerův kód je posloupnost N hodnoty +1 a -1,
takhle
pro všechny .[7]
Kódy Barker o délkách 11 a 13 se používají v rozprostřené spektrum přímé sekvence a pulzní kompresní radar systémy kvůli jejich nízkému autokorelace vlastnosti.
Viz také
Poznámky
- ^ Konev, Boris; Lisitsa, Alexei (17. února 2014). „SAT útok na spor o nesouladu Erdos“. arXiv:1402.2184. Bibcode:2014arXiv1402.2184K. Citovat deník vyžaduje
| deník =
(Pomoc) - ^ Aron, Jacob (17. února 2014). „Matematický důkaz velikosti Wikipedie je příliš velký na to, aby ho lidé mohli zkontrolovat“. Nový vědec. Citováno 18. února 2014.
- ^ Slavný matematický problém vyřešený díky crowdsourcingu. USA dnes 28. září 2015
- ^ Jacob Aron, Davy porazily počítače v reakci na matematický problém velikosti Wikipedie, Nový vědec, 30. září, vyvoláno 21. 10. 2015
- ^ Tao, Terence (2016). "Erdőův problém s nesrovnalostmi". Diskrétní analýza: 1–29. arXiv:1509.05363. doi:10.19086 / da.609. ISSN 2397-3129. PAN 3533300.
- ^ Li, Wentian; Thanos, Dimitrios; Provata, Astero (2019-01-14). "Kvantifikace lokální náhodnosti v sekvencích lidské DNA a RNA pomocí Erdösových motivů". Journal of Theoretical Biology. 461: 41–50. arXiv:1805.10248. doi:10.1016 / j.jtbi.2018.09.031. ISSN 0022-5193. PMID 30336158.
- ^ Barker, R. H. (1953). "Skupinová synchronizace binárních digitálních sekvencí". Teorie komunikace. London: Butterworth. str. 273–287.
Reference
- Chazelle, Bernard (2000-07-24). Metoda nesrovnalosti: náhodnost a složitost. Cambridge University Press. ISBN 0-521-77093-9.
externí odkazy
- Erdőův problém s nesrovnalostmi - Polymath Project
- Počítač rozluští Erdőovu hádanku - ale žádný lidský mozek nemůže ověřit odpověď —Nezávislý (Pátek 21. února 2014)