Вы QR-разложение от QR-алгоритма хорошо отличаете? Вы мне приводите ссылку на итерационный алгоритм. Как вы будете его использовать в конечных полях, где и сходимости-то как таковой не существует?
Вот это поворот! И как же QR-разложение помогает вычислять собственные значения, м?
С корнями многочленов очень даже понятно, как это делать численно — запускаете любимый алгоритм минимизации для |f(x)|2 и всё. См. также Root-finding algorithms.
Да, очевидно. Ну а какой метод для нахождения собственных чисел над простыми полями вы можете посоветовать?
Потом, не ищут корни многочленов не потому, что это дорого, а потому, что это неустойчиво. Что опять-таки проблема только для поля с нулевой характеристикой.
Не квадратично. Матрица n x n сопоставляется каждому биту (или более длинной «цифре»). Размер шифротекста = размер исходного текста, умноженный на n2, n — параметр.
Ну возьмите матрицу порядка 2^(n/3), будет O(2^n).
Потом, O(n^3) — это если у вас матрица вещественная или комплексная. А если над конечным полем, то не так всё просто.
Можно-то можно, а вот удобство — это уже спорный вопрос. Например, кучу поверхностей в пространстве уже не так удобно обозревать, потому что они будут перекрывать друг друга и потребуется ядрёный рендер с полупрозрачностью и сортировкой, чтобы вообще увидеть больше одной. Можно одну из переменных вынести в качестве координаты z, и получить кучу кривых, распределённых в пространстве, но опять-таки это будет менее удобно. Обозревать данные в 3D, вероятнее всего, станет действительно удобно только когда у каждого будет свой голографический проектор на столе.
Ну дык, сгенерировать список ходов по описанию обычно не сложно. Вот выбрать наилучший — это как раз и есть целая наука. Ведь, как правило, выбрать совсем наилучший вычислительно невозможно, тут и возникает проблема выбора стратегий, «хороших» ходов и так далее.
Стесняюсь спросить, слышали ли вы о GDL ( en.wikipedia.org/wiki/Game_Description_Language )?
Кроме того, ваши требования к языку довольно утопичны: <<чтобы можно было легко писать ботов и ИИ>>. Писать ботов для игры по её формальному описанию — целая наука (см., например, курс General Game Playing на Coursera). Или вы не это имели в виду?
Взял сомнительные предпосылки, вывел уже триста лет как обсуждаемые результаты. Я, главным образом, поражаюсь тому, насколько хабравчане толерантны к этому бессмертному жанру.
Ну, я знал, что это такое и зачем, и предложенный автором ответ меня вполне устроил, я бы и сам дал такой же (опять-таки, нет смысла писать подробнее: люди, знакомые с диффурами, всё поняли, незнакомые — и не поймут). Сама статья показалась мне очень интересной и качественной. Особенно интересно было узнать реальное положение дел в свете низкопробной статьи на эту тему, которая была несколькими днями ранее.
А. Ну группу/полугруппу я вам просто по определению такую привести не смогу, но не вижу проблемы в том, чтобы сочинить коммутативную неассоциативную операцию. Взять хотя бы m * n = (m + n) max {m, n}.
Если вы не знаете, что такое задача Коши, восполнить эти пробелы в предисловии к топику всё равно не удастся. Но есть на Хабре люди, которые знают, вот эти детали для них.
С корнями многочленов очень даже понятно, как это делать численно — запускаете любимый алгоритм минимизации для |f(x)|2 и всё. См. также Root-finding algorithms.
Потом, не ищут корни многочленов не потому, что это дорого, а потому, что это неустойчиво. Что опять-таки проблема только для поля с нулевой характеристикой.
Потом, O(n^3) — это если у вас матрица вещественная или комплексная. А если над конечным полем, то не так всё просто.
К тому же, придётся выбирать одно из многих, и непонятно, как.
Кроме того, ваши требования к языку довольно утопичны: <<чтобы можно было легко писать ботов и ИИ>>. Писать ботов для игры по её формальному описанию — целая наука (см., например, курс General Game Playing на Coursera). Или вы не это имели в виду?