Cтраница 3
Построением латинских квадратов и изучением их свойств занимаются специалисты по комбинаторной математике и по математической статистике. [31]
Задачу о существовании системы троек Киркмана можно, конечно, ставить для произвольного порядка и. Доказательство достаточности этого условия существования системы троек Кирдшана долго оставалось нерешенной проблемой комбинаторной математики. [32]
Описанное направление эмиссионной томографии в целом относится к алгебраическим методам томографии. Развитие математического аппарата вычислительной томографии в данном случае заключается в дополнительном использовании свойств исключительно интересного объекта комбинаторной математики - так называемых ( v, k, А) - матриц. [33]
Татта представлять нет необходимости: его яркие, насыщенные своеобразными идеями исследования комбинаторных проблем известны многим математикам - геометрам, специалистам по дискретной математике, алгебраистам. Его известные монографии по связности графов и теории матроидов продолжают оказывать существенное влияние на молодых исследователей, занимающихся комбинаторной математикой. [34]
Математические методы принятия решений ( теория исследования операций) используют теорию игр, теорию массового обслуживания, приемы дискретного анализа ( комбинаторная математика) и математического программирования. Эти методы имеют решающее значение для успешного исследования больших систем, управления ими вообще и, в частности, при применении кибернетики и теории исследования операций. Весьма актуальны здесь проблемы многоступенчатой оптимизации и разработки соответствующих многоступенчатых процедур принятия решения, позволяющих добиться оптимального функционирования отраслей социалистического народного хозяйства и служить основой рационального применения ЦВМ и систем ЦВМ. Статистическим методам исследования и в том числе методам оценки надежности и эффективности на этапах проектирования и разработок должно быть при этом уделено особое внимание. При этом особое внимание должно быть уделено методам теории эксплуатации, обслуживания и восстановления больших систем, а также методам их технической диагностики. Проблема - человек - машина для больших систем должна иметь особо важное значение. [35]
Конечно, каждую из рассматриваемых ниже задач можно сейчас отнести к теории кодирования, но есть нечто общее в их предыстории, на что мы и хотели бы обратить внимание. В то же время все задачи, как и вторая, давно и очень естественно могли бы быть поставлены в рамках комбинаторной математики. Их можно было бы назвать надуманными, но сейчас мы знаем их применения. Напрашивается вывод: если комбинаторная задача формулируется естественно и красиво, то она заслуживает самого пристального внимания не только потому, что се решение может доставить эстетическое удовольствие или привести к развитию новых методов, но и потому, что в этом случае очень правдоподобна возможность ее практического использования. Заметим, что аргументы в пользу этого вывода далеко не исчерпываются приводимыми ниже примерами. Иллюстраций из дискретного анализа, являющегося основным математическим аппаратом кибернетики, более чем достаточно. [36]
Это привело к развитию вычислительных методов, применимых к широкому кругу комбинаторных задач; некоторые из этих методов мы обсудим в этой главе. Наиболее фундаментальным и часто используемым является алгоритм перебора с возвратом ( разд. Теория графов относится к областям комбинаторной математики, имеющим самые широкие приложения; в разд. Раздел 2.5 содержит введение в проблему сортировки, которая непосвященным часто кажется тривиальной, а в действительности связана с глубокими математическими исследованиями и чрезвычайно важна практически. Если бы удалось выяснить, чем заняты в произвольно заданный момент времени все ЭВМ мира, то обнаружилось бы, что большая их часть занимается именно сортировкой. [37]
Другой важной стороной всякой развитой математической теории является присущий только ей аппарат решения возникающих в ней проблем. Комбинаторная математика, однако, широко заимствует сиоп методы из разных математических дисциплин: алгебры, анализа, теории вероятностей, геометрии и др. В этом не только ее слабость, но и сила: известно, что в настоящее время многие выдающиеся научные результаты получаются именно на стыке паук, на перекрестках различных направлений. Тем не менее специалисты по комбинаторной математике с конца СО-х гг. стремятся выявить специфические комбинаторные методы трактовки задач дискретной математики, чтобы поставить комбинаторные исследования на более прочный теоретический фундамент. [38]
Существенно, что на эту процедуру мало влияют ограничения типа: число единиц в строке должно равняться q, или не превышать q, или быть простым. Вычислительный подход важен еще и потому, что в теории блок-схем много нерешенных задач, для которых надо либо найти точное решение, либо построить опровергающий пример. Именно в таких случаях - как и вообще в комбинаторной математике - разумное использование ЭВМ в качестве инструмента поиска почтц неизбежно. [39]
Точная физико-химическая природа описанных процессов очень сложна, и нет сомнения, что в них играют вспомогательную роль отдельные ферменты, переносящие свободные нуклеотиды к РНК, а также АТФ ( аденозинтрифосфат), поставляющий необходимую для этого синтеза энергию. Вероятно, потребуется очень большой срок, прежде чем мы получим подробную картину всех явлений, из которых складывается процесс синтеза белков. Однако и при современном уровне наших знаний можно поставить вопрос: какие принципы комбинаторной математики полезны для изучения того, как генетическая информация, содержащаяся в цепях нуклеиновых кислот, переносится в цепи белков. [40]
Однако применить линейное программирование для задач о па-росочетании в недвудольных графах оказалось весьма сложно; для этого потребовались новые средства: техника описания выпуклой оболочки векторов инцидентности паросочетаний с помощью линейных неравенств. Такой подход положил начало изучению других комбинаторно определяемых полиэдров и привел к новой ветви комбинаторной математики, называемой полиэдральной комбинаторикой. [41]
Прежде чем переходить к изложению этих идей, предупредим читателя относительно метода, принятого в настоящей главе. Многие свойства приводятся без доказательств, поскольку их можно легко найти в ряде стандартных учебников. С другой стороны, комбинаторная математика и диаграммная техника, используемые в более строгих доказательствах, весьма сложны. Основные физические идеи и математические приемы могут оказаться скрытыми за фасадом обозначений. Поэтому мы надеемся, что принятое здесь упрощенное изложение послужит достаточно полным введением в предмет и облегчит заинтересованному читателю дальнейшее его изучение. [42]
В полученном квадрате каждая буква одного квадрата связана один и только один раз с каждой буквой другого квадрата. Такие два латинских квадрата называются ортогональными. Полученный квадрат второго порядка называют также греко-латинским квадратом. Задача о нахождении ортогональных латинских квадратов в комбинаторной математике еще полностью не решена. [43]
В полученном квадрате каждая буква одного квадрата связана один и только один раз с каждой буквой другого квадрата. Такие два латинских квадрата называются ортогональными. Полученный квадрат второго, порядка называют также греко-латинским квадратом. Задача о нахождении ортогональных латинских квадратов в комбинаторной математике еще полностью не решена. Латинский квадрат для п10 не исследован. Если имеется - k n - 1 попарно ортогональных латинских квадратов, то они образуют так называемую полную систему ортогональных латинских квадратов. Полную систему ортогональных латинских квадратов для пр ( р - простое число) можно построить, - используя поля Галуа. [44]
В полученном квадрате каждая буква одного квадрата связана один и только один раз с каждой буквой другого квадрата. Такие два латинских квадрата называются ортогональными. Полученный квадрат второго порядка называют также греко-латинским квадратом. Задача о нахождении ортогональных латинских квадратов в комбинаторной математике еще полностью не решена. [45]