Հաջորդականություն (մաթեմատիկա)

Հաջորդականությունը, մաթեմատիկայում, օբյեկտների (կամ իրադարձությունների) կարգավորված ցանկ է։ Բազմության նման, այն պարունակում է անդամներ (որոնք նաև կոչվում են էլեմենտներ կամ տարրեր), և տարրերի քանակը (հնարավորինս անսահման) կոչվում է հաջորդականության երկարություն։ Ի տարբերություն բազմության, կարգը նշանակություն ունի, և ճիշտ նույն էլեմենտները կարող են բազմաթիվ անգամներ հայտնվել հաջորդականության տարբեր դիրքերում։ Հաջորդականությունը դիսկրետ ֆունկցիա է։

Օրինակ, (C, R, Y) տառերի հաջորդականություն է, որը տարբերվում է (Y, C, R)-ից, քանի որ կարգավորությունը նշանակություն ունի։ Հաջորդականությունները կարող են լինել սահմանափակ, ինչպես այս օրինակում է, կամ անսահմանափակ, ինչպես դրական զույգ թվերը (2, 4, 6, ...), դրական և բացասական ամբողջ թվերը։ Սահամանափակ հաջորդականությունները երբեմն անվանում են տողեր կամ բառեր, իսկ անսահմանափակ հաջորդականությունները հոսքեր։ Դատարկ հաջորդականությունը() ներառված է հաջորդականության հասկացությունների մեծ մասի մեջ, բայց կարող է բացառվել կախված համատեքստից։

Օրինակ և նշագրություն 
Մաթեմատիկայում կան հաջորդականությունների՝ բազմազան և միանգամայն տարբեր հասկացություններ, որոնցից մի քանիսը (օրինակ, ճշմարիտ հաջորդականությունը) կազմված չեն ստորև ներկայացված նշագրությամբ։

Բացի այդ հաջորդականության էլեմենտների ճանաչումը իրենց դիրքերի միջոցով, ինչպես օրինակ "3-րդ էլեմենտը", էլեմենտներին կարող են տրվել անուններ, հարմար հղման համար։ Օրինակ հաջորդականությունը կարող է գրվել այսպես՝ (a1, a2, a2, … ), or (b0, b1, b2, … ), կամ (c0, c2, c4, … ), կախված նրանից՝ որն է պիտանի հավելվածում։

Սահմանափակ և անսահմանափակ
Սահմանափակ հաջորդականության ավելի պաշտոնական սահմանումը S բազմության տարրերի միջոցով ֆունկցիա է {1, 2, ..., n}-ից մինչև S շատ մեծ n > 0 համար։ Անսահմանափակ հաջորդականությունը S-ում ֆունկցիա է {1, 2, ... }-ից մինչև S։ Օրինակ, պարզ թվերի հաջորդականությունը (2, 3, 5, 7, 11, … ) հետևյալ ֆունկցիան է 1→2, 2→3, 3→5, 4→7, 5→11, … ։

Հաջորդականության սահմանափակ երկարությունը՝ n կոչվում է նաև n-կորտեժ։ Սահամանափակ հաջորդականությունները ներառում են դատարկ հաջորդականություն ( ), որը չունի էլեմենտներ։

Հավաքածուում բոլոր ամբողջ թվերից ֆունկցիան երբեմն կոչվում է bi-անսահմանափակ հաջորդականություն կամ երկկողմանի անսահմանափակ հաջորդականություն։ Օրինակը բոլոր զույգ ամբողջ թվերի bi-անսահմանափակ հաջորդականությունն է ( …, -4, -2, 0, 2, 4, 6, 8… )։

Մուլտիպլիկատիվ
Դիցուք՝ A = (հաջորդականություն սահմանափակված f ֆունկցիայով։{1, 2, 3, ...} → {1, 2, 3, ...}, այնպես որ a i = f(i)։

Հաջորդականությունը մուլտիպլիկատիվ է եթե f(xy) = f(x)f(y) բոլոր x, y համար, այնպես որ x և y փոխադարձաբար պարզ են։

Հաջորդականությունների տեսակները և հատկությունները
Տրված հաջորդականության ենթահաջորդականությունը հաջորդականություն է, որը կազմված է՝ որոշ էլեմենտներ ջնջելով, առանց խախտելու մնացած էլեմենտների հարաբերական դիրքերը։

Եթե հաջորդականության տարրերը կարգավորված բազմության ենթաբազմություն է, ապա մոնոտոն աճող հաջորդականությունը մի հաջորդականություն է, որի յուրաքանչյուր տարր ավելի մեծ է, քան իրեն նախորդողը կամ հավասար է նախորդողին։ Եթե յուրաքանչյուր տարր խիստ ավելի մեծ է, քան նախորդը, հաջորդականությունը կոչվում է մոնոտոն խիստ աճող։ Մոնոտոն նվազող հաջորդականությունը սահմանվում է նմանապես. Ցանկացած հաջորդականություն, որը բավարարում է մոնոտոնության հատկությանը կոչվում է մոնոտոնային կամ մոնոտոն։ Սա մոնոտոն ֆունկցիայի ավելի ընդհանուր հասկացության հատուկ դեպքն է։

Չնվազող և չաճող տերմինները օգտագործվում են ցանկացած հնարավոր շփոթմունքներից խուսափելու համար՝ կապված խիստ աճելու և խիստ նվազելու հետ։

Եթե հաջորդականության տարրերը ամբողջ թվեր են, ապա հաջորդականությունը ամբողջ հաջորդականություն է։ Եթե հաջորդականության տարրերը բազմանդամներ են, ապա հաջորդականությունը բազմանդամ հաջորդականություն է։

Եթե S-ը օժտված է տոպոլոգիայով, ապա հնարավոր է դառնում որոշել անսահմանափակ հաջորդականության զուգամիտությունը S-ում։ Այսպիսի որոշումները ներառում են հաջորդականության սահման հասկացությունը։

Եթե A-ն բազմանդամ է, ազատ մոնոիդը A-ի նկատմամբ (նշանակված է A*) մոնոիդ պարունակում է բոլոր սահմանափակ հաջորդականությունները (կամ տողերը) կազմված զրո կամ ավելի A-ի էլեմենտներից, զուգամիտության երկուական գործողությամբ։ Ազատ կիսախումբը A+, A*-ի կիսախումբ է, որը պարունակում է բոլոր էլեմենտները, բացի դատարկ հաջորդականությունից։

Հաջորդականությունների վերլուծությունը
Վերլուծություններում, երբ խոսվում է հաջորդականությունների մասին, ընդհանրապես նկատի է առնվում հետևյալ տեսքի հաջորդականությունը

ըստ որի, էլեմենտների անսահմանափակ հաջորդականությունը ինդեքսավորված է բնական թվերով։

Հարմար կլինի ունենալ հաջորդականություն, որ սկսվում է 1-ից կամ 0-ից տարբեր ինդեքսով։ Օրինակ, հաջորդականությունը կազմված xn = 1/log(n)-ով որոշված կլինի միայն n ≥ 2 համար։
Երբ խոսվում է այսպիսի անսահմանափակ հաջորդականությունների մասին, սովորաբար բավական է (և շատ բան չի փոխի նկատառումների մեծամասնության համար) ենթադրել, որ հաջորդականության անդամները սահմանված են նվազագույնը բոլոր բավական մեծ ցուցանիշների համար, որը ավելի մեծ է քան ինչ-որ տրված N։

Հաջորդականությունների ամենապարզ տեսակը թվայինն է, որոնք իրական կամ կոմպլեքս թվերի հաջորդականություն է։
Այս տեսակը կարող է ընդհանրացվել ինչ-որ վեկտորական տարածության էլեմենտների հաջորդականության։ Վերլուծություններում, վեկտորական տարածությունները հաճախ ֆունկցիոնալ տարածություններ են։ Ավելի ընդհանուր, հաջորդականությունները կարելի է ուսումնասիրել ինչ-որ տոպոլոգիական տարածության էլեմենտներով։

Շարքեր

Հաջորդականության էլեմենտների գումարը շարք է։ Ավելի ճիշտ, եթե (x1, x2, x3, ...) հաջորդականություն է, կարելի է որոշել մասնակի գումարների հաջորդականությունը՝ (S1, S2, S3, ...)

 միջոցով։

Ձևականորեն, այս հաջորդականությունների զույգը ներառում է շարքեր x1, x2, x3, ...էլեմենտներով, որը նշանակվում է այսպես

Եթե մասնակի գումարների հաջորդականությունը զուգամետ է, ապա նրա սահմանի համար նաև օգտագործվում է անսահմանափակ գումարի նշագրությունը։ Ավելի մանրամասն, նայիր շարքեր։

Անսահմանափակ հաջորդականությունները տեսական համակարգչային գիտությունում
Թվային սիմվոլների (կամ բնութագրեր) ահսահմանափակ հաջորդականությունները կազմված սահմանափակ այբուբենից հատուկ հետաքրքրություն են ներկայացնում տեսական համակարգչային գիտությունում։ Դրանք հաճախ հղվում են որպես հաջորդականություններ կամ հոսքեր, որպես սահմանափակ տողերին հակադիր։ Անսահմանափակ երկուական հաջորդականությունները, օրինակ, բիթերի (բնութագրեր կազմված {0, 1} այբուբենից) անսահմանափակ հաջորդականություններ են։ Բոլոր անսահմանափակ, երկուական հաջորդականությունների C = {0, 1}∞ բազմությունը երբեմն կոչվում է Քենթորի տարածություն։

Անսահմանափակ երկուական հաջորդականությունները կարող են ներկայացնել պաշտոնական լեզու (տողերի բազմություն)` նշանակելով հաջորդականության n րդ բիթը 1, միայն և միայն այն դեպքում, եթե n րդ տողը(շորթլեքս կարգում) կա լեզվում։Ուստի, կոմպլեքս տեսակների ուսումնասիրությունը, որոնք լեզուների բազմություն են, կարող են դիտարկվել որպես անսահմանափակ հաջորդականությունների բազմության ուսումնասիրություն։

Անսահմանափակ հաջորդականությունը կազմված {0, 1, ..., b−1} այբուբենից կարող է նաև ներկայացնել իրական թիվ` արտահայտված b-հիմքով դիրքային թվային համակարգում։ Այս համարժեքությունը հաճախ օգտագործվում է իրական վերլուծության տեխնիկան կոմպլեքսային տեսակների բերելու նպատակով։

Հաջորդականությունները որպես վեկտորներ
Դատից մեծ հաջորդականությունները կարող են նաև ներկայացվել որպես վեկտորներ վեկտորական տարածությունում։ Մասնավորապես, F-գնահատված հաջորդականությունների բազմությունը (որտեղ F դաշտ) է, բնական թվերի բազմությունից մեծ F-գնահատված ֆունկցիայի ֆունկցիոնալ տարածք (փաստորեն, արդյունքային տարածք)։

Մասնավորապես, հաջորդականության տարածք տերմինը սովորաբար վերաբերում է -ի էլեմենտներով բոլոր հնարավոր անսահմանափակ հաջորդականությունների բազմության գծային ենթատարածքին։

Կրկնակի անսահմանափակ հաջորդականություններ
Սովորաբար, անսահմանափակ հաջորդականություն տերմինը վերաբերում է մի հաջորդականության, որը անսահմանափակ է մի ուղղությամբ և սահմանափակ մյուս ուղղությամբ, հաջորդականությունն ունի առաջին էլեմենտ, բայց ոչ վերջին էլեմենտ (եզակի անսահմանափակ հաջորդականություն)։ Կրկնակի անսահմանափակ հաջորդականությունը անսահմանափակ է երկու ուղղություններով՝ այն չունի ոչ առաջին, ոչ վերջին էլեմենտ։ Եզակի անսահմանափակ հաջորդականությունները ֆունկցիաներ են բնական թվերից (N) մինչև ինչ-որ բազմություն, մինչդեռ կրկնակի անսահմանափակ հաջորդականությունները ֆունկցիաներ են ամբողջ թվերից (Z) մինչև ինչ-որ բազմություն։

Եզակի անսահմանափակ հաջորդականությունները կարելի է մեկնաբանել որպես բնական թվերի  կիսախումբ շրջանակի էլեմենտներ, իսկ կրկնակի անսահմանափակ հաջորդականությունները՝ որպես ամբողջ թվերի  խմբային շրջանակի էլեմենտներ։ Այս հեռանկարն օգտագործվում է հաջորդականությունների Կոշիի արդյունքում։

Դասական-ինդեքսավորված հաջորդականություն
 հաջորդականությունների ընդհանրացումն է։ Եթե α-ն սահմանային դասական թիվ է, իսկ X-ը՝ բազմություն, X-ի էլեմենտների α-ինդեքսավորված հաջորդականությունը ֆունկցիա է α-ից to X-ին։ Այս տերմինաբանությամբ ω-ինդեքսավորված հաջորդականությունը դասական հաջորդականություն է։

Հաջորդականություններ և ավտոմատներ 
Ավտոմատները կամ սահմանափակ հաղորդման մեքենաները կարող են ենթադրվել որպես ուղղորդված դիագրամներ, նշված առավելություններով օգտագործելով հատուկ այբուբեն Σ։ Մի հաղորդումից մյուսին ավտոմատ անցնելու ամենատարածված տեսակները մուտքագրված սիմվոլների կարդալն է Σ-ից; կարգավորված մուտքը այսպիսի ավտոմոտների համար հաջորդականությունն անվանում է բառ (կամ մուտքային բառ)։ Հաղորդումների հաջորդականությունը, որոնք հանդիպում են ավտոմատի կողմից բառի մշակման շամանակ, կոչվում է հոսք։ Չդետերմինացված ավտոմոտը կարող է ունենալ չնշված կամ կրկնօրինակ ելք ամեն հաղորդման համար, որը տալիս է ավելին քան մեկ հաղորդողը ինչ-որ մուտքի սիմվոլի։ Սա ուղղակի ենթադրում է մի քանի հնարավոր հոսքերի ստեղծում տրված բառի համար, յուրաքանչյուրը լինելով մեկ հաղորդման հաջորդականություն, այլ ոչ թե մեկ հաղորդման ստեղծում, որը հաղորդումների բազմության հաջորդականություն է; այնուամենայնիվ, 'հոսք'ը երբեմն օգտագործվում է նշանակելով վերջում ասվածը։

Հաջորդականությունների տեսակները
±1-հաջորդականություն
Թվաբանական պրոգրեսիա
Կոշիի հաջորդականություն
Ֆարեի հաջորդականություն
Ֆիբոնաչիի հաջորդականություն
Երկրաչափական պրոգրեսիա
Նայիր-և-ասա հաջորդականություն
Տուե–Մորսի հաջորդականություն

Կապված համակցություններ
Ցանկ (հաշվարկ)

Ռեկուրսիա(համակարգչային գիտություն)
Կորտեժ
Բազմության թեորեմ

Գործողությունները և հաջորդականությունները
Կոշիի արդյունք
Հաջորդականության սահման

Ուշացումով Ֆիբոնաչիի գեներատոր 

Ուշացումով Ֆիբոնաչիի գեներատորը պատահական թվերի գեներատորի օրինակ է։ Այս դասի պատահական թվերի գեներատորը ուղղված է բարելավելու «ստանդարտ» գծային ներդաշնակ գեներատորները։ Սրանք հիմնված են Ֆիբոնաչիի հաջորդականության ընդհանրացման վրա։ Ֆիբոնաչիի հաջորդականությունը կարող է բնութագրվել կրկնվող հարաբերությամբ։

Հետևաբար նոր ստացվող թիվը հաջորդականության նախորդ երկու թվերի գումարն է։ Սա ընդհանրացված հաջորդականությունն է։
Որի դեպքում նոր ստացվող թիվը նախորդ երկու թվերի որոշակի կոմբինացիա է. m-ը սովորաբար 2-ի որոշակի աստիճան է։ (m = 2M), հաճախ 232 կամ 264. օպերատորը հիմնականում բինար գործողություն է։ Սա կարող է լինել գումարում, հանում, բազմապատկում կամ էլ բիթային գործողություն թվաբանական բացառիկ-կամ օպերատոր (XOR)։ Այս տիպի գեներատորների օգտագործման մեխանիզմը բավականին բարդ է, և դժվար է ընտրել j և k-ի համար պատահական թվեր։
Եթե կատարվող գործողությունը գումարում է, ապա գեներատորն անվանում են գումարմամբ ուշացման Ֆիբոնաչիի գեներատոր, եթե բազմապատկում է, ապա բազմապատկմամբ ուշացման Ֆիբոնաչիի գեներատոր, և եթե գործողությունը յուրահատուկ-կամ է XOR, գործողությունն անվանում են երկհնարավոր ընդհանրացված հետադարձ քայլով մուտքագրում։ Մերսենի ոլորապտույտ ալգորիթմը երկհնարավոր ընդհանրացված գեներատորի տարատեսակ է։ Վերջինս նման է նաև գծային հետադարձ կապով գեներատորի ալգորիթմին։

Ուշացումով Ֆիբոնաչիի գեներատորի հատկությունները 
Ուշացումով Ֆիբոնաչիի գեներատորը կատարվում է (2k - 1)*2M-1 անգամ, եթե կատարվող գործողությունը գումարու կամ հանում է, և (2k-1)*k, եթե գործողությունը յուրահատուկ-կամ է։ Մյուս կողմից, եթե կատարվում է բազմապատկում (2k - 1)*2M-3 կամ գումարման 1/4-ը։ Այս մաքսիմում քանակին հասնելու համար անհրաժեշտ բազմանդամի տեսքն է
y = xk + xj + 1
j և k-ի այս հավասարմանը բավարարող արժեքներից ամենաճանաչվածներն են
{j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159} [1], {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521}, {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 1279}

j և k-ի բոլոր այն հարաբերությունները, որոնք բավարարում են հավասարմանը, անվանում են ոսկե հարաբերություն։

Ուշացումով Ֆիբոնաչիի գեներատորի հետ հնարավոր պրոբլեմները 
Ռոբերտ Զիֆը ասում, որ հայտնի է, որ երկարժեքանի գեներատորների տիպի գեներատորները, ինչպիսին է R(103-250)-ը, ունեն լուրջ թերություններ։ Մարսալիան ուսումնասիրել է այդ տիպի գեներատորների վարքը և խորհուրդ է տալիս չօգտագործել այս տիպի գեներատորները։ Երկարժեքանի հետադարձ կապով գեներատորների հիմնական թերությունն այն է, որ նրանք կառուցվում են xn, xn − a, և xn − b մեծությունների միջև կոռելյացիայի հիման վրա։ Երբ այս գեներատորները տարածվում են գեներատորների չափսերի վրա, դրանք կարող են բերել ակնհայտ էական սխալների։ Ուշացումով Ֆիբոնաչիի գեներատորի կարգաբերումը բարդ, համալիր խնդիր է։ Այս գեներատորի մեկ այլ պոտենցիալ պրոբլեմ է այն, որ դրան վերաբերող մաթեմատիկական տեսությունն ամբողջական չէ, և այդ պատճառով ավելի շատ հաշվի են առնվում վիճակագրական դիտարկումներն ու հետազոտությունները, քան տեսական գաղափարները։

Հաջորդականություններ և շարքեր
Տարրական մաթեմատիկա