Cтраница 2
Таким образом, для нахождения пути и факторов, необходимых для подсчета числителя передаточного отношения Ge / fte из (3.17), необходимо взять производную по вершине е от структурного числа 5 ( ГЮ), раскрыть ее и определить цикловую структуру получаемых при этом отображений. [16]
Для случайной n - подстановки вводится ряд новых характеристик, связанных с ее цикловой структурой, и проводится их асимптотический ( при п - оо) анализ, проливающий дополнительный свет на ее асимптотические свойства. Рассматриваются некоторые вопросы цикловой структуры при неравновероятном выборе подстановок. [17]
Теория случайных подстановок является хорошо развитым разделом вероятностной комбинаторики. Гончаров уже в сороковых годах достаточно полно исследовал цикловую структуру случайных подстановок, интерес к этой области исследований не пропал. [18]
В данной статье мы рассмотрим также некоторые неравновероятные схемы выбора n - подстановок. Первый тип - это подстановки, вероятность появления которых пропорциональна числу циклов в ее цикловой структуре. Это так называемая схема Эванса, хорошо известная в литературе ( см. [14-17]), в которой более вероятны подстановки с малым числом циклов или наоборот, в зависимости от величины некоторого параметра в. Здесь мы рассмотрим схему серий, когда вероятности РА появления подстановки А зависят от числа циклов в этой подстановке. [19]
Поводом для рассмотрения объемов алгоритмов является изучение экономичности различных формализмов, представляющих алгоритмические процессы. При написании машинных программ для функций, возникающих в практических ситуациях, можно обойтись без операторов условного перехода и написать программу, процесс выполнения которой определяется очень просто вложенной цикловой структурой. Более того, время выполнения этой программы не будет сильно отличаться от времени выполнения произвольной программы. Возникает вопрос, зачем вообще мы используем условные переходы. Ответ заключается в эффективности представления. Сравним, например, объем изображения примитивно рекурсивной функции, использующего примитивно рекурсивную схему, с представлением посредством машины Тьюринга, которая вычисляет ту же функцию. [20]
В соответствии с равенством (2.7) вторая и третья суммы в этой формуле имеют простые выражения. В первой сумме перманент per ( J - TI - Tj ] равен числу подстановок степени п, противоречивых с подстановками tgi и tgj. Согласно результатам Тушара [4], это число зависит от цикловой структуры подстановки t - ltg. [21]
На языке теории групп элементы R и R 1 являются взаимно обратными, ибо R ( Rp - l) RP I. Они являются также взаимно сопряженными; действительно, напомним, что если Р является любой перестановкой и РР 1 /, P - 1QP S, то S называется элементом, сопряженным с Q. Важно отметить, что сопряженные перестановки имеют одну и ту же цикловую структуру. [22]