Category: компьютеры

Category was added automatically. Read all entries about "компьютеры".

for food
  • p_k

Действие свободной абелевой группы нв цепном комплексе

Столкнулся со следующей конструкцией, которая выглядит как часть какой-то более общей науки, не знаю только какой:

Имеется цепной комплекс абелевых групп, на котором свободно действует свободная абелева группа конечного ранга ($\mathbb{Z}^n$). Действие группы коммутирует с граничными операторами, поэтому можно формально спроецировать комплекс на неприводимые представления $\mathbb{Z}^n$. Если считать характеры представлений независимыми переменными $z_1, \dots, z_n$, то все проекции вместе можно описать как цепной комплекс модулей над кольцом полиномов Лорана над $z_1, \dots, z_n$.

Прежде всего вопрос - такое описание факторизации по действию абелевой группы, как перехода к меньшему комплексу с коэффициентами в кольце полиномов Лорана от характеров - это же что-то стандартное небось? Что почитать на эту тему? И что можно сказать про связь циклов, границ и гомологий исходного комплекса и вот такого "фактора"?

И еще практический вопрос - какой пакет компьютерной алгебры годится, чтобы посчитать гомологии комплекса модулей конечного ранга над кольцом полиномов Лорана от нескольких переменных?

Ищу интересующихся компьютерными вычислениями для PL многообразий

Здравствуйте. Я сейчас веду интересные вычисления, относящиеся к кусочно-линейным многообразиям, с помощью нашего (трёх авторов пока) пакета PL (и свеженаписанных мною дополнений), вот он: https://sourceforge.net/projects/plgap/
По-моему, он прекрасно работает, и я подумал, что он может заинтересовать более широкий круг математиков, как в плане применения готовых функций, так и в плане дальнейшего его развития.

Приветствуется дальнейшее распространение этого письма.

С наилучшими пожеланиями,

vaproseg@gmail.com
киса

Задача из компьютерной графики



Картинка скорей для привлечения внимания, но задача из той же области. На клетчатой бумаге (или экране из квадратных пикселей) нарисован произвольный треугольник. Надо: для каждой клетки, центр которой принадлежит треугольнику, вычислить, какой процент её площади покрыт треугольником. Что при этом можно использовать: вершинам треугольника можно приписать произвольные числа. После этого программа-интерполятор для центра каждой клетки вычисляет линейную интерполяцию этих чисел (по принципу барицентрических координат). Можно приписать вершинам сразу несколько чисел (например, 10) и вычислить 10 интерполяций. Кроме интерполяций, ничем пользоваться нельзя. Покрытие клетки надо вычислить по значению интерполяций в её центре (думаю, допустимо использовать и значения для ближайших соседних клеток). Или обосновать, что это невозможно.

Игры с числами: Порядок vs Хаос

Идея 1. Устроим ситуацию, в которой Рамсеевский Порядок проигрывает Хаосу.
Рассмотрим перестановку {a_i \in 1,..,N, i=1,..,N; a_i \neq a_j, i \neq j} (биекция множества N первых положительных чисел в себя).
Определим понятие ПАП-3 (перестановочная арифметическая прогрессия длины 3) таким образом:
Три элемента перестановки a_j, a_k, a_l составляют ПАП-3, если:
  l = 2*k – j;
  a_l = 2*a_k – a_j.

Очевидно, что для любого N = 1,2,... существует перестановка, не содержащая ПАП-3 (её всегда можно построить по простому алгоритму). Переборы на компьютере показывают, что количество таких перестановок стремительно растёт с ростом N, хотя их относительное число асимптотически падает к 0. Тоже вполне очевидно и ожидаемо.

Идея 2. Можно навести Порядок, введя ограничения для Хаоса.
Проще всего так: запретить элементам перестановки далеко убегать от своего места (не более, чем на М):
j – M <= a_j <= j + M.
Интуитивно понятно, что Рамсей в этом случае побеждает. Компьютерные игры при M = 2 это подтверждают. Количество беспорядка (числа перестановок, не содержащих ПАП-3) монотонно растёт c ростом длины перестановки N до N = 22 (3335 перестановок). Затем монотонно падает, пока N растёт до 36 (11 перестановок). При N = 37 происходит небольшой агонизирующий всплеск (12 перестановок -- первое нарушение монотонности). При N = 38 Хаос погибает.

