Задача линейного программирования (ЗЛП) состоит в определении значений упорядоченной совокупности переменных xj, j=1(1)n при которых линейная целевая функция достигает экстремального значения и при этом выполняются (удовлетворяются) все ограничения (они также линейные) в форме равенств или неравенств. Требуется найти план Х <n> = <x1, x2, ..., xn>, который обеспечивает получение целевой функцией с экстремальным значением.
Пользователь
Метод ветвей и границ. Задача коммивояжера
Среди методов, привлекаемых к решению задач исследования операций (ИО) особое место занимает метод ветвей и границ (МВГ), который внес оригинальный взгляд в целом на проблемы оптимизации и позволил по другому воспринимать смысл оптимальности решений. Авторы разработанного метода предложили оценивать целевую функцию (ЦФ) задачи нижней границей целевой функции (НГЦФ) всего множества решений конкретной задачи, не получая ни всех решений, ни одного из них. Располагая такой оценкой, можно формировать решения задачи последовательно их улучшая не сильно уклоняясь от НГЦФ. В статье предлагается детальный разбор этого метода решения на числовом примере с подробными комментариями выполняемых действий при поиске оптимального решения.
Исследование операций
При функционировании больших сложно устроенных систем в них, как правило, протекают многообразные процессы, сущность которых состоит в различного рода преобразованиях физико-химической субстанции из сырья в конечный продукт, поставляемый на рынок. Наряду с материальной субстанцией в производственных процессах широко используется информация управленческая и технологическая. Когда-то не в столь давние времена достаточно сложным механизмом, системой считался часовой механизм, реализуемый зацеплением шестеренок. Механизм преобразовывал временную субстанцию в информацию. Выходным продуктом такого механизма была информация - сведения о текущем временном моменте, к точности которой уже в те времена предъявлялись жесткие требования. Все процессы сложных производственных систем также, подобно механизму часов, постоянно должны быть в "зацеплении", тесно взаимодействовать, протекать синхронно и согласованно. Главным требованием к такой системе с шестеренками была точность отсчетов временных промежутков. Точность нужна везде от водных, наземных, воздушных транспортных систем до спутниковых космических, атомных энергетических станций. Исследуя операции следует помнить об истории их появления и проявления в различных отраслях хозяйства и производства.
Факторизация и эллиптическая кривая. Часть V
К тем сведениям об эллиптических кривых (ЭК), которые доступны читателям Хабра и Интернета в целом, а также из бумажных книг, предлагаю дополнительные, уточняющие важные детали, опущенные в некоторых статьях. Например, в работе приводится изображение тора (рис. 4), но никаких оговорок не делается. Откуда он взялся, почему тор? Другие авторы вообще не упоминают эту фигуру. В чем здесь дело?
Не могу назвать публикацию на Хабре и других сайтах, где автор говорил бы о полях многочленов, хотя обозначение ) таких полей некоторыми авторами и используются, но делается это неправильно. Неприводимый многочлен и примитивный элемент поля и не задаются, что не позволяет читателю построить такое поле и работать с ним, проверить вычислением приводимый результат, если числовой пример вообще приводится. От таких публикаций остается ощущение зря потраченного времени. Такие поля расширения используются в стандартах цифровой подписи и шифрования рядом государств.
Факторизация чисел и сумма неизвестных делителей. Часть IV
Факторизация чисел и методы решета. Часть II
Факторизация чисел и эллиптическая кривая. Часть III
Факторизация чисел и сумма неизвестных делителей. Часть IV
Факторизация и эллиптическая кривая. Часть V
Возможность единственного представления составного нечетного натурального числа (СННЧ) N в виде произведения степеней простых (кроме 2) чисел составляет существо основной теоремы арифметики (ОТА). Для больших чисел, содержащих в своей записи и более цифр, эта возможность, а точнее задача не получила приемлемого для практики (за обозримое время) решения до наших дней. Кратко эту задачу называют задачей факторизации больших чисел(ЗФБЧ). Ее формулировка проста и известна уже несколько тысячелетий: для заданного натурального числа N = pq найти все его нетривиальные делители.
Факторизация и эллиптическая кривая. Часть III
Факторизация чисел и методы решета. Часть II
Факторизация и эллиптическая кривая. Часть III
Факторизация чисел и сумма неизвестных делителей. Часть IV
Факторизация и эллиптическая кривая. Часть V
Использование эллиптических кривых (ЭК) для решения разнообразных задач криптологии коснулось каким-то боком и факторизации чисел. Здесь будем рассматривать вопрос, касающийся ЭК и не только в связи с проблемой факторизации составного нечетного натурального числа (СННЧ), но несколько шире.
Если пройтись по Интернету и по статьям об ЭК на Хабре, то после этого возникает мысль, что существует определенный пробел всех без исключения публикаций, включая и объемные бумажные книги. Авторы почему-то считают само-собой разумеющимся понимание природы ЭК и ее аддитивной группы, ее появление. На самом деле ЭК и ее группа (мое мнение) — это чудо!
Группа точек плоскости, множество которых замкнуто по операции сложения, оказалась каким-то образом встроена в ЭК и мы об этом до сего дня не знали бы, не располагая теорией групп, и даже при наличии теории групп, без гения Эйлера и Пуанкаре, которые нам эту группу открыли. В свое время Иоганн Кеплер открыл человеку законы движения Планет и качественно описал их траектории, но только гений Ньютона смог объяснить природу этих законов.
Правда для этого ему пришлось открыть свои законы движения/тяготения и изобрести дифференциальное и интегральное исчисления. Задача взятие двукратного интеграла от второго закона Ньютона, в котором ускорение — вторая производная пути, решением имеет плоскую кривую второго (не третьего, не путать эллипсы — траектории планет, спутников и эллиптические кривые в криптологии) порядка, что до И. Ньютона было открыто И.Кеплером.
Факторизация чисел и методы решета. Часть II
Задается N — большое составное нечетное натуральное число (СННЧ), которое требуется факторизовать. Математическая теория метода решета числового поля (NFS) строится на основе теории делимости в алгебраических числовых полях. Перед любым автором, как и передо мной, возникает трудность сжатого изложения весьма обширного материала, касающегося методов SNFS и GNFS. Так как 2-й возник из 1-го я не привожу их отличий, хотя об этом много сказано.
О методах написаны целые книги. Но, помня о собственных затруднениях в изучении методов и преодолении их, считаю, что даже «куцее» урезанное изложение будет способствовать ознакомлению читателей с методами и идеями, лежащими в их основе. Надеюсь, что понимание этих идей их ограниченности (что практика подтверждает многократно), позволит более трезво подойти к тому, что предлагается мной в проблеме факторизации.
Можно сказать читатели принудили меня доносить до них чужие идеи, которые я не разделяю, так как свои считаю более обоснованными и прогрессивными, более здравыми. Они пока не получили завершенного вида, но время еще есть. Хочу изменить у читателей отношение к своим идеям и получить поддержку, а не минусы в комментариях, не подкрепляемые доводами. Личную неприязнь или «ничего не понял» доводом для минусования публикации считать не могу.
Неоправданное усложнение (матрица СЛАУ для имеет размер 6000000×6000000) задачи факторизации больших чисел (ЗФБЧ) подвигло меня серьезно заняться этой проблемой. Уже удалось вскрыть закон распределения делителей СННЧ в НРЧ, т.е. понять где и как прячутся делители в натуральном ряде чисел, что конечно же упростит их поиск и обнаружение.
Факторизация чисел и методы решета. Часть I
В работе рассматривается традиционный подход, который автором в ряде статей критикуется.
Здесь я воздержусь от критики, и направлю свои усилия на разъяснение сложных моментов в традиционном подходе. Весь арсенал существующих методов не решает задачу факторизации в принципе, так как почти все решеточные и другие алгоритмы построены на жесткой связи и зависимости времени их выполнения от разрядности факторизуемого числа N. Но замечу, что у чисел имеются и другие свойства кроме разрядности, которые можно использовать в алгоритмах факторизации.
Оценки сложности — эвристические опираются на рассуждения ограниченные авторским пониманием проблемы. Пора бы уже понять, что факторизация чисел в глубоком тупике, а математикам (не только им) пересмотреть свое отношение к проблеме и создать новые модели.
Простая идея факторизации целого нечетного числа N исторически — состоит в поиске пары квадратов чисел разной четности, разность которых кратна kN, при k =1 разложение успешно реализуется так как в этом случае сразу получаем произведение двух скобок c сомножителями N. При k>1 случаются тривиальные разложения.
Таким образом, проблема факторизации преобразуется в проблему поиска подходящих квадратов чисел. Понимали эти факты многие математики, но П. Ферма первым в 1643 году реализовал идею поиска таких квадратов в алгоритме, названном его именем. Перепишем иначе приведенное соотношение .
Если разность слева от равенства не равна квадрату, то изменяя х, можно подобрать другой квадрат, чтобы и справа получался квадрат. Практически все нынешние алгоритмы используют эту идею (поиска пары квадратов), но судя по результатам, похоже, что идея себя исчерпала.
Количественные характеристики отношений
Теория отношений в математике и в ряде предметных областей (принятие решений, базы знаний и данных, математическая лингвистика, моделирование процессов, и др.) играет весьма заметную роль, но пока далека от завершения. Как и в других отраслях математического знания ее известные результаты в большей мере относятся к вопросам и задачам существования тех или иных ее объектов, чем к задачам их перечисления. Казалось бы любой исследователь в конкретной отрасли теории должен бы интересоваться общей и полной картиной, интересующих его объектов и их зависимостей, обозревать полную панораму. Но увы, сделать это весьма проблематично, так как такую панораму (картину) никто не создал и не предлагает. Даже предложенный в работе каталог отношений проблему не закрывает.
Принятие решений. Пример
Продолжая тему скажу, что посмотрел публикации других авторов Хабра по этой теме. Интерес к проблемам имеется, но в теорию влезать никто не желает. Действуют как пионеры первооткрыватели. Это было бы прекрасно, при получении ими новых результатов, достижений, но к этому никто и не стремится.
А на деле получается хуже, чем уже известно, не учитывается масса факторов, результаты теории применяются там, где она это делать не рекомендует и вообще не очень серьезно все выглядит, хотя Хабр, как надо понимать к этому и не стремится. Читатели не могут и не должны играть роль фильтра.
Принятие решений
Эта работа о безопасности информационных систем, в которых принимаются серьезные информационные решения и которые можно подразделить на три типа:
- во-первых, системы извлечения информации (информационно-поисковые системы (ИПС), информационно-измерительные системы (ИИС) и другие);
- во-вторых, приемопередающие системы (системы передачи данных (СПД), запросно-ответные системы (ЗОС) и другие);
- в-третьих, системы разрушения, уничтожения информации (постановки помех, подавления сигналов, радиоглушители и другие).
Во всех системах управление — важное явление, процесс, деятельность, которые включают в себя как компоненты организацию системы, распределение ресурсов (планирование), принятие решения и связь.
Трудно назвать область деятельности, в которой не принимались бы время от времени решения. Эта ситуация и явление имеет место всегда и раньше, и теперь, и в будущем.Человек пальцем не пошевелит, не приняв решения об этом. Не всегда это осознается, но это именно так.
Здесь (в работе) основное внимание уделим теории выбора и принятия решений, которая исследует математические модели принятия решений и их свойства. Наука о принятии решений долгое время развивалась, можно сказать, однобоко. Классическая схема охватывается статистической теорией, основывающейся на функции риска, на ошибках первого и второго рода.
Этот подход к принятию решений сыграл свою положительную роль и применимость его сегодня не отрицается, но ограничивается принципами рациональности. Подход не лишен и недостатков. Известно крылатое выражение, приписываемое классику (Госсету (псевдоним Стьюдент)) от статистической теории «о трех видах лжи: преднамеренной, непреднамеренной и статистике».
Код Рида-Соломона
Важной задачей кодологии при обработке информационных потоков кодированных сообщений в каналах систем связи и компьютерных является разделение потоков и селектирование их по заданным признакам. Выделенный поток расчленяется на отдельные сообщения и для каждого из них выполняется углубленный анализ с целью установления кода и его характеристик с последующим декодированием и доступом к семантике сообщения.
Так, например, для определенного Рида-Соломона кода (РС-кода) необходимо установить:
- длину n кодового слова (блока);
- количество k информационных и N-k проверочных символов;
- неприводимый многочлен р(х), задающий конечное поле GF(2r);
- примитивный элемент α конечного поля;
- порождающий многочлен g(x);
- параметр j кода;
- используемое перемежение;
- последовательность передачи кодовых слов или символов в канал и еще некоторые другие.
Здесь в работе рассматривается несколько другая частная задача — моделирование собственно РС-кода, являющаяся центральной основной частью названной выше задачи анализа кода.
Исправление кратных ошибок при кодировании сообщений
В информационных системах обмен сообщениями в сетях связи или вычислительных сопровождается возмущающими воздействиями среды или нарушителя, что приводит к появлению искажений сигналов и к ошибкам в символах при цифровой передаче. Борьбу с этим явлением ведут, используя корректирующие коды. Ранее я описывал код Хемминга, и показал как исправляется одиночная ошибка в кодовом слове. Естественно возник вопрос и о ситуациях с большим количеством ошибок. Сегодня рассмотрим случай двух ошибок в кодовом слове (кратную ошибку). С одной стороны, все в теории более менее просто и понятно, но с другой — совершенно не очевидно. Изложение материала выполнено на основе работ Э. Берлекемпа.
Отношения. Часть II
Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические объекты и процессы их функционирования. Эта публикация является продолжением предшествующей, прочтение которой желательно, так как многие понятия и термины, используемые здесь, описываются там.
Предлагается изложение не в традиционном (стрелочном) стиле, а так, как мне самому пришлось всю эту кухню представлять и осваивать и по учебникам/пособиям, и по журнальным статьям. Особенно полезной вещью считаю созданный мной каталог, он позволяет выделить практически любое пространство и представить его элементы в удобном виде: матрицей, графом и др. Сразу видишь с чем имеешь дело и свойства (они уже выписаны) проверять часто не требуется.
Отношения. Часть I
Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические и информационные объекты, процессы их функционирования. К числу последних я отношу, например, базы данных (реляционные базы данных (РеБД)). Не менее важной считаю область принятия решений, которая состоит из двух основных статистической и алгебраической, основанной целиком на теории отношений. Образовательный уровень специалистов в этой теории близок к нулю.
Откройте учебник по специализации и там увидите в лучшем случае об эквивалентностях, которые авторами трактуются весьма своеобразно. Одного защитившегося уже ДТН спрашиваю: Вы рассматриваете отношение эквивалентности на указывая ни носителя отношения, ни конкретного отношения, как оно у Вас выглядит в записи? Ответ: как выглядит — обыкновенно. Выясняется, что он обо всем этом имеет весьма смутное представление.
Векторные пространства
При проведении научных и прикладных исследование часто создаются модели, в которых рассматриваются точки и/или векторы определенных пространств. Например, в моделях шифров на эллиптических кривых используются аффинные и проективные пространства. К проективным прибегают тогда, когда необходимо ускорить вычисления, так как в формулах манипулирования с точками эллиптической кривой выводимых в рамках проективного пространства отсутствует операция деления на координату, которую в случае аффинного пространства обойти не удается.
Операция деления как раз одна из самых «дорогих» операций. Дело в том, что в алгебраических полях, а соответственно и в группах операция деления вообще отсутствует и выход из положения (когда не делить нельзя) состоит в том, что операцию деления заменяют умножением, но умножают не на саму координату, а на обращенное ее значение. Из этого следует, что предварительно надо привлекать расширенный алгоритм Евклида НОД и кое что еще. Одним словом, не все так просто как изображают авторы большинства публикаций о ЕСС. Почти все, что по этой теме опубликовано и не только в Интернете мне знакомо. Мало того, что авторы не компетентны и занимаются профанацией, оценщики этих публикаций плюсуют авторов в комментариях, т. е. не видят ни пробелов, ни явных ошибок. Про нормальную же статью пишут, что она уже 100500-я и от нее нулевой эффект. Так все пока на Хабре устроено, анализ публикаций делается огромный, но не качества содержания. Здесь возразить нечего — реклама двигатель бизнеса.
Математические основы кодирования и шифрования
Информационное взаимодействие абонентов в компьютерных и связных сетях подвергается возмущениям, которые приводят к возникновению ошибок и возмущений разного рода. Помимо возникновения ошибок в передаваемых сообщениях возможен несанкционированный доступ к содержанию сообщений нарушителя. Борьба с этими нежелательными явлениями ведется тысячелетиями, но с переменным успехом. Создатели Интернета задумывали его совсем не таким, каким он стал сейчас. О хакерах тогда и не думали.
Основные теоретические проблемы информационного противостояния, задачи по их решению возлагаются на теории кодологии, криптологии и стеганологии, в которых во всем мире интенсивно развиваются направления кодоанализа, криптоанализа и стегоанализа. Практические аспекты также не остаются в стороне, но замечу, что в РФ активность не очень-то высока, сказывается инертность молодых (сам я разменял уже 9-й десяток, но администрация Хабра ограничила возрастной ценз 1950 г). Мое мнение, конечно, ограничено наблюдением потомства (вплоть до правнуков) и общением в интернете, а также с обучаемыми и сотрудниками фирмы, где подрабатываю. СМИ тоже добавляют негатива. Кто из молодежи чуть поумнел, уходят за бугор. Поведение остальных видите сами.
Корректирующие коды. Начало новой теории кодирования
Проблемы информационной безопасности требуют изучения и решения ряда теоретических и практических задач при информационном взаимодействии абонентов систем. В нашей доктрине информационной безопасности формулируется триединая задача обеспечения целостности, конфиденциальности и доступности информации. Представляемые здесь статьи посвящаются рассмотрению конкретных вопросов ее решения в рамках разных государственных систем и подсистем. Ранее автором были рассмотрены в 5 статьях вопросы обеспечения конфиденциальности сообщений средствами государственных стандартов. Общая концепция системы кодирования также приводилась мной ранее.
Сознание и мозг
Сознание — рефлексия субъектом действительности, своей деятельности, самого себя. Оно порождается не природой, а самим человеком и окружающим миром, семьей, обществом.
В свое время Г. В. Ф. Гегелем были высказаны идеи о трех слоях в его учении о субъективном духе, который выделял три ступени в развитии субъективного духа: антропологию, феноменологию и психологию. Сегодня этот подход вполне применим к сознанию.
Квантовые вычисления и криптология
Развитие вычислительной техники движется по различным направлениям, не ограничиваясь явлениями классической физики, электроники, оптики и теперь уже квантовой механики.
Ознакомление с проблемой квантовой криптологии и смежными, близкими к ней (не только по публикациям), показало, что имеют место определенные недостатки и пробелы в ее описании и представлении. Описывая конкретику того или иного физического явления, объекта, автор игнорирует его окружение даже ближайшее, оказывающее на объект непосредственное воздействие (часто возмущающее влияние). Это не упрек авторам, их право излагать так как они излагают. Это скорее мой мотив включиться в общий поток сознания. Материальная вещественная сторона квантовых явлений так или иначе проявляет себя и неучет ее, может сказаться существенным негативом. Что имеется ввиду? Материальная реализация квантовых компьютеров (КК), регистров, отдельных кубитов — всего того из чего КК сделаны. Обмен пользователей полученными результатами через сети связи и, наконец, защита, целостность и доступность таких результатов от нарушителя — тоже проблемы.
Information
- Rating
- 468-th
- Location
- Санкт-Петербург, Санкт-Петербург и область, Россия
- Date of birth
- Registered
- Activity