Кіріспе
Дөңгелек ауысу: Математикалық ұғым және бағдарламалық жасақтаманы әзірлеудегі қолданыстары. Комбинаторлық математикада дөңгелек ауысу – бұл топтағы элементтерді қайта орналастыру операциясы, онда соңғы элементтің бірінші орынға жылжуымен, қалған барлық элементтер келесі орынға ығыстырылады немесе кері операция орындалады. Дөңгелек ауысу – циклдық пермутацияның ерекше түрі, ал циклдық пермутация – пермутацияның ерекше түрі. Формальды түрде, дөңгелек ауысу – бұл топтағы n элементтің σ пермутациясы, яғни, барлық i = 1, …, n үшін modulo n немесе барлық i = 1, …, n үшін modulo n.
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the n entries in the tuple such that either
modulo n, for all entries i = 1, , n
or
modulo n, for all entries i = 1, , n.
The result of repeatedly applying circular shifts to a given tuple are also called the circular shifts of the tuple. For example, repeatedly applying circular shifts to the four tuple (a, b, c, d) successively gives
(d, a, b, c),
(c, d, a, b),
(b, c, d, a),
(a, b, c, d) (the original four tuple),
and then the sequence repeats; this four tuple therefore has four distinct circular shifts. However, not all n tuples have n distinct circular shifts. For instance, the 4 tuple (a, b, a, b) only has 2 distinct circular shifts. The number of distinct circular shifts of an n tuple is , where k is a divisor of n, indicating the maximal number of repeats over all subpatterns. In computer programming, a bitwise rotation, also known as a circular shift, is a bitwise operation that shifts all bits of its operand. Unlike an arithmetic shift, a circular shift does not preserve a number's sign bit or distinguish a floating point number's exponent from its significand. Unlike a logical shift, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.
Дөңгелек ауысуды берілген топқа қайталап қолдану нәтижесі де топтың дөңгелек ауысулары деп аталады. Мысалы, төрттік (a, b, c, d) топтарына дөңгелек ауысуды қайталап қолдану келесіні береді: (d, a, b, c), (c, d, a, b), (b, c, d, a), (a, b, c, d) (алғашқы төрттік), содан кейін тізбек қайталанады; осы төрттікке сәйкес төрт түрлі дөңгелек ауысу бар. Дегенмен, барлық n топтарының n ерекше дөңгелек ауысуы бола бермейді. Мысалы, (a, b, a, b) төрттігі үшін тек 2 ерекше дөңгелек ауысу бар. n топтарының ерекше дөңгелек ауысуларының саны , мұнда k – n-нің бөлгіші, бұл барлық ішкі үлгілер бойынша қайталанудың максималды санын көрсетеді. Компьютерлік бағдарламалауда биттік айналу, сонымен қатар дөңгелек ауысу деп те аталады, – бұл операцияның барлық биттерін ығыстыратын биттік операция. Арифметикалық ығысудан айырмашылығы, дөңгелек ауысу санның таңба битін сақтамайды және қозғалмалы нүктелі санның экспонентасын оның маңызды бөлігінен ажыратпайды. Логикалық ығысудан айырмашылығы, бос бит позициялары нөлдермен толтырылмайды, бірақ тізбектен ығыстырылған биттермен толтырылады.
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the n entries in the tuple such that either
modulo n, for all entries i = 1, , n
or
modulo n, for all entries i = 1, , n.
The result of repeatedly applying circular shifts to a given tuple are also called the circular shifts of the tuple. For example, repeatedly applying circular shifts to the four tuple (a, b, c, d) successively gives
(d, a, b, c),
(c, d, a, b),
(b, c, d, a),
(a, b, c, d) (the original four tuple),
and then the sequence repeats; this four tuple therefore has four distinct circular shifts. However, not all n tuples have n distinct circular shifts. For instance, the 4 tuple (a, b, a, b) only has 2 distinct circular shifts. The number of distinct circular shifts of an n tuple is , where k is a divisor of n, indicating the maximal number of repeats over all subpatterns. In computer programming, a bitwise rotation, also known as a circular shift, is a bitwise operation that shifts all bits of its operand. Unlike an arithmetic shift, a circular shift does not preserve a number's sign bit or distinguish a floating point number's exponent from its significand. Unlike a logical shift, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence.
Қолданбалар
Циклдік кодтар – код сөзінің шеңберлік ығысуы әрқашан басқа код сөзін тудыратын қасиетке ие блок кодтарының бір түрі. Бұл келесі жалпы анықтаманы негіздейді: Σ әліпбиі бойынша s жолы үшін, shift(s) оның барлық шеңберлік ығысулар жиынын білдірсін, ал L жолдар жиыны үшін, shift(L) L жиынындағы жолдардың барлық шеңберлік ығысулар жиынын білдірсін. Егер L циклдік код болса, онда shift(L) ⊆ L; бұл L-дің циклдік тіл болуы үшін қажетті шарт. shift(L) операциясы формальды тілдер теориясында зерттелді. Мысалы, егер L контекстсіз тіл болса, онда shift(L) де контекстсіз болады. Сондай-ақ, егер L ұзындығы n тұрақты өрнекпен сипатталса, онда shift(L)-ді сипаттайтын ұзындығы O(n³) тұрақты өрнек болады.
and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a cyclic language. The operation shift(L) has been studied in formal language theory. For instance, if L is a context free language, then shift(L) is again context free. Also, if L is described by a regular expression of length n, there is a regular expression of length O(n3) describing shift(L).