Пример перестановки без ПАП-3 при N = 37, M = 2:
2 1 3 4 6 5 7 8 11 12 9 10 15 16 13 14 17 19 18 21 23 20 22 26 27 24 25 28 29 31 30 32 33 35 34 37 36.
Время работы сколько-то оптимизированного компьютерного перебора здесь уже занимает десятки секунд, и очевидно, что в дальнейших играх (при M = 3, например) и Порядок и Хаос проигрывают Времени.

Я игрок, а не математик, так что не скажу, есть ли у современных служителей культа Рамсея знания хотя бы для M = 3 (пусть даже с привлечением ван дер Варденовской гигантомании).

Спасибо за внимание всем, прочитавшим до этой фразы.
Приношу извинения за злоупотребление вниманием всем, читающим эту фразу.

Представление перестановок в компьютере

Вопрос - а как оптимально представляются перестановки в информатике.

То есть вот у нас есть N-элементная перестановка F([1,...,N])=[F(1),F(2)...,F(N)]. Сколько бит достаточно для ее описания?

Каждое число от 1 до N можно записать используя log(N) бит (логарифм двоичный).

То есть N*Log(N) бит хватит. Но есть ли способы оптимальнее?

Update:

Уточню постановку. Понятно что так перестановок всего N!, то нам нужно как минимум N*log(N) для всех. Но я о том как записывать перестановки с относительно простой структурой, например N-цикл, или когда наоборот циклы могут быть только малой длины, и т.д. и т.п. То есть какие альтернативные способы задания перестановок, где это могло бы учитывать. И прояснить, что "это", то есть какие свойства перестановок есть информационно простые.
kurit
  • flaass

одна старая статья

Тем, у кого есть доступ к старым номерам "Докладов Академии Наук Белорусской ССР":
Откопал на старой перфокарте ссылку на статью
В.П.Унукович, ДАН БССР, 1977, том XXI № 9, стр. 309-312.
Если я правильно помню, эта статья - несомненный маст-рид для любого профессионального математика или даже просто любителя.
Если у кого есть возможность выложить ее в интернет - вам многие будут благодарны!

UPD garvej говорит, что правильные номера страниц - 809-812.
UPD2 Ура! Статья (временно) выложена в инет! Ссылка там, в комментариях.
burka
  • zavr

Mathematica vs Maple

Надо мне тут было посчитать как некоторые операторы (по x) действуют на (x^2+y^2)^\alpha. Ручками не получается и решил я спросить у умного компьютера.

Операторов много, но например корень из Лапласа (или какая другая степень Лапласа).
Соответственно интересует
invfourier(abs(t)*fourier((x^2+y^2)^alpha,x,t),t,x);

Так вот, эти две программы дают довольно разные ответы (Maple не сокращает пару членов, но это не так интересно), главное что они дают ответ в виде двух РАЗНЫХ гипергеометрий. Совершенно не очевидно что эти гипергеометрии на самом деле равны (и пакеты этого тоже не видят), более того у меня есть основания считать что они действительно разные т.к. одна гипергеомтрия от -x^2/y^2, а вторая от -y^2/x^2 а это плохо согласуется с группой трансформаций для гипергеометрии.

Вот мне теперь и интересно, кто прав (а может оба пакета), и как это можно руками проверить (я в таких делах пакетам не очень доверяю).

PS Может кто знает как по символу оператора проверять что он является генератором положительной полугруппы?
  • Current Music
    Kill Bill

putnam

Я вообще не понял, почему после поста southwest никто не решает задачи из Putnam. Уж по крайней мере B5 (планиметрия) - очень красивая и несложная задачка. Получил массу удовольствия, решая ее.

UPDATE
Для ленивых привожу условие. Равносторонний треугольник ABC вписан в окружность единичного радиуса, O - центр этой окружности, P - произвольная точка внутри нее. Тогда PA,PB,PC - длины сторон некого треугольника, площадь которого зависит только от расстояния PO.

UPDATE 2
Я недавно выкладывал у себя в журнале частный случай этой задачки, который сильно помогает: докажите для начала, что если P лежит на окружности, то эта площадь равна нулю. Это почти очевидно.

UPDATE 3
А если я через некоторое время выложу решение, это будет кому-то интересно? или не стоит?

UPDATE 4
Мда. Я посмотрел там в архиве решение - оно ужасно. Через комплексные числа. Мое лучше раз в сто, и практически чисто планиметрическое. Обалденная задача